From: Rusty Russell Date: Fri, 17 Jun 2022 04:34:14 +0000 (+0930) Subject: htable: opportunistically avoid delete marker. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=9fc8ff8ddff079adf31de16b030df17a1407f783 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 --- diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index c5f166f8..f631ffeb 100644 --- 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)