Re: [PATCH]: Add new bytecode op `switch' for implementing branch tables.

[Vibhav Pant]

On Tue, Feb 7, 2017 at 9:26 PM, Clément Pit-Claudel
<address@hidden> wrote:
> The timings fluctuate quite a bit, but the byte-switch branch seems to be 
> about 5-7% slower.  Hopefully linear-scan hash tables will make things much 
> faster :)

The following patch makes hash_lookup use linear search when the number of keys
in the hash table is <= 5 (chosen arbitrarily). switch bytecode run with this
patch takes 15.96 seconds to run the benchmark, while the goto-if-nil code takes
17.15 seconds.

-- 
Vibhav Pant
address@hidden

diff --git a/src/fns.c b/src/fns.c
index ac7c1f265a..2940bfdfbb 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -3915,6 +3915,17 @@ hash_lookup (struct Lisp_Hash_Table *h,
Lisp_Object key, EMACS_UINT *hash)
   ptrdiff_t start_of_bucket;
   Lisp_Object idx;

+  if (HASH_TABLE_SIZE (h) <= 5 && h->test.cmpfn) {
+    /*Try doing a linear search first */
+    ptrdiff_t i;
+    for (i = 0; i < HASH_TABLE_SIZE (h); i++)
+      {
+        if (h->test.cmpfn (&h->test, key, HASH_KEY (h, i)))
+          return i;
+      }
+    return -1;
+  }
+
   hash_code = h->test.hashfn (&h->test, key);
   eassert ((hash_code & ~INTMASK) == 0);
   if (hash)

gethash-linear-search.diff
Description: Text document