]> git.ozlabs.org Git - ccan/commitdiff
htable: handle v. unlikely case where entries look deleted/empty.
authorRusty Russell <rusty@rustcorp.com.au>
Thu, 9 Jun 2022 03:12:31 +0000 (12:42 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Thu, 9 Jun 2022 04:12:44 +0000 (13:42 +0930)
If the hash function doesn't set any bits we use, and the common
bits are all zero the slot will look empty (or, just the lower bit is
set: the slow looks deleted).

However, each bucket is distinct since there are no duplicates, so
at worse there can be two "looks invalid but actually is valid"
buckets.  Keep them at the end.

Lookup suffers in raw tools/speed though:

-Lookup after half-change (match): 53-61(54.8+/-2.3) ns
+Lookup after half-change (match): 61-113(83.3+/-17) ns
-Lookup after churn & spread (match): 54-90(59.9+/-11) ns
+Lookup after churn & spread (match): 70-108(85.2+/-14) ns

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

No differences found