htable: rehash to clear delete markers
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%