hash

Berkeley DB で、バージョンが変わると速度にどの様な変化が出るんだろう？ FreeBSD 13.1(i386)で、確認してみる。5.3版は自前でコンパイルしたんで、 下記のようにして準備した。スレッドが有効になってるんですねぇ。

cc big5.c -I/home/sakae/MINE/include -L/home/sakae/MINE/lib -ldb -dl -lthr

結果はgnuplotでグラフにした。

set terminal svg
set output "btree.svg"
set title "BDB5.3"
plot "btree.log" using 1:2 w l, "btree.log" using 1:4 w l

100万個のキー/データを登録。それぞれ1万個単位で、登録に要した時間(秒)をY軸 にした。

Berkeley DB 1.85

Berkeley DB 5.3

5.3の方が遅いな。きっと機能が増えた分、余計な事をやっているのでしょう。 それよりハッシュの波うちが気になる。何でかな？ (hxx.logはハッシュDB, bxx.logは B木によるDB)

少し深く潜ってみるか。

#0  __addel (hashp=0x6c175800, bufp=0x6c14f160, key=0xcf7d07b4, val=0xcf7d07ac) at /usr/src/lib/libc/db/hash/hash_page.c:441
#1  0x0c91760a in hash_access (hashp=<optimized out>, action=<optimized out>, key=0xcf7d07b4, val=0xcf7d07ac) at /usr/src/lib/libc/db/hash/hash.c:636
#2  0x0c916bb6 in hash_put (dbp=0x6c16f940, key=0xcf7d07b4, data=0xcf7d07ac, flag=0) at /usr/src/lib/libc/db/hash/hash.c:532
#3  0x1a49c8c2 in reg_kv (mykey=0x1a49b3b0 "HACKING") at mydb.c:19
#4  0x1a49c98a in main () at mydb.c:26

キー、データ登録ルーチンの最後の所。

/*
 * If the average number of keys per bucket exceeds the fill factor,
 * expand the table.
 */
hashp->NKEYS++;
if (do_expand ||
    (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
        return (__expand_table(hashp));
return (0);

テーブル拡張時の状態。テーブルに占めるキーの数が増加すると、テーブルが 拡張される。その為に大量のデータ移動が裏で実行されるんだな。

(gdb) p (*hashp)->hdr
    max_bucket = 1,
    ffactor = 399,
    nkeys = 756,     ;; keyの登録数
     :
    max_bucket = 37, ;; expand_tableが呼ばれる度に +1 される。
    ffactor = 399,
    nkeys = 13222,

ふと、rubyやschemeでsymbolの扱いがどうなってるか気になった。

irb(main):001:0> a = {}
irb(main):003:0> a["hoge"] = 123
=> 123
irb(main):005:0> a[:foo] = 2
=> 2
irb(main):006:0> a
=> {"hoge"=>123, :foo=>2}

gosh$ (define a (make-hash-table))
gosh$ (hash-table-put! a "hoge" 123)
gosh$ (hash-table-put! a 'foo 2)
gosh$ (hash-table-map a (lambda (k v) (vector k v)))
(#(foo 2) #("hoge" 123))

pythonはどうかなとググッてみたら、 symbol — Python 解析木と共に使われる定数 こんなのが申し訳程度に出てきて、

代表的な例として、やってみる。方式は前回のバークレーDBと同じように、 100万件のキーとデータの登録時間。データは、キーを反転したものにした。

(use srfi-13)   ;; string-reverse
(use srfi-19)   ;; time

(define a (make-hash-table))
(define st (current-time))
(define sp (current-time))
(define dif (time-difference sp st))

(with-input-from-file "./SEED"
  (lambda ()
    (generator-fold (lambda (key cnt)
                      (when (= 0 (mod cnt 10000))
                        (set! sp (current-time))
                        (set! dif (time-difference sp st))
                        (set! st sp)
                        ;;(format #t "~7d ~a\n" cnt dif)
                        (format #t "~7d ~a.~a\n"
                                cnt
                                (time-second dif)
                                (time-nanosecond dif)))
                      (hash-table-put! a  key (string-reverse key))
                      (+ cnt 1))
                    1
                    read-line)))

久ぶりなんでGauche本を参照。それで不足してる情報はinfoのCとSchemeの関数の対応 のセクションを参照して、scheme言語に変換した。

10000 #<time-duration 0.163062000>
20000 #<time-duration 0.317233000>

時間の引き算が定義されてて、こんな風に型と共に表示される(コメントを外 すと確認できる)。秒とナノ秒でも取り出せるんで、それを合成した。

  10000 0.200341000
   :
 990000 3.415444000
1000000 2.359766000

結果は、上記のようになった。普通の世界だな。

gosh> (gc-stat)
((:total-heap-size 3346432) (:free-bytes 32768) (:bytes-since-gc 995440)
 (:total-bytes 4691248))
   :
((:total-heap-size 161304576) (:free-bytes 1929216) (:bytes-since-gc 1160200)
 (:total-bytes 340380240))

普通じゃないのは、裏でゴミ集めが行なわれる事。開始前と終了後の状態を確 認してみた。

ハッシュに対抗して、赤黒木によるものも実装されている。まるで、BDBな世 界だ。使い方は簡単で 、make-hash-table/hash-table-put!の部分を make-tree-map/tree-map-put!に変更するだけ。

gosh hash and tree-map

X軸の表示が渋滞して酷い事になっててスマソ。一目盛が10万。最右が100万と なってますんで、心眼で宜しく。

走っている最中に止めたら、gcしてた。いつもgcしてる。

(gdb) bt 12
#0  0x2072dd0b in GC_push_contents_hdr (current=0x2235efe0 "`a-\"@a-\"\220\260\034\"", <incomplete sequence \326>, mark_stack\
_top=<optimized out>, mark_stack_limit=0x20e28000, source=<optimized out>, hhdr=0x223d0f98, do_offset_check=1) at ./include/p\
rivate/gc_pmark.h:349
#1  0x2072a917 in GC_mark_from (mark_stack_top=0x2235efe0, mark_stack=0x20e20000, mark_stack_limit=0x20e28000) at extra/../ma\
rk.c:888
#2  0x20722e61 in GC_mark_some (cold_gc_frame=0xffbfe020 "P\340\277\377:\033r P\023r ") at extra/../mark.c:394
#3  0x207221fb in GC_stopped_mark (stop_func=0x20721350 <GC_never_stop_func>) at extra/../alloc.c:793
#4  0x20721b3a in GC_try_to_collect_inner (stop_func=0x20721350 <GC_never_stop_func>) at extra/../alloc.c:541
#5  0x20728771 in GC_grow_table (table=0x208eb240 <GC_fnlz_roots>, log_size_ptr=0x2086fdb8 <log_fo_table_size>, entries_ptr=0\
x208eb19c <GC_fo_entries>) at extra/../finalize.c:133
#6  0x2072a009 in GC_register_finalizer_inner (obj=0x224da4c8, fn=0x205cd330 <port_finalize>, cd=0x0, ofn=0xffbfe110, ocd=0xf\
fbfe114, mp=0x20729ea0 <GC_null_finalize_mark_proc>) at extra/../finalize.c:707
#7  0x2072806b in GC_register_finalizer_no_order (obj=0x224da4c8, fn=0x205cd330 <port_finalize>, cd=0x0, ofn=0xffbfe110, ocd=\
0xffbfe114) at extra/../finalize.c:848
#8  0x205782e9 in Scm_RegisterFinalizer (z=0x224da4c8, finalizer=0x205cd330 <port_finalize>, data=0x0) at core.c:326
#9  0x205c5b3b in make_port (klass=<optimized out>, name=<optimized out>, dir=2, type=2) at port.c:222
#10 0x205cc2b3 in Scm_MakeOutputStringPortFull (name=0x2075ec2c <scm.sc+2408>, flags=0) at port.c:1505
#11 0x2068990c in libioopen_output_string (SCM_FP=0x20e44284, SCM_ARGCNT=1, data_=0x0) at libio.scm:394
(More stack frames follow...)

しょうがないので、ハッシュのテーブルを拡張する所にBPを設置。

(gdb) b hash.c:573
Breakpoint 1 at 0x205c0e9c: file hash.c, line 573.
(gdb) c
Continuing.

Breakpoint 1, insert_entry (table=<optimized out>, key=<optimized out>, hashval\
=1523131600, index=32665) at hash.c:573
573             int newsize = (table->numBuckets << EXTEND_BITS);
(gdb) bt
#0  insert_entry (table=<optimized out>, key=<optimized out>, hashval=1523131600, index=32665) at hash.c:573
#1  0x205beff8 in address_access (table=0x21000eb8, key=582397568, op=SCM_DICT_CREATE) at hash.c:650
#2  0x205bfe4c in Scm_HashCoreSearch (table=0x30000, op=(unknown: 0x30000), key=<optimized out>) at hash.c:894
#3  Scm_HashTableSet (ht=0x21000eb0, key=0x22b6ae80, value=0x22b6ae60, flags=0) at hash.c:1002
#4  0x2066b320 in libdicthash_table_putX (SCM_FP=0x20e4420c, SCM_ARGCNT=3, data_=0x0) at libdict.scm:283
#5  0x20580bf9 in run_loop () at ././vmcall.c:192
#6  0x2057a08d in user_eval_inner (program=<optimized out>, codevec=0xffbfe87c) at vm.c:1572
#7  0x2057aaf7 in apply_rec (vm=<optimized out>, proc=<optimized out>, nargs=<optimized out>) at vm.c:1691
#8  Scm_ApplyRec (proc=0x20ea98d0, args=<optimized out>) at vm.c:1711
#9  0x20601221 in Scm_Load (cpath=0x20ef3640 "./hash.scm", flags=20, packet=0xffbfe97c) at load.c:231
#10 0x00405a73 in execute_script (scriptfile=0x20ef3640 "./hash.scm", args=0x20fbc290) at main.c:684
#11 0x004064a9 in main (ac=2, av=0xffbfeb24) at main.c:895

こんな回数で、拡張が行わてていた。

190000 0.612608000
 :
780000 2.611347000

goshばかりではなくて、Chez Schemeも持ってる事を思い出した。 ファイルから種を読み出すのが面倒だったので、shellの命令seqを埋めこんで みた(seq -f q%.6fp 0 0.000997 1000)。また、string-reverseも不足してたんで手抜きしてる。

(define a (make-hash-table))
(define st (current-time))
(define sp (current-time))
(define dif (time-difference sp st))

(let loop ((seq 0.0)
           (cnt 1))
  (when (< seq 1000.0)
    (when (= 0 (mod cnt 10000))
      (set! sp (current-time))
      (set! dif (time-difference sp st))
      (set! st sp)
      (format #t "~7d ~a.~a\n"
              cnt
              (time-second dif)
              (time-nanosecond dif)))
    (hashtable-set! a (format #f "q~ap" seq) cnt)
    (loop (+ seq 0.000997) (+ cnt 1))))

(exit)

Chez Scheme hashtable

やっぱりガツンとごみ収集が実施されてますなあ。Lisp/Schemeの宿命か。

詳しい事は、Section 7.12. Hashtables

cnt = 1
a = {}
st = Time.now()

File.foreach("./SEED") do |line|
    key = line.chomp()
    if (cnt % 10000 == 0) then
         sp = Time.now()
         printf("%7d %f\n", cnt, sp - st)
         st = sp
    end
    cnt += 1
    a[key] = key.reverse()
end

Ruby hash speed

結構、山が有るな。まあ、大量のデータですからね。無理もないか。

次はpythonでハッシュもとえ辞書のスピード試験。

import time

cnt = 1
a = {}
st = time.time()
with open('./SEED') as f:
    while(True):
        line = f.readline().rstrip()
        if(not line):
            break
        if cnt % 10000 == 0 :
            sp = time.time()
            print(cnt, sp - st )
            st = sp
        a[line] = line[::-1]      # reverse
        cnt = cnt + 1

Python dict speed

ごみ収集は、まとめてドンって言う方式じゃなくて、こまめにやるんで隠され ているんだな。一時的に遅くなるのは、辞書の拡張のせいか。

pythonでシンボルを検索すると、上にあげたものしかヒットせず。後は、 SymPyの類ばかり。maximaになりたいのか。

ときならぬschemeなんてのに触れてしまったおかげで、pythonでも、っぽく出 来るか調べてみた。

関数型プログラミングライブラリtoolzを使ってみた

こんなのがあるのね。しらんかったぞ。