]> git.ozlabs.org Git - ccan/commit
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)
commit7218ee2476d8a7e4f9413781e2bedcd2daaa8190
tree587c3e56782d15ccba9da327ddc3b13fc2f661c8
parent609670cc6a5fc9ba819cacca251cde1709c053d6
htable: handle v. unlikely case where entries look deleted/empty.

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>
ccan/htable/htable.c
ccan/htable/test/run-clash.c [new file with mode: 0644]
ccan/htable/test/run-debug.c
ccan/htable/test/run.c
ccan/htable/tools/speed.c