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

[Vibhav Pant <vibhavp@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1209 bytes --]

On Tue, Feb 7, 2017 at 9:26 PM, Clément Pit-Claudel
<cpitclaudel@gmail.com> 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
vibhavp@gmail.com

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)

[-- Attachment #2: gethash-linear-search.diff --]
[-- Type: text/plain, Size: 637 bytes --]

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)