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>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index c5f166f83e3fc0f188f9907a6a6da55f0e60cb5a..f631ffebf1f7540416a050c800bcf5cd42268470 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -418,8 +418,12 @@ void htable_delval_(struct htable *ht, struct htable_iter *i)
        assert(entry_is_valid(ht->table[i->off]));
 
        ht->elems--;
-       ht->table[i->off] = HTABLE_DELETED;
-       ht->deleted++;
+       /* Cheap test: if the next bucket is empty, don't need delete marker */
+       if (ht->table[hash_bucket(ht, i->off+1)] != 0) {
+               ht->table[i->off] = HTABLE_DELETED;
+               ht->deleted++;
+       } else
+               ht->table[i->off] = 0;
 }
 
 void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i)