hash: optimization in remhash.

* hash.c (remhash): Walk chain to splice out to-be-removed
entry using an approach similar to what is done in
do_weak_tables to splice out lapsed weak entries.  This
eliminates one extra traversal of the chain as well as consing
due to the ldiff call. We use raw pointers obtained using
valptr, and direct assignment through *pchain because later
cells in a chain are strictly older objects than earlier
cells and so so the *pchain = cdr(*pchain) assignment cannot
make a generation 1 object point to a generation 0 object.

1 files changed, 8 insertions, 4 deletions

diff --git a/hash.c b/hash.c
index 444a32b8..7459ec8a 100644
--- a/hash.c
+++ b/hash.c
@@ -792,12 +792,16 @@ val remhash(val hash, val key)
   struct hash *h = coerce(struct hash *, cobj_handle(hash, hash_s));
   int lim = hash_rec_limit;
   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));
+  val *pchain = valptr(vecref_l(h->table, num_fast(hv % h->modulus)));
+  val existing = h->assoc_fun(key, hv, *pchain);
 
   if (existing) {
-    val cell = memq(existing, deref(pchain));
-    set(pchain, nappend2(ldiff(deref(pchain), cell), cdr(cell)));
+    for (; *pchain; pchain = valptr(cdr_l(*pchain))) {
+      if (car(*pchain) == existing) {
+        *pchain = cdr(*pchain);
+        break;
+      }
+    }
     h->count--;
     bug_unless (h->count >= 0);
     return cdr(existing);