From 0f144bfe0ca3cc06564e19a7f3ea40177d1a3c2c Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Thu, 9 Jun 2022 13:40:40 +0930 Subject: [PATCH] htable: optimize a little more. tools/speed (10 runs) vs before fix: -Lookup after half-change (match): 53-61(54.8+/-2.3) ns +Lookup after half-change (match): 63-97(72.4+/-9) ns -Churning fifth time: 171-181(175.4+/-2.9) ns +Churning fifth time: 179-198(183.9+/-5.2) ns Signed-off-by: Rusty Russell --- ccan/htable/htable.c | 22 ++++++++++------------ ccan/htable/htable.h | 6 +++--- 2 files changed, 13 insertions(+), 15 deletions(-) diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 0371e81d..70e0afc1 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,5 +1,6 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #include +#include #include #include #include @@ -66,9 +67,8 @@ static inline uintptr_t *actually_valid_pair(const struct htable *ht) static inline bool entry_actually_valid(const struct htable *ht, size_t off) { const uintptr_t *valid = actually_valid_pair(ht); - /* Empty table looks like this! */ - if (valid == &ht->common_bits + 1) - return false; + /* In the empty case, these are "common_mask" and "rehash" + * which cannot be 0 */ return valid[0] == off || valid[1] == off; } @@ -115,11 +115,6 @@ static inline bool entry_is_valid(const struct htable *ht, size_t off) return entry_actually_valid(ht, off); } -static inline bool entry_is_deleted(const struct htable *ht, size_t off) -{ - return ht->table[off] == HTABLE_DELETED && !entry_actually_valid(ht, off); -} - static inline uintptr_t ht_perfect_mask(const struct htable *ht) { return (uintptr_t)2 << ht->perfect_bitnum; @@ -212,11 +207,14 @@ static void *htable_val(const struct htable *ht, struct htable_iter *i, size_t hash, uintptr_t perfect) { uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; + const uintptr_t *valid = actually_valid_pair(ht); - while (ht->table[i->off] || entry_actually_valid(ht, i->off)) { - if (!entry_is_deleted(ht, i->off)) { - if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) - return get_raw_ptr(ht, ht->table[i->off]); + while (ht->table[i->off] || valid[0] == i->off || valid[1] == i->off) { + uintptr_t e = ht->table[i->off]; + if (e != HTABLE_DELETED || valid[0] == i->off || valid[1] == i->off) { + if (get_extra_ptr_bits(ht, e) == h2) { + return get_raw_ptr(ht, e); + } } i->off = (i->off + 1) & ((1 << ht->bits)-1); h2 &= ~perfect; diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index eac57e37..358b7428 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -22,12 +22,12 @@ * supply inline functions. */ struct htable { + /* These are the bits which are the same in all pointers. */ + uintptr_t common_bits, common_mask; size_t (*rehash)(const void *elem, void *priv); void *priv; unsigned int bits, perfect_bitnum; size_t elems, deleted; - /* These are the bits which are the same in all pointers. */ - uintptr_t common_mask, common_bits; uintptr_t *table; }; @@ -49,7 +49,7 @@ struct htable { * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); */ #define HTABLE_INITIALIZER(name, rehash, priv) \ - { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits } + { 0, -1, rehash, priv, 0, 0, 0, 0, &name.common_bits } /** * htable_init - initialize an empty hash table. -- 2.39.2