"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とか使ってしまいました。

GHCソースコードリーディング勉強会 第1回 行ってきた

第0回に続いて、
GHCソースコードリーディング勉強会 第1回 #readghc に行ってきた。

というか発表しました。

発表資料:
GCをみればRTSが見えてくる、かも。。。

まー、ちょっと読み込み不足なところもあって、メンバー見たらかなりこわい人達だったので、これは殺される!って思ったんだけど、予想通りやさしく殺していただきました。

いちおー、下記のような質問がこたえられなかったんで、これはおいおい調べておきたいと思います。

  1. nurseryとgeneration 0は同じ?(いちおう、Commentaryのここによると、nurseryからgen 0へコピーする、といった記述があって、まるでnurseryという明示的な領域があるように書いてあるが、、、)
  2. Promotionの前にAgingをやっているはずなのだが、相当するコードが見当たらない。

自分のほか、3名の方が発表されていました。


@nothingcosmosさん
飛び込みLTスゲー。GHCのLLVMへの対応について。LLVMに対応するためにあの手この手使ってるサマがよくわかりました。。。というか、RTSの型超越的自由奔放実装はやはり良くないのでは?と思ってしまいました。

@khibinoさん
Core最適化処理を追加する!GHCのterm re-writingの処理を実装されてて面白かった。ツリー変換ぐらいまでならHaskellでサクッと(とは行かないかもだが)書けちゃうのはGHCの一つの魅力かなと思いました。

@master_qさん
gdbデバッグCommentary GeneratedCode (I know kung fu)の解説。20分で話しきれるわけもなく速すぎてわからんかったわ。

最後に、当初の時間余りの見込みをはるかに通り越してハーフウェイギリギリまでやっちゃってすいませんでした。みんなmaster_q師匠のkung-fu聞きたかったに違いない。。。

STG祭りとCapabilityまわりの挙動について今後期待します。

Low Layer楽しいよ!

        • -

懇親会ではsherarcyさんに並列処理(Par Monad)教えてもらったんで、近々にSMPコードを書きたい。

        • -

資料を追記(2012/10/01)
議事録: HaskellJP wiki - Workshop/ReadGHC/1
http://wiki.haskell.jp/Workshop/ReadGHC/1

readghc 第一回 - Togetter
http://togetter.com/li/381712

Miller-Rabin法で擬素数を探す

Miller-Rabbin法による擬素数探索をHaskellで書いてみた。

感想
1. 多倍長計算を気にせずできるInteger型素晴らしい!
2. とりあえず乱択のパラメーターを乱数にしているけど、IOモナド破壊しても大して困らなそうなので破壊したいと思います。

改善点
1. 実際に暗号などの目的で素数探索を使うとなると、HaskellのStdGenの乱数は暗号的にはちょっと信用ならないので乱数自体は改善する必要がある。Miller-Rabinの方のテスターは別にいいと思うのですが、素数探索の開始点は十分品質の良い暗号的乱数を選ぶべし。
2. 速度を稼ぐのであれば、事前にエラトステネスのふるいを使ってある程度ふるい落としたほうが早いらしい。(そりゃそうか)
3. 並列化を睨むのであれば逐次処理であるfind_next_prime処理を並列に投機実行できるようにするのが望ましいが、この部分をもうちょっと抽象的に書けないか。
4. Miller Rabinテスト自体は乱択なのでIOを含むが、大したIOじゃないので破壊したい!

疑問点
1. 一旦余再帰で書いた関数を末尾再帰型にリファクタしたんですけど、これ、普通なんですかね。パフォーマンスとか比べてないけどやっぱりやるべきなんだろうか。
2. Haskellコードを美しく書くコツってなんですかね。。。。今時点での実装能力ではレイアウトにどうしても気が行ってしまってコードの読みやすさなどを考慮できていない気がします。

import System.Random

modexp m p n = modexp_sub m p n m 1
  where
    modexp_sub m p n c r
      | p == 0 = r
      | otherwise =
         let res = if ( p `mod` 2 == 1 ) then (c * r) `mod` n else r in
         modexp_sub m (p `div`2) n ((c * c)`mod` n) res

find_s_k r = find_s_k_sub (r-1) 1 1
  where
    find_s_k_sub r ss s
      | (r`div` ss) `mod` 2 == 1 = (s,r `div` ss)
      | otherwise = find_s_k_sub r (2*ss) (1+ s)

