SBCL コンパイラの最適化は、型が宣言されている場合は「オープン コーディング」が行われるという考えに基づいています。一般的な操作を特定の操作に置き換えることができます。
たとえば
(defun add (a b)
(declare (type fixnum a b))
(+ a b))
汎用の + を fixnum の単一の命令に置き換えることができます。
しかし、実際には次の理由により、これが可能であることはほとんどないことがわかりました。
関数を特殊化/最適化するには、関数をインライン可能にする必要があります。宣言は (declaim (inline ...)) で明示的にマークする必要があるため、関数の作成者は他の人がそれをインライン化する可能性があることを予測する必要があります。 (理論的には、コンパイラーは複数のバージョンを生成できますが、そうではないようです。)
ほとんどの標準関数はインライン化できないように見えます。
たとえば、次のようなことが期待されます。オープン コーディングを行うには、次の宣言で十分です。
(defun max-integers (array)
(declare (optimize (speed 3) (space 0) (safety 0)))
(declare (inline reduce))
(declare (type (simple-array fixnum (*)) array))
(reduce (lambda (a b) (if (> b a) b a)) array))
ただし、アセンブリは汎用のreduceへの関数呼び出しを行っていることを示しています。
; Size: 22 bytes. Origin: #x1001BC8109
; 09: 488B15B0FFFFFF MOV RDX, [RIP-80] ; no-arg-parsing entry point
; #<FUNCTION (LAMBDA
; # ..)>
; 10: B904000000 MOV ECX, 4
; 15: FF7508 PUSH QWORD PTR [RBP+8]
; 18: B8781C3220 MOV EAX, #x20321C78 ; #<FDEFN REDUCE>
; 1D: FFE0 JMP RAX
結論としては、reduce、map などの使用法はそれぞれ型の伝播に対する障壁であり、他のすべての構成要素であるため、コンパイラーは実際には型の最適化をあまり行うことができないということのようです。
これを克服し、型を宣言することで最適化を利用するにはどうすればよいでしょうか?
各関数のタイプ固有のバージョンを作成したり、関数を「マクロ化」したりすることは本当に避けたいのです。関数は何であるべきか。
1
(reduce #'> 配列) は意味がありません。 #'> の有効な入力ではない t または nil を返します。
– スヴァンテ
2020 年 9 月 4 日 19:10
1
@Svante バカバカしい！正しく書いて質問を更新させてください。
– ジャスティン・マイナーズ
2020 年 9 月 4 日 19:56
@Svante 訂正させていただきました。
– ジャスティン・マイナーズ
2020 年 9 月 4 日 20:00
最適化を強制するためにできることはそれほど多くありません。あなたにできることは、可能な限り型を宣言し、コンパイラが型を使用できることを祈ることだけです。一部のコンパイラは、他のコンパイラよりもこの点で優れています。
– バルマー
2020 年 9 月 4 日 20:47
@B確かに、CL では型の使用方法が指定されていないことは理解していますが、私は SBCL に焦点を当てています。明らかに、最適化を行うために構築された多くのインフラストラクチャがあり、私の質問はそれをどのように効果的に使用するかです。 reduce は、大規模なシステムの制限と思われるものを示す一例にすぎません。私の例が機能しないのに他の方法では機能するという奇妙な理由がある場合は、興味があります。
– ジャスティン・マイナーズ
2020 年 9 月 4 日 20:50
------------------------
答えの 1 つは、FORTRAN スタイルの arr を書きたい場合、ということだと思います。ay-bashing コードの場合は、FORTRAN スタイルの配列バッシング コードを作成します。特に、reduce などを使用することは、おそらくこれを行う方法ではありません。
たとえば、関数を完全に読みやすいものに変更した場合
(defun max-integers/loop (array)
(declare (optimize (speed 3) (space 0) (safety 0))
(type (simple-array fixnum (*)) array))
(loop for i of-type fixnum across array
maximizing i))
その後、SBCL はそれを最適化する上ではるかに優れた仕事をします。
あなたの質問のもう一つの混乱を指摘する価値があります。あなたは次のようなことについてそれを言っています
(defun add (a b)
(declare (type fixnum a b))
(+ a b))
SBCL は + を機械語命令に最適化します。いいえ、そうではありません。そうならない理由は、fixnum 型が加算で閉じられていないためです。(most-positive-fixnum 1 を加算) が何をすべきかを考えてください。整数に対して非常に高速なコードを生成したい場合は、整数型が十分小さいことを確認して、整数に対して実行している操作がマシン整数のままであることをコンパイラーが確認できるようにする必要があります。(または、危険な状況を避けたい場合は、コードを (fixnum ...) で覆い、コンパイル時に安全性を 0 に設定します。これにより、コンパイラーは、コンピューターが通常期待する方法で、加算に対して間違った答えを返すことができるようですすること）。
4
はい、まさに私はそれが普及することを望んでいました。どの関数がインライン化可能であるかを指定する、CL 標準または SBCL 実装自体に対するガイダンスはありますか?
– ジャスティン・マイナーズ
2020 年 9 月 4 日 20:56
申し訳ありませんが、いいえ。最適化は完全に「実装の品質」に委ねられます。実装では INLINE を完全に無視することができます。これらすべての宣言は、実装が必要に応じて使用できるヒントとしてのみ考慮されます。
– バルマー
2020 年 9 月 4 日 20:57
SBCL 固有の最適化についてはわかりません。
– バルマー
2020 年 9 月 4 日 20:58
ご協力ありがとうございます。おそらくこれは SBCL メーリング リストの質問です。そうですね、reduce の呼び出しにコストがかかるとは思いませんが、あらゆる種類の反復や検索の最適化がテーブルから除外されています。それが単純な配列であること。
– ジャスティン・マイナーズ
2020 年 9 月 4 日 21:16
