mod-exptの高速化

タイトルは大分嘘です。

Linux上での暗号ライブラリテストが以上に遅かった。他のOSでは問題ないのだが、Linuxだけ10倍以上遅い。何が遅いのかなぁと調べてみると、鍵対の生成が1024ビット程度でも3秒くらいかかっているというものだった。これはおかしいなぁと思っておもむろに鍵対生成をプロファイラにかけてみるとmod-exptが遅い。120回程度呼ばれて1500ms消費という感じであった。

この手続き自体は確かに重いものなのだが、どうもおかしい。以前(多分0.5.x辺り)ではそんなに時間がかかった記憶がない。つまりその辺から今までで入れた変更でLinuxのみが遅くなった可能性がある。記憶を辿ってみると確かにBignumの演算に手を入れた記憶があったので、とりあえずソースを覗いてみる。っが、特に不審な部分も見当たらない。Linux固有の何かを使ったものはないという意味でではあるが。

疑問を疑問のままにしておくのは今一気持ちが悪いので、Valgrindについてるcallgrindを使ってCレベルのプロファイルを取る。すると、mod-exptの処理自体は高速に終わっているという結果が取れた。っで、コールグラフのその下を見ると、スタック領域の割り出しの処理が異常に重たい。そういえば、Bignumの計算でスタックが溢れる不具合を直した際にそんな処理入れたなぁと思い、ダミーの値を返すようにしてSchemeのプロファイルを取る。3秒が30msになった。お前か・・・

具体的にはスタックベースを取得するのが異常に遅いっぽかった。そもそもスタックベースなど一回取得してしまえば変更されることはないはずなので毎回値を律儀に取得しにいくこともないよなぁと思いスレッドローカルな静的領域に格納するように変更。これだけで100倍の高速化に成功した。(実際は100倍の低速化が行われているので、元に戻っただけだが・・・)

ここからは(も？)与太話。
スタックベースの取得にはBoehmGCのGC_get_stack_baseを使っているのだが、LinuxとCygwinで100倍以上の差が付くのはなぜだろうと思いちょっと実装を覗いてみた。Linux(x86_64)では以下の処理を行う：

1. pthread_getattr_npの呼び出し
2. pthread_attr_getstackの呼び出し
3. pthread_attr_destroyの呼び出し

それぞれの関数の呼び出しがどれくらい重いかはよく知らないが、1万回以上の呼び出しがあったのでそれなりにはかかるだろう。(Bignumの処理は大抵再帰なので再帰的にスタック領域の確認をするのだ。)

っで、Cygwinの実装を見てみた。

    GC_API int GC_CALL GC_get_stack_base(struct GC_stack_base *sb)
    {
      void * _tlsbase;

      __asm__ ("movl %%fs:4, %0"
               : "=r" (_tlsbase));
      sb -> mem_base = _tlsbase;
      return GC_SUCCESS;
    }

以上！そら速いわ。。。1万回呼び出されても誤差の範囲に収まるだろうなぁというのは想像に難くない。

特に何もなく、callgrindが便利だったというだけの話だったりはする。他のプロファイラと違いランタイムにリンクさせる必要ないというのはとてもありがたい。その分処理は劇的に遅くなるけど、的が絞れているならこれほど便利なものはないなぁと思ったのでした。