2013/10/28

が、「mmapだと必ず速くなる」なんて迷信ですから！！！
これらの記事で紹介されているベンチマークで read が mmap よりも遅く見えるのは、非常に大きなバッファを確保しているから。正しいコードを書けば、シーケンシャルアクセスを行うケースにおいて read(2) が mmap(2) より大幅に遅いということは、まず起こらない。むしろ、read(2) のほうが mmap(2) よりも速くなるというケースも実際には多い。

以前、データベースを書いていた時にひっかかったのは、mmapは速いんだけど munmapに思わぬ時間がかかることがあるってこと。1～2年前のLinuxでの話。

クエリエンジンが数GB～数10GBのデータファイルをいくつもread-onlyのmap_sharedでmmapしてて、別プロセスがデータファイルを追記更新したので読み直さないとならない、って場合で、ディスクI/Oが静かなのにクエリが数秒とかのオーダーでつっかえることがある。読み直しに時間かかってるなら別だけどそのページは既にバッファに入ってるはずで (別のプロセスが先行してマッピングしてる)、どこでつっかえてるのか調べていったらmunmapだった。カーネル内部で何かが競合してるのかとも思ったけど深くは追求してない。その時は、mremapを使えば時間がかからないことがわかったのでそれで回避した。

この例に限らず、リソースの確保を速くしたはいいが解放に思わぬ時間がかかることがあるってのはちょくちょくある落とし穴かも。

Tag: Programming

Comments (0)

2013/10/03

#permalink

bitset

Gaucheプログラミングの小ネタ。

小さい非負整数の集合同士のintersectionを高速に計算しないとならない用事が出来た。例えば (0 1 4 7 9) と (2 3 7 8 9 16) から (7 9) を求める、といった話。データは100万個のオーダー。整数値の範囲は今のところ最大でも50くらい、今後増えることはありえるがそう極端に大きくはならない。

こういう話なら、整数の集合をビット集合に変換してビット毎のandを取るのが素直だろう。

整数値のリストからビット集合への変換はfoldですぐできる。

(define (integer-list->bitset ints)
  (fold (cut copy-bit <> <> #t) 0 ints)))

gosh> (integer-list->bitset '(0 3 4 9 15))
33305

ビット集合からリストに戻す方はどうだろう。srfi-60のinteger->listを使うと整数の各ビットをbooleanにしたリストが得られるが、右から0,1,2,...と数えないとならないので一旦reverseするのがちと煩わしい。

(define (bitset->integer-list bits)
  (filter-map (^[b n] (and b n)) 
              (reverse (integer->list bits))
              (lrange 0)))

gosh> (bitset->integer-list 33305)
(0 3 4 9 15)

gauche.genreator には整数を真偽値のジェネレータに変換する手続きがある。 bits->generatorは右からビットを取り出すのでそのまま使えるけど、ジェネレータをリストに変換してやらないとならない。

(define (bitset->integer-list2 bits)
  (filter-map (^[b n] (and b n))
              (generator->list (bits->generator bits))
              (lrange 0)))

あるいは、ジェネレータのまま変換していって最後にリストに戻すか。

(define (bitset->integer-list3 bits)
  (generator->list
   (gfilter-map (^[b n] (and b n))
                (bits->generator bits)
                (grange 0))))

結果を整数の集合と考えるなら数値の順序はどうでも良いはずだ。それならば、先に最大ビット番号を求めておいて、そこから逆順に畳み込む手もある。そしたらinteger->list の結果をそのまま使える。ただ、逆順の整数リストを作るのがちと煩わしい。

(define (bitset->integer-list4 bits)
  (let1 len (integer-length bits)
    (filter-map (^[b n] (and b n))
                (integer->list bits)
                (iota len (- len 1) -1))))

gosh> (bitset->integer-list4 33305)
(15 9 4 3 0)

さてどれが速いだろうか。適当にランダムデータを生成してベンチマーク。

(use data.random)
(use gauche.time)

(let1 testdata (generator->list (integers$ (expt 2 50)) 100000)
  ($ time-these/report 1
     `((srfi-60 . ,(^[] (for-each bitset->integer-list testdata)))
       (gen1    . ,(^[] (for-each bitset->integer-list2 testdata)))
       (gen2    . ,(^[] (for-each bitset->integer-list3 testdata)))
       (rev     . ,(^[] (for-each bitset->integer-list4 testdata))))))

結果:

Benchmark: ran srfi-60, gen1, gen2, rev, each for 1 times.
  srfi-60: 4.384 real, 4.380 cpu (4.370 user + 0.010 sys)@0.23/s n=1
     gen1: 3.865 real, 3.860 cpu (3.860 user + 0.000 sys)@0.26/s n=1
     gen2: 5.648 real, 5.650 cpu (5.650 user + 0.000 sys)@0.18/s n=1
      rev: 3.510 real, 3.510 cpu (3.510 user + 0.000 sys)@0.28/s n=1

          Rate srfi-60  gen1  gen2   rev
  srfi-60  0/s      -- 0.881 1.290 0.801
     gen1  0/s   1.135    -- 1.464 0.909
     gen2  0/s   0.775 0.683    -- 0.621
      rev  0/s   1.248 1.100 1.610    --

data.random は新しいモジュールで、ランダムデータの生成ツールが色々揃っている。integer$ は0から与えられた数までの間の整数値を一様分布で生成するジェネレータを作る関数。ここでは条件を揃えるために一旦リストに直して各関数に与えた。

最後のやつは、lrange で降順のシーケンスが作れないので iotaを使うためにちょっとごちゃっとしたんだけど、lrangeで降順のシーケンスを作れないようにしたのは何でだったかな? 何か理由があって意識的にそうした覚えがあるんだけど…

Tags: Programming, Gauche

Comments (0)

2013/09/30

#permalink

ピアノレッスン108回目

Kapustin: Concerto Etude Op40-1
- 暗譜した。八分音符=112。
Ravel: Ondine
- LAにいた頃に暗譜して通せるくらいまでやったんだけど、改めて挑戦。細かい音符をすっかり忘れてる。今回はペルルミュテール校訂の楽譜があるので指使いなど参考にしながら読譜から。今回はゆっくり最初の3ページ。

さてここから2週間ほど追い込みなので、レッスンも休むことになりそう。

Tag: Piano

Comments (0)

More entries ...

Island Life

About

最近のエントリ

最近のコメント

最近のリリース

書いたり訳したりした本

2013/10/28

どっち?

2013/10/23

Science terms

2013/10/10

mmap

2013/10/03

bitset

2013/09/30

ピアノレッスン108回目