millerrabbintest r t =
  let (s,k) = find_s_k r in
  let rabbintest_sub j b' =
        if (b' == r-1)||(b' == 1)
        then True
        else
            if j < s
            then rabbintest_sub (j+1)((b'*b')`mod` r)
            else False
  in
  let rabbintest a k r = rabbintest_sub 0 $ modexp a k r in
  let millerrabbin_sub r t i =
        if (i > t )
        then
          do
            putChar '\n'
            return True
        else
          do
            a <- randomRIO ( 1, r-1)
            ires <- return $ rabbintest a k r
            putChar '+'
            case ires of
              False -> return False
              True -> millerrabbin_sub r t (i+1)
  in
  millerrabbin_sub r t 1

find_next_prime n =
  do
    res <- millerrabbintest n 10
      case res of
      True -> return n
      False -> find_next_prime (n + 1)

relative_prime p q
  | p == 0 || q == 0 = False
  | p == 1 || q == 1 = True
  | p > q = relative_prime q (p `mod` q)
  | otherwise = relative_prime p (q `mod` p)

find_prime keylen =
  let randomv = let min = 2 ^ (keylen - 1)
                    max = 2 * min
                in
                randomRIO ( min,max)
  in
  do
    v <- randomv
    find_next_prime v

書いてから下記のサイトにmiller rabinテストの実装があることに気づいた。。。ただ、他のサイトでもそうなのだけど、乱択の際にIOとかが混入しちゃうのを嫌って乱択のところを端折るのがセオリーみたいです。

http://www.haskell.org/haskellwiki/Testing_primality#Miller-Rabin_Primality_Test

         ∧_∧   ┌────────────
       ◯( ´∀` )◯ < 僕は、unsafePerformIOちゃん!
        \    /  └────────────
       _/ __ \_
      (_/   \_)
           lll

Euler 4 を Haskell で高速化してみたが、、、

下記のような記事があって、

HaskellとOCamlの速度を比較してみた - let start programming = fun life -> life * 100;;

キャミバ様とガリグ先生がOCamlでコードを戦わせていたようだったので、こりゃ勝てないと思ってHaskellで高速化をしてみた。
結果、ぼくのコードは10倍に膨れ上がってしまった。

改善の趣旨としては、この問題は最大値を求める問題なので、探索空間をおおよそ大きい方からのリストにして、最初に見つかった解に対して、明らかに小さくなってしまう部分を切り捨てる。という方針。

is_circle n =
    let is_circle_sub m n r = if m == 0
        then r == n
        else is_circle_sub (m `div` 10) n (r * 10 + m `mod` 10)
    in
    is_circle_sub n n 0

declist a b limit tail =
    if b <= a
    then (a,b):(declist (a-1) (b+1) limit tail )
    else tail

-- decendant list of pair (a,b) on value a + b
declist_rec a b limit  = declist a b limit $
    if(a + b > 2)
    then
        if (a+b-1) > limit
        then declist_rec limit (a + b -1 -limit) limit
        else declist_rec (a+b-2) 1 limit
    else []

mult_list        = map (\ (x,y) -> x * y) $ declist_rec 999 999 999
index_mult_list  = zip [1..] mult_list

main =
    let (index,first_sol) = head $ filter (is_circle.snd) index_mult_list
        root              = floor $ sqrt $ fromInteger first_sol
        search_limit      = (\x->x * x) $ (\x -> (999 - x +1)) $ root
    in
    do
        print $ maximum $ filter is_circle $ drop (index-1) $ take search_limit mult_list

これがhideshi_oさんのオリジナルのコード

--Haskell
import Data.List
main = do
  print $ last $ filter (\x -> (reverse $ show x) == show x) $ sort ([x * y | x <- [100..999], y <- [100..999]])

さて、実行結果は

オリジナルコード:

[seg@seg-PC ~/haskell-sample]$ time ./Euler0
906609
0.000u 0.046s 0:04.09 0.9%      0+0k 0+0io 1355pf+0w

今回アルゴリズム改善したコード:

[seg@seg-PC ~/haskell-sample]$ time ./Euler
906609
0.000u 0.031s 0:00.04 75.0%     0+0k 0+0io 1356pf+0w

爆速になった。100万要素リストのトラバースをしないのだから当然と言っては当然。実際に探索した空間は2300くらい。500倍の差がつかないのは他に余計な計算をたくさんしているせいか。あ、takeを使わないでリストをたぐるだけの関数書けば速くなりそうな気がしますね。

ただ、元のコードにあった簡潔さはもうみじんもないし、コード行数も実質15倍。トレードオフといえばそれまでだけどなんだかなぁ、という気分にもなる。

元の趣旨であったと思われる「簡潔で見やすいコードの速度を比べてみる」というところからは明らかに外れたコード修正でした。