masatoi.github.io Index
2024-03-03: On Lisp読書会(2) 参加メモ
On Lisp読書会@Shibuya.lisp
2章 関数
末尾再帰
末尾再帰とは再帰呼び出しから戻ってきた後に何も処理がない再帰のこと。 最近の処理系なら単純なループに変換してくれる。
例として、リストの長さを計算する関数の末尾再帰でないバージョンが出てくる。
#>はデバッグプリント用のリーダーマクロで事前にロードしておく。
(ql:quickload :cl-debug-print)
(cl-debug-print:use-debug-print)
(defun our-length (lst)
(if (null #>lst)
0
#>(1+ (our-length (cdr lst)))))
(our-length '(1 2 3))
; LST => (1 2 3)
; LST => (2 3)
; LST => (3)
; LST => NIL
; (1+ (OUR-LENGTH (CDR LST))) => 1
; (1+ (OUR-LENGTH (CDR LST))) => 2
; (1+ (OUR-LENGTH (CDR LST))) => 3
これを見るとlstが再帰呼び出しの度に縮退していき、空リストに到達してから長さに1ずつ足されていっているのが分かる。
この末尾再帰でないバージョンで100万件のリストの長さをカウントしようとするとstackoverflowになる。
(defun our-length (lst)
(if (null lst)
0
(1+ (our-length (cdr lst)))))
(let ((huge-list (loop for i from 1 to 1000000 collect i)))
(our-length huge-list))
;; Control stack exhausted (no more space for function call frames).
;; This is probably due to heavily nested or infinitely recursive function
;; calls, or a tail call that SBCL cannot or has not optimized away.
;; PROCEED WITH CAUTION.
;; [Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED]
次にdisassembleしてみる。 大体の見方は
RSIなどのRから始まるのがレジスタL0などがラベルCALLが関数呼び出しJMPやJNEがジャンプで指定したラベル位置にジャンプするJNEはJump Not Equalで、直前のTESTが失敗したときにジャンプするという条件分岐命令でもある
(disassemble 'our-length)
; disassembly for OUR-LENGTH
; Size: 83 bytes. Origin: #x54CE23E3 ; OUR-LENGTH
; 3E3: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 3E7: 488945F8 MOV [RBP-8], RAX
; 3EB: 4881FE17010050 CMP RSI, #x50000117 ; NIL
; 3F2: 7505 JNE L1
; 3F4: 31D2 XOR EDX, EDX
; 3F6: L0: C9 LEAVE
; 3F7: F8 CLC
; 3F8: C3 RET
; 3F9: L1: 8D46F9 LEA EAX, [RSI-7]
; 3FC: A80F TEST AL, 15
; 3FE: 7531 JNE L2
; 400: 488B5601 MOV RDX, [RSI+1]
; 404: 4883EC10 SUB RSP, 16
; 408: B902000000 MOV ECX, 2
; 40D: 48892C24 MOV [RSP], RBP
; 411: 488BEC MOV RBP, RSP
; 414: E8C9DA65FB CALL #x5033FEE2 ; #<FDEFN OUR-LENGTH> <= 再帰呼び出し
; 419: 480F42E3 CMOVB RSP, RBX
; 41D: 488B75F0 MOV RSI, [RBP-16]
; 421: BF02000000 MOV EDI, 2
; 426: E8E5EA11FF CALL #x53E00F10 ; SB-VM::GENERIC-+
; 42B: 488B75F0 MOV RSI, [RBP-16]
; 42F: EBC5 JMP L0
; 431: L2: CC53 INT3 83 ; OBJECT-NOT-LIST-ERROR
; 433: 18 BYTE #X18 ; RSI(d)
; 434: CC10 INT3 16 ; Invalid argument count trap
42FのJMPと3F6のL0の間でループしており、その途中で再帰呼び出しのCALL命令があるのでループの度に関数が呼ばれていることが分かる。
次に、末尾最適化版の例が出てくる。 アキュームレータaccを導入することで計算の途中結果を関数の引数として次の再帰呼び出し時に渡している。
こちらはlstの縮退とaccへの加算が並行して進んでいることが分かる。
(defun our-length-tco (lst)
(labels ((rec (lst acc)
#>lst #>acc
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
(our-length-tco '(1 2 3))
; LST => (1 2 3)
; ACC => 0
; LST => (2 3)
; ACC => 1
; LST => (3)
; ACC => 2
; LST => NIL
; ACC => 3
これは100万要素のリストに対して呼び出してもstackoverflowエラーにならない。
(defun our-length-tco (lst)
(labels ((rec (lst acc)
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
(let ((huge-list (loop for i from 1 to 1000000 collect i)))
(our-length-tco huge-list))
; => 1000000
disassembleしてみると、4FAのJNEと4D0のL0の間でループになっており、間には加算以外の関数呼び出しはないことが分かる。
(disassemble 'our-length-tco)
; disassembly for OUR-LENGTH-TCO
; Size: 84 bytes. Origin: #x54CE24B3 ; OUR-LENGTH-TCO
; 4B3: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 4B7: 488945F8 MOV [RBP-8], RAX
; 4BB: 488B75F0 MOV RSI, [RBP-16]
; 4BF: 4531C0 XOR R8D, R8D
; 4C2: EB2F JMP L1
; 4C4: 660F1F440000 NOP
; 4CA: 660F1F440000 NOP
; 4D0: L0: 8D46F9 LEA EAX, [RSI-7]
; 4D3: A80F TEST AL, 15
; 4D5: 752B JNE L2
; 4D7: 488B7601 MOV RSI, [RSI+1]
; 4DB: 488975E8 MOV [RBP-24], RSI
; 4DF: BF02000000 MOV EDI, 2
; 4E4: 498BD0 MOV RDX, R8
; 4E7: E824EA11FF CALL #x53E00F10 ; SB-VM::GENERIC-+
; 4EC: 4C8BC2 MOV R8, RDX
; 4EF: 488B75E8 MOV RSI, [RBP-24]
; 4F3: L1: 4881FE17010050 CMP RSI, #x50000117 ; NIL
; 4FA: 75D4 JNE L0 ; 再帰呼び出しがなく、L0へのジャンプ(ループになっている)
; 4FC: 498BD0 MOV RDX, R8
; 4FF: C9 LEAVE
; 500: F8 CLC
; 501: C3 RET
; 502: L2: CC53 INT3 83 ; OBJECT-NOT-LIST-ERROR
; 504: 18 BYTE #X18 ; RSI(d)
; 505: CC10 INT3 16 ; Invalid argument count trap
SBCLの場合は (proclaim '(optimize speed)) などはしなくても末尾再帰最適化はやってくれるようだ。
再帰アルゴリズムの中には必ずしも末尾再帰の形にできないものもある。(quicksortとか)
(defun quicksort (list)
(if (null list)
nil
(let ((pivot (first list))
(rest (rest list)))
(append (quicksort (remove-if-not (lambda (x) (<= x pivot)) rest))
(list pivot)
(quicksort (remove-if-not (lambda (x) (> x pivot)) rest))))))
ここで最適化オプションの話が出てきており、1からnまでの整数の和を返す関数triangleの例が出てくる。
10億までの総和にすると10倍くらいの違いが出てくる。
(defun triangle (n)
(labels ((tri (c n)
(declare (optimize (speed 3) (safety 0))
(type fixnum n c))
(if (zerop n)
c
(tri (the fixnum (+ n c))
(the fixnum (- n 1))))))
(tri 0 n)))
(time (triangle 1000000000))
; Evaluation took:
; 0.252 seconds of real time
; 0.251020 seconds of total run time (0.251020 user, 0.000000 system)
; 99.60% CPU
; 953,885,348 processor cycles
; 0 bytes consed
(defun triangle-no-optimize (n)
(labels ((tri (c n)
(if (zerop n)
c
(tri (+ n c)
(- n 1)))))
(tri 0 n)))
(time (triangle-no-optimize 1000000000))
; Evaluation took:
; 2.948 seconds of real time
; 2.950525 seconds of total run time (2.950434 user, 0.000091 system)
; 100.10% CPU
; 11,212,179,642 processor cycles
; 0 bytes consed
コンパイル
compile関数で関数をコンパイルし、compiled-function-pで確認するという流れになっているのだが、SBCLの場合は普通に関数定義などを評価しただけでコンパイル済みになっていることが分かる。
clispのインタプリタで明示的にコンパイルする例を示した。
ここでSBCLはJITコンパイルか？という議論になった。 関数毎にインタラクティブに定義できるが、使われるときになってはじめてコンパイルされる(Just In Time)わけでないのでAhead of Timeコンパイルだろうという話になった。
インライン宣言の話にも軽く触れられている。4章のユーティリティ関数のところで実際に使っているのでそのときに紹介することにした。
3章 関数的プログラミング
関数的プログラミングとは、副作用を使わず、参照透明にしておくこと。(参照透明: 内部状態を持たず、同じ引数に対して常に返値を返すこと) このようになっていると関数単位でテスト、デバッグがしやすい。REPL上でのインタラクティブな開発とも相性がよい。
副作用を使う例:
;; 悪いポイント: 値を返さない。副作用のみを目的にしている
(defun bad-reverse (lst)
(declare (optimize speed))
(let* ((len (length lst))
(ilimit (truncate (/ len 2))))
(do ((i 0 (1+ i))
(j (1- len) (1- j)))
((>= i ilimit))
(rotatef (nth i lst) (nth j lst)))))
(setf lst '(a b c))
(bad-reverse lst)
; => NIL
lst ; => (C B A)
rotatefはsetfのように汎変数を受け取って、リスト要素のポインタ操作によって要素の置き換えを実現する。 そのためコンシングは発生しないが、リストは破壊的に変更される。
(time (rotatef (car lst) (caddr lst)))
; 0 bytes consed
lst ; => (A B C)
2024-02-23: On Lisp読書会(1) 参加メモ
On Lisp読書会@Shibuya.lisp
Shiubya.lispで、最近RustでSci-Lispという独自処理系を作られているchaploudさんからご提案があり、週一でOn Lispの読書会に参加することになった。 参加者は予定範囲を読んでいることを前提としており、モデレータが本の流れをなぞりながら都度質問や議論をするという感じの進め方だった。 以下は第1回の個人的なメモである。
1章 拡張可能なプログラミング言語
Lispが拡張可能な言語であり、ボトムアップスタイルのプログラミングに向いているということが主張されている。 ボトムアッププログラミングの対義語はトップダウンなデザインであり、ダムの建設など事前に全てパーツを計画し、それらを順序立てて組み立てていくやり方のことを指している。 ボトムアッププログラミングでは細かく汎用的なユーティリティを作っていき、その層を重ねていくということのようだ。より探索的なアプローチといえる。
プログラムはソフトウェアなのでダムの建設と違って柔らかく、一度作ってしまえば後戻りできないというものでもないため、このようなアプローチが向いている場面もある。
Lispは言語自体が柔軟なので汎用的なユーティリティを作りやすい(例として高階関数とマクロが挙げられている) → 言語自体を成長させていくことが容易、ということだと思った。
この辺はUNIX的な考え方−すなわち直交したシンプルなコマンドラインツールをシェル上で組み合わせることによって複雑なタスクを実現する−と近いという意見も出た。
問題に合わせてDSLを作るとより問題を短く記述できるため、メンテナンス性が増し、独自に導入した流儀を揃えることができる環境では威力を発揮すると主張している。 そのため小規模グループでの開発に向いているとされている。
感想: 最近では、高階関数やパターンマッチベースのマクロ機能はLispの専売特許というわけでもなくなってきているので、他の言語でもボトムアップアプローチはできるし、普通にやられていると思う。 とはいえCommon Lispのいい意味での枯れ具合とインタラクティブ性が高性能な処理系と同居しているというのは、いまだに特異的だと思っている。
2章 関数
Lispはほとんど関数の集合体であり、例外が少ない。
普通の言語では組込みオペレータであるような+も単なる関数として実装されている。
2章冒頭では関数定義の方法、lambdaによる無名関数、関数と変数の名前空間が異なりそれぞれにアクセスする方法が異なることが説明される。 関数もLispのデータ(操作対象)であるという例として、シンボルの属性リストに関数を格納して呼び出す例が出てきた。 Common Lispのシンボルが実はリッチなデータ構造で、属性リストを持てるというのが説明なしに出てくるのでシンボルの中身をインスペクタで見ることで解説した。
(defun behave (animal)
(funcall (get animal 'behavior)))
(setf (get 'dog 'behavior)
#'(lambda ()
(print "bark")))
(behave 'dog)
;; "bark"
(setf (get 'dog 'height) 30)
(inspect 'dog)
#|
The object is a SYMBOL.
0. Name: "DOG"
1. Package: #<PACKAGE "COMMON-LISP-USER">
2. Value: #<unbound slot>
3. Function: #<unbound slot>
4. Plist: (HEIGHT 30 BEHAVIOR #<FUNCTION (LAMBDA ()) {54CEF72B}>)
> 4
The object is a proper list of length 4.
0. 0: HEIGHT
1. 1: 30
2. 2: BEHAVIOR
3. 3: #<FUNCTION (LAMBDA ()) {54CEF72B}>
|#
レキシカルスコープとダイナミックスコープ
最近の言語ではレキシカルスコープが当たり前になっているので、むしろダイナミックスコープが何かという話になった。
defvarなどでスペシャル変数宣言するとダイナミックスコープになる(関数内部で自由な変数を外側のletで束縛するなどして実行時に変更できる)という説明をした(たぶん合ってる)
;; ダイナミックスコープの例
(defvar *y*)
(defun scope-test2 (x)
(list x *y*))
(let ((*y* 5))
(scope-test 3))
; => (3 5)
レキシカルクロージャ
関数が作られた環境への参照を関数内に閉じ込めることができ、そのような関数をクロージャと呼ぶ、ということだと理解している。
次の例では db が連想リストで、make-dbms内で作られている3つのアクセサ関数経由でしか参照も変更もできないというカプセル化がなされている。
あとは継承があればオブジェクト指向がほぼ実現できる、と書かれている。
(defun make-dbms (db)
(list
;; referrer
#'(lambda (key)
(cdr (assoc key db)))
;; setter
#'(lambda (key val)
(push (cons key val) db)
key)
;; cleaner
#'(lambda (key)
(setf db (delete key db :key #'car))
key)))
(defparameter cities (make-dbms '((boston . us) (paris . france))))
;; referrer
(funcall (first cities) 'boston) ; => US
(funcall (first cities) 'paris) ; => FRANCE
;; setter
(funcall (second cities) 'london 'england)
(funcall (first cities) 'london) ; => ENGLAND
;; cleaner
(funcall (third cities) 'london)
(funcall (first cities) 'london) ; => NIL
ローカル関数
labelsを導入して関数内の補助関数をローカル関数として定義する例が出てくる。
このinstances-inが外側のobjを閉じ込めているのでこれもクロージャの例になっている。
(defun count-instances (obj lsts)
(labels ((instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0)))
(mapcar #'instances-in lsts)))
;; リストの各要素リスト内のaの数を数える
(count-instances 'a '((a b c) (d a r p a) (d a r) (a a)))
余談として、labels以外にも flet や flet* などもあって、これらを使うと再帰を使っていないことが明確になるという話をした。
とはいえlabelsがあればこれらは基本いらないはず。とにかく言語要素を少なくするという考え方と、用途が微妙に異なる構文を多数用意しておくことでコンテキスト情報を与えるとう考え方があり、Common Lispは後者であるということだと思う。
Schemeのように内部関数定義でもいいのでは？と思うが、defunを使うとトップレベルに定義される。
(defun count-instances (obj lsts)
(defun instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0))
(mapcar #'instances-in lsts))
;; count-instancesを呼ぶ度にinstances-inが上書かれる
(count-instances 'b '((a b c) (d a r p a) (d a r) (a a)))
(instances-in '(d a r p a)) ; => 0
末尾再帰
ここから次回ということになった。 次回は自分がモデレータなので予習しておかねば…
2024-02-10: Common LispでBOM付きCSVを扱う方法
BOM(Byte Order Mark)とは
CSVファイルを他人から受け取るときに、それがExcelで作られたUTF-8でエンコードされたCSVファイルの場合、BOMと呼ばれるデータがファイルの冒頭3バイトについていることがある。 これがヘッダー検査のときに悪さをしてバリデーションに引っかかって読み込めないということがよくある。 逆に、システムからUTF-8のCSVファイルを出力したが、BOMを付けないとExcel側で文字化けするということもある。
ChatGPTによるBOMの解説
BOM（Byte Order Mark）は、テキストファイルの先頭に配置される特定のバイトシーケンスで、ファイルのエンコーディング形式と、特にエンコーディングが複数のバイトを使用する場合のバイト順（エンディアン）を示します。BOMは、Unicodeテキストファイルを識別するために使われ、特にUTF-16とUTF-32エンコーディング形式ではバイト順を区別するのに役立ちます。
UTF-8の文脈では、BOMはEF BB BFというバイトシーケンスで表され、UTF-8エンコードされたテキストファイルの先頭にオプションで置かれることがあります。UTF-8では、バイトの順序が問題になることはありませんが、BOMを使用すると、ファイルがUTF-8でエンコードされていることを明示的に示すことができます。
BOM付きファイルを出力する
Common LispでBOM付きファイルを出力するならば、with-open-fileの冒頭でEF BB BFの3バイトをくっつけるマクロを定義すればよい。
(defmacro with-output-file-with-bom ((file-stream file) &body body)
`(progn
(with-open-file (,file-stream ,file :direction :output :if-exists :supersede
:element-type '(unsigned-byte 8))
(write-sequence (make-array 3 :element-type '(unsigned-byte 8)
:initial-contents '(#xEF #xBB #xBF))
,file-stream))
(with-open-file (,file-stream ,file :direction :output :if-exists :append)
,@body)))
使用例
(ql:quickload '(:fare-csv :alexandria))
(with-output-file-with-bom (f "/tmp/with-bom.csv")
(fare-csv:write-csv-lines '(("id" "val")
(1 "foo"))
f))
;; 比較対象に普通のBOMなしのファイルを出力しておく
(alexandria:with-output-to-file (f "/tmp/without-bom.csv")
(fare-csv:write-csv-lines '(("id" "val")
(1 "foo"))
f))
出力されたファイルを読み出してみると、一見同じ文字列だが、インスペクトしてみると冒頭に #\ZERO_WIDTH_NO-BREAK_SPACE が付いていることが分かる。
当然equalは失敗する。
(defparameter *id-with-bom*
(with-open-file (f "/tmp/with-bom.csv")
(first (fare-csv:read-csv-line f))))
#|
=> "id"
#<(SIMPLE-ARRAY CHARACTER (3)) {1014FE473F}>
--------------------
Dimensions: (3)
Element type: CHARACTER
Total size: 3
Adjustable: NIL
Fill pointer: NIL
Contents:
0: #\ZERO_WIDTH_NO-BREAK_SPACE
1: #\i
2: #\d
|#
(defparameter *id-without-bom*
(with-open-file (f "/tmp/without-bom.csv")
(first (fare-csv:read-csv-line f))))
#|
=> "id"
#<(SIMPLE-ARRAY CHARACTER (2)) {1015020B8F}>
--------------------
Dimensions: (2)
Element type: CHARACTER
Total size: 2
Adjustable: NIL
Fill pointer: NIL
Contents:
0: #\i
1: #\d
|#
(equal *id-with-bom* *id-without-bom*)
;; => NIL
BOMを取り除いて読み込む
BOM付きのファイルから読み出すときは、最初にBOM付きかどうかをチェックした上で、そのままストリームを開くか、冒頭3バイトを削った上で開くマクロが必要。
BOM付きファイルかどうは以下のような関数で判定できる(後にマクロ定義内で使うのでeval-whenでコンパイル時に評価されるようにしておく)
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun has-bom-p (file)
(with-open-file (stream file
:direction :input
:element-type '(unsigned-byte 8))
(let ((b1 (read-byte stream nil nil))
(b2 (read-byte stream nil nil))
(b3 (read-byte stream nil nil)))
(and b1 b2 b3 (= b1 #xEF) (= b2 #xBB) (= b3 #xBF))))))
with-open-fileでは、途中でファイル読み込みのモードをバイナリモードから文字モードへ切り替えるということはできないので、2回with-open-fileすることになる。 BOM部分がどの文字オブジェクトになるかは処理系依存のようだが、1文字として判定されるのは共通のようなので、BOM付きの場合は冒頭1文字読み飛ばす。
(defmacro with-input-file-with-bom ((file-stream file) &body body)
(alexandria:with-gensyms (has-bom-p)
`(let ((,has-bom-p (has-bom-p ,file)))
(with-open-file (,file-stream ,file
:direction :input
:element-type 'character)
(when ,has-bom-p
(read-char ,file-stream))
,@body))))
使用例
(equal (with-input-file-with-bom (f "/tmp/without-bom.csv")
(first (fare-csv:read-csv-line f)))
(with-input-file-with-bom (f "/tmp/with-bom.csv")
(first (fare-csv:read-csv-line f))))
;; => T
2024-01-14: SBCLのリストのランダムアクセスが速すぎる件
データ構造をどう選択するかがスピード上重要になるという実験
連結リストに対するランダムアクセスと配列に対するランダムアクセスで実際にどの程度差が出るのものを確認する。
- SBCL 2.4.0
- AMD Ryzen 7 5800X 8-Core Processor
- Linux prime 5.15.0-91-generic #101-Ubuntu SMP x86_64 GNU/Linux
100万件のデータのランダムな位置に1億回アクセスする時間を測る。 連結リストであればシーケンシャルアクセスは速いがランダムアクセスは遅いというのが期待値。
連結リスト
;;; linked-list
(defparameter lst (loop for i from 1 to 1000000 collect i))
(time
(loop repeat 100000000
do (nth (random 1000000) lst)))
;; Evaluation took:
;; 0.687 seconds of real time
;; 0.684590 seconds of total run time (0.683457 user, 0.001133 system)
;; 99.71% CPU
;; 2,621,812,964 processor cycles
;; 0 bytes consed
連結リスト(最適化宣言付き)
(time
(locally
(declare (optimize (speed 3) (safety 0)))
(loop repeat 100000000
do (nth (random 1000000) lst))))
;; Evaluation took:
;; 0.328 seconds of real time
;; 0.328652 seconds of total run time (0.328427 user, 0.000225 system)
;; 100.30% CPU
;; 1,248,868,784 processor cycles
;; 0 bytes consed
型指定無しの固定長配列
;;; non typed array
(defparameter arr-non-typed (make-array 1000000))
(loop for i from 0 below 1000000
do (setf (aref arr-non-typed i) (1+ i)))
(time
(loop repeat 100000000
do (aref arr-non-typed (random 1000000))))
;; Evaluation took:
;; 1.484 seconds of real time
;; 1.485203 seconds of total run time (1.485024 user, 0.000179 system)
;; 100.07% CPU
;; 5,643,859,712 processor cycles
;; 0 bytes consed
型指定無しの固定長配列(最適化宣言付き)
(time
(locally
(declare (optimize (speed 3) (safety 0)))
(loop repeat 100000000
do (aref arr-non-typed (random 1000000)))))
;; Evaluation took:
;; 0.332 seconds of real time
;; 0.333449 seconds of total run time (0.333405 user, 0.000044 system)
;; 100.30% CPU
;; 1,267,148,836 processor cycles
;; 0 bytes consed
型指定有りの固定長配列
;;; typed array
(defparameter arr-typed (make-array 1000000 :element-type 'fixnum))
(loop for i from 0 below 1000000
do (setf (aref arr-typed i) (1+ i)))
(time
(loop repeat 100000000
do (aref arr-typed (random 1000000))))
;; Evaluation took:
;; 1.564 seconds of real time
;; 1.563470 seconds of total run time (1.563470 user, 0.000000 system)
;; 99.94% CPU
;; 5,941,252,386 processor cycles
;; 0 bytes consed
型指定有りの固定長配列(最適化宣言付き)
(time
(locally
(declare (optimize (speed 3) (safety 0)))
(loop repeat 100000000
do (aref arr-typed (random 1000000)))))
;; Evaluation took:
;; 0.328 seconds of real time
;; 0.329280 seconds of total run time (0.329280 user, 0.000000 system)
;; 100.30% CPU
;; 1,251,274,640 processor cycles
;; 0 bytes consed
実際には、固定長配列よりもリストの方が速いという結果になっている・・・！ 最適化宣言付けると同じくらいになっている。
他の処理系では？
CLISP (GNU CLISP 2.49.93+)
CLISPだと予想通りになっている。 リストのランダムアクセスは遅すぎて1億回もアクセスしていたら終わらないため1000回にしてある。
CL-USER> (defparameter lst (loop for i from 1 to 1000000 collect i))
LST
CL-USER> (time
(loop repeat 1000
do (nth (random 1000000) lst)))
Real time: 0.726303 sec.
Run time: 0.726299 sec.
Space: 9208 Bytes
NIL
CL-USER> (defparameter arr-typed (make-array 1000000 :element-type 'fixnum))
ARR-TYPED
CL-USER> (loop for i from 0 below 1000000
do (setf (aref arr-typed i) (1+ i)))
NIL
CL-USER> (time
(locally
(declare (optimize (speed 3) (safety 0)))
(loop repeat 1000
do (aref arr-typed (random 1000000)))))
Real time: 0.001569 sec.
Run time: 0.001568 sec.
Space: 9264 Bytes
NIL
Clozure CL (Version 1.12.2 (v1.12.2) LinuxX8664)
Clozure CLでもCLISPと同様の結果になった。
CL-USER> (time
(loop repeat 1000
do (nth (random 1000000) lst)))
(LOOP REPEAT 1000 DO (NTH (RANDOM 1000000) LST))
took 1,502,529 microseconds (1.502529 seconds) to run.
During that period, and with 16 available CPU cores,
1,502,684 microseconds (1.502684 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
CL-USER> (time
(locally
(declare (optimize (speed 3) (safety 0)))
(loop repeat 1000
do (aref arr-typed (random 1000000)))))
(LOCALLY (DECLARE (OPTIMIZE (SPEED 3) (SAFETY 0))) (LOOP REPEAT 1000 DO (AREF ARR-TYPED (RANDOM 1000000))))
took 19 microseconds (0.000019 seconds) to run.
During that period, and with 16 available CPU cores,
25 microseconds (0.000025 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
なのでSBCLが何か特殊なことをやっているのだと予想される。内部的には単純な連結リストではない？ SBCLのリスト処理は常々速すぎると思っていたが・・・
ChatGPT4のコメント:
Common Lispで行ったこの実験の結果に関して、リストが配列よりも高速に動作するように見える理由について考察します。
キャッシュ効果: 実験で使用されたリストのサイズが小さかったり、アクセスパターンがキャッシュに最適化されていた場合、リストの方が高速に動作する可能性があります。しかし、通常の状況下では、連結リストは配列に比べてランダムアクセスにおいて遅いはずです。これは連結リストがメモリ内で非連続的に配置されるため、キャッシュミスが発生しやすいからです。
オプティマイザの影響: Common Lispのコンパイラは非常に強力なオプティマイザを持っています。あなたのコードにおいて (declare (optimize (speed 3) (safety 0))) が使用されており、これはコンパイラに最高レベルの最適化を行うよう指示しています。この最適化により、リストへのアクセスが予想以上に高速化されることがあります。
実装の詳細: Common Lispの実装によっては、リストや配列の内部表現が異なり、特定の操作に最適化されている場合があります。そのため、理論的な性能と実際の性能が異なることがあります。
測定方法: time マクロを使用した測定では、実行環境によって結果が大きく異なる可能性があります。また、測定時のシステムの状態（他のプロセスの動作など）によっても結果は変わります。
配列の種類: 配列が非型指定（arr-non-typed）と型指定（arr-typed）であることも考慮する必要があります。型指定配列は一般にメモリ使用量が少なく、アクセス速度が高速ですが、この実験では大きな差は見られませんでした。
これらの要因を考慮すると、リストが配列よりも高速に見えるのは、特定の条件下での測定結果であり、一般的なケースではない可能性が高いです。データ構造の選択は、常にアプリケーションの要件や動作する環境に応じて慎重に行う必要があります。
2024-01-13: Common Lispのlambdaについて
lambdaは身近な存在だが、感覚で使ってしまっていると思ったので改めて調べてみた。 lambdaはLispで最も根源的な概念と言える。そのため特殊な扱いを受けている。 純Lispの定義でもlambdaは直接定義されていた。
基本
lambda式は(無名)関数を表現する特別な式である。 Hyperspecにはマクロのように記載されているのでややこしいが、マクロとしてのlambdaと言語組込みの特別扱いされるlambdaがあり、マクロとしてのlambdaは本来のlambda式から関数オブジェクトを取り出すショートカットとして定義されているもの、という位置付けらしい。
(lambda (x y)
(+ x y))
=> #<FUNCTION (LAMBDA (X Y)) {700861A20B}>
本来のlambda式は関数オブジェクトを返す関数、というわけではない。なので式の第一要素に置ける。
((lambda (x) (1+ (1+ x))) 10)
=> 12
これが例えばalexandriaのcompose(合成した関数を返す関数)だったとしたらエラーになり、funcallが必要になるだろう。
((alexandria:compose #'1+ #'1+) 10)
; in: (ALEXANDRIA:COMPOSE #'1+ #'1+) 10
; ((ALEXANDRIA:COMPOSE #'1+ #'1+) 10)
;
; caught ERROR:
; illegal function call
;
; compilation unit finished
; caught 1 ERROR condition
(funcall (alexandria:compose #'1+ #'1+) 10)
=> 12
lambda式には#’が必要なのか？
lambda式に#'を付けることで明示的に関数オブジェクトを取り出せる。
こうなるとfuncallで関数として呼び出さなければエラーになる。
(#'(lambda (x) (1+ (1+ x))) 10)
; in: #'(LAMBDA (X) (1+ (1+ X))) 10
; (#'(LAMBDA (X) (1+ (1+ X))) 10)
;
; caught ERROR:
; illegal function call
;
; compilation unit finished
; caught 1 ERROR condition
; Evaluation aborted on #<SB-INT:COMPILED-PROGRAM-ERROR {700C0609A3}>.
(funcall #'(lambda (x) (1+ (1+ x))) 10)
=> 12
SBCLではlambdaをmacroexpand-1すると#’付きの形に展開されるので同じことだが、式の先頭にlambdaを置いてもエラーにならないためその場合だけ特別扱いされているようだ。
(macroexpand-1 '(lambda (x) (1+ (1+ x))))
#'(LAMBDA (X) (1+ (1+ X)))
mapcarなどにlambda式を渡すときには、#’を付けて関数オブジェクトであることを示すのが本来的には正しいらしい。 #’を付けないでも上述のlambdaマクロによって#’を付けていることになるが、これは単なる糖衣構文であり好まない人も多いらしい。
手持ちの本を調べてみると、mapcarなどに関数オブジェクトを渡す際に#’を付けているのは、
- Paul GrahamのANSI Common Lisp
- 実践Common Lisp(Practical Common Lisp)
- 実用Common Lisp(PAIP)
逆に#’を付けていないのは
- Land of Lisp
- はじめてのLisp関数型プログラミング――ラムダ計算からリファクタリングまで一気にわかる
「実践Common Lisp」と「はじめてのLisp関数型プログラミング」にはコラムや注釈でこの違いについても触れられていた。