Elisp performance tuning

雑記 Elisp

究極の隙間産業 elisp のパフォーマンスチューニングをした。
↓これを作ってるときにスピードが遅い原因を調べたときのメモを適当にまとめた。

http://d.hatena.ne.jp/mhayashi1120/20130827/1377606396

なお aes.el との比較は aes-256-cbc で大雑把に比較した。
入力パラメータは kaesar.el のデフォルトと同じにしておく。
cbc という block mode は openssl コマンドのデフォルトにもなっている、実行コストは高いが安全なモードである。

(setq aes-default-method "CBC")
(setq aes-Nk 8)

活用したライブラリや関数

  • elp ライブラリ (関数呼び出しにかかる時間がわかる)
  • benchmark ライブラリ (GC の回数とかかる時間がわかる)
  • macroexpand-all

elp はあんまり日本語の解説がみられない。
そんなに使い方が難しいわけじゃないのだけど

M-x elp-instrument-package kaesar

一度暗号、復号を実行してから M-x elp-results をすると関数の実行時間一覧が得られる。
以下に記述するような defsubst form の inline 展開をした後だと、それぞれの subst 関数の実行時間が得られないので byte-comiple されてないものを load しておく。
この結果をもって最適化の目安とする。

performance up の指針

  • byte-compile されてない場合は遅くても構わない。
  • AES の仕様を十分に理解できるまで何度も読み続けたいので可読性を犠牲にしない。AES の仕様に書かれた関数と elisp 関数の整合性をできる限り保つ。
  • 関数呼び出しを減らす。具体的には defsubst で byte-compile 後に inline 展開する。
  • lisp ファイルを load する時間は遅くても構わない。もちろん速ければそれに越したことはない。

結果を cache する

できるだけ実行時の計算を抑えるために、演算の結果を前もって load 時に cache する。
例えば乗算は char * char の範囲しかないので 256 の要素を持つ集合を 256 個作る。
集合を保持する形式は何にするか？ hash だと明らかにオーバースペックであろう。list か vector か、どちらがいいか。

普通に考えれば

list: nth O(n)
vector: aref O(1)

だと思うけど、一応 benchmark してみる。先頭の要素と最後尾の要素を参照する際の消費時間を測る。

(let ((v (make-vector 255 0)))
  (list
   (benchmark 1000 `(aref v 0))
   (benchmark 1000 `(aref v 254))))

=> ("Elapsed time: 0.000115s" "Elapsed time: 0.000111s")

(let ((l (make-list 255 0)))
  (list
   (benchmark 1000 `(nth 0 l))
   (benchmark 1000 `(nth 254 l))))

=> ("Elapsed time: 0.000151s" "Elapsed time: 0.001107s")

というわけで、先刻の予想通り vector を使うのがよろしい。いくつかの計算結果を vector に格納すると大部はやくなった。数字は残っていない。

ループを減らす

暗号機能内部の話は複雑なのでカット。とにかく内部のループ処理を少し減らした。
aes.el を参考にしたわけじゃないけど、結果としてほとんど同じことをするようになった。*1

ループを減らす (2)

4 byte を一塊として扱っているので 4 回ずつのループが随所にある。
マクロでうまく展開する方法が思いつかなかったので単純に 4 個別々の form に。

(dotimes (i 4)
  (aset word i (aref kaesar--S-box (aref word i))))

↑を単純にこんな感じに。

(aset word 0 (aref kaesar--S-box (aref word 0)))
(aset word 1 (aref kaesar--S-box (aref word 1)))
(aset word 2 (aref kaesar--S-box (aref word 2)))
(aset word 3 (aref kaesar--S-box (aref word 3)))

compile 時に計算をする

あんまり使ったことなかった eval-when-compile, eval-and-compile を使って byte-compile 時に前もって計算をしておく。
byte-compile する時間は長くなるけど load する時間は一気に短縮される。計測はしていない。

defsubst を使う

inline 展開するように defun ではなく defsubst を使った。
defsubst にした関数は呼び出し元の定義よりもソース上部に書いておかないといけない。
load を早くするため、defsubst form を上述した eval-when-compile で包むと内部でしか使わない余計な関数が生成されなくなるようだ。

GC を減らす

GC を減らすための指針。

  • append 関数を使わない。できれば nconc を使う。append 関数を使っていても、それで生成された list を nconc でくっつけるのならセルの無駄遣いにならないので ok
  • vconcat, make-vector など配列を生成する関数を実行時にできるだけ使わない。
  • substring で文字列切り出しもしない。これは配列を生成してるのとほとんど同じ(はず)。
