Store hash values in hash entries.

Here, we augment the cons cells used for the hash chain assoc
lists with one more field to store the hash value. This lets
us grow hash tables without recalculating the hashes, and to
perform hash searches with fewer equality comparisons.

* hash.c (struct hash): assoc_fun and acons_new_c_fun function
pointers get a new cnum hash argument.
(hash_equal_op): Pass cell's hash value to assoc_fun.
(hash_grow): No need to compute each hash entry's hash
code; just pull it out from the cell, and mod it with the
new modulus to get the chain index.
(hash_assoc, hash_assql, hash_acons_new_c,
hash_aconsql_new_c): New static functions.
(make_hash): Store hash_assoc, hash_assql, hash_acons_new_c
and hash_aconsql_new_c in place of assoc, assql,
acons_new_c and aconsql_new_c.
(gethash_c, gethash, gethash_f, gethash_n, remhash):
Pass hash alue to assoc_fun or acons_new_c_fun.

* lib.h (struct cons_hash_entry): New struct type.
(union obj): New member ch.

2 files changed, 93 insertions, 19 deletions

diff --git a/hash.c b/hash.c
index f40b3a50..feecce28 100644
--- a/hash.c
+++ b/hash.c
@@ -58,8 +58,8 @@ struct hash {
   int usecount;
   cnum (*hash_fun)(val, int *);
   val (*equal_fun)(val, val);
-  val (*assoc_fun)(val key, val list);
-  val (*acons_new_c_fun)(val key, loc new_p, loc list);
+  val (*assoc_fun)(val key, cnum hash, val list);
+  val (*acons_new_c_fun)(val key, cnum hash, loc new_p, loc list);
 };
 
 struct hash_iter {
@@ -300,7 +300,7 @@ static val hash_equal_op(val left, val right)
      * a difference between the hash tables, and conclude they are different.
      * If there is no match, then we insert the cell into the pending list.
      */
-    found = l->assoc_fun(car(lcell), pending);
+    found = l->assoc_fun(car(lcell), lcell->ch.hash, pending);
 
     if (found && !equal(cdr(found), cdr(lcell))) {
       return nil;
@@ -319,7 +319,7 @@ static val hash_equal_op(val left, val right)
     /*
      * The logic is mirrored for the right cell.
      */
-    found = l->assoc_fun(car(rcell), pending);
+    found = l->assoc_fun(car(rcell), rcell->ch.hash, pending);
 
     if (found && !equal(cdr(found), cdr(rcell))) {
       return nil;
@@ -491,10 +491,8 @@ static void hash_grow(struct hash *h, val hash)
     while (conses) {
       val entry = car(conses);
       val next = cdr(conses);
-      val key = car(entry);
-      int lim = HASH_REC_LIMIT;
       loc pchain = vecref_l(new_table,
-                            num_fast(h->hash_fun(key, &lim) % new_modulus));
+                            num_fast(entry->ch.hash % new_modulus));
       set(cdr_l(conses), deref(pchain));
       set(pchain, conses);
       conses = next;
@@ -506,6 +504,70 @@ static void hash_grow(struct hash *h, val hash)
   set(mkloc(h->table, hash), new_table);
 }
 
+static val hash_assoc(val key, cnum hash, val list)
+{
+  list = nullify(list);
+
+  while (list) {
+    val elem = car(list);
+    if (elem->ch.hash == hash && equal(car(elem), key))
+      return elem;
+    list = cdr(list);
+  }
+
+  return nil;
+}
+
+static val hash_assql(val key, cnum hash, val list)
+{
+  list = nullify(list);
+
+  while (list) {
+    val elem = car(list);
+    if (elem->ch.hash == hash && eql(car(elem), key))
+      return elem;
+    list = cdr(list);
+  }
+
+  return nil;
+}
+
+static val hash_acons_new_c(val key, cnum hash, loc new_p, loc list)
+{
+  val existing = hash_assoc(key, hash, deref(list));
+
+  if (existing) {
+    if (!nullocp(new_p))
+      deref(new_p) = nil;
+    return existing;
+  } else {
+    val nc = cons(key, nil);
+    nc->ch.hash = hash;
+    set(list, cons(nc, deref(list)));
+    if (!nullocp(new_p))
+      deref(new_p) = t;
+    return nc;
+  }
+}
+
+static val hash_aconsql_new_c(val key, cnum hash, loc new_p, loc list)
+{
+  val existing = hash_assql(key, hash, deref(list));
+
+  if (existing) {
+    if (!nullocp(new_p))
+      deref(new_p) = nil;
+    return existing;
+  } else {
+    val nc = cons(key, nil);
+    nc->ch.hash = hash;
+    set(list, cons(nc, deref(list)));
+    if (!nullocp(new_p))
+      deref(new_p) = t;
+    return nc;
+  }
+}
+
 val make_hash(val weak_keys, val weak_vals, val equal_based)
 {
   if (weak_keys && equal_based) {
@@ -528,8 +590,8 @@ val make_hash(val weak_keys, val weak_vals, val equal_based)
     h->usecount = 0;
     h->hash_fun = equal_based ? equal_hash : eql_hash;
     h->equal_fun = equal_based ? equal : eql;
-    h->assoc_fun = equal_based ? assoc : assql;
-    h->acons_new_c_fun = equal_based ? acons_new_c : aconsql_new_c;
+    h->assoc_fun = equal_based ? hash_assoc : hash_assql;
+    h->acons_new_c_fun = equal_based ? hash_acons_new_c : hash_aconsql_new_c;
 
     return hash;
   }
@@ -588,9 +650,10 @@ val gethash_c(val hash, val key, loc new_p)
 {
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = HASH_REC_LIMIT;
-  loc pchain = vecref_l(h->table, num_fast(h->hash_fun(key, &lim) % h->modulus));
+  cnum hv = h->hash_fun(key, &lim);
+  loc pchain = vecref_l(h->table, num_fast(hv % h->modulus));
   val old = deref(pchain);
-  val cell = h->acons_new_c_fun(key, new_p, pchain);
+  val cell = h->acons_new_c_fun(key, hv, new_p, pchain);
   if (old != deref(pchain) && ++h->count > 2 * h->modulus && h->usecount == 0)
     hash_grow(h, hash);
   return cell;
@@ -600,8 +663,9 @@ val gethash(val hash, val key)
 {
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = HASH_REC_LIMIT;
-  val chain = vecref(h->table, num_fast(h->hash_fun(key, &lim) % h->modulus));
-  val found = h->assoc_fun(key, chain);
+  cnum hv = h->hash_fun(key, &lim);
+  val chain = vecref(h->table, num_fast(hv % h->modulus));
+  val found = h->assoc_fun(key, hv, chain);
   return cdr(found);
 }
 
@@ -625,8 +689,9 @@ val gethash_f(val hash, val key, loc found)
 {
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = HASH_REC_LIMIT;
-  val chain = vecref(h->table, num_fast(h->hash_fun(key, &lim) % h->modulus));
-  set(found, h->assoc_fun(key, chain));
+  cnum hv = h->hash_fun(key, &lim);
+  val chain = vecref(h->table, num_fast(hv % h->modulus));
+  set(found, h->assoc_fun(key, hv, chain));
   return cdr(deref(found));
 }
 
@@ -634,8 +699,9 @@ val gethash_n(val hash, val key, val notfound_val)
 {
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = HASH_REC_LIMIT;
-  val chain = vecref(h->table, num_fast(h->hash_fun(key, &lim) % h->modulus));
-  val existing = h->assoc_fun(key, chain);
+  cnum hv = h->hash_fun(key, &lim);
+  val chain = vecref(h->table, num_fast(hv % h->modulus));
+  val existing = h->assoc_fun(key, hv, chain);
   return if3(existing, cdr(existing), default_bool_arg(notfound_val));
 }
 
@@ -657,8 +723,9 @@ val remhash(val hash, val key)
 {
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = HASH_REC_LIMIT;
-  loc pchain = vecref_l(h->table, num_fast(h->hash_fun(key, &lim) % h->modulus));
-  val existing = h->assoc_fun(key, deref(pchain));
+  cnum hv = h->hash_fun(key, &lim);
+  loc pchain = vecref_l(h->table, num_fast(hv % h->modulus));
+  val existing = h->assoc_fun(key, hv, deref(pchain));
 
   if (existing) {
     val cell = memq(existing, deref(pchain));
diff --git a/lib.h b/lib.h
index a004926b..8ead64fb 100644
--- a/lib.h
+++ b/lib.h
@@ -98,6 +98,12 @@ struct cons {
   val car, cdr;
 };
 
+struct cons_hash_entry {
+  obj_common;
+  val car, cdr;
+  cnum hash;
+};
+
 struct string {
   obj_common;
   wchar_t *str;
@@ -272,6 +278,7 @@ struct range {
 union obj {
   struct any t;
   struct cons c;
+  struct cons_hash_entry ch;
   struct string st;
   struct sym s;
   struct package pk;