__builtin_ffsはどこへ行くのか?(続編)

GCのマークビット判定などに使用される__builtin_ffsというGCCコンパイラ拡張が気になったので 「__builtin_ffsはどこへ行くのか? - dec9ue's diary」って記事をちょっと前に書きました。

続編です。

さて、何の話だったかというと、__builtin_ffsとは



Other Builtins - Using the GNU Compiler Collection (GCC) http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html によると

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

ということで、ビットマップ何かを操作するときに使えるGCC拡張のようだ。



ということでした。

そして、今回は

でも、対象をもうちょっとモダンなアーキテクチャに変えちゃうかも。。。

の予告通り、armv7-aのアーキテクチャに変えてみました。

arm-linux-gnueabihf-gcc -O0 -S -std=gnu99 builtin_ffs_test.c 

の結果:

test:
        @ args = 0, pretend = 0, frame = 8
        @ frame_needed = 1, uses_anonymous_args = 0
        @ link register save eliminated.
        push    {r7}
        sub     sp, sp, #12
        add     r7, sp, #0
        str     r0, [r7, #4]
        ldr     r3, [r7, #4]
        rbit    r3, r3
        clz     r3, r3
        ldr     r2, [r7, #4]
        cmp     r2, #0
        bne     .L2
        mov     r3, #-1
.L2:
        add     r3, r3, #1
        mov     r0, r3
        add     r7, r7, #12
        mov     sp, r7
        pop     {r7}
        bx      lr

ARMv7AのARMインストラクションセットにはclzという先行0ビット判定を行うインストラクションがあります。これ使っちゃえば楽勝じゃん?

本当にありがとうございました。



あ、でもちょっと気になるのは、このインストラクションの発行フローはclzrbitの組み合わせがあれば使う価値があるのですが、これはARMv6T2以降のARM/32bitThumbで使えるはずです。じゃぁ、なんでCortex-M3向けのコードはあんなややこしいコードになってたのか。16bitThumbを使うことを優先したのかな?

Lucky Thirteen Attackの攻撃手法を説明してみるよ

Lucky ThirteenはTLS, DTLSのCBCモードを利用する暗号の脆弱性を突く攻撃です。具体的に言うと、CBCモードに対するPadding処理の弱い部分を狙ったPadding Oracle攻撃の一種です。

その影響とか、脅威とか、対処法とかは結構いろんな所で説明されているのですが、単純な興味とか、知識とか、内容を実感したい、というような方が読むことを想定した記事はあまりないように思われたので、その仕組みを説明したいと思います。

TLSパケットの仕組み

まずはじめに、TLSパケットの暗号処理の仕組みを簡単に説明します。

イメージとしてはこんなかんじで、ヘッダ+平文データのMAC(チェックサム的なもの)をとる→パディングをつける→暗号化する、
と言った流れでパケット(レコード)を構築します。

f:id:dec9ue:20130324132031p:plain

TLSのパディング

ブロック暗号はそのままではブロックの幅に合わないデータを取り扱えないので、パディングを付与して使用します。TLSのパディング処理はとてもシンプルです。(そしてありきたりです)

f:id:dec9ue:20130324132334p:plain

このように、ブロック長の残りがnのとき、(n-1)をn個埋めるのがTLSのパディングです。

TLSのMAC処理

MACは、復号後にデータが変更されていないことを確認するために使用します。
現在、最もよく使われているのはHMAC-SHA1です。ハッシュを繰り返して
20バイトのMACを生成します。

ここで実はちょっとしたポイントがあります。

HMAC-SHA1はデータ長によって使用されるハッシュ処理の回数が違います。
例えば、~55Byteだと4回のハッシュで済むのですが、56Byte~だと5回必要になります。

タイミングリーク

タイミングリークとは、処理のタイミングからデータや鍵に関する情報が漏れてしまうことを言います。

よくあるのは不正なパケットに対するエラー処理のタイミングリークで、Lucky Thirteenもこのケースに当たります。

適当な64バイトのシーケンスを受信者に復号させてみた場合、基本的にエラーになるわけですが、このエラーパターンは激レアなケースを除くと概ね下記のように分類されます。

  1. パディングエラー … ほぼ 255/256の確率
  2. 0x00 で終わる(1Byteパディング) ほぼ 1/256 の確率
  3. 0x01 0x01で終わる(2Byteパディング) ほぼ 2^-16 の確率
  4. : (その他レアケース)


f:id:dec9ue:20130324134008p:plain

ところで、これらについてMACを計算すると、実は0x01 0x01で終わるケースだけが必要なハッシュが少なくなっています。

f:id:dec9ue:20130324134248p:plain

実装に工夫がないと、この2^-16の確率で発生するケースだけが微妙に早くエラーパケットを返すことになります。

これぐらいの差、そうそう発見できないだろ?って思いますよね。でも、外からの観測で実際にわかった、というのがLucky Thirteen Attackの報告の主旨なのです。

Lucky Thirteen Attack

攻撃者がC*という暗号ブロックを復号したい場合、下記のようなヘッダ+4ブロックのレコードパケットを復号者に送りつけます。

ヘッダ || ブロック1 || ブロック2 || 調整ブロック || 解析対象ブロックC*

復号者は最終ブロックC*を下記のようにCBCモードで復号します。

復号後のブロック = (復号後の(解析対象ブロックC*)) XOR 調整ブロック

この復号後のブロックは先に述べたとおり下記のどれかに類型されます。

  1. パディングエラー … ほぼ 255/256の確率
  2. 0x00 で終わる(1Byteパディング) ほぼ 1/256 の確率
  3. 0x01 0x01で終わる(2Byteパディング) ほぼ 2^-16 の確率
  4. : (その他レアケース)

3.の「0x01 0x01で終わる」ケースだった場合、C*の最後の2バイトは

調整ブロックの最後の2バイト XOR 0x01 0x01

で得られるわけです。

攻撃者は2^-16の確率でこのケースを手に入れます。このケースが手に入ったかどうかはエラーが返ったタイミングで判断します。

タイミングを検出出来れば攻撃者は調整ブロックとのXORによりC*の最終ブロックの平文の最後の2バイトを取り出せます。

このような調子で次々にブロックを復号できるのですが、実は大変なのは最初の2^-16の部分だけで、
残りは2^-8の確率で見つけることができます。

こうやって攻撃者は2^16+14*2^8回のトライで暗号文を復号できます。

最後に

2^16という数字は小さいでしょうか?大きいでしょうか?

統計的な攻撃方法については述べませんでしたが、同じ平文を送信するセッションが260万回ぐらい、半分程度だとしても130万回ぐらい必要です。検索サイトのログインクッキーだったらこれくらい行ってしまうでしょうか?ちょっとわからないですね。。。

また、攻撃者の位置によってはネットワークノイズの影響をかなり受けると思われます。

いずれにせよ、リスクと投資のバランスを考えた対応が重要だとは思います。

参考

今回、参考にしたのは下記の文書のみです。おそらく、他にも良資料があるとは思いますが。

Lucky Thirteen: Breaking the TLS and DTLS Record Protocols

__builtin_ffsはどこへ行くのか?

__builtin_ffsとはなにか?

Other Builtins - Using the GNU Compiler Collection (GCC) http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html によると

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

ということで、ビットマップ何かを操作するときに使えるGCC拡張のようだ。

これ、何やってるかちょっと気になったのでアセンブラ見てみよー!

ということで、x86アセンブラはしばらくやる気ないので、ARMのアセンブラをやってみる。

gcc version 4.7.3 20130102 (prerelease) (Linaro GCC 4.7-2013.01) 
decque@ubuntu:~$ arm-none-eabi-gcc -print-multi-lib 
.;
thumb/arm7tdmi-s;@mthumb@mcpu=arm7tdmi-s
thumb/cortex-m0;@mthumb@mcpu=cortex-m0
thumb/cortex-m3;@mthumb@mcpu=cortex-m3
thumb/cortex-m4;@mthumb@mcpu=cortex-m4
thumb/cortex-m4/float-abi-hard/fpuv4-sp-d16;@mthumb@mcpu=cortex-m4@mfloat-abi=hard@mfpu=fpv4-sp-d16

この人、thumbしか吐けません。

__builtin_ffsを含むコードをアセンブラ化してみると:

ffsl:
        @ Function supports interworking.
        @ args = 0, pretend = 0, frame = 8
        @ frame_needed = 1, uses_anonymous_args = 0
        stmfd   sp!, {fp, lr}
        add     fp, sp, #4
        sub     sp, sp, #8
        str     r0, [fp, #-8]
        ldr     r0, [fp, #-8]
        bl      __ffssi2
        mov     r3, r0
        mov     r0, r3
        sub     sp, fp, #4
        ldmfd   sp!, {fp, lr}
        bx      lr

__ffssi2へ飛んでいる。


主よ、どこへ行かれるのですか?

探してみた。

バイナリファイル /lib/gcc/arm-none-eabi/4.7.3/thumb/cortex-m0/libgcc.a に一致しました

ほう。

_ffssi2.o:
00000010 N $d
00000000 t $t
         U __ctzsi2
00000001 T __ffssi2

_ffssi2.oを逆アセンブルしてみると

ar x gcc.a _ffssi2.o
objdump -D _ffssi2.o
00000000 <__ffssi2>:
   0:   b508            push    {r3, lr}
   2:   2300            movs    r3, #0
   4:   2800            cmp     r0, #0
   6:   d002            beq.n   e <__ffssi2+0xe>
   8:   f7ff fffe       bl      0 <__ctzsi2>
   c:   1c43            adds    r3, r0, #1
   e:   1c18            adds    r0, r3, #0
  10:   bc08            pop     {r3}
  12:   bc02            pop     {r1}
  14:   4708            bx      r1

だからどこへいくねん。。。

さらに追いかけてみると。。。

00000000 <__ctzsi2>:
   0:   e2601000        rsb     r1, r0, #0
   4:   e0000001        and     r0, r0, r1
   8:   e3a0101c        mov     r1, #28
   c:   e3500801        cmp     r0, #65536      ; 0x10000
  10:   21a00820        lsrcs   r0, r0, #16
  14:   22411010        subcs   r1, r1, #16
  18:   e3500c01        cmp     r0, #256        ; 0x100
  1c:   21a00420        lsrcs   r0, r0, #8
  20:   22411008        subcs   r1, r1, #8
  24:   e3500010        cmp     r0, #16
  28:   21a00220        lsrcs   r0, r0, #4
  2c:   22411004        subcs   r1, r1, #4
  30:   e28f2008        add     r2, pc, #8
  34:   e7d20000        ldrb    r0, [r2, r0]
  38:   e0400001        sub     r0, r0, r1
  3c:   e12fff1e        bx      lr

あー、なんか追い詰めきれないです。。。

  • 知らないインストラクションばっかになってる。。。単語帳引きながら英語読んでるレベル。。。
  • 32bit長になっちゃってるけどなんかARM modeになっているのでは
  • objdumpにもうちょっと頑張ってもらわないといけないのではないだろうか。。。

明日以降もうちょっと追ってみます。。。でも、対象をもうちょっとモダンなアーキテクチャに変えちゃうかも。。。

"volatile"をつけると値がレジスタに浮かない

チラ裏にでも書いてろ、って内容なので何ですが、、、

C言語の変数にvolatileをつけたら値がレジスタにキャッシュされたままにならないね、と言う話を実際に確認してみました、と言う話。

そのままろくに考えないでやってみます。

まず、下記のような意味のないコードを用意してみました。

int n = 0;

int main(){
        n++;
        n--;
        n = 100;
        return 0;
}

これを

arm-none-eabi-gcc -O0 -S test.c

のようにコンパイルしてみると

main:
        str     fp, [sp, #-4]!
        add     fp, sp, #0
        ldr     r3, .L3
        ldr     r3, [r3, #0]
        add     r2, r3, #1
        ldr     r3, .L3
        str     r2, [r3, #0]
        ldr     r3, .L3
        ldr     r3, [r3, #0]
        sub     r2, r3, #1
        ldr     r3, .L3
        str     r2, [r3, #0]
        ldr     r3, .L3
        mov     r2, #100
        str     r2, [r3, #0]
        mov     r3, #0
        mov     r0, r3
        add     sp, fp, #0
        ldmfd   sp!, {fp}
        bx      lr

インクリメント・デクリメントが明確にコード化されていて、(`add`,`sub`)それがメモリに直書きされている。(`str`) また、変数位置をいちいちメモリからロードし直している。

これを`-O1`でコンパイルしてみる

arm-none-eabi-gcc -O1 -S test.c

すると

main:
        mov     r2, #100
        ldr     r3, .L2
        str     r2, [r3, #0]
        mov     r0, #0
        bx      lr

あっ、演算どころか、変数値の読み込みすらしてねぇ。。。

最適化オプションつけてみると、、、

arm-none-eabi-gcc -O3 -S test.c

main:
        mov     r2, #100
        ldr     r3, .L2
        str     r2, [r3, #0]
        mov     r0, #0
        bx      lr

まぁ、これ以上削るのは難しいわな。。。

`volatile`版を用意した。

volatile int n = 0;

int main(){
        n++;
        n--;
        n = 100;
        return 0;
}

これをO0でコンパイルしてみる。

arm-none-eabi-gcc -O0 -S testv.c

この結果は、non-volatile版の-O0とまったく同じでした。。。

では、最適化オプションつけてみよう。。。

arm-none-eabi-gcc -O1 -S testv.c
arm-none-eabi-gcc -O3 -S testv.c

下記のコードのように定数値のロードについて少し工夫された様子が見える。
ただ、算術演算やデータ領域との読み書きに使用する。`ldr`や`str`は端折らずに入れられている。

main:
        ldr     r3, .L2
        ldr     r2, [r3, #0]
        add     r2, r2, #1
        str     r2, [r3, #0]
        ldr     r1, [r3, #0]
        mov     r2, #100
        sub     r1, r1, #1
        str     r1, [r3, #0]
        mov     r0, #0
        str     r2, [r3, #0]
        bx      lr
結論

最適化オプションによらずにリード、ライトを確実にしたかったらvolatileをつけるとよさそう。
でも、それ以上の保障をしたければ排他命令(LDREX/STREX,CLREX)を使用するべきなのかも。

copying_gcという車輪の再発明

なんか、最近、「車輪の再発明をしよう」みたいな話がちょくちょくあるので、GCを再発明してみた。

車輪の再発明をしよう」の例:
https://twitter.com/viscuit/status/288181884658257922

…まぁ、再発明っていうか、スクラッチで書いただけなんですけど。

コード

ここに置きました。
https://github.com/dec9ue/copy_gc/blob/master/copy_gc.c

簡単に解説

基本的にGHCのGCコードとほぼ同じアイディアで作っています。
つまり、

  1. Cheneyのアルゴリズムがベース
  2. 比較的サイズの大きなオブジェクトはコピーすると不利なので、pin留めされるように作っている

ただし、下記のような点は違います。

  1. 世代別GCはない
  2. Parallel GCもない
  3. InfoPointerのかわりに先頭1wordでオブジェクトの性質をメモっている

Cheneyのアルゴリズムについては以前に書いたスライドのp.12とかGCの神の記事とか見てください。

時間的な問題もありますが、世代別GCは実行コード側に手が入るのでやってません。
ParallelGCは。。。知らんがな。

「大きなサイズ」の話

GHCもそうなんですが、純粋なコピーGCではなく、マークスイープの考え方を混ぜています。
これによって、コピーGCの弱点であるコピーのコストを回避するとともに、FFIなどで使用するための「動かないオブジェクト」を作ることができます。

f:id:dec9ue:20130110233309p:plain

InfoPointerがらみの話

コピーGCでは、オブジェクトのサイズと含まれているポインタを正確に把握しなくては行けません。
GHCではInfoPointerというのがこの仕事をしています。このInfoPointerの先はTEXT領域にあって、リンク先をたどるとオブジェクトのサイズなどがわかります。
今回はこれは使用せず、(実行側に依存しちゃうもんね)オブジェクトの直上に1ワードとってその中にサイズやポインタ数を記録しました。

f:id:dec9ue:20130110233053p:plain

GHCのヒープ構造はここをみると解説があります。

良いコードなのか?

実戦で評価してないのでわからないです。何で評価したらいいんだろう。。。

感想

  • ムシャクシャしてやった。でもまだ反省してない。
  • gcのコードサイズはJHCのGCコードとさほど変わらない。(けど、統計機能が入ってないので、同じ機能に対してはこちらのほうが大きいとも言える。。。)
  • gcって意外に書ける気がする。でも時間かかりすぎたか。
  • パフォーマンスまだ測ってない。測り方募集中。
  • 「ここがヘンだよ」みたいなのあったら教えてくださいこわい人。

参考:
JHCのGCコード:
http://repetae.net/dw/darcsweb.cgi?r=jhc;a=headblob;f=/rts/rts/gc_jgc.c

JHCのGC解説

GC Advent Calendarでは時間的に書けなかった、JHCのGCの解説をまとめる。

JHCのGC概要


JHCには下記3つのGCオプションがある。

  • GCなし
  • BOEHM GC
  • JGC

このうち、上の二つはgc_noneによる実装であり、JGCはgc_jgcによる実装である。
この様な構成になったのは、JGCが後から追加されたためだと思われる。

gc_none の挙動


GCなし


アロケーションのために必要となるメモリ空間の確保は基本的にmallocで行われる。
mutatorへの割り当ては jhc_malloc と jhc_malloc_atomicの二種類の関数がある。

Boehm GC


BOEHM GCを使用するための実装(初期化等)も一部はここにあるようだ。

gc_jgc の挙動


JHCオブジェクトの基本構造


JHCの世界ではすべての値がポインタを介してアクセスされる。ポインタは次の4種類に分類される。なお、JHCの実行系内のポインタは下位2ビットがオブジェクト種別を識別するために使用されている。

下位2ビット GC対象のポインタを含むか?
P_WHNF 0x00 Yes 直値、関数値以外の値。
P_LAZY 0x01 Yes 遅延評価オブジェクト。値を含む。
P_VALUE 0x02 No 直値。16ビット、または30ビットの値でポインタではない。
P_FUNC 0x03 No 関数

JHCのメモリ領域はページ単位で管理されており、その先頭にあるのがS_BLOCK構造体。S_BLOCK構造体はオブジェクトのサイズによって微妙に内容が異なるが、ほぼ同じである。
なお、大きなオブジェクトを格納するページはMONOLITHIC BLOCKと呼ばれる。

struct s_block {
        SLIST_ENTRY(s_block) link;
        unsigned char flags;  // defined in rts/constants.h
        unsigned char color;  // offset in words to first entry.
        union {
                // A normal block.
                struct {
                        unsigned char num_ptrs;
                        unsigned char size;
                        unsigned short num_free;
                        unsigned short next_free;
                } pi;
                // A monolithic block.
                struct {
                        unsigned num_ptrs;
                } m;
        } u;
        bitarray_t used[];
};

s_block構造体のメンバーにusedというのがいるが、これがGC時のマークに使用されるビットである。MONOLITHICなブロックはusedのメンバーは常に一つである。

JHCのアロケーションシステムは独特の仕組みを持っている。

サイズによって

  • MONOLITHIC BLOCKから割り当てられたオブジェクト(150Byte~(4K-SBLOCKサイズ)まで)
  • キャッシュされた領域から割り当てられたオブジェクト(1~149Byteまで)

に大きく分けられる。

キャッシュは、サイズとポインタ数の組別に作られている。
割り当てを行う際はサイズとポインタ数の組から検索されるキャッシュを探す。
それぞれのキャッシュは双連結リストで管理されており、ある程度ヒューリスティックにソートされている。
実際の割り当ては、空きのあるブロックからUSEDビットの空きを探す形で実施される。

なお、キャッシュが使用するBLOCKはMEGA BLOCKSから割り当てて使用される。MEGABLOCK自体はmallocで確保される。(あえてmalloc?)

MONOLITHIC BLOCKは、MEGABLOCKとは別に、動的に確保/開放が行われる。(posix_memalignを使用)
実際のサイズにかかわらず、ページサイズが割り当てられるようである。(このため、巨大なオブジェクトは割り当てられなそう。)

GCの挙動


実際にGCが呼ばれた後の挙動を説明する。
1. すべてのオブジェクトのマークビットがOFFにされる。
2. ルート、および、StablePTRがマークされる。
3. ポインタをたどって、マークを付けていく。
4. 不要なMONOLITHをsweep/freeし、空のBLOCKをキャッシュ内のfree blocksにつなぐ。(MEGA BLOCKSの解放はしない)
5. 割り当てが速くなるよう、キャッシュ内のBLOCKの順序を整えて終了。

上記で特徴的なのは、MONOLITHIC BLOCKのオブジェクトには明示的なSweepフェーズがあり、ファイナライザを呼べるのに対し、キャッシュされたオブジェクトについてはSweepフェーズがない上にファイナライザもコールできないことである。また、usedビットは立てっぱなしにして、再割当て時の判定に使用する。(逆に言うと、再割当て時にはusedビットを再検索する必要がある。)

GCが呼ばれるタイミング


明示的に呼ばれる以外は使用中のブロック数が閾値以上になった時点で呼び出されるようだ。
ただし、GC実行後も閾値の90%以上のサイズを使用しているままの場合、閾値が2倍に増やされる。

Haskell の GC を比較してみる

GC Advent Calendar 22日目の記事です。

同じ言語に対する異なる処理系があれば、GCを比べてみたくなるのは人間のサガですよね。
今回はHaskellの2つの処理系のGCを比べて見ることにします。


GHC(the Glasgow Haskell Compiler)

Haskellの実行系といえばこれ。というような処理系です。Javaで言えばOracle JRERubyで言えばCRubyというところでしょうか。実用世界の処理系なので様々なオプションや最適化の実装が施されています。

JHC

コード効率を優先した処理系です。様々なコンパイラテクニックをフルスケールのコンパイラに実装するための場である、というようなコンセプト説明がされています。頭文字のJはJohn Meachamの頭文字なんでしょうか。

それぞれのGCの特徴

■ GHC

ではまず、GHCから。
GHCのGCは下記のような特徴を持っています。

  • コピーGC
  • 世代別GC
  • Parallel GC(ConcurrentとかIncrementalではなく、SMPで並列処理するGC)
  • マークスイープのオプションがある

GHCの動きを視覚的に見るには、ThreadScopeというプロファイル表示ツールが便利です。

f:id:dec9ue:20121223085348p:plain

適当にやっててもそれなりに表示されてなにかできた気分になる!

■ JHC

JHCのGCは下記のようなオプションがあります。

  • Boehm GC
  • JGC
  • GCなし

Boehm GCは有名な保守的GCの処理系ですね。
また、GCなしというのがあるのが面白いですが。。。

メインのGCはJHCの固有実装である、JGCとなります。

JGCの特徴は下記です。

  • マークスイープGC
  • World Stopping
  • その他、凝った仕組みは特に無し

JGCにもプロファイリング機能はありますが、グラフィカルなツールは見つかりませんでした。ごめんなさい。

同じコードを動かしてみる

下記は悪名高きHaskellの5行クイックソートです。
比較的ゴミが出やすいこのコードを使って、これらの実行系の動作を比較してみたいと思います。

sort_len :: Int
sort_len = 20000
main = do
        print $ show $ drop (sort_len - 1) $ quicksort [1..sort_len]

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

それぞれ、コンパイルします。

./sorttest: $(SRC)
        ghc -O2 $(SRC) -o $@

./sorttest_jhc: $(SRC)
        jhc $(SRC) -o $@

実行結果は、流石にGHCが速いですが、JHCもなかなかのものです。
JHCのシステム時間が短いのが印象的です。(理由はよくわからないですが、、、)

seg@ubuntu:~/haskell-training$ time ./sorttest
"[20000]"
real	0m54.974s
user	0m46.387s
sys	0m7.544s

seg@ubuntu:~/haskell-training$ time ./sorttest_jhc
"[20000]"
real	0m57.992s
user	0m56.904s
sys	0m0.396s

以下はプロファイラを使用して簡単に挙動を見た結果です。

■ GHC
デフォルトではGCの呼び出し回数が10000回程度に達していました。
別途ヒープ使用量を見てみたのですが、1MB程度で安定して動作していました。

プロファイラの表示画像を見るとわかりやすいですが、GCの動作時間がかなり長いことがわかります。

f:id:dec9ue:20121223102629p:plain

もう少しメモリ使用量が増えることを許容してもGCの実行頻度を落としたほうがよさそうだなぁ。。。

■ JHC

デフォルトではGCの呼び出し回数が1300回程度でした。
一方で、メモリ使用量が時間とともに増加し、最終的に2MB程度まで達しました。

コードに少し手を入れてGCの動作時間を見てみましたが、全体の比率から言うと1割に達しない程度かなと思われました。

まとめ

Haskellのような遅延評価型の言語ではヒープに配置されるデータが多く、それらが評価が進むだけでゴミになるので、コピーGCの方が圧倒的に有利だと私は思っているのですが、、、
今回、デフォルト状態で動かした様子だけでは機構による差異よりも動かしたいプログラムの挙動とGCの呼び出し頻度のミスマッチの方が簡単に深刻な問題を呼んでしまうのかな、という印象を受けました。

ということで、実際の現場ではGCの実装を云々議論するより、パラメーターを調整してみるというトライが非常に重要だということかなと。出来ればこういうのをある程度簡単に調整してくれるしくみがあると嬉しいなぁ。

追記

サンプルコードの中でlastを使うとJHCでうまく動かなかったですね。。。なんでだろう。。。dropとか使ってしまいました。