loop マクロ

この暗号プログラム作ったときに初めて cl ライブラリをふんだんに使ってみた。loop マクロが超便利。
しかし、こういう macro 展開をしているのに気付かなくて悩んでた。
append 関数がすごくセルを無駄遣いして GC の原因になる、ということを知った後に macroexpand をしてみるとすぐに分かった。


どちらも同じものを生成するのかと思ったら、

(loop for x in '(1 2 3)
      append (list x))

(loop for x in '(1 2 3)
      append (list x)
      into res
      finally return res)

(macroexpand-all
 '(loop for x in '(1 2 3) append (list x)))

=>

 (progn
   (let* ((--cl-var-- (quote (1 2 3))) (x nil) (--cl-var-- nil))
     (while (consp --cl-var--)
       (setq x (car --cl-var--))
       (setq --cl-var-- (nconc (reverse (list x)) --cl-var--))
       (setq --cl-var-- (cdr --cl-var--)))
     (nreverse --cl-var--)))

append keyword で返却値を設定すると (nconc (reverse (list x)) --cl-var--) で繋いでいってくれるけど、

(macroexpand-all
 '(loop for x in '(1 2 3)
        append (list x)
        into res
        finally return res))

=>

(progn
  (let* ((--cl-var-- (quote (1 2 3))) (x nil) (res nil))
    (while (consp --cl-var--)
      (setq x (car --cl-var--))
      (setq res (append res (list x)))
      (setq --cl-var-- (cdr --cl-var--)))
    res))

append に into を加えるとなぜか (append res (list x)) へと展開される。
なんでこんな仕様なのか考えてみると into で代入先の変数を明示しちゃうと、プログラマに見えるようにしないといけないから reverse して nconc して隠し変数に蓄積するわけにいかないから。

とにかく vector と list を削減

タプルを使いたいときでも list, vector を生成しない。めんどくさくてもそれぞれの item をそれぞれ別々のローカル変数に格納する。

わかりづらい例

(let ((x [0 1 2 3])
      (y [4 5 6 7]))
  (let ((v1 (vector (aref x 1) (aref y 2)))
        (v2 (vector (aref y 0) (aref x 3))))
    (logxor (aref v1 0) (aref v2 1))))

みたいにしてたとこを

(let ((x [0 1 2 3])
      (y [4 5 6 7]))
  (let ((v1-1 (aref x 1))
        (v1-2 (aref y 2))
        (v2-0 (aref y 0))
        (v2-3 (aref x 3)))
    (logxor v1-1 v2-3)))


さしたる意味もなく append してた箇所はがんがん削減。

やってみたけど、そんなに意味なかったこと

loop マクロを while ループへ。loop マクロは遅いなどと思いこんでたけど、 byte-compile したら展開されてほとんど一緒になる。
その他、愚にもつかないことをいっぱいやったような。。あとは思い出せない。

M-x profiler-start

なにこれすごい。一通り書き終わった頃に存在に気付いた。いつからか Emacs に標準装備されたっぽい。
しかし GC で開放されてるメモリが獲得された箇所は特定できないのかな？
まだ十分に理解してないけど、この performance tuning では使う方法が思いつかなかった。

最終結果

core 関数を byte-compile したもので正確なベンチマークを取ってみた。

aes.el

(load-library "aes.elc")
(benchmark 10
    '(aes-Cipher 
      "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"
      '(((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0) ((0 . 0) 0 . 0))
      4 14))

=> "Elapsed time: 0.002048s"

kaesar.el

(load-library "kaesar.el")
(load-library "kaesar.elc")
(byte-compile 'kaesar--cipher!)
(setq kaesar--Nk 8)
(setq kaesar--Nr 14)
(benchmark 10
    '(kaesar--cipher!
      [[0 0 0 0][0 0 0 0][0 0 0 0][0 0 0 0]]
      [[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]]
      ))

=> "Elapsed time: 0.001660s"


と、いうわけで最終的には若干 aes.el を上回ることはできたようだ。
数学の知識があればもっとスピードアップできるのだろうか。

配列から配列にまとめてコピーする機能、 C でいうところの memcpy な機能が C レベルで提供してあればもう少し高速化できる気がする。

*1:SubByte しながら ShiftRow する、MixColumn しながら AddRoundKey する