前回の続き。 githubにあるloopの簡易版を載せておく。 基本的な考え方 基本的なJava等のIteratorと似た*1インタフェースを通してループ処理を実現している。 異なるのは全ての関数をinline展開可能にすることで、同等のループを非関数型的に書いた場合と同…

マージソート(1)の改良版。 ソートのような高階関数では、引数で渡した比較関数の間接呼び出しのコストも実行速度にそれなりの影響を与えるので、それを(マクロをほとんど使わずに)できるだけ低く抑えるための試み。 比較関数最適化 まず、比較関数自体の実…

以下、sbcl-1.0.51-x86-64-linuxでの実行結果。 ;; 計時用関数 (defun compare-time (fn nums1 nums2) (declare (optimize (speed 3) (safety 0) (debug 0)) (function fn)) (time (loop FOR n1 fixnum IN nums1 FOR n2 fixnum IN nums2 WHEN (funcall fn n1…

Forthでハノイの塔 - sileの日記でハノイの塔を解くcommon lispプログラムを載せたら「inline宣言を付けるともっと早くなりますよ」というコメントを頂いたので試してみた。 inline宣言付与結果 再帰関数をinline展開する際の深さはsb-ext:*inline-expansion…

SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て＋GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィ…

関数を書いていると、引数の型チェックを有効にするかどうかで悩むことがたまにある。 ;;;; sbcl-1.0.37 ;; 足し算を行う関数 ;; 引数が適切な前提としている (defun plus-impl (x y) (declare ((integer 0 1000) x y) (optimize (speed 3) (safety 0))) (+ …

あまり話題に関連性がないが、一応前々回の続き。 sbcl(1.0.37)での文字列関連の型の階層は以下のようになっている*1。 僕は最近までsimple-string型*2が文字列関連型の最下層だと思い込んでいたので、文字列を扱う部分のプログラムを高速化したい場合、(dec…

common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…

前回と重複するところがあるが、ftype型宣言の有用な使い方について書いておく。 関数の戻り値の型指定 ftype型宣言を使うと、関数の戻り値の型を指定することができる。 これが何故有用かと云うと、sbclは関数の戻り値の型が指定されている場合、それに基づ…

ftype型宣言。 あまり使われているのを見ない気がするが、これを使うと「型宣言なしでは遅いけど、宣言をつけるとコードが汚くなる」というような問題を解決できる時があるので、少し書いておく。以下はsbcl(1.0.34)での挙動。 準備 ;; 処理速度を最優先 (de…

今日たまたま見つけた『(Sather を試そう) 1. Sather vs C++: 実行速度の比較』*1というページに触発され、lisp(sbcl-1.0.28)でも同様の比較を行ってみた。 C++のソースコードは、上記ページのものと同様だが、g++のオプションには'-O3'を渡している。 実行…

最近のバージョンのSBCL*1では、処理速度を最優先にする宣言を行って関数をコンパイルした場合でも、デフォルトではコンパイラノート*2が表示されないことがある*3。 そのため、最適化を確実に行いたい場合は、コンパイラノートを出力するように明示的に宣言…

sbcl(1.0.28)は、適切に型宣言を行っておけば、冗長な型判定を実行コードから除外してくれるようだ。例えば次のようなマクロを定義する。 (defmacro get-type (obj) `(typecase ,obj (list :list) (fixnum :fixnum) (vector :vector) (t :others))) ; ↓のよ…