]> git.ozlabs.org Git - ccan/commit
htable: opportunistically avoid delete marker.
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 17 Jun 2022 04:34:14 +0000 (14:04 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 17 Jun 2022 04:34:14 +0000 (14:04 +0930)
commit9fc8ff8ddff079adf31de16b030df17a1407f783
treebbc5db2713ba6d58ab65c00a61e69462ad76b9fc
parent3fcc6bfb0447e07a69c4912951021a4104a6f726
htable: opportunistically avoid delete marker.

Fairly cheap test, we can see a drop in initial re-inserting, probably
because it has just been cleaned at this point with the old code, but
generally we do better with churn.

I also tried a variant which only checked if next bucket was on same
cacheline, but no significant difference.

5 runs of tools/speed 10000000:

```
-Initial re-inserting: 88-99(94.6+/-5) ns
+Initial re-inserting: 104-116(107.2+/-4.4) ns
-Adding (a different) half: 94-101(98.6+/-3) ns
+Adding (a different) half: 38-44(39.8+/-2.1) ns
-Lookup after half-change (miss): 90-105(96.4+/-5.7) ns
+Lookup after half-change (miss): 112-118(113.4+/-2.3) ns
-Churning third time: 301-323(314.4+/-9.8) ns
+Churning third time: 233-259(239+/-10) ns
-Details: worst run 146 (24 deleted)
+Details: worst run 115 (2 deleted)
-Lookup after churn & spread (match): 78-87(83.6+/-4.2) ns
+Lookup after churn & spread (match): 71-81(73.6+/-3.8) ns
-Lookup after churn & spread (miss): 118-137(124.2+/-6.9) ns
+Lookup after churn & spread (miss): 93-104(95.4+/-4.3) ns
-Adding (a different) half after churn & spread: 81-89(85.4+/-3.6) ns
+Adding (a different) half after churn & spread: 38-43(39.6+/-1.7) ns
```

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/htable/htable.c