<div dir="ltr"><div class="gmail_default" style="font-family:'comic sans ms',sans-serif">Hey Rusty,</div><div class="gmail_default" style="font-family:'comic sans ms',sans-serif"><br></div><div class="gmail_default" style="font-family:'comic sans ms',sans-serif">
Thanks a lot for the explanation, it helped me write a simple code that simulates your hash table: <a href="https://gist.github.com/decltype/49f08c78ac40bf0124cc">https://gist.github.com/decltype/49f08c78ac40bf0124cc</a></div>
<div class="gmail_default" style="font-family:'comic sans ms',sans-serif"><br></div><div class="gmail_default" style="font-family:'comic sans ms',sans-serif">Cheers!</div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Wed, Jun 11, 2014 at 7:09 AM, Rusty Russell <span dir="ltr"><<a href="mailto:rusty@rustcorp.com.au" target="_blank">rusty@rustcorp.com.au</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="">Ahmed Samy <<a href="mailto:f.fallen45@gmail.com">f.fallen45@gmail.com</a>> writes:<br>
> Hey Rusty,<br>
><br>
> I am having difficulties understanding your hashtable implementation and<br>
> have some questions for you if you don't mind:<br>
<br>
</div>Hi Ahmed,<br>
<br>
Sure, they're a bit obscure. I've cc'd the mailing list so<br>
this gets archived...<br>
<div class=""><br>
> - The following bit twiddling hacks are kind of unfamiliar to me, I<br>
> couldn't make sense out of them:<br>
><br>
> static inline uintptr_t get_extra_ptr_bits(const struct htable *ht,<br>
> uintptr_t e)<br>
> {<br>
> return e & ht->common_mask;<br>
> }<br>
><br>
> static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e)<br>
> {<br>
> return (void *)((e & ~ht->common_mask) | ht->common_bits);<br>
> }<br>
><br>
> static inline uintptr_t make_hval(const struct htable *ht,<br>
> const void *p, uintptr_t bits)<br>
> {<br>
> return ((uintptr_t)p & ~ht->common_mask) | bits;<br>
> }<br>
<br>
</div>These three are related. The idea behind htable (and why it's so fast)<br>
is because we use redundant bits in the pointers to hide more hash bits.<br>
<br>
In a normal hash table to find an entry, you hash it to find the bucket<br>
it would be in, then if that bucket's pointer isn't NULL, follow it to<br>
see if it's the entry we want. This involves loading two cache lines:<br>
the bucket and the entry.<br>
<br>
By stashing some hash bits in the pointer, we can often know that an<br>
entry isn't correct without dereferencing the pointer. eg. with 10<br>
extra hash bits, we'll eliminate 1023 of 1024 failed lookups.<br>
<br>
But what bits of the pointer can we use? To do that, we track what bits<br>
are common to all the pointers in the hash (ht->common_mask). For a<br>
64-bit system that can be a lot of bits, but even for 32-bit pointers we<br>
can expect a few bits: the lower bits and some upper bits if everything<br>
in the hash table is on the heap.<br>
<div class=""><br>
> static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,<br>
> size_t hash)<br>
> {<br>
> /* Shuffling the extra bits (as specified in mask) down the<br>
> * end is quite expensive. But the lower bits are redundant, so<br>
> * we fold the value first. */<br>
> return (hash ^ (hash >> ht->bits))<br>
> & ht->common_mask & ~ht->perfect_bit;<br>
> }<br>
<br>
</div>This is a bit trickier. It decides *which* hash bits we try to stash in<br>
the pointer. The lower bits are redundant, since they already determine<br>
which hash bucket it's in. But spreading the rest of the bits out<br>
according to the common_mask is computationally expensive, so we simply<br>
xor the hash and the shifted hash, which mixes a little and is cheap<br>
(and means that those high pointer bits are still useful).<br>
<br>
ht->perfect_bit is another bit we steal from the pointer. If a hash<br>
bucket is full, we try the next hash bucket, until we find an empty<br>
one. ht->perfect_bit is set if a hash entry is in the first bucket it<br>
can be (see commit 78e983a7a6e5250ebf963d5d93fe34c1d27d5a39). Knowing<br>
this means we don't have to move the entry when we do a delete.<br>
<br>
This costs a little on insert, but really helps on deletion from a<br>
crowded table. I hacked it out (patch below) and re-benchmarked. The<br>
most noticable improvement is on a table with many deleted markers:<br>
<br>
64 bit with perfect bit:<br>
Initial re-inserting: 76-92(77.5867+/-2.9) ns<br>
32 bit with perfect bit:<br>
Initial re-inserting: 74-81(75.35+/-1.7) ns<br>
<br>
64 bit without perfect bit:<br>
Initial re-inserting: 107-111(107.75+/-0.94) ns<br>
32 bit without perfect bit:<br>
Initial re-inserting: 102-110(105.45+/-2.1) ns<br>
<br>
Hope that helps!<br>
Rusty.<br>
<br>
Subject: Remove perfect_bit.<br>
<br>
diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c<br>
index b7e65d1..687b141 100644<br>
--- a/ccan/htable/htable.c<br>
+++ b/ccan/htable/htable.c<br>
@@ -39,7 +39,7 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,<br>
<div class=""> * end is quite expensive. But the lower bits are redundant, so<br>
* we fold the value first. */<br>
return (hash ^ (hash >> ht->bits))<br>
</div>- & ht->common_mask & ~ht->perfect_bit;<br>
+ & ht->common_mask;<br>
}<br>
<br>
void htable_init(struct htable *ht,<br>
@@ -49,12 +49,12 @@ void htable_init(struct htable *ht,<br>
*ht = empty;<br>
ht->rehash = rehash;<br>
ht->priv = priv;<br>
- ht->table = &ht->perfect_bit;<br>
+ ht->table = &ht->common_bits;<br>
}<br>
<br>
void htable_clear(struct htable *ht)<br>
{<br>
- if (ht->table != &ht->perfect_bit)<br>
+ if (ht->table != (void *)&ht->table)<br>
free((void *)ht->table);<br>
htable_init(ht, ht->rehash, ht->priv);<br>
}<br>
@@ -65,9 +65,9 @@ static size_t hash_bucket(const struct htable *ht, size_t h)<br>
}<br>
<br>
static void *htable_val(const struct htable *ht,<br>
- struct htable_iter *i, size_t hash, uintptr_t perfect)<br>
+ struct htable_iter *i, size_t hash)<br>
{<br>
- uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;<br>
+ uintptr_t h2 = get_hash_ptr_bits(ht, hash);<br>
<br>
while (ht->table[i->off]) {<br>
if (ht->table[i->off] != HTABLE_DELETED) {<br>
@@ -75,7 +75,6 @@ static void *htable_val(const struct htable *ht,<br>
return get_raw_ptr(ht, ht->table[i->off]);<br>
}<br>
i->off = (i->off + 1) & ((1 << ht->bits)-1);<br>
- h2 &= ~perfect;<br>
}<br>
return NULL;<br>
}<br>
@@ -84,14 +83,14 @@ void *htable_firstval(const struct htable *ht,<br>
struct htable_iter *i, size_t hash)<br>
{<br>
i->off = hash_bucket(ht, hash);<br>
- return htable_val(ht, i, hash, ht->perfect_bit);<br>
+ return htable_val(ht, i, hash);<br>
}<br>
<br>
void *htable_nextval(const struct htable *ht,<br>
struct htable_iter *i, size_t hash)<br>
{<br>
i->off = (i->off + 1) & ((1 << ht->bits)-1);<br>
- return htable_val(ht, i, hash, 0);<br>
+ return htable_val(ht, i, hash);<br>
}<br>
<br>
void *htable_first(const struct htable *ht, struct htable_iter *i)<br>
@@ -116,15 +115,13 @@ void *htable_next(const struct htable *ht, struct htable_iter *i)<br>
static void ht_add(struct htable *ht, const void *new, size_t h)<br>
{<br>
size_t i;<br>
- uintptr_t perfect = ht->perfect_bit;<br>
<br>
i = hash_bucket(ht, h);<br>
<br>
while (entry_is_valid(ht->table[i])) {<br>
- perfect = 0;<br>
i = (i + 1) & ((1 << ht->bits)-1);<br>
}<br>
- ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);<br>
+ ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h));<br>
}<br>
<br>
static COLD bool double_table(struct htable *ht)<br>
@@ -143,17 +140,7 @@ static COLD bool double_table(struct htable *ht)<br>
ht->max = ((size_t)3 << ht->bits) / 4;<br>
ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;<br>
<br>
- /* If we lost our "perfect bit", get it back now. */<br>
- if (!ht->perfect_bit && ht->common_mask) {<br>
- for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {<br>
- if (ht->common_mask & ((size_t)1 << i)) {<br>
- ht->perfect_bit = (size_t)1 << i;<br>
- break;<br>
- }<br>
- }<br>
- }<br>
-<br>
- if (oldtable != &ht->perfect_bit) {<br>
+ if (oldtable != &ht->common_bits) {<br>
for (i = 0; i < oldnum; i++) {<br>
if (entry_is_valid(e = oldtable[i])) {<br>
void *p = get_raw_ptr(ht, e);<br>
@@ -181,7 +168,7 @@ static COLD void rehash_table(struct htable *ht)<br>
continue;<br>
if (e == HTABLE_DELETED)<br>
ht->table[h] = 0;<br>
- else if (!(e & ht->perfect_bit)) {<br>
+ else {<br>
void *p = get_raw_ptr(ht, e);<br>
ht->table[h] = 0;<br>
ht_add(ht, p, ht->rehash(p, ht->priv));<br>
@@ -208,7 +195,6 @@ static COLD void update_common(struct htable *ht, const void *p)<br>
<br>
ht->common_mask = ~((uintptr_t)1 << i);<br>
ht->common_bits = ((uintptr_t)p & ht->common_mask);<br>
- ht->perfect_bit = 1;<br>
return;<br>
}<br>
<br>
@@ -227,10 +213,9 @@ static COLD void update_common(struct htable *ht, const void *p)<br>
ht->table[i] |= bitsdiff;<br>
}<br>
<br>
- /* Take away those bits from our mask, bits and perfect bit. */<br>
+ /* Take away those bits from our mask, bits. */<br>
ht->common_mask &= ~maskdiff;<br>
ht->common_bits &= ~maskdiff;<br>
- ht->perfect_bit &= ~maskdiff;<br>
}<br>
<br>
bool htable_add(struct htable *ht, size_t hash, const void *p)<br>
diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h<br>
index ed668e7..f5cb336 100644<br>
--- a/ccan/htable/htable.h<br>
+++ b/ccan/htable/htable.h<br>
@@ -19,7 +19,6 @@ struct htable {<br>
size_t elems, deleted, max, max_with_deleted;<br>
/* These are the bits which are the same in all pointers. */<br>
uintptr_t common_mask, common_bits;<br>
- uintptr_t perfect_bit;<br>
uintptr_t *table;<br>
};<br>
<br>
@@ -40,7 +39,7 @@ struct htable {<br>
* static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);<br>
*/<br>
#define HTABLE_INITIALIZER(name, rehash, priv) \<br>
- { rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }<br>
+ { rehash, priv, 0, 0, 0, 0, 0, -1, 0, &name.common_bits }<br>
<br>
/**<br>
* htable_init - initialize an empty hash table.<br>
diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c<br>
index 7fc05e2..ac1d2d4 100644<br>
--- a/ccan/htable/test/run.c<br>
+++ b/ccan/htable/test/run.c<br>
@@ -98,14 +98,13 @@ static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)<br>
int main(int argc, char *argv[])<br>
{<br>
unsigned int i, weight;<br>
- uintptr_t perfect_bit;<br>
struct htable ht;<br>
uint64_t val[NUM_VALS];<br>
uint64_t dne;<br>
void *p;<br>
struct htable_iter iter;<br>
<br>
- plan_tests(29);<br>
+ plan_tests(25);<br>
for (i = 0; i < NUM_VALS; i++)<br>
val[i] = i;<br>
dne = i;<br>
@@ -175,20 +174,6 @@ int main(int argc, char *argv[])<br>
find_vals(&ht, val, NUM_VALS);<br>
ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));<br>
<br>
- /* Corner cases: wipe out the perfect bit using bogus pointer. */<br>
- htable_clear(&ht);<br>
- htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));<br>
- ok1(ht.perfect_bit);<br>
- perfect_bit = ht.perfect_bit;<br>
- htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]<br>
- | perfect_bit));<br>
- ok1(ht.perfect_bit == 0);<br>
- htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));<br>
-<br>
- /* Enlarging should restore it... */<br>
- add_vals(&ht, val, 0, NUM_VALS-1);<br>
-<br>
- ok1(ht.perfect_bit != 0);<br>
htable_clear(&ht);<br>
<br>
return exit_status();<br>
diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c<br>
index dce3fdf..cb24f1d 100644<br>
--- a/ccan/htable/tools/speed.c<br>
+++ b/ccan/htable/tools/speed.c<br>
@@ -74,8 +74,6 @@ static size_t perfect(const struct htable *ht)<br>
continue;<br>
if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),<br>
ht->priv)) == i) {<br>
- assert((ht->table[i] & ht->perfect_bit)<br>
- == ht->perfect_bit);<br>
placed_perfect++;<br>
}<br>
}<br>
</blockquote></div><br><br clear="all"><div><br></div><div dir="ltr"><blockquote style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><font face="courier new, monospace">Ahmed, C/C++/Java/Assembly/Python/Lua Developer<br>
</font><font face="courier new, monospace"><a href="https://github.com/decltype/" target="_blank">https://github.com/decltype/</a></font><br></blockquote></div>
</div></div>