Hash or B-Tree
Yasushi Shinjo
In article <uhdhak...@katsu.watanabe.name>
WATANABE Katsuhiro <ka...@watanabe.name> writes:
> > hash だと、rehash されちゃうと破綻します。最初にhashの
> > 大きさを指定できれば良いんですけどね。
> 今日 man して初めてわかったんですが、dbopen(3) インタフェース
> のうちの hash(3) 型データベースは、hash の大きさを初期設定
> できるみたいです。そして今の dbm は、もはや独立した実装では
> なく、dbopen/hash の wrapper になっているとわかりました。
私は、Berkeley DB で、なんとなく B 木ばかり使っています。ハッ
シュも使えるけど。B 木でも、400 万件くらい平気です。B木は、3
レベルかな。「普通は3レベルで足りでしょう」、みたいな話がド
キュメントに入っていたと思いました。
リハッシュって、そんなに重たいんですか。
B木には、リハッシュはないわけですが。
Berkeley DB は、データベースではないという世界もあるというこ
とで、Followup-To: fj.comp.programming としてみました。
＼＼ 新城 靖 （しんじょう やすし） ＼＼
＼＼ 筑波大学 電子・情報 ＼＼
Shinji KONO
In article <YAS.05Ma...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> 私は、Berkeley DB で、なんとなく B 木ばかり使っています。ハッ
> シュも使えるけど。B 木でも、400 万件くらい平気です。B木は、3
> レベルかな。「普通は3レベルで足りでしょう」、みたいな話がド
> キュメントに入っていたと思いました。
Bツリーも、偏ったデータのinsertが続くと破綻します。
> リハッシュって、そんなに重たいんですか。
> B木には、リハッシュはないわけですが。
rehash は、table をallocation して、全部hashし直して
元のtableをdeallocate するっていう手順ですよね。これは
重いです。メモリネックです。
Bツリーも、バランスし直すていう作業が必要なはずです。
でも、rehash よりは軽いです。
> Berkeley DB は、データベースではないという世界もあるというこ
> とで、Followup-To: fj.comp.programming としてみました。
サイボウズが、Berkeley DB と MySQL で MySQL を(ライセンスの関係で)
採用したなんて話が出てましたね。普通は、OODB の方がRDBより速い
ってのが普通なんだけどなぁ。実装がたこかったか?
---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科
Hideo Sir MaNMOS Morishita
ほとんどBerkleyDB使った事がないです。
In article <3991847...@rananim.ie.u-ryukyu.ac.jp>,
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。
>
> In article <YAS.05Ma...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> > 私は、Berkeley DB で、なんとなく B 木ばかり使っています。ハッ
> > シュも使えるけど。B 木でも、400 万件くらい平気です。B木は、3
> > レベルかな。「普通は3レベルで足りでしょう」、みたいな話がド
> > キュメントに入っていたと思いました。
>
> Bツリーも、偏ったデータのinsertが続くと破綻します。
B-Treeって、binary treeに対して偏ったinsertがあった時でも、各leafに対
する検索回数の最大値がlog2(n)を越えない様な改良ですよね。Berkley DBだ
けの問題ですか？
--
___ わしは、山吹色のかすてーらが大好きでのぅ
[[o o]] ふぉっふぉっふぉ
'J' 森下 お代官様 ＭａＮＭＯＳ 英夫＠ステラクラフト
PGP Finger = CD EA D5 A8 AD B2 FE 7D 02 74 87 52 7C B7 39 37
Yasushi Shinjo
In article <3991847...@rananim.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。
> Bツリーも、偏ったデータのinsertが続くと破綻します。
> Bツリーも、バランスし直すていう作業が必要なはずです。
> でも、rehash よりは軽いです。
片寄った insert が続く情況は、平均的には起きないし、アプリケー
ションによっては起きないし、そういう時には、B木がいいと言え
るのでしょうね。
昔書いた論文で、B木を使ったと書いたら、ハッシュが速いと突っ
込まれてボツになったんだけど。あの査読はひどかった。
B木使って悪いなら、Microsoft とか Apple に向って言って欲しい。
> rehash は、table をallocation して、全部hashし直して
> 元のtableをdeallocate するっていう手順ですよね。これは
> 重いです。メモリネックです。
ハッシュ表がメモリに入るかというと、、、入りそうではあります
ね。1000万件くらいなら。Berkeley DB で、メモリ中でやっている
かどうかは、わかりません。
> サイボウズが、Berkeley DB と MySQL で MySQL を(ライセンスの関係で)
> 採用したなんて話が出てましたね。普通は、OODB の方がRDBより速い
> ってのが普通なんだけどなぁ。実装がたこかったか?
Berkeley DB は、OODB ではなくて、単にハッシュ表が永続的になっ
たようなものです。キーは可変長のバイト列。dbm とか ndbm とか
そういう名前で入っていて、Perl で、tie したり、Ruby の DBM
なんかで使えます。
ハッシュ表で十分な時に、わざわざ SQL を使うのは、気乗りしま
せん。慣れると平気なのかもしれないけど。SQLite というのもあ
るみたいだし。誰か使った人いませんか。これって、サーバ立てな
いで SQL が使えるというものですよね。
Shinji KONO
In article <YAS.05Ma...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> 昔書いた論文で、B木を使ったと書いたら、ハッシュが速いと突っ
> 込まれてボツになったんだけど。あの査読はひどかった。
> B木使って悪いなら、Microsoft とか Apple に向って言って欲しい。
(僕じゃないぞ...) ファイルシステムでハッシュはないですよね。
拡張性ないもの。
> ハッシュ表がメモリに入るかというと、、、入りそうではあります
> ね。1000万件くらいなら。Berkeley DB で、メモリ中でやっている
> かどうかは、わかりません。
INN のヒストリが500MB越えてて「メモリに入らない」ってのを
実際にくらいました。
> Berkeley DB は、OODB ではなくて、単にハッシュ表が永続的になっ
> たようなものです。キーは可変長のバイト列。dbm とか ndbm とか
> そういう名前で入っていて、Perl で、tie したり、Ruby の DBM
> なんかで使えます。
サイボウズは独自OODBを持っていたらしいんですよね。どうせ
捨てるなら Open Source にすれば良いのに。
> ハッシュ表で十分な時に、わざわざ SQL を使うのは、気乗りしま
> せん。
一つは、SQL 自体がダサイからだよな。Datalog 復活! なんてこと
になるわけもなく...
Yasushi Shinjo
In article <3991867...@rananim.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> (僕じゃないぞ...) ファイルシステムでハッシュはないですよね。
> 拡張性ないもの。
別にそんなにこだわりはなかったんだけど。そこは突っ込む所じゃ
ないとだろうと言いたい。
> INN のヒストリが500MB越えてて「メモリに入らない」ってのを
> 実際にくらいました。
本当にハッシュ表のリハッシュの時に全部メモリに入れるんですか。
１ブロックごとに read, write でもできますよね。
mmap() してやっていて、局所性がなくて仮想記憶が非命を上げたっ
てことですか。
> サイボウズは独自OODBを持っていたらしいんですよね。どうせ
> 捨てるなら Open Source にすれば良いのに。
そのうち気が変って OODB に戻ってくるかもしれませんよ。
Open Source の OODB って、何がいいでしょうか。
WATANABE Katsuhiro
ごめんなさい。少し勉強して出直してきました。
dbm や gdbm や Berkeley DB など、永続性を備えた hash 表
(external hashing)の性能に関して、データ数が多い(>10^6)
領域での話です。
記事 <3991827...@rananim.ie.u-ryukyu.ac.jp> で
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) さんいはく
> hash だと、rehash されちゃうと破綻します。最初にhashの
> 大きさを指定できれば良いんですけどね。
今の dbm ファミリでは、破綻というほど酷いことにはなりません。
実は、rehash で天地創造的に表を作り直すような実装は廃れて
しまっています。一部分を split（分割・詳細化)することで
徐々に表を広げていく実装の方が一般的です。
記事 <3991847...@rananim.ie.u-ryukyu.ac.jp> で
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) さんいはく
> rehash は、table をallocation して、全部hashし直して
> 元のtableをdeallocate するっていう手順ですよね。これは
> 重いです。メモリネックです。
初期の dbm や ndbm はそうでした [XMLDB] [SDBM]。しかし、
sdbm 以降、現在の gdbm や Berkeley DB の hash では、
そうした手順はとりません。これらは、表の部分的な拡張に
備えた Dynamic hashing という類のアルゴリズムを採用して
います。いっときに集中して全体を hash しなおすのは
避けるように考えてあります。
Dynamic hashing には何種類かあるのですが、それらを
dbm ファミリのデザインと対応付けて示すと、以下のように
なります。
sdbm : 狭義の Dynamic hashing [DYNAMIC]
gdbm : Extendible hashing [INDEX]
Berkeley DB : Linear hashing [INDEX]
なお、Linear hashing には興味深い別名があって、
Incremental hashing とも呼ばれます。
多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket
を "split" することで行います。address 範囲が増える分は、
hash 関数自体は変えず addressing に用いる bit 数を増やして
対応します。最初は LSB 4bit を使い、混んできたら 5bit を
使うという具合です。今まで 1101 の bucket に入っていた
データは、01101 と 11101 の bucket へと split して振り分け
られます。
Dynamic hashing では、split は表の一部に留めて楽をします。
すると bucket の粒度が一様になりませんが、それでも hash 値
からの addressing が困難にならないためには bucket をどう
整列したらよいのでしょう？ここがバリエーションになります。
狭義 Dynamic は trie 辞書、Extensible は一段階の間接表、
Linear では表中で split を進める順番をあらかじめ都合よく
固定しておくことで解決しています。詳細は参考文献をどうぞ。
参考文献
[XMLDB]
"Open Source XML Database Toolkit"
Liam R. E. Quin
ISBN 0-471-37522-5
http://www.holoweb.net/~liam/xmldb/
から、Chapter 12: Dynamic Hashing: dbm の中の
"How ndbm Works" の節の中の要点：
XMLDB> hash 値の下位の数ビットを pair 保存用ブロックの
XMLDB> アドレスとする。ブロック内に pair を追加する余裕が
XMLDB> なければ、用いる下位ビット数を +1 して表を広げる。
XMLDB> これは非常に遅い。なぜなら key を全部調べ、新しい
XMLDB> ブロックへデータを移動しなければならないから。
上の引用の原文は以下の URL で参照することができる。
http://www.holoweb.net/~liam/ftp/xmldb/p3-nonrelational/p3-ch12-dynamic-hashing.doc
ただし Word 形式のファイルが読めない人は、代替として
Google に変換をお願いすることができる。
http://www.google.com/search?q=cache:L-6784SYbWUJ:www.holoweb.net/~liam/ftp/xmldb/p3-nonrelational/p3-ch12-dynamic-hashing.doc&hl=ja
[SDBM]
"sdbm - Substitute DBM or Berkeley ndbm for Every UN*X
Made Simple"
Ozan (oz) Yigit
http://search.cpan.org/src/NWCLARK/perl-5.8.7/ext/SDBM_File/sdbm/README
要点1:
SDBM> dbm, ndbm は、insert の時に空きがないとデータの
SDBM> ページ群を split しようとして帰ってこなくなる
SDBM> ことがある。sdbm では worst case に対する備えが
SDBM> してあって、そのようなことは起きない。
要点2:
SDBM> 3つのアルゴリズム(Dynamic, Linear, Extensible)
SDBM> をプロトタイプし、sdbm では Larson の記事にある
SDBM> "Dynamic Hashing" を採用した。
[INDEX]
"Database Management Systems"
Raghu Ramakrishnan and Johannes Gehrke
ISBN: 0-07-246563-8
http://www.cs.wisc.edu/~dbbook/
から、この本に付随する Lecture 用スライド
"Hash-Based Indexes"
http://www.cs.wisc.edu/~dbbook/openAccess/thirdEdition/slides/slides3ed-english/Ch11_Hash_Index.pdf
は Linear hashing と Extendible hasing をわかりやすく
説明している。
[DYNAMIC]
"Dynamic Hashing"
Course materials for COMP201 class
Victoria Univ. of Welington
Mengjie Zhang
http://www.mcs.vuw.ac.nz/courses/COMP201/2004T1/Handouts/LectureNotes/part2-lec06.pdf
http://www.mcs.vuw.ac.nz/courses/COMP201/2004T1/Handouts/LectureNotes/part2-lec07.pdf
狭義の Dynamic hashing では、hash 表を trie 辞書で
管理している。表に混んできた部分が出たら、そこで trie
の枝を分岐させればよい。
--
渡邊克宏 http://katsu.watanabe.name
WATANABE Katsuhiro
私 WATANABE Katsuhiro <ka...@watanabe.name> いはく
> > hash だと、rehash されちゃうと破綻します。最初にhashの
> > 大きさを指定できれば良いんですけどね。
>
>
> 実は、rehash で天地創造的に表を作り直すような実装は廃れて
> しまっています。
現実の実験例をひとつ出してみます。
key 数を横軸とし、insert にかかる累積時間を縦軸として
グラフを描いてみました。記事の最後に添付した shar archive
を展開し、make graph して time.png をご覧あれ。
グラフでは、[階段]状に急に遅くなっている部分は見られません。
これは、平均性能（＝多数の insert の累積時間）を重視する
タイプの応用なら、問題は小さいことを意味しています。
対比して、key 数が大きくなるにつれグラフの[傾斜]すなわち
１回１回の insert の性能が悪化します。これは、rehash の
ような全域的再計算によるものではないにもかかわらず、
破綻というのにふさわしい状況(傾きが急になる一方)です。
このとき、loadavg は下がり、ページングではない種類の
ディスクアクセスばかりをやる状況になっていました。
しかし、この性能悪化の本質を私は絞れていません。
別途 insert １回毎の時間の最大値も監視してみています。
遅い回というのは間歇的にやってくるのですが、それも
Berkeley DB では1～2秒、gdbm だと 2～3秒でした
(Pentium 1GHz)。応用によっては許せる範囲でしょう。
--------
グラフ上の FAIL の部分は、Berkeley DB が insert に失敗した
ことを示してます。これは、あふれたデータを救い上げるための
overflow bucket というものが、さらにあふれてしまう現象の
ようです。添付のグラフでは長大なデータで加速されて問題が
現れましたが、小さなデータでも数百万件で再現できます。
なお、(仮想)記憶空間の状態とは無関係に起きる現象です。
注：
この記事でいう Berkeley DB は、FreeBSD や NetBSD の
libc のものです。4.4BSD-Lite に含まれていたものの子孫で、
最近はあまり保守されてないように見えます。バージョン4系列
(sleepycat が保守していて Linux のディストリビューション
でよく見るもの)は現在も進化中で、状況が違うかもしれません。
--
渡邊克宏 http://katsu.watanabe.name
# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# Makefile
# makegdbm
# makegdbm.c
# makendbm
# makendbm.c
# plotsize.sh
# plottime.sh
# v1.gdbm.time
# v1.ndbm.time
# v1024.gdbm.time
# v1024.ndbm.time
# v128.gdbm.time
# v128.ndbm.time
#
echo x - Makefile
sed 's/^X//' >Makefile << 'END-of-Makefile'
X#
X# Graph
X#
Xgraph: time.png size.png
X
X
Xtime.png: v1.ndbm.time v128.ndbm.time v1024.ndbm.time v1.gdbm.time v128.gdbm.time v1024.gdbm.time
X sh plottime.sh | gnuplot
X
Xsize.png: v1.ndbm.time v128.ndbm.time v1024.ndbm.time v1.gdbm.time v128.gdbm.time v1024.gdbm.time
X sh plotsize.sh | gnuplot
X
X#
X# Statistics
X#
XPAIRLIMIT=1015808
X
Xv16=0123456789abcdef
Xv32=$(v16)$(v16)
Xv64=$(v32)$(v32)
Xv128=$(v64)$(v64)
Xv256=$(v128)$(v128)
Xv512=$(v256)$(v256)
Xv1024=$(v512)$(v512)
X
Xv1.ndbm.time: makendbm
X yes | head -$(PAIRLIMIT) | cat -n | \
X ./makendbm v1.ndbm | \
X tee $@
X
Xv128.ndbm.time: makendbm
X yes $(v128) | head -$(PAIRLIMIT) | cat -n | \
X ./makendbm v128.ndbm | \
X tee $@
X
Xv1024.ndbm.time: makendbm
X yes $(v1024) | head -$(PAIRLIMIT) | cat -n | \
X ./makendbm v1024.ndbm | \
X tee $@
X
Xv1.gdbm.time: makegdbm
X yes | head -$(PAIRLIMIT) | cat -n | \
X ./makegdbm v1.gdbm | \
X tee $@
X
Xv128.gdbm.time: makegdbm
X yes $(v128) | head -$(PAIRLIMIT) | cat -n | \
X ./makegdbm v128.gdbm | \
X tee $@
X
Xv1024.gdbm.time: makegdbm
X yes $(v1024) | head -$(PAIRLIMIT) | cat -n | \
X ./makegdbm v1024.gdbm | \
X tee $@
X
X#
X# Commands
X#
XCFLAGS= -I /usr/local/include -L /usr/local/lib
XLDFLAGS= -lgdbm
X
Xmakegdbm:
X
X
Xmakendbm:
X
X#
X#
X#
Xclean:
X -rm -f compare.png v*.ndbm.time v*.gdbm.time v*.ndbm v*.gdbm
END-of-Makefile
echo x - makegdbm
sed 's/^X//' >makegdbm << 'END-of-makegdbm'
X#!/bin/sh
Xecho "I am dummy."
Xecho "Remove me and make makegdbm from the source."
END-of-makegdbm
echo x - makegdbm.c
sed 's/^X//' >makegdbm.c << 'END-of-makegdbm.c'
X/*
X Register key value pairs in text database into gdbm database.
X $Id: makegdbm.c,v 1.1 2003/11/25 23:14:05 katsu Exp $
X
X See peformance comment at the end.
X*/
X
X#define MAX_LINE_LENGTH 4096
X
X
X#include <stdlib.h>
X#include <stdio.h>
X#include <string.h>
X#include <gdbm.h>
X#include <time.h>
X#include <errno.h>
X#include <sys/types.h>
X#include <sys/stat.h>
X
Xstatic int keycount;
Xstatic char *gdbmdb_name;
X
Xvoid atput(GDBM_FILE gdbmdb, char keystring[], char valuestring[])
X{
X int duplicate;
X datum key, value;
X
X key.dptr = keystring;
X key.dsize = strlen(keystring);
X value.dptr = valuestring;
X value.dsize = strlen(valuestring);
X duplicate = gdbm_store(gdbmdb, key, value, GDBM_INSERT);
X if (duplicate < 0) {
X fprintf(stderr, "Cannot store data at %d-th key.\n",
X keycount + 1);
X perror(NULL);
X gdbm_close(gdbmdb);
X exit(1);
X }
X/*
X if (duplicate) {
X fprintf(stderr,
X "Duplicated key: %s\n",
X keystring);
X }
X*/
X}
X
Xlong long filesize(char *path)
X{
X struct stat filestatus;
X
X if (stat(path, &filestatus) < 0) {
X return (-1);
X }
X return ((long long)filestatus.st_size);
X}
X
Xint main(int argc, char** argv)
X{
X GDBM_FILE gdbmdb;
X char textbuf[MAX_LINE_LENGTH];
X char key[MAX_LINE_LENGTH];
X char value[MAX_LINE_LENGTH];
X double elapsed;
X time_t starttime;
X
X if (argc != 2) {
X fprintf(stderr, "Usage: %s output_gdbm\n", argv[0]);
X exit(1);
X }
X gdbmdb_name = argv[1];
X if (!(gdbmdb = gdbm_open(gdbmdb_name, 0, GDBM_NEWDB, 0644, 0))) {
X fprintf(stderr, "Cannot open %s\n", gdbmdb_name);
X exit(1);
X }
X keycount = 0;
X starttime = time(NULL);
X while (fgets(textbuf, sizeof(textbuf), stdin)) {
X if (sscanf(textbuf, "%s %s", key, value) < 2) {
X fprintf(stderr, "Cannot scan text db correctly.\n");
X exit(1);
X }
X atput(gdbmdb, key, value);
X keycount++;
X if (keycount % 16384 == 0) {
X elapsed = difftime(time(NULL), starttime);
X /*
X If you wanted accurate filesize, you would
X flush buffers. But you may care more about
X accuracy of time statistics.
X */
X /*
X gdbm_sync(gdbmdb);
X */
X printf("keys: %d elapsed: %f filesize: %lld\n",
X keycount, elapsed, filesize(gdbmdb_name));
X fflush(stdout);
X }
X }
X if (ferror(stdin)) {
X fprintf(stderr, "Cannot read input\n");
X }
X gdbm_close(gdbmdb);
X exit(0);
X}
X
X
X/*
XPerformance:
X
X(1) Printing 'Duplicated key' message to the stderr make it slower
Xvery much.
X
X(2) It doesn't scales in terms of the number of keys.
XAs an example, the following list is the number of keys
Xprocessed and the elapsed time on wharf, using full list
Xof jaist and ancientfj.
X
Xkatsu@wharf$ nice -n 20 /var/tmp/makegdbm mid2fn-full.gdbm < mid2fn.txt
X16384 1.000000
X32768 6.000000
X49152 19.000000
X65536 43.000000
X81920 68.000000
X98304 98.000000
X114688 129.000000
X131072 161.000000
X147456 188.000000
X163840 220.000000
X180224 255.000000
X196608 296.000000
X212992 336.000000
X229376 378.000000
X245760 419.000000
X262144 459.000000
X278528 506.000000
X294912 550.000000
X311296 589.000000
X327680 637.000000
X344064 685.000000
X360448 735.000000
X376832 788.000000
X393216 842.000000
X409600 897.000000
X425984 949.000000
X442368 1001.000000
X458752 1051.000000
X475136 1102.000000
X491520 1153.000000
X507904 1209.000000
X524288 1260.000000
X540672 1316.000000
X557056 1368.000000
X573440 1425.000000
X589824 1481.000000
X606208 1538.000000
X622592 1596.000000
X638976 1655.000000
X655360 1713.000000
X671744 1769.000000
X688128 1828.000000
X704512 1881.000000
X720896 1939.000000
X737280 2000.000000
X753664 2063.000000
X770048 2127.000000
X786432 2193.000000
X802816 2259.000000
X819200 2329.000000
X835584 2402.000000
X851968 2471.000000
X868352 2543.000000
X884736 2609.000000
X901120 2675.000000
X917504 2726.000000
X933888 2795.000000
X950272 2864.000000
X966656 2929.000000
X983040 2998.000000
X999424 3063.000000
X1015808 3127.000000
X1032192 3190.000000
X1048576 3253.000000
X1064960 3320.000000
X1081344 3385.000000
X1097728 3454.000000
X1114112 3529.000000
X1130496 3600.000000
X1146880 3674.000000
X1163264 3747.000000
X1179648 3813.000000
X1196032 3884.000000
X1212416 3954.000000
X1228800 4025.000000
X1245184 4101.000000
X1261568 4180.000000
X1277952 4255.000000
X1294336 4330.000000
X1310720 4405.000000
X1327104 4480.000000
X1343488 4548.000000
X1359872 4621.000000
X1376256 4699.000000
X1392640 4787.000000
X1409024 4874.000000
X1425408 4958.000000
X1441792 5065.000000
X1458176 5179.000000
X1474560 5296.000000
X1490944 5416.000000
X1507328 5528.000000
X1523712 5648.000000
X1540096 5777.000000
X1556480 5912.000000
X1572864 6053.000000
X1589248 6204.000000
X1605632 6365.000000
X1622016 6532.000000
X1638400 6704.000000
X1654784 6882.000000
X1523712 5648.000000
X1540096 5777.000000
X1556480 5912.000000
X1572864 6053.000000
X1589248 6204.000000
X1605632 6365.000000
X1622016 6532.000000
X1638400 6704.000000
X1654784 6882.000000
X1671168 7062.000000
X1687552 7235.000000
X1703936 7424.000000
X1720320 7610.000000
X1736704 7801.000000
X1753088 7989.000000
X1769472 8172.000000
X1785856 8363.000000
X1802240 8560.000000
X1818624 8754.000000
X1835008 8954.000000
X1851392 9155.000000
X1867776 9348.000000
X1884160 9537.000000
X1900544 9729.000000
X1916928 9916.000000
X1933312 10110.000000
X1949696 10294.000000
X1966080 10481.000000
X1982464 10673.000000
X1998848 10861.000000
X2015232 11053.000000
X2031616 11241.000000
X2048000 11428.000000
X2064384 11617.000000
X2080768 11805.000000
X2097152 11994.000000
X2113536 12195.000000
X2129920 12395.000000
X2146304 12593.000000
X2162688 12793.000000
X2179072 12992.000000
X2195456 13187.000000
X2211840 13386.000000
X2228224 13583.000000
X2244608 13779.000000
X2260992 13977.000000
X2277376 14175.000000
X2293760 14367.000000
X2310144 14561.000000
X2326528 14744.000000
X2342912 14937.000000
X2359296 15141.000000
X2375680 15341.000000
X2392064 15542.000000
X2408448 15742.000000
X2424832 15942.000000
X2441216 16148.000000
X2457600 16352.000000
X2473984 16557.000000
X2490368 16764.000000
X2506752 16946.000000
X2523136 17147.000000
X2539520 17350.000000
X2555904 17552.000000
X2572288 17754.000000
X2588672 17956.000000
X2605056 18160.000000
X2621440 18491.000000
X2637824 18929.000000
X2654208 19371.000000
X2670592 19796.000000
X-- interrupted here by ^C --
X
X*/
END-of-makegdbm.c
echo x - makendbm
sed 's/^X//' >makendbm << 'END-of-makendbm'
X#!/bin/sh
Xecho "I am dummy."
Xecho "Remove me and make makendbm from the source."
END-of-makendbm
echo x - makendbm.c
sed 's/^X//' >makendbm.c << 'END-of-makendbm.c'
X/*
X Register key value pairs in text database into Berkeley DB.
X $Id:$
X*/
X
X#define MAX_LINE_LENGTH 4096
X
X
X#include <stdlib.h>
X#include <stdio.h>
X#include <string.h>
X#include <db.h>
X#include <fcntl.h>
X#include <limits.h>
X#include <time.h>
X#include <errno.h>
X#include <sys/types.h>
X#include <sys/stat.h>
X
Xstatic int keycount;
Xstatic char *db_name;
X
Xvoid atput(DB *db, char keystring[], char valuestring[])
X{
X int duplicate;
X DBT key, value;
X
X key.data = keystring;
X key.size = strlen(keystring);
X value.data = valuestring;
X value.size = strlen(valuestring);
X duplicate = db->put(db, &key, &value, R_NOOVERWRITE);
X if (duplicate < 0) {
X fprintf(stderr, "Cannot store data at %d-th key.\n",
X keycount + 1);
X perror(NULL);
X db->close(db);
X exit(1);
X }
X/*
X if (duplicate > 0) {
X fprintf(stderr,
X "Duplicated key: %s\n",
X keystring);
X }
X*/
X}
X
Xlong long filesize(char *path)
X{
X struct stat filestatus;
X
X if (stat(path, &filestatus) < 0) {
X return (-1);
X }
X return ((long long)filestatus.st_size);
X}
X
Xint main(int argc, char** argv)
X{
X DB *db;
X char textbuf[MAX_LINE_LENGTH];
X char key[MAX_LINE_LENGTH];
X char value[MAX_LINE_LENGTH];
X double elapsed;
X time_t starttime;
X
X if (argc != 2) {
X fprintf(stderr, "Usage: %s output_gdbm\n", argv[0]);
X exit(1);
X }
X db_name = argv[1];
X if (!(db = dbopen(db_name, O_RDWR | O_TRUNC | O_CREAT, 0666, DB_HASH, NULL))) {
X fprintf(stderr, "Cannot open %s\n", db_name);
X exit(1);
X }
X keycount = 0;
X starttime = time(NULL);
X while (fgets(textbuf, sizeof(textbuf), stdin)) {
X if (sscanf(textbuf, "%s %s", key, value) < 2) {
X fprintf(stderr, "Cannot scan text db correctly.\n");
X exit(1);
X }
X atput(db, key, value);
X keycount++;
X if (keycount % 16384 == 0) {
X elapsed = difftime(time(NULL), starttime);
X /*
X If you wanted accurate filesize, you would
X flush buffers. But you may care more about
X accuracy of time statistics.
X */
X /*
X db->sync(db, 0);
X */
X printf("keys: %d elapsed: %f filesize: %lld\n",
X keycount, elapsed, filesize(db_name));
X fflush(stdout);
X }
X }
X if (ferror(stdin)) {
X fprintf(stderr, "Cannot read input\n");
X }
X db->close(db);
X exit(0);
X}
END-of-makendbm.c
echo x - plotsize.sh
sed 's/^X//' >plotsize.sh << 'END-of-plotsize.sh'
X#!/bin/sh
X#
X#
X#
X
X#gnuplotfile=/tmp/plot.gp
X#rm -f $gnuplotfile
X
Xcat - << __EOF__
Xset terminal png
Xset output "size.png"
Xset title "dbm family space usage"
Xset xlabel "keys"
Xset ylabel "size"
Xset key right top box
Xset label "Gdbm: ver 1.8.3" at graph 0.05,0.70
Xset label "Berkeley DB: ver 1.8.5? in libc on FreeBSD 4.11" at graph 0.05,0.65
Xset label "Via ndbm interface." at graph 0.05,0.62
X__EOF__
X
Xexpect_maxkeys=`tail -1 v1.ndbm.time | awk '{print $2}'`
X
Xfor statfile in v*.ndbm.time v*.gdbm.time
Xdo
X total=`tail -1 $statfile`
X maxkeys=`echo $total | awk '{print $2}'`
X if [ 0"$expect_maxkeys" -ne 0"$maxkeys" ]
X then
X echo $total | awk '{print \
X "set label \"FAIL\" at ", $2, ",", $6, "left front"}'
X fi
Xdone
X
Xcat - << __EOF__
Xplot \
X "v128.gdbm.time" using 1:3 'keys: %lf elapsed: %lf filesize: %lf' title "GDBM datasize=128", \
X "v1024.gdbm.time" using 1:3 'keys: %lf elapsed: %lf filesize: %lf' title "GDBM datasize=1024", \
X "v128.ndbm.time" using 1:3 'keys: %lf elapsed: %lf filesize: %lf' title "Berkeley DB datasize=128", \
X "v1024.ndbm.time" using 1:3 'keys: %lf elapsed: %lf filesize: %lf' title "Berkeley DB datasize=1024"
X__EOF__
END-of-plotsize.sh
echo x - plottime.sh
sed 's/^X//' >plottime.sh << 'END-of-plottime.sh'
X#!/bin/sh
X#
X#
X#
X
X#gnuplotfile=/tmp/plot.gp
X#rm -f $gnuplotfile
X
Xexpect_maxkeys=`tail -1 v1.ndbm.time | awk '{print $2}'`
X
Xcat - << __EOF__
Xset terminal png
Xset output "time.png"
Xset title "dbm family insert speed"
Xset xlabel "keys"
Xset ylabel "elapsed time"
Xset key left top box
Xset label "Gdbm: ver 1.8.3" at graph 0.05,0.70
Xset label "Berkeley DB: ver 1.8.5? in libc on FreeBSD 4.11" at graph 0.05,0.65
Xset label "Via ndbm interface." at graph 0.05,0.62
X__EOF__
X
Xfor statfile in v*.ndbm.time v*.gdbm.time
Xdo
X total=`tail -1 $statfile`
X maxkeys=`echo $total | awk '{print $2}'`
X if [ 0"$expect_maxkeys" -eq 0"$maxkeys" ]
X then
X filesize=`echo $total | awk '{print $6}'`
X echo $total | awk '{print \
X "set label \"filesize " \
X int('$filesize' / 1024 / 1024) \
X "M\" at ", $2 , "," , $4, "right front"}'
X else
X echo $total | awk '{print \
X "set label \"FAIL\" at ", $2, ",", $4, "left front"}'
X fi
Xdone
X
Xcat - << __EOF__
Xplot \
X "v1.gdbm.time" using 'keys: %lf elapsed: %lf' title "GDBM datasize=1", \
X "v128.gdbm.time" using 'keys: %lf elapsed: %lf' title "GDBM datasize=128", \
X "v1024.gdbm.time" using 'keys: %lf elapsed: %lf' title "GDBM datasize=1024", \
X "v1.ndbm.time" using 'keys: %lf elapsed: %lf' title "Berkeley DB datasize=1", \
X "v128.ndbm.time" using 'keys: %lf elapsed: %lf' title "Berkeley DB datasize=128", \
X "v1024.ndbm.time" using 'keys: %lf elapsed: %lf' title "Berkeley DB datasize=1024"
X__EOF__
END-of-plottime.sh
echo x - v1.gdbm.time
sed 's/^X//' >v1.gdbm.time << 'END-of-v1.gdbm.time'
Xkeys: 16384 elapsed: 2.000000 filesize: 1327104
Xkeys: 32768 elapsed: 4.000000 filesize: 2637824
Xkeys: 49152 elapsed: 7.000000 filesize: 5259450
Xkeys: 65536 elapsed: 9.000000 filesize: 5260254
Xkeys: 81920 elapsed: 12.000000 filesize: 5261022
Xkeys: 98304 elapsed: 27.000000 filesize: 10502324
Xkeys: 114688 elapsed: 64.000000 filesize: 10502696
Xkeys: 131072 elapsed: 104.000000 filesize: 10503151
Xkeys: 147456 elapsed: 143.000000 filesize: 10503571
Xkeys: 163840 elapsed: 184.000000 filesize: 10504068
Xkeys: 180224 elapsed: 233.000000 filesize: 20905984
Xkeys: 196608 elapsed: 298.000000 filesize: 21004288
Xkeys: 212992 elapsed: 362.000000 filesize: 21004288
Xkeys: 229376 elapsed: 426.000000 filesize: 21004288
Xkeys: 245760 elapsed: 490.000000 filesize: 21004288
Xkeys: 262144 elapsed: 554.000000 filesize: 21020721
Xkeys: 278528 elapsed: 618.000000 filesize: 21020952
Xkeys: 294912 elapsed: 682.000000 filesize: 21021162
Xkeys: 311296 elapsed: 746.000000 filesize: 21021358
Xkeys: 327680 elapsed: 810.000000 filesize: 21021561
Xkeys: 344064 elapsed: 880.000000 filesize: 28590080
Xkeys: 360448 elapsed: 958.000000 filesize: 40288256
Xkeys: 376832 elapsed: 1042.000000 filesize: 41992276
Xkeys: 393216 elapsed: 1124.000000 filesize: 41992402
Xkeys: 409600 elapsed: 1207.000000 filesize: 42008639
Xkeys: 425984 elapsed: 1290.000000 filesize: 42025079
Xkeys: 442368 elapsed: 1373.000000 filesize: 42025170
Xkeys: 458752 elapsed: 1456.000000 filesize: 42025303
Xkeys: 475136 elapsed: 1541.000000 filesize: 42025436
Xkeys: 491520 elapsed: 1625.000000 filesize: 42025548
Xkeys: 507904 elapsed: 1710.000000 filesize: 42025611
Xkeys: 524288 elapsed: 1793.000000 filesize: 42025709
Xkeys: 540672 elapsed: 1875.000000 filesize: 42025814
Xkeys: 557056 elapsed: 1958.000000 filesize: 42025891
Xkeys: 573440 elapsed: 2041.000000 filesize: 42025996
Xkeys: 589824 elapsed: 2124.000000 filesize: 42026115
Xkeys: 606208 elapsed: 2207.000000 filesize: 42026220
Xkeys: 622592 elapsed: 2289.000000 filesize: 42026367
Xkeys: 638976 elapsed: 2372.000000 filesize: 42026451
Xkeys: 655360 elapsed: 2456.000000 filesize: 42026563
Xkeys: 671744 elapsed: 2540.000000 filesize: 43761664
Xkeys: 688128 elapsed: 2628.000000 filesize: 56918016
Xkeys: 704512 elapsed: 2722.000000 filesize: 71221248
Xkeys: 720896 elapsed: 2864.000000 filesize: 81559552
Xkeys: 737280 elapsed: 3049.000000 filesize: 84033550
Xkeys: 753664 elapsed: 3225.000000 filesize: 84033627
Xkeys: 770048 elapsed: 3413.000000 filesize: 84033676
Xkeys: 786432 elapsed: 3595.000000 filesize: 84033732
Xkeys: 802816 elapsed: 3777.000000 filesize: 84033795
Xkeys: 819200 elapsed: 3970.000000 filesize: 84033844
Xkeys: 835584 elapsed: 4150.000000 filesize: 84033907
Xkeys: 851968 elapsed: 4337.000000 filesize: 84033991
Xkeys: 868352 elapsed: 4527.000000 filesize: 84034040
Xkeys: 884736 elapsed: 4707.000000 filesize: 84034117
Xkeys: 901120 elapsed: 4894.000000 filesize: 84034180
Xkeys: 917504 elapsed: 5085.000000 filesize: 84034250
Xkeys: 933888 elapsed: 5266.000000 filesize: 84034271
Xkeys: 950272 elapsed: 5456.000000 filesize: 84034348
Xkeys: 966656 elapsed: 5638.000000 filesize: 84034390
Xkeys: 983040 elapsed: 5821.000000 filesize: 84034446
Xkeys: 999424 elapsed: 6014.000000 filesize: 84034509
Xkeys: 1015808 elapsed: 6104.000000 filesize: 84034549
END-of-v1.gdbm.time
echo x - v1.ndbm.time
sed 's/^X//' >v1.ndbm.time << 'END-of-v1.ndbm.time'
Xkeys: 16384 elapsed: 2.000000 filesize: 344064
Xkeys: 32768 elapsed: 5.000000 filesize: 622592
Xkeys: 49152 elapsed: 10.000000 filesize: 1179648
Xkeys: 65536 elapsed: 15.000000 filesize: 1359872
Xkeys: 81920 elapsed: 20.000000 filesize: 2490368
Xkeys: 98304 elapsed: 25.000000 filesize: 2490368
Xkeys: 114688 elapsed: 29.000000 filesize: 2490368
Xkeys: 131072 elapsed: 34.000000 filesize: 2490368
Xkeys: 147456 elapsed: 38.000000 filesize: 2637824
Xkeys: 163840 elapsed: 43.000000 filesize: 2637824
Xkeys: 180224 elapsed: 48.000000 filesize: 2637824
Xkeys: 196608 elapsed: 54.000000 filesize: 4947968
Xkeys: 212992 elapsed: 60.000000 filesize: 5128192
Xkeys: 229376 elapsed: 66.000000 filesize: 5292032
Xkeys: 245760 elapsed: 72.000000 filesize: 5308416
Xkeys: 262144 elapsed: 78.000000 filesize: 5308416
Xkeys: 278528 elapsed: 85.000000 filesize: 5308416
Xkeys: 294912 elapsed: 91.000000 filesize: 5406720
Xkeys: 311296 elapsed: 97.000000 filesize: 5406720
Xkeys: 327680 elapsed: 103.000000 filesize: 5554176
Xkeys: 344064 elapsed: 109.000000 filesize: 9994240
Xkeys: 360448 elapsed: 115.000000 filesize: 10043392
Xkeys: 376832 elapsed: 122.000000 filesize: 10043392
Xkeys: 393216 elapsed: 128.000000 filesize: 10125312
Xkeys: 409600 elapsed: 134.000000 filesize: 10240000
Xkeys: 425984 elapsed: 141.000000 filesize: 10272768
Xkeys: 442368 elapsed: 148.000000 filesize: 10321920
Xkeys: 458752 elapsed: 154.000000 filesize: 10321920
Xkeys: 475136 elapsed: 161.000000 filesize: 10321920
Xkeys: 491520 elapsed: 168.000000 filesize: 10567680
Xkeys: 507904 elapsed: 174.000000 filesize: 10797056
Xkeys: 524288 elapsed: 181.000000 filesize: 11042816
Xkeys: 540672 elapsed: 189.000000 filesize: 11091968
Xkeys: 557056 elapsed: 196.000000 filesize: 11255808
Xkeys: 573440 elapsed: 204.000000 filesize: 11436032
Xkeys: 589824 elapsed: 210.000000 filesize: 11436032
Xkeys: 606208 elapsed: 217.000000 filesize: 11599872
Xkeys: 622592 elapsed: 225.000000 filesize: 11763712
Xkeys: 638976 elapsed: 233.000000 filesize: 11763712
Xkeys: 655360 elapsed: 241.000000 filesize: 11911168
Xkeys: 671744 elapsed: 249.000000 filesize: 11911168
Xkeys: 688128 elapsed: 257.000000 filesize: 11943936
Xkeys: 704512 elapsed: 266.000000 filesize: 12156928
Xkeys: 720896 elapsed: 276.000000 filesize: 12156928
Xkeys: 737280 elapsed: 288.000000 filesize: 20594688
Xkeys: 753664 elapsed: 299.000000 filesize: 20774912
Xkeys: 770048 elapsed: 310.000000 filesize: 20856832
Xkeys: 786432 elapsed: 320.000000 filesize: 20856832
Xkeys: 802816 elapsed: 330.000000 filesize: 20856832
Xkeys: 819200 elapsed: 342.000000 filesize: 20922368
Xkeys: 835584 elapsed: 353.000000 filesize: 20955136
Xkeys: 851968 elapsed: 364.000000 filesize: 20971520
Xkeys: 868352 elapsed: 374.000000 filesize: 20987904
Xkeys: 884736 elapsed: 385.000000 filesize: 21102592
Xkeys: 901120 elapsed: 396.000000 filesize: 21102592
Xkeys: 917504 elapsed: 408.000000 filesize: 21397504
Xkeys: 933888 elapsed: 420.000000 filesize: 21676032
Xkeys: 950272 elapsed: 431.000000 filesize: 21676032
Xkeys: 966656 elapsed: 442.000000 filesize: 22020096
Xkeys: 983040 elapsed: 452.000000 filesize: 22151168
Xkeys: 999424 elapsed: 462.000000 filesize: 22200320
Xkeys: 1015808 elapsed: 471.000000 filesize: 22331392
END-of-v1.ndbm.time
echo x - v1024.gdbm.time
sed 's/^X//' >v1024.gdbm.time << 'END-of-v1024.gdbm.time'
Xkeys: 16384 elapsed: 4.000000 filesize: 18664463
Xkeys: 32768 elapsed: 10.000000 filesize: 37356549
Xkeys: 49152 elapsed: 16.000000 filesize: 56886277
Xkeys: 65536 elapsed: 23.000000 filesize: 74695685
Xkeys: 81920 elapsed: 30.000000 filesize: 92652549
Xkeys: 98304 elapsed: 52.000000 filesize: 113673221
Xkeys: 114688 elapsed: 101.000000 filesize: 131449862
Xkeys: 131072 elapsed: 154.000000 filesize: 149324806
Xkeys: 147456 elapsed: 196.000000 filesize: 167248902
Xkeys: 163840 elapsed: 238.000000 filesize: 185271302
Xkeys: 180224 elapsed: 292.000000 filesize: 211339276
Xkeys: 196608 elapsed: 381.000000 filesize: 227263494
Xkeys: 212992 elapsed: 456.000000 filesize: 245138438
Xkeys: 229376 elapsed: 548.000000 filesize: 262947846
Xkeys: 245760 elapsed: 627.000000 filesize: 280791052
Xkeys: 262144 elapsed: 713.000000 filesize: 298796038
Xkeys: 278528 elapsed: 804.000000 filesize: 316687366
Xkeys: 294912 elapsed: 890.000000 filesize: 334496774
Xkeys: 311296 elapsed: 981.000000 filesize: 352470022
Xkeys: 327680 elapsed: 1076.000000 filesize: 370541574
Xkeys: 344064 elapsed: 1174.000000 filesize: 396133382
Xkeys: 360448 elapsed: 1271.000000 filesize: 421495814
Xkeys: 376832 elapsed: 1379.000000 filesize: 437109766
Xkeys: 393216 elapsed: 1479.000000 filesize: 454460422
Xkeys: 409600 elapsed: 1590.000000 filesize: 472417286
Xkeys: 425984 elapsed: 1696.000000 filesize: 490275846
Xkeys: 442368 elapsed: 1786.000000 filesize: 508150790
Xkeys: 458752 elapsed: 1888.000000 filesize: 526320646
Xkeys: 475136 elapsed: 1987.000000 filesize: 543376390
Xkeys: 491520 elapsed: 2104.000000 filesize: 561792006
Xkeys: 507904 elapsed: 2230.000000 filesize: 579601414
Xkeys: 524288 elapsed: 2328.000000 filesize: 597526540
Xkeys: 540672 elapsed: 2445.000000 filesize: 615351302
Xkeys: 557056 elapsed: 2547.000000 filesize: 633209862
Xkeys: 573440 elapsed: 2645.000000 filesize: 651412486
Xkeys: 589824 elapsed: 2756.000000 filesize: 669123590
Xkeys: 606208 elapsed: 2862.000000 filesize: 687473670
Xkeys: 622592 elapsed: 2984.000000 filesize: 705053702
Xkeys: 638976 elapsed: 3107.000000 filesize: 722781190
Xkeys: 655360 elapsed: 3222.000000 filesize: 740819974
Xkeys: 671744 elapsed: 3323.000000 filesize: 760759302
Xkeys: 688128 elapsed: 3436.000000 filesize: 792134662
Xkeys: 704512 elapsed: 3564.000000 filesize: 820592640
Xkeys: 720896 elapsed: 3752.000000 filesize: 843318278
Xkeys: 737280 elapsed: 3984.000000 filesize: 857572358
Xkeys: 753664 elapsed: 4213.000000 filesize: 873579526
Xkeys: 770048 elapsed: 4491.000000 filesize: 890913798
Xkeys: 786432 elapsed: 4780.000000 filesize: 908968966
Xkeys: 802816 elapsed: 5065.000000 filesize: 926827526
Xkeys: 819200 elapsed: 5385.000000 filesize: 944669702
Xkeys: 835584 elapsed: 5671.000000 filesize: 962118662
Xkeys: 851968 elapsed: 5918.000000 filesize: 980485126
Xkeys: 868352 elapsed: 6177.000000 filesize: 997966854
Xkeys: 884736 elapsed: 6437.000000 filesize: 1016808454
Xkeys: 901120 elapsed: 6684.000000 filesize: 1034028038
Xkeys: 917504 elapsed: 6914.000000 filesize: 1052132358
Xkeys: 933888 elapsed: 7139.000000 filesize: 1069630470
Xkeys: 950272 elapsed: 7369.000000 filesize: 1088029702
Xkeys: 966656 elapsed: 7599.000000 filesize: 1105724422
Xkeys: 983040 elapsed: 7822.000000 filesize: 1123910662
Xkeys: 999424 elapsed: 8060.000000 filesize: 1141228550
Xkeys: 1015808 elapsed: 8177.000000 filesize: 1159775239
END-of-v1024.gdbm.time
echo x - v1024.ndbm.time
sed 's/^X//' >v1024.ndbm.time << 'END-of-v1024.ndbm.time'
Xkeys: 16384 elapsed: 15.000000 filesize: 43384832
Xkeys: 32768 elapsed: 47.000000 filesize: 85540864
Xkeys: 49152 elapsed: 94.000000 filesize: 96010240
Xkeys: 65536 elapsed: 163.000000 filesize: 171933696
Xkeys: 81920 elapsed: 271.000000 filesize: 183009280
Xkeys: 98304 elapsed: 404.000000 filesize: 191971328
Xkeys: 114688 elapsed: 515.000000 filesize: 198492160
Xkeys: 131072 elapsed: 647.000000 filesize: 340164608
Xkeys: 147456 elapsed: 791.000000 filesize: 348471296
Xkeys: 163840 elapsed: 931.000000 filesize: 353697792
Xkeys: 180224 elapsed: 1084.000000 filesize: 359137280
Xkeys: 196608 elapsed: 1247.000000 filesize: 362594304
Xkeys: 212992 elapsed: 1429.000000 filesize: 368885760
Xkeys: 229376 elapsed: 1628.000000 filesize: 648790016
Xkeys: 245760 elapsed: 1840.000000 filesize: 656474112
Xkeys: 262144 elapsed: 2042.000000 filesize: 669810688
Xkeys: 278528 elapsed: 2232.000000 filesize: 1219723264
Xkeys: 294912 elapsed: 2419.000000 filesize: 1232994304
Xkeys: 311296 elapsed: 2608.000000 filesize: 1242988544
Xkeys: 327680 elapsed: 2839.000000 filesize: 2330705920
END-of-v1024.ndbm.time
echo x - v128.gdbm.time
sed 's/^X//' >v128.gdbm.time << 'END-of-v128.gdbm.time'
Xkeys: 16384 elapsed: 2.000000 filesize: 3016252
Xkeys: 32768 elapsed: 5.000000 filesize: 6014258
Xkeys: 49152 elapsed: 8.000000 filesize: 10650531
Xkeys: 65536 elapsed: 11.000000 filesize: 12124559
Xkeys: 81920 elapsed: 14.000000 filesize: 14254213
Xkeys: 98304 elapsed: 29.000000 filesize: 21349815
Xkeys: 114688 elapsed: 66.000000 filesize: 21807238
Xkeys: 131072 elapsed: 109.000000 filesize: 24215686
Xkeys: 147456 elapsed: 150.000000 filesize: 25247878
Xkeys: 163840 elapsed: 192.000000 filesize: 28541196
Xkeys: 180224 elapsed: 246.000000 filesize: 41598976
Xkeys: 196608 elapsed: 310.000000 filesize: 42942598
Xkeys: 212992 elapsed: 371.000000 filesize: 43680146
Xkeys: 229376 elapsed: 434.000000 filesize: 44040326
Xkeys: 245760 elapsed: 500.000000 filesize: 46104710
Xkeys: 262144 elapsed: 566.000000 filesize: 48546060
Xkeys: 278528 elapsed: 632.000000 filesize: 49545886
Xkeys: 294912 elapsed: 696.000000 filesize: 51003526
Xkeys: 311296 elapsed: 774.000000 filesize: 55033990
Xkeys: 327680 elapsed: 854.000000 filesize: 57081990
Xkeys: 344064 elapsed: 920.000000 filesize: 67125248
Xkeys: 360448 elapsed: 1009.000000 filesize: 81362944
Xkeys: 376832 elapsed: 1111.000000 filesize: 84574610
Xkeys: 393216 elapsed: 1205.000000 filesize: 85704838
Xkeys: 409600 elapsed: 1302.000000 filesize: 86474886
Xkeys: 425984 elapsed: 1410.000000 filesize: 86950290
Xkeys: 442368 elapsed: 1507.000000 filesize: 87244934
Xkeys: 458752 elapsed: 1599.000000 filesize: 87621766
Xkeys: 475136 elapsed: 1693.000000 filesize: 89800972
Xkeys: 491520 elapsed: 1792.000000 filesize: 93061254
Xkeys: 507904 elapsed: 1888.000000 filesize: 94879878
Xkeys: 524288 elapsed: 1984.000000 filesize: 96993414
Xkeys: 540672 elapsed: 2079.000000 filesize: 98238598
Xkeys: 557056 elapsed: 2180.000000 filesize: 99090566
Xkeys: 573440 elapsed: 2272.000000 filesize: 99500300
Xkeys: 589824 elapsed: 2366.000000 filesize: 100843654
Xkeys: 606208 elapsed: 2465.000000 filesize: 107659398
Xkeys: 622592 elapsed: 2571.000000 filesize: 110805126
Xkeys: 638976 elapsed: 2665.000000 filesize: 112312454
Xkeys: 655360 elapsed: 2766.000000 filesize: 114196748
Xkeys: 671744 elapsed: 2879.000000 filesize: 117391360
Xkeys: 688128 elapsed: 2979.000000 filesize: 133644288
Xkeys: 704512 elapsed: 3083.000000 filesize: 151126016
Xkeys: 720896 elapsed: 3259.000000 filesize: 163774464
Xkeys: 737280 elapsed: 3473.000000 filesize: 167248006
Xkeys: 753664 elapsed: 3699.000000 filesize: 169328774
Xkeys: 770048 elapsed: 3934.000000 filesize: 171376774
Xkeys: 786432 elapsed: 4161.000000 filesize: 171917580
Xkeys: 802816 elapsed: 4387.000000 filesize: 172212358
Xkeys: 819200 elapsed: 4622.000000 filesize: 172638342
Xkeys: 835584 elapsed: 4845.000000 filesize: 172982406
Xkeys: 851968 elapsed: 5075.000000 filesize: 173359238
Xkeys: 868352 elapsed: 5310.000000 filesize: 173801606
Xkeys: 884736 elapsed: 5532.000000 filesize: 173981830
Xkeys: 901120 elapsed: 5757.000000 filesize: 174276876
Xkeys: 917504 elapsed: 5989.000000 filesize: 174440582
Xkeys: 933888 elapsed: 6214.000000 filesize: 175751302
Xkeys: 950272 elapsed: 6455.000000 filesize: 179601542
Xkeys: 966656 elapsed: 6682.000000 filesize: 183173254
Xkeys: 983040 elapsed: 6911.000000 filesize: 185647238
Xkeys: 999424 elapsed: 7152.000000 filesize: 188842118
Xkeys: 1015808 elapsed: 7260.000000 filesize: 191299719
END-of-v128.gdbm.time
echo x - v128.ndbm.time
sed 's/^X//' >v128.ndbm.time << 'END-of-v128.ndbm.time'
Xkeys: 16384 elapsed: 4.000000 filesize: 5570560
Xkeys: 32768 elapsed: 10.000000 filesize: 9977856
Xkeys: 49152 elapsed: 17.000000 filesize: 11649024
Xkeys: 65536 elapsed: 26.000000 filesize: 20905984
Xkeys: 81920 elapsed: 37.000000 filesize: 22446080
Xkeys: 98304 elapsed: 49.000000 filesize: 23969792
Xkeys: 114688 elapsed: 60.000000 filesize: 24870912
Xkeys: 131072 elapsed: 72.000000 filesize: 42647552
Xkeys: 147456 elapsed: 84.000000 filesize: 43008000
Xkeys: 163840 elapsed: 98.000000 filesize: 43008000
Xkeys: 180224 elapsed: 115.000000 filesize: 43008000
Xkeys: 196608 elapsed: 130.000000 filesize: 43008000
Xkeys: 212992 elapsed: 147.000000 filesize: 43008000
Xkeys: 229376 elapsed: 170.000000 filesize: 76677120
Xkeys: 245760 elapsed: 203.000000 filesize: 78692352
Xkeys: 262144 elapsed: 238.000000 filesize: 80707584
Xkeys: 278528 elapsed: 273.000000 filesize: 81985536
Xkeys: 294912 elapsed: 300.000000 filesize: 83066880
Xkeys: 311296 elapsed: 331.000000 filesize: 83656704
Xkeys: 327680 elapsed: 365.000000 filesize: 84672512
Xkeys: 344064 elapsed: 405.000000 filesize: 85983232
Xkeys: 360448 elapsed: 444.000000 filesize: 87097344
Xkeys: 376832 elapsed: 483.000000 filesize: 88326144
Xkeys: 393216 elapsed: 527.000000 filesize: 89505792
Xkeys: 409600 elapsed: 588.000000 filesize: 90800128
Xkeys: 425984 elapsed: 662.000000 filesize: 159186944
Xkeys: 442368 elapsed: 746.000000 filesize: 159989760
Xkeys: 458752 elapsed: 826.000000 filesize: 160825344
Xkeys: 475136 elapsed: 906.000000 filesize: 161579008
Xkeys: 491520 elapsed: 983.000000 filesize: 162545664
Xkeys: 507904 elapsed: 1058.000000 filesize: 163201024
Xkeys: 524288 elapsed: 1160.000000 filesize: 164757504
Xkeys: 540672 elapsed: 1267.000000 filesize: 166854656
Xkeys: 557056 elapsed: 1377.000000 filesize: 168280064
Xkeys: 573440 elapsed: 1485.000000 filesize: 168968192
Xkeys: 589824 elapsed: 1579.000000 filesize: 169623552
Xkeys: 606208 elapsed: 1681.000000 filesize: 170409984
Xkeys: 622592 elapsed: 1809.000000 filesize: 172015616
Xkeys: 638976 elapsed: 1932.000000 filesize: 173686784
Xkeys: 655360 elapsed: 2067.000000 filesize: 175636480
Xkeys: 671744 elapsed: 2191.000000 filesize: 177684480
Xkeys: 688128 elapsed: 2308.000000 filesize: 179961856
Xkeys: 704512 elapsed: 2431.000000 filesize: 181616640
Xkeys: 720896 elapsed: 2585.000000 filesize: 182927360
Xkeys: 737280 elapsed: 2735.000000 filesize: 184467456
Xkeys: 753664 elapsed: 2890.000000 filesize: 185974784
Xkeys: 770048 elapsed: 3023.000000 filesize: 187580416
Xkeys: 786432 elapsed: 3168.000000 filesize: 188973056
Xkeys: 802816 elapsed: 3301.000000 filesize: 189972480
Xkeys: 819200 elapsed: 3466.000000 filesize: 191250432
Xkeys: 835584 elapsed: 3645.000000 filesize: 192364544
Xkeys: 851968 elapsed: 3816.000000 filesize: 328056832
Xkeys: 868352 elapsed: 3969.000000 filesize: 329351168
Xkeys: 884736 elapsed: 4123.000000 filesize: 330317824
Xkeys: 901120 elapsed: 4250.000000 filesize: 330891264
Xkeys: 917504 elapsed: 4428.000000 filesize: 331513856
Xkeys: 933888 elapsed: 4612.000000 filesize: 331939840
Xkeys: 950272 elapsed: 4776.000000 filesize: 332283904
Xkeys: 966656 elapsed: 4945.000000 filesize: 333185024
Xkeys: 983040 elapsed: 5098.000000 filesize: 333545472
Xkeys: 999424 elapsed: 5221.000000 filesize: 334299136
Xkeys: 1015808 elapsed: 5370.000000 filesize: 334823424
END-of-v128.ndbm.time
touch makendbm makegdbm
touch v1.ndbm.time v128.ndbm.time v1024.ndbm.time v1.gdbm.time v128.gdbm.time v1024.gdbm.time
exit
Shinji KONO
In article <ull4l3...@katsu.watanabe.name>, WATANABE Katsuhiro <ka...@watanabe.name> writes
> あまりのフォローアップの遅さが議論の妨げになっていたら
> ごめんなさい。少し勉強して出直してきました。
つうか、レベル高すぎ...
> sdbm : 狭義の Dynamic hashing [DYNAMIC]
> gdbm : Extendible hashing [INDEX]
> Berkeley DB : Linear hashing [INDEX]
> なお、Linear hashing には興味深い別名があって、
> Incremental hashing とも呼ばれます。
おぉ。僕も勉強しないとあかんな。
> 多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket
> を "split" することで行います。address 範囲が増える分は、
> hash 関数自体は変えず addressing に用いる bit 数を増やして
> 対応します。最初は LSB 4bit を使い、混んできたら 5bit を
> 使うという具合です。今まで 1101 の bucket に入っていた
> データは、01101 と 11101 の bucket へと split して振り分け
> られます。
なるほどね。微妙に、B-Tree 的ですね。多段の表にするんだ
ろうな。
In article <ufyut3...@katsu.watanabe.name>,WATANABE Katsuhiro <ka...@watanabe.name> writes
> グラフでは、[階段]状に急に遅くなっている部分は見られません。
> これは、平均性能（＝多数の insert の累積時間）を重視する
> タイプの応用なら、問題は小さいことを意味しています。
ふむふむ。
> 対比して、key 数が大きくなるにつれグラフの[傾斜]すなわち
> １回１回の insert の性能が悪化します。これは、rehash の
> ような全域的再計算によるものではないにもかかわらず、
> 破綻というのにふさわしい状況(傾きが急になる一方)です。
> このとき、loadavg は下がり、ページングではない種類の
> ディスクアクセスばかりをやる状況になっていました。
> しかし、この性能悪化の本質を私は絞れていません。
DB は、normal file ですか? Unix FS 上に作っちゃうと、
i-node 自体が B-Tree 的な構造になるので、hash と干渉
するかも知れません。
> 注：
> この記事でいう Berkeley DB は、FreeBSD や NetBSD の
> libc のものです。4.4BSD-Lite に含まれていたものの子孫で、
> 最近はあまり保守されてないように見えます。バージョン4系列
> (sleepycat が保守していて Linux のディストリビューション
> でよく見るもの)は現在も進化中で、状況が違うかもしれません。
Berkeley DB って、レコードの大きさは32bit 表現なんですね。
64bit 対応のが欲しいんだけど... PostgreSQL は出来るとか
聞きましたが、どうなんだろう?
WATANABE Katsuhiro
DB 屋さんが 20 年ぐらい前にさんざんやったとの追体験なの
でしょうか。
記事 <3992098...@rananim.ie.u-ryukyu.ac.jp> で
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) さんいはく
> > このとき、loadavg は下がり、ページングではない種類の
> > ディスクアクセスばかりをやる状況になっていました。
> > しかし、この性能悪化の本質を私は絞れていません。
>
> DB は、normal file ですか? Unix FS 上に作っちゃうと、
> i-node 自体が B-Tree 的な構造になるので、hash と干渉
> するかも知れません。
FFS 上の普通のファイルです。
具体的なプログラム *.c や計測手順 Makefile は、すべて記事
<ufyut3...@katsu.watanabe.name> の shar に入ってます。
関係する i-node は dbm ファイルの１つだけでキャッシュに
当然入ってるでしょう。i-node → block の対応表を厳しく
アクセスして重くなったとしても、それは結局メモリのアクセスの
範囲内で、デバイスのアクセスにつながることはないはずです。
もっと dbm のアルゴリズムに直接関係した事情と見ています。
> Berkeley DB って、レコードの大きさは32bit 表現なんですね。
> 64bit 対応のが欲しいんだけど... PostgreSQL は出来るとか
> 聞きましたが、どうなんだろう?
もう何でも 64bit の時代なんでしょうか。
PostgreSQL はまだできないと思います。field に入るのは 1GB
までです。
http://www.postgresql.org/docs/faqs.FAQ.html#4.4
row あたりだと 1.6TB という話とどこかで混ざったのでは。
(Berkeley DB の hash に代表される)表だと「レコード」と
表現して会話をしても 1 field って決まってますが、
それを row と解釈されたとか。
--
渡邊克宏 http://katsu.watanabe.name
Yasushi Shinjo
いい記事は、いつ投稿されてもいいですね。
In article <ull4l3...@katsu.watanabe.name>
WATANABE Katsuhiro <ka...@watanabe.name> writes:
> 多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket
> を "split" することで行います。address 範囲が増える分は、
> hash 関数自体は変えず addressing に用いる bit 数を増やして
> 対応します。最初は LSB 4bit を使い、混んできたら 5bit を
> 使うという具合です。今まで 1101 の bucket に入っていた
> データは、01101 と 11101 の bucket へと split して振り分け
> られます。
size.png で、横軸にキーの数、縦軸にファイルの大きさをとると、
２倍になっている所がありますよね。この時は、ファイル全体をど
んと２倍にするというよりは、キーのあるブロックだけとりあえず
２倍にするのでしょうか。
検索の時ですが、最大が 4 ビットから 5ビットになったすると、
まず、5ビットと思って探してみつかればよし、みつからない（ブ
ロックがない）と、4ビットにしてさがす、それでもなければ、さ
らに３ビット、２ビットと減らしていくと。ブロックの存在確認は
少し無駄な気もするけど、それはまた別途なにかやっているのです
かね。
In article <ufyut3...@katsu.watanabe.name>
WATANABE Katsuhiro <ka...@watanabe.name> writes:
> 別途 insert １回毎の時間の最大値も監視してみています。
> 遅い回というのは間歇的にやってくるのですが、それも
> Berkeley DB では1～2秒、gdbm だと 2～3秒でした
> (Pentium 1GHz)。応用によっては許せる範囲でしょう。
この1～2秒は、Berkeley DB のせいじゃないかもしれませんよ。OS
のファイル・システムのせいかもしれません。FreeBSD でなくて、
Linux ですが、大量データを書込んでいると、時々、数秒止まりま
す。あれやめて欲しいんだけど。
> 注：
> この記事でいう Berkeley DB は、FreeBSD や NetBSD の
> libc のものです。4.4BSD-Lite に含まれていたものの子孫で、
> 最近はあまり保守されてないように見えます。バージョン4系列
> (sleepycat が保守していて Linux のディストリビューション
> でよく見るもの)は現在も進化中で、状況が違うかもしれません。
グラフには、Berkeley DB 1.8.5 と書いてありますね。今新しいの
は、4.3 だから、番号だけはだいぶちがいます。時々、ライブラリ
で 1 用と 2 以降用に分かれていますが、あれは API の違いなん
ですか？
API が違っても、内部のアルゴリズムはあんまり変ってないんじゃ
ないかな。
API が同じなら、Berkeley DB 2/3/4 の違いって何なんでしょう？
In article <3992098...@rananim.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> なるほどね。微妙に、B-Tree 的ですね。多段の表にするんだ
> ろうな。
ビットが長い所から見れば、多段の表にはならないと思いました。
ビットを減らしていくので、バイナリサーチには違いないけれど。
> DB は、normal file ですか? Unix FS 上に作っちゃうと、
> i-node 自体が B-Tree 的な構造になるので、hash と干渉
> するかも知れません。
OS のバッファ・キャッシュとの競合が大きいと思います。この時
代から。
M.Stonebraker: "Operating System Support for Database
Management", Communications of the ACM, Vol.24, No.7,
(1981).
この時代のイメージは、今でもけっこう残っていて、Oracle で
raw disk が常識かと思っていたら、Oracle でもファイル・システ
ムを使うのもけっこう多いみたいね。
In article <upstop...@katsu.watanabe.name>
WATANABE Katsuhiro <ka...@watanabe.name> writes:
> いまここで議論している大規模な hash 表の扱いなんてものは、
> DB 屋さんが 20 年ぐらい前にさんざんやったとの追体験なの
> でしょうか。
DB屋さんは、そう見えるでしょうね。実際には、回りの情況まで含
めて考えると、考えるべき要素が増えていて、話が難しんだけど。
Tadasuke YAMAGUCHI
現象の話だけ。
>> In article <ufyut3...@katsu.watanabe.name>
>> WATANABE Katsuhiro <ka...@watanabe.name> writes:
>> > 別途 insert １回毎の時間の最大値も監視してみています。
>> > 遅い回というのは間歇的にやってくるのですが、それも
>> > Berkeley DB では1～2秒、gdbm だと 2～3秒でした
>> > (Pentium 1GHz)。応用によっては許せる範囲でしょう。
>>
>> この1～2秒は、Berkeley DB のせいじゃないかもしれませんよ。OS
>> のファイル・システムのせいかもしれません。FreeBSD でなくて、
>> Linux ですが、大量データを書込んでいると、時々、数秒止まりま
>> す。あれやめて欲しいんだけど。
つい最近、Solaris10 + PostgreSQL8.0.3の環境で、fjのここ
1年分およそ12,000記事のヘッダーをinsertしていったんですが、
たまーに同じように4-5秒とまっているように見える時がありま
した。
trussで監視していた所、PostgreSQLがsystem callの返り待ち
をしているように見えたのですが、具体的に何待ちだったか
記憶があやふや。
body部のMD5値を計算して、insert間の時間が少し長くなり、
そういった止まる現象も無くなったように思います。
ちなみにその時にかかった時間は、全体で1h20m。1 insertあたり
0.4s掛かってます。実際には存在しない記事のチェックやdecode
処理があるので、純粋にinsertに掛かる時間はもっと短いですけど。
--
Tadasuke YAMAGUCHI @ Hyogo
WATANABE Katsuhiro
dbm ファイルの大きさの変化や、Berkeley DB のバージョン間の
差異については、私はよくわかりません。
記事 <YAS.05Ju...@kirk.is.tsukuba.ac.jp> で
y...@is.tsukuba.ac.jp (Yasushi Shinjo) さんいはく
> > 多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket
> > を "split" することで行います。address 範囲が増える分は、
> > hash 関数自体は変えず addressing に用いる bit 数を増やして
> > 対応します。最初は LSB 4bit を使い、混んできたら 5bit を
> > 使うという具合です。今まで 1101 の bucket に入っていた
> > データは、01101 と 11101 の bucket へと split して振り分け
> > られます。
>
> 検索の時ですが、最大が 4 ビットから 5ビットになったすると、
> まず、5ビットと思って探してみつかればよし、みつからない（ブ
> ロックがない）と、4ビットにしてさがす、それでもなければ、さ
> らに３ビット、２ビットと減らしていくと。
探し方の部分はバリエーションになっていて色々な戦略があります。
bucket をアドレスする hash 値の bit 数が混在してもよいように、
狭義 Dynamic は trie 辞書、Extensible は一段階の間接表を
利用します。Linear では、split する順番を決めてしまい、split
済みのものとまだのものが表中で仕切りを隔てて区分されるように
工夫します。
[狭義の Dynamic hashing]
初期状態として bucket がどれも 4bit で指されてるとしましょう。
準備として、高さ 4+1 の完全な二分木を作ります。根から葉へと
向かう path に沿って {0,1} で印をつけ、これを hash 値の LSB 側
から順の bit pattern と解釈します。つまり、根直下の節は bit0、
葉は bit3 です。例えば 1101 の周辺はこんな感じ：
+-0-
| +-0001
| +-001-+
+ | +-1001
| +-01-+
| | | +-0101
| | +-101-+
+-1-+ +-1101
|
各葉から対応する bucket への pointer を埋め込めば、hash 値の
bit pattern から bucket への対応が自明に完成します。
今、hash 値の 1101 に対応する bucket[1101] を split し、
bucket[01101] と bukect[11101] に分けたとしましょう。このとき、
木の方でも 1101 の葉で分岐を起します。新たな葉は 01101, 11101
とみなせます。これらに bucket[01101] と bucket[11101] への
pointer を埋め込みます。
こうして成長する木をたどれば、hash 値の bit 数が場所によって
違っていても、常に bucket を正しくアドレスできます。
[Extendible hashing]
ほとんどの bucket は 4bit で指されているけれど、例外的に
...1101 の部分だけ 5bit で bucket[01101] とbucket[11101] に
split されているという状態を考えましょう。
大きいほうの bit 数 5 に都合を合わせて、大きさ 2^5=32 の配列
directory を作り、これを bucket への間接表とします。間接表の
中身はどうするかというと、まず split されている部分については
directory[01101] -> bucket[01101]
directory[11101] -> bucket[11101]
のように直に指し示すようにします。そして、その他ほとんどの
split されていない部分については、たとえば 0000 についてなら
directory[00000] -> bucket[0000]
directory[10000] -> bucket[0000]
のように 4bit の bucket[0000] を重複して指させます。この間接表
を経由すれば、常に 5bit 固定で楽に bucket をアドレスできます。
もし将来 bucket[0000] が split されても、directory[00000] と
directory[10000] だけをいじればよいです。
さらに将来 6bit 分必要な部分が出たら、このときは directory の
大きさを 64に倍増させて再構成する羽目になります。しかしこの
作業は結局 bucket への pointer のコピーの繰り返しであり、多少
重いながらも致命的ではありません。
[Linear hashing]
ある仕切りの値を境として、それより hash 値が小さい方の bucket
は split し、大きい方の bucket は split しないよう区分したら
どうでしょうか。大小比較によって 4bit, 5bitを切り替えればよい
ので、hash 値から trie 辞書や間接表を引く手間が生じません。
初期状態として bucket がどれも 4bit で指されてるとしましょう。
2^4=16 個の bucket を、hash 値の昇順に配列の形で並べます。
hash 表の混み具合に応じて適当な時期に split しますが、好き勝手
な場所を split するのではなく、配列の先頭から順に行うように
固定します。split で bucket が増える分は最後尾に連結します。
0000 0001 0010 ... 1111
|
+-----------------------------+ 0000を00000,10000にsplit
V V
00000 0001 0010 ... 1111 10000
|
+-----------------------------+ 0001をsplit
V V
00000 00001 0010 ... 1111 10000 10001
|
次のsplit対象はここ
このように整列し、4bit, 5bit 部分がバラバラではなく塊で区分け
できれば、アクセスすべき bucket は次のように決まります。
h = hash 値;
q = 最後に split した場所; // 上図 3 段目の状態では 0001
n = (h の LSB 4bit 分だけ);
if (n > q) {
未 split の領域なので bucket[n] をアクセスする;
} else {
bucket[h の LSB 5bit] をアクセスする;
}
一段階の条件判断が入っているのみで、木や間接表などの二次的な
データ構造の助けを借りていないことに注意してください。
このアルゴリズムでは、表の混んでいる部分を恣意的に split する
ことはできません。安定して動作するためには、いつ・どの程度
split を進めるかの schedule も考える必要があります。
--
渡邊克宏 http://katsu.watanabe.name
--
渡邊克宏 http://katsu.watanabe.name