From dde800c8c9ea198996229d03df1fc45c7d057339 Mon Sep 17 00:00:00 2001
From: Vibhav Pant <vibhavp@gmail.com>
Date: Thu, 9 Feb 2017 12:18:54 +0530
Subject: [PATCH] Improve byte-switch execution.

* lisp/emacs-lisp/byte-opt.el,
  lisp/emacs-lisp/bytecomp.el (byte-decompile-bytecode-1),
  (byte-compile-lapcode): Calculate the actual jump address while
  compiling, store it in the jump table.

* src/bytecode.c: Jump to the looked up value directly, do a linear
  search when the number of elements is <= 5.
---
 lisp/emacs-lisp/byte-opt.el |  4 +---
 lisp/emacs-lisp/bytecomp.el |  9 +++++----
 src/bytecode.c              | 35 +++++++++++++++++++++++++++--------
 3 files changed, 33 insertions(+), 15 deletions(-)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 888a5f85007..3bec3e61df9 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -1411,10 +1411,8 @@
                ;; Replace all addresses with TAGs.
                (maphash #'(lambda (value tag)
                             (let (newtag)
-                              (cl-assert (consp tag)
-                                         nil "Invalid address for byte-switch")
                               (setq newtag (byte-compile-make-tag))
-                              (push (cons (+ (car tag) (lsh (cdr tag) 8)) newtag) tags)
+                              (push (cons tag newtag) tags)
                               (puthash value newtag last-constant)))
                         last-constant)
                ;; Replace the hash table referenced in the lapcode with our
diff --git a/lisp/emacs-lisp/bytecomp.el b/lisp/emacs-lisp/bytecomp.el
index d5a163e5fdd..748a8cd01f3 100644
--- a/lisp/emacs-lisp/bytecomp.el
+++ b/lisp/emacs-lisp/bytecomp.el
@@ -917,10 +917,11 @@ CONST2 may be evaluated multiple times."
       (if (> (car bytes-tail) 255) (error "Bytecode overflow")))
 
     (dolist (hash-table byte-compile-jump-tables)
-      (cl-loop for k being the hash-keys of hash-table do
-               (let ((tag (cdr (gethash k hash-table))))
-                 (setq pc (car tag))
-                 (puthash k (cons (logand pc 255) (lsh pc -8)) hash-table))))
+      (maphash #'(lambda (value tag)
+                   (setq pc (cadr tag))
+                   (puthash value (+ (logand pc 255) (lsh (lsh pc -8) 8))
+                            hash-table))
+               hash-table))
     (apply 'unibyte-string (nreverse bytes))))
 
 
diff --git a/src/bytecode.c b/src/bytecode.c
index f9531761b3c..9bb7bd4e685 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -1415,20 +1415,39 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
 
         CASE (Bswitch):
           {
+            /*TODO: Perhaps introduce another byte-code for switch when the
+              number of cases is less, which uses a simple vector for linear
+              search as the jump table.  */
             Lisp_Object jmp_table = POP;
             Lisp_Object v1 = POP;
 #ifdef BYTE_CODE_SAFE
             CHECK_TYPE (HASH_TABLE_P (jmp_table), Qhash_table_p, jmp_table);
 #endif
+            ptrdiff_t i;
             struct Lisp_Hash_Table *h = XHASH_TABLE(jmp_table);
-            ptrdiff_t i = hash_lookup(h, v1, NULL);
-            if (i >= 0) {
-              Lisp_Object dest = HASH_VALUE(h, i);
-              int car = XINT(XCAR(dest));
-              int cdr = XINT(XCDR(dest));
-              op = car + (cdr << 8); /* Simulate FETCH2 */
-              goto op_branch;
-            }
+            if (HASH_TABLE_SIZE (h) <= 5)
+              { /* Do a linear search if there are not many cases
+                   FIXME: 5 is arbitrarily chosen.  */
+                for (i = 0; i < HASH_TABLE_SIZE (h); i++)
+                  {
+                    if (!NILP (HASH_HASH (h, i)) &&
+                        (EQ (v1, HASH_KEY (h, i)) ||
+                         (h->test.cmpfn &&
+                          h->test.cmpfn (&h->test, v1, HASH_KEY (h, i)))))
+                      {
+                        op = XINT (HASH_VALUE (h, i));
+                        goto op_branch;
+                      }
+                  }
+              }
+            else
+              {
+                i = hash_lookup(h, v1, NULL);
+                if (i >= 0) {
+                  op = XINT(HASH_VALUE (h, i));
+                  goto op_branch;
+                }
+              }
           }
           NEXT;
 
-- 
2.39.5