tdb2: shrink free header from 32 to 24 bytes.
authorRusty Russell <rusty@rustcorp.com.au>
Wed, 1 Dec 2010 13:22:43 +0000 (23:52 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Wed, 1 Dec 2010 13:22:43 +0000 (23:52 +1030)
commit5e30abc662990449444769c71cf98ca788db4117
treecfe6d11b9d679bc7c9fa3f16f0a3f5891302fd96
parentdfae76fd82d4bbd8989264dadc2c3c9cde7e5af7
tdb2: shrink free header from 32 to 24 bytes.

This reduces our minimum key+data length to 8 bytes; we do this by packing
the prev pointer where we used to put the flist pointer, and storing the
flist as an 8 bit index (meaning we can only have 256 free tables).

Note that this has a perverse result on the size of the database, as our
4-byte key and 4-byte data now fit perfectly in a minimal record, so
appeding causes us to allocate new records which are 50% larger,
since we detect growing.

Current results of speed test:
$ ./speed 1000000
Adding 1000000 records:  23210 ns (59193360 bytes)
Finding 1000000 records:  2387 ns (59193360 bytes)
Traversing 1000000 records:  2150 ns (59193360 bytes)
Deleting 1000000 records:  13392 ns (59193360 bytes)
Re-adding 1000000 records:  11546 ns (59193360 bytes)
Appending 1000000 records:  29327 ns (91193360 bytes)
Churning 1000000 records:  33026 ns (91193360 bytes)

Previous:
$ ./speed 1000000
Adding 1000000 records:  28324 ns (67232528 bytes)
Finding 1000000 records:  2468 ns (67232528 bytes)
Traversing 1000000 records:  2200 ns (67232528 bytes)
Deleting 1000000 records:  13083 ns (67232528 bytes)
Re-adding 1000000 records:  16433 ns (67232528 bytes)
Appending 1000000 records:  2511 ns (67232528 bytes)
Churning 1000000 records:  31068 ns (67570448 bytes)
ccan/tdb2/check.c
ccan/tdb2/free.c
ccan/tdb2/private.h
ccan/tdb2/summary.c
ccan/tdb2/test/layout.c
ccan/tdb2/test/run-03-coalesce.c