htable: push capacity limit from 66 to 75%
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 8 Nov 2010 03:02:51 +0000 (13:32 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 8 Nov 2010 03:02:51 +0000 (13:32 +1030)
commit0473813acdfad62221ec9f2b9b41bc10d1f4586d
tree49614dd110e0f67288aed6e5d646657bb035ad96
parentd3104024f71cf4f89195787add6c7ac381d62f40
htable: push capacity limit from 66 to 75%

With the extra bits, long runs don't hurt our cache very much on search,
so we can pack quite a few in.  Here are the runs at maximal density before
and after:

Before:
$ ./speed 3145000
Initial insert:  248 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  142 ns
Initial lookup (random):  170 ns
Initial delete all:  134 ns
Details: rehashes 3145000
Initial re-inserting:  149 ns
Deleting first half:  73 ns
Details: rehashes 1572500, delete markers 1572500
Adding (a different) half:  128 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  129 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  703 ns
Churning third time:  725 ns
Churning fourth time:  717 ns
Churning fifth time:  710 ns
Details: reinserting with spread
Details: delete markers 149261, perfect 57%
Details: worst run 254 (2 deleted)
Lookup after churn & spread (match):  132 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  184 ns
Deleting half after churn & spread:  71 ns
Adding (a different) half after churn & spread:  129 ns
Details: delete markers 0, perfect 62%

After:
$ ./speed 3145727
Initial insert:  232 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  141 ns
Initial lookup (random):  234 ns
Initial delete all:  129 ns
Details: rehashes 3145727
Initial re-inserting:  153 ns
Deleting first half:  80 ns
Details: rehashes 1572864, delete markers 1572864
Adding (a different) half:  137 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  125 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  702 ns
Churning third time:  719 ns
Churning fourth time:  712 ns
Churning fifth time:  709 ns
Details: reinserting with spread
Details: delete markers 169474, perfect 56%
Details: worst run 248 (12 deleted)
Lookup after churn & spread (match):  129 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  242 ns
Deleting half after churn & spread:  70 ns
Adding (a different) half after churn & spread:  133 ns
Details: delete markers 0, perfect 62%
ccan/htable/htable.c
ccan/htable/tools/speed.c