From 1ce4659039a548fdbf204e868a11475b1f6dcd0a Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 23 Oct 2017 06:54:36 -0700 Subject: 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. --- hash.c | 12 ++++++++---- 1 file 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); -- cgit v1.2.3