]> git.ozlabs.org Git - ccan/commitdiff
htable: rehash to clear delete markers
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 8 Nov 2010 05:53:17 +0000 (16:23 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 8 Nov 2010 05:53:17 +0000 (16:23 +1030)
Delete markers build up over time, even if we try to clean as we go.
So just garbage collect them when there are too many.

Before:
rusty@vivaldi:~/devel/cvs/ccan/ccan/htable/tools (htable)$ ./speed 50000000
Initial insert:  467 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  160 ns
Initial lookup (miss):  169 ns
Initial lookup (random):  328 ns
Initial delete all:  165 ns
Details: rehashes 50000000
Initial re-inserting:  317 ns
Deleting first half:  86 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  89 ns
Details: delete markers 18894324, perfect 76%
Lookup after half-change (match):  174 ns
Lookup after half-change (miss):  203 ns
Details: initial churn
Churning second time:  816 ns
Churning third time:  615 ns
Churning fourth time:  621 ns
Churning fifth time:  846 ns
Details: reinserting with spread
Details: delete markers 11078719, perfect 74%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  191 ns
Lookup after churn & spread (miss):  208 ns
Lookup after churn & spread (random):  374 ns
Deleting half after churn & spread:  102 ns
Adding (a different) half after churn & spread:  103 ns
Details: delete markers 27442234, perfect 73%

After:
Initial insert:  462 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  161 ns
Initial lookup (miss):  168 ns
Initial lookup (random):  326 ns
Initial delete all:  164 ns
Details: rehashes 50000000
Initial re-inserting:  167 ns
Deleting first half:  86 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  217 ns
Details: delete markers 0, perfect 81%
Lookup after half-change (match):  169 ns
Lookup after half-change (miss):  180 ns
Details: initial churn
Churning second time:  593 ns
Churning third time:  611 ns
Churning fourth time:  619 ns
Churning fifth time:  622 ns
Details: reinserting with spread
Details: delete markers 13800468, perfect 73%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  192 ns
Lookup after churn & spread (miss):  211 ns
Lookup after churn & spread (random):  373 ns
Deleting half after churn & spread:  103 ns
Adding (a different) half after churn & spread:  102 ns
Details: delete markers 29539689, perfect 72%


No differences found