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 <rusty@rustcorp.com.au>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 0371e81d0fac4837c221fcb7cb57fff5a12b8fdf..70e0afc1140d86ad17c3d5e3fdc822a84f5cab93 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -1,5 +1,6 @@
 /* Licensed under LGPLv2+ - see LICENSE file for details */
 #include <ccan/htable/htable.h>
+#include <ccan/likely/likely.h>
 #include <ccan/compiler/compiler.h>
 #include <stdlib.h>
 #include <stdio.h>
@@ -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 eac57e37a326612226f6cd7907c04bcbc589c360..358b74280867c8694fd90ce11689091fd57055fd 100644 (file)
--- 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.