Re: rehash of dbm

記事 <ull4l3kjw.fsf@katsu.watanabe.name> で
私 WATANABE Katsuhiro <katsu@watanabe.name> いはく
> > hash だと、rehash されちゃうと破綻します。最初にhashの
> > 大きさを指定できれば良いんですけどね。
> 
> 今の dbm ファミリでは、破綻というほど酷くはないようです。
> 
> 実は、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