Common Lispの処理系SBCLにおける型と最適化

ここ数日はしんどいスケジュールだった。

11/19(火)に8時間ほど働いた後に夜行バスで東京に移動、11/20, 21でLINE DEVELOPER DAYに2日間参加して夜行バスで京都に戻り、その後8時間労働。

少々この1週間はおおよそ人権がないのではという感じだったが、なんとか乗り切ってゆっくりとした休日を迎えている。

そんな休日ということで今日はのんびり散歩したりしていたのだが、ふとLispの型と最適化方針について気になったので今日は少しそこらへんについて調べていた。

今回のエントリーはそこらへんを簡単にまとめたもの。

結論から

ちなみに結論から言うと、Lispはめちゃくちゃ速い言語である。

ちゃんと型を指定した上で最適化してコンパイルすればC言語と遜色ないレベルの速度が出る。

Lispインタプリタコンパイラの両方で実行ができる言語で、インタプリタで実行した際あまり速度は期待できないのは事実ではあるが。

色々な記事でLispはめちゃくちゃ遅いというように断定するようなものがあったりするが、これはLispについて何も知らないド素人が自分はプログラミング言語について詳しいですよという顔をするために書いたクソ記事である可能性が高い。

実際にこんな名言もある。

Cで書くコードの方がCommon Lispで書くより速いって人がいたら、それは彼のCの技量が高すぎるってことだね。

“If you can't outperform C in CL, you're too good at C.” — Eric Naggum

また、このSchemeのサイトにて川合史朗さんも

普通に(教科書的に)書かれたLispコードは、コンパイルしても確かにCより 数倍遅いでしょう (ソースコード量は数分の一でしょうが)。

C並に速いLispコードを書くためには、いくつも気を付けなければならないことがあります。

  • inner loopでメモリをアロケートしない: Cと違ってLispの場合は暗黙のうちに メモリアロケーションが入ることが多いので、どういう操作だとアロケーションが 入らないかを熟知している必要があります。
  • 型宣言をつけまくる: あいにく、商用のLispコンパイラでもあまり賢い 型推論は行ってくれないみたいで、とにかく鬼のように型宣言をつけまくる 必要があります。
  • safetyを0にすると処理系は救ってくれない:宣言された型とは違う型の オブジェクトを渡すとSEGVしてくれます ;-(

なので、C並に速いLispコードは見た目も安全性もC並になる、というのが 私 (Shiro) の経験です。

このように高速化に際して危険性を孕みつつもC並みに高速化することへの可能性について語っている。

本エントリーではどのように型を指定してプログラムを高速化するかということを簡単にまとめる。

Lispというプログラミング言語

プログラミング言語は型についてシステムとして(静的|動的)な(強い|弱い)型付けという説明がなされたりする。

静的型付けは、簡単に説明すると変数や関数に型を予め定義しておき、その型以外のデータを変数では使えないような型システムのこと。

一方で動的型付けとは、動的に型を付けるという読んでそのままの通り、プログラムを書くときに変数や関数に何が入ってくるかというのが特に決まっていない形を指す。

主に静的型付けとして代表されるのがC言語とかで、動的型付けとして代表的な言語がPythonとか。

また、強い型付けと弱い型付けについて、プログラムでは基本的に演算は型の指定をしてくるが、もし指定ではない型を用いてしまった場合にどのような挙動を示すかについての分類を強い型付けとか弱い型付けとか言ったりする。

具体的に、C言語

int a = 10;
char b = "20";

のようにしたときa + bは整数と文字列の和をとろうとしてエラーを吐く。

しかしJavaScriptだと10 + "20"は結果として"1020"という文字列を返してくる。

型の強い弱いに関して、整数型を浮動小数点型に自動的にキャストするような言語は弱い型付けと言っていいと思われる。

個人的にはここらへんの型システムとプログラミングスタイル(オブジェクト指向型と関数型)については色々言いたいことがあるのだけれど、それについては来月のアドベントカレンダーまで温めておこうと思う。

さて、このような型システムにおいて、Lispは動的な強い型付けの言語であると言うことができる。

動的な型と速度の問題

動的な型を用いた言語は、プログラムの実行に際してその都度に変数や関数の型をチェックしたり推論したりするので、静的な言語に比べて一般的に実行速度で劣る。

動的な型システムを持つ言語ではプログラムの実行に際してユーザーが厳密に指定する必要はないので高速な開発に向いていると言えるが、その分プログラムの実行速度は遅くなるのでこれらの型システムとユーザーの自由度(開発スピード)はトレードオフの関係にあると言える。

余談だが、自分が一番最初に触ったプログラミング言語C言語で、最初はプログラミングとは変数を型とともに宣言してそれをコンピュータに読ませる必要があるものだと認識していたのだけど、そのあとにPythonを触ってこんなにも使いやすい言語が存在するのかと非常に驚いた記憶がある。

Pythonを触り始めて以降、自分はアルゴリズムの実装において基本的に静的な型システムを持つ言語は使っておらず、だいたいLispPythonばかり使っている。

動的な型システムの言語で型を指定して速くする

さて、先述の通り、動的な型システムを持つ言語でプログラムを普通に記述するとC言語のような速度は出ない。

しかし、型の指定を行えばかなりの高速化が狙える。

例えば具体的に以下の階乗を計算するコードを見てみよう。

(defun factorial (n)
  (if (= n 1)
      1
      (* n
         (factorial (1- n)))))

これで10000の階乗を計算すると、実行時間は以下の通り。

CL-USER> (time (factorial 10000))

Evaluation took:
  0.050 seconds of real time
  0.050077 seconds of total run time (0.044013 user, 0.006064 system)
  [ Run times consist of 0.026 seconds GC time, and 0.025 seconds non-GC time. ]
  100.00% CPU
  110,624,296 processor cycles
  4 page faults
  69,740,608 bytes consed

ちなみにコンパイルすると実行速度は以下の通り。

CL-USER> (time (factorial 10000))
Evaluation took:
  0.038 seconds of real time
  0.037463 seconds of total run time (0.024041 user, 0.013422 system)
  [ Run times consist of 0.005 seconds GC time, and 0.033 seconds non-GC time. ]
  97.37% CPU
  82,108,806 processor cycles
  69,739,648 bytes consed

さて、こいつに型宣言をつけてやる。

まず関数の型について、

(declaim (ftype [typespec] [関数名]))
(defun 関数名 (引数)
  (...))

というような感じで引数と返り値の型を定義する。

今回のケースにおいて10000の階乗を計算するが、今回のSBCLにおいてmost-positive-fixnum4611686018427387903であってそれを超えるとintegerになるので、引数の型をfixnumとして返り値をinteger`とする。

(declaim (ftype (function (fixnum) (values integer &optional)) factorial))
(defun factorial (n)
  (if (= n 1)
      1
      (* n
         (factorial (1- n)))))

これをコンパイルして実行した結果として

CL-USER> (time (factorial 10000))
Evaluation took:
  0.021 seconds of real time
  0.021132 seconds of total run time (0.020203 user, 0.000929 system)
  [ Run times consist of 0.005 seconds GC time, and 0.017 seconds non-GC time. ]
  100.00% CPU
  46,617,370 processor cycles
  69,735,360 bytes consed

うん、スクリプトとして実行した際の実行時間は0.050077コンパイル時の実行時間が0.37463だったので、これらと比較したらだいぶ速くなった。

次に変数の型宣言をしてやる。

これは

(declare (type fixnum 変数名))

としてやれば良い。

また、同時に各出力フォームについても型を宣言してやる。

(declaim (ftype (function (fixnum) (values integer &optional)) factorial))
(defun factorial (n)
  (declare (type fixnum n))
  (the integer
       (if (= n 1)
           1
           (* n
              (factorial (1- n))))))

速度は以下の通り。

CL-USER> (time (factorial 10000))
Evaluation took:
  0.022 seconds of real time
  0.022008 seconds of total run time (0.021223 user, 0.000785 system)
  [ Run times consist of 0.005 seconds GC time, and 0.018 seconds non-GC time. ]
  100.00% CPU
  47,991,386 processor cycles
  69,754,544 bytes consed

パッと見だと前より遅くなっているが、システム側の実行時間はさらに短縮されていることがわかる。

さて、ダメ押しで関数のインライン化をして関数の呼び出しを節約し、呼び出しのオーバヘッドを殺そうと思う。

(declaim (ftype (function (fixnum) (values integer &optional)) factorial)
         (inline factorial))
(defun factorial (n)
  (declare (type fixnum n))
  (the integer
       (if (= n 1)
           1
           (* n
              (factorial (1- n))))))

これはコンパイラ側に関数を埋め込むことになり、インライン展開されたコードが実行されればされるほど効果的となる。

Evaluation took:
  0.026 seconds of real time
  0.026104 seconds of total run time (0.025496 user, 0.000608 system)
  [ Run times consist of 0.009 seconds GC time, and 0.018 seconds non-GC time. ]
  100.00% CPU
  57,044,664 processor cycles
  66,851,024 bytes consed

今回は単純な再帰アルゴリズムなのでインライン化の恩恵を受けてないが(むしろ遅くなってる)、これは大きなプロジェクトなどでじわじわと効いてくる最適化なので重宝したい。

まとめ

今回はSBCLでコードを高速化する手法についてざっとまとめた。

最終的に最初のインタプリタとして実行した際の倍以上の速度を獲得することができた。

Lispはかなり速い部類の言語だと思うし、そもそも言語としてアルゴリズムの表現性が高いのでコードデザインの部分として最適化の余地はいくらでもあるように思える。

自分もまだまだCommon LIspについては未熟であるが、もっと極めていきたい。