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

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

[Vibhav Pant]

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

The following patch adds support for a new op `switch` to the Emacs bytecode VM
and compiler. As described in etc/TODO, switch takes 2 arguments from the stack:
a value to test, and a hash table from the constant pool. It then jumps to the
"address" the value in the hash-table maps to. This replaces the traditional
goto/goto-if-(not)-nil bytecode for cond forms, with a smaller and
more performant
bytecode. Currently, certain cond forms like:
(cond ((eq v 1) 'foo)
      ((eq v 'bar) 'baz)
      (t 'blah))
are compiled using byte- switch. The structure of switch bytecode for
the cond form
above is as follows:

varref v
constant #s(hash-table data (1 TAG1 bar TAG2))
switch
goto DEFAULT-TAG
TAG1:
constant 1
goto DONETAG
TAG2:
constant 'baz
goto DONETAG
DEFAULT-TAG:
constant 'blah ;; 'blah is 'nil' when there is no 't' clause.
DONETAG:
...

(This should also work with `pcase' forms, as it expands to a `cond')
The hash table used as the jump table for switch maps possible values to a cons
pair of two numbers. The jump address for the value is found by calculating
car(pair) + (cdr(pair) << 8), an inexpensive operation. The hash table is also
declared with :purecopy t, as it is always constant and can thus be copied
to pure storage.

However, since switch replaces all goto-if-nil code, I've used a few workarounds
to avoid breaking compiler invariants:

* byte-compile-cond-jump-table: After emitting an unconditional jump to DONETAG,
(cdr (cdr DONETAG)) is set to nil, and the value of byte-compile-depth is
restored (unconditional jumps set it to nil). This is to avoid depth conflicts
down the road, and is documented in `byte-compile-cond-jump-table'.

* byte-compile-inline-lapcode also replicates this behavior if any lapcode
containing byte-switch is being inlined.

Aside from this, the peephole optimizer in byte-opt.el has been
modified so as to
not screw up switch bytecode (and has been documented as well). disass.el has
also been changed to the show contents of the jump table with the correct tags.
Lastly, I've added a defcustom `byte-compile-cond-use-jump-table', which when
nil will use the original goto-if-(not)-nil bytecode while compiling cond. This
is a workaround for when `byte-compile-cond-jump-table' accidentally generates
wrong code (hasn't happened so far in my tests), and should be removed
once we're
sure there are no issues with it.

The code for this feature is in the branch 'feature/byte-switch',
feedback would be
appreciated.

-- 
Vibhav Pant
vibhavp@gmail.com

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 13f885448a..888a5f8500 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -185,6 +185,7 @@
 (require 'bytecomp)
 (eval-when-compile (require 'cl-lib))
 (require 'macroexp)
+(require 'subr-x)

 (defun byte-compile-log-lap-1 (format &rest args)
   ;; Newer byte codes for stack-ref make the slot 0 non-nil again.
@@ -1356,7 +1357,7 @@ byte-decompile-bytecode
 (defun byte-decompile-bytecode-1 (bytes constvec &optional make-spliceable)
   (let ((length (length bytes))
         (bytedecomp-ptr 0) optr tags bytedecomp-op offset
- lap tmp)
+ lap tmp last-constant)
     (while (not (= bytedecomp-ptr length))
       (or make-spliceable
   (push bytedecomp-ptr lap))
@@ -1385,7 +1386,8 @@ byte-decompile-bytecode-1
     (or (assq tmp byte-compile-variables)
                                 (let ((new (list tmp)))
                                   (push new byte-compile-variables)
-                                  new)))))
+                                  new)))
+                   last-constant tmp))
     ((eq bytedecomp-op 'byte-stack-set2)
      (setq bytedecomp-op 'byte-stack-set))
     ((and (eq bytedecomp-op 'byte-discardN) (>= offset #x80))
@@ -1394,7 +1396,34 @@ byte-decompile-bytecode-1
      ;; lapcode, we represent this by using a different opcode
      ;; (with the flag removed from the operand).
      (setq bytedecomp-op 'byte-discardN-preserve-tos)
-     (setq offset (- offset #x80))))
+     (setq offset (- offset #x80)))
+            ((eq bytedecomp-op 'byte-switch)
+             (cl-assert (hash-table-p last-constant) nil
+                        "byte-switch used without preceeding hash table")
+             ;; We cannot use the original hash table referenced in the op,
+             ;; so we create a copy of it, and replace the addresses with
+             ;; TAGs.
+             (let ((orig-table last-constant))
+               (cl-loop for e across constvec
+                        when (eq e last-constant)
+                        do (setq last-constant (copy-hash-table e))
+                        and return nil)
+               ;; 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)
+                              (puthash value newtag last-constant)))
+                        last-constant)
+               ;; Replace the hash table referenced in the lapcode with our
+               ;; modified one.
+               (cl-loop for el in-ref lap
+                        when (and (listp el) ;; make sure we're at
the correct op
+                                  (eq (nth 1 el) 'byte-constant)
+                                  (eq (nth 2 el) orig-table))
+                        do (setf (nth 2 el) last-constant) and return nil))))
       ;; lap = ( [ (pc . (op . arg)) ]* )
       (push (cons optr (cons bytedecomp-op (or offset 0)))
             lap)
@@ -1728,7 +1757,10 @@ byte-optimize-lapcode
       ;; unused-TAG: --> <deleted>
       ;;
       ((and (eq 'TAG (car lap0))
-    (not (rassq lap0 lap)))
+    (not (rassq lap0 lap))
+                    (cl-loop for table in byte-compile-jump-tables
+                             when (member lap0 (hash-table-values table))
+                             return nil finally return t))
        (and (memq byte-optimize-log '(t byte))
     (byte-compile-log "  unused tag %d removed" (nth 1 lap0)))
        (setq lap (delq lap0 lap)
@@ -1736,9 +1768,15 @@ byte-optimize-lapcode
       ;;
       ;; goto   ... --> goto   <delete until TAG or end>
       ;; return ... --> return <delete until TAG or end>
-      ;;
+      ;; (unless a jump-table is being used, where deleting may affect
+              ;; other valid case bodies)
+              ;;
       ((and (memq (car lap0) '(byte-goto byte-return))
-    (not (memq (car lap1) '(TAG nil))))
+    (not (memq (car lap1) '(TAG nil)))
+                    ;; FIXME: Instead of deferring simply when jump-tables are
+                    ;; being used, keep a list of tags used for switch tags and
+                    ;; use them instead (see `byte-compile-inline-lapcode').
+                    (not byte-compile-jump-tables))
        (setq tmp rest)
        (let ((i 0)
      (opt-p (memq byte-optimize-log '(t lap)))
diff --git a/lisp/emacs-lisp/bytecomp.el b/lisp/emacs-lisp/bytecomp.el
index 63be7e208b..d5a163e5fd 100644
--- a/lisp/emacs-lisp/bytecomp.el
+++ b/lisp/emacs-lisp/bytecomp.el
@@ -223,6 +223,11 @@ byte-compile-delete-errors
   :group 'bytecomp
   :type 'boolean)

+(defcustom byte-compile-cond-use-jump-table t
+  "Compile `cond' clauses to a jump table implementation (using a hash-table)."
+  :group 'bytecomp
+  :type 'boolean)
+
 (defvar byte-compile-dynamic nil
   "If non-nil, compile function bodies so they load lazily.
 They are hidden in comments in the compiled file,
@@ -412,6 +417,8 @@ byte-compile-call-tree-sort
  (const calls+callers) (const nil)))

 (defvar byte-compile-debug nil)
+(defvar byte-compile-jump-tables nil
+  "List of all jump tables used during compilation of this form.")
 (defvar byte-compile-constants nil
   "List of all constants encountered during compilation of this form.")
 (defvar byte-compile-variables nil
@@ -747,6 +754,10 @@ byte-extrude-byte-code-vectors
 ;; `byte-compile-lapcode').
 (defconst byte-discardN-preserve-tos byte-discardN)

+(byte-defop 183 -2 byte-switch
+ "to take a hash table and a value from the stack, and jump to the address
+the value maps to, if any.")
+
 ;; unused: 182-191

 (byte-defop 192  1 byte-constant "for reference to a constant")
@@ -823,7 +834,7 @@ byte-compile-lapcode
  op off ; Operation & offset
  opcode ; numeric value of OP
  (bytes '()) ; Put the output bytes here
- (patchlist nil)) ; List of gotos to patch
+ (patchlist nil))        ; List of gotos to patch
     (dolist (lap-entry lap)
       (setq op (car lap-entry)
     off (cdr lap-entry))
@@ -905,6 +916,11 @@ byte-compile-lapcode
       ;; FIXME: Replace this by some workaround.
       (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))))
     (apply 'unibyte-string (nreverse bytes))))


@@ -1954,7 +1970,8 @@ byte-compile-from-buffer
 ;; (edebug-all-defs nil)
 ;; (edebug-all-forms nil)
  ;; Simulate entry to byte-compile-top-level
- (byte-compile-constants nil)
+        (byte-compile-jump-tables nil)
+        (byte-compile-constants nil)
  (byte-compile-variables nil)
  (byte-compile-tag-number 0)
  (byte-compile-depth 0)
@@ -2250,7 +2267,8 @@ byte-compile-flush-pending
       byte-compile-variables nil
       byte-compile-depth 0
       byte-compile-maxdepth 0
-      byte-compile-output nil))))
+      byte-compile-output nil
+              byte-compile-jump-tables nil))))

 (defvar byte-compile-force-lexical-warnings nil)

@@ -2862,7 +2880,8 @@ byte-compile-top-level
  (byte-compile-maxdepth 0)
         (byte-compile--lexical-environment lexenv)
         (byte-compile-reserved-constants (or reserved-csts 0))
- (byte-compile-output nil))
+ (byte-compile-output nil)
+        (byte-compile-jump-tables nil))
     (if (memq byte-optimize '(t source))
  (setq form (byte-optimize-form form byte-compile--for-effect)))
     (while (and (eq (car-safe form) 'progn) (null (cdr (cdr form))))
@@ -3114,15 +3133,49 @@ byte-compile-inline-lapcode
   ;; happens to be true for byte-code generated by bytecomp.el without
   ;; lexical-binding, but it's not true in general, and it's not true for
   ;; code output by bytecomp.el with lexical-binding.
-  (let ((endtag (byte-compile-make-tag)))
+  ;; We also restore the value of `byte-compile-depth' and remove TAG depths
+  ;; accordingly when inlining byte-switch lap code, as documented in
+  ;; `byte-compile-cond-jump-table'.
+  (let ((endtag (byte-compile-make-tag))
+        last-jump-tag ;; last TAG we have jumped to
+        last-depth ;; last value of `byte-compile-depth'
+        last-constant ;; value of the last constant encountered
+        last-switch ;; whether the last op encountered was byte-switch
+        switch-tags ;; a list of tags that byte-switch could jump to
+        ;; a list of tags byte-switch will jump to, if the value doesn't
+        ;; match any entry in the hash table
+        switch-default-tags)
     (dolist (op lap)
       (cond
-       ((eq (car op) 'TAG) (byte-compile-out-tag op))
-       ((memq (car op) byte-goto-ops) (byte-compile-goto (car op) (cdr op)))
+       ((eq (car op) 'TAG)
+        (when (or (member op switch-tags) (member op switch-default-tags))
+          (when last-jump-tag
+            (setcdr (cdr last-jump-tag) nil))
+          (setq byte-compile-depth last-depth
+                last-jump-tag nil))
+        (byte-compile-out-tag op))
+       ((memq (car op) byte-goto-ops)
+        (setq last-depth byte-compile-depth
+              last-jump-tag (cdr op))
+        (byte-compile-goto (car op) (cdr op))
+        (when last-switch
+          (push (cdr op) switch-default-tags)
+          (setcdr (cdr (cdr op)) nil)
+          (setq byte-compile-depth last-depth
+                last-switch nil)))
        ((eq (car op) 'byte-return)
         (byte-compile-discard (- byte-compile-depth end-depth) t)
         (byte-compile-goto 'byte-goto endtag))
-       (t (byte-compile-out (car op) (cdr op)))))
+       (t
+        (when (eq (car op) 'byte-switch)
+          (push last-constant byte-compile-jump-tables)
+          (setq last-switch t)
+          (maphash #'(lambda (_k tag)
+                       (push tag switch-tags))
+                   last-constant))
+        (setq last-constant (and (eq (car op) 'byte-constant) (cadr op)))
+        (setq last-depth byte-compile-depth)
+        (byte-compile-out (car op) (cdr op)))))
     (byte-compile-out-tag endtag)))

 (defun byte-compile-unfold-bcf (form)
@@ -3951,37 +4004,162 @@ byte-compile-if
  (byte-compile-out-tag donetag))))
   (setq byte-compile--for-effect nil))

+(defun byte-compile-cond-vars (obj1 obj2)
+  ;; We make sure that of OBJ1 and OBJ2, one of them is a symbol,
+  ;; and the other is a constant expression whose value can be
+  ;; compared with `eq' (with `macroexp-const-p').
+  (or
+   (and (symbolp obj1) (macroexp-const-p obj2) (cons obj1 obj2))
+   (and (symbolp obj2) (macroexp-const-p obj1) (cons obj2 obj1))))
+
+(defun byte-compile-cond-jump-table-info (clauses)
+  "If CLAUSES is a `cond' form where:
+The condition for each clause is of the form (TEST VAR VALUE).
+VAR is a variable.
+TEST and VAR are the same throughout all conditions.
+VALUE is either a constant or a quoted form.
+
+Return a list of the form ((TEST . VAR)  ((VALUE BODY) ...))"
+  (let ((cases '())
+        (ok t)
+        prev-var prev-test)
+    (and (catch 'break
+           (dolist (clause (cdr clauses) ok)
+             (let* ((condition (car clause))
+                    (test (car-safe condition))
+                    (vars (when (consp condition)
+                            (byte-compile-cond-vars (cadr condition)
(cl-caddr condition))))
+                    (obj1 (car-safe vars))
+                    (obj2 (cdr-safe vars))
+                    (body (cdr-safe clause)))
+               (unless prev-var
+                 (setq prev-var obj1))
+               (unless prev-test
+                 (setq prev-test test))
+               (if (and obj1 (memq test '(eq eql equal))
+                        (consp condition)
+                        (eq test prev-test)
+                        (eq obj1 prev-var)
+                        ;; discard duplicate clauses
+                        (not (assq obj2 cases)))
+                   (push (list (if (consp obj2) (eval obj2) obj2) body) cases)
+                 (if (eq condition t)
+                     (progn (push (list 'default body) cases)
+                            (throw 'break t))
+                   (setq ok nil)
+                   (throw 'break nil))))))
+         (list (cons prev-test prev-var) (nreverse cases)))))
+
+(defun byte-compile-cond-jump-table (clauses)
+  (let* ((table-info (byte-compile-cond-jump-table-info clauses))
+         (test (caar table-info))
+         (var (cdar table-info))
+         (cases (cadr table-info))
+         jump-table test-obj body tag donetag default-tag default-case)
+    (when (and cases (not (= (length cases) 1)))
+      ;; TODO: Once :linear-search is implemented for `make-hash-table'
+      ;; set it to `t' for cond forms with a small number of cases.
+      (setq jump-table (make-hash-table :test test
+                                        :purecopy t
+                                        :size (if (assq 'default cases)
+                                                  (1- (length cases))
+                                                (length cases)))
+            default-tag (byte-compile-make-tag)
+            donetag (byte-compile-make-tag))
+      ;; The structure of byte-switch code:
+      ;;
+      ;; varref var
+      ;; constant #s(hash-table purecopy t data (val1 (TAG1) val2 (TAG2)))
+      ;; switch
+      ;; goto DEFAUT-TAG
+      ;; TAG1
+      ;; <clause body>
+      ;; goto DONETAG
+      ;; TAG2
+      ;; <clause body>
+      ;; goto DONETAG
+      ;; DEFAULT-TAG
+      ;; <body for `t' clause, if any (else `constant nil')>
+      ;; DONETAG
+
+      (byte-compile-variable-ref var)
+      (byte-compile-push-constant jump-table)
+      (byte-compile-out 'byte-switch)
+
+      ;; When the opcode argument is `byte-goto', `byte-compile-goto' sets
+      ;; `byte-compile-depth' to `nil'. However, we need `byte-compile-depth'
+      ;; to be non-nil for generating tags for all cases. Since
+      ;; `byte-compile-depth' will increase by atmost 1 after compiling
+      ;; all of the clause (which is further enforced by cl-assert below)
+      ;; it should be safe to preserve it's value.
+      (let ((byte-compile-depth byte-compile-depth))
+        (byte-compile-goto 'byte-goto default-tag))
+
+      (when (assq 'default cases)
+        (setq default-case (cadr (assq 'default cases))
+              cases (butlast cases 1)))
+
+      (dolist (case cases)
+        (setq tag (byte-compile-make-tag)
+              test-obj (nth 0 case)
+              body (nth 1 case))
+        (byte-compile-out-tag tag)
+        (puthash test-obj tag jump-table)
+
+        (let ((byte-compile-depth byte-compile-depth)
+              (init-depth byte-compile-depth))
+          ;; Since `byte-compile-body' might increase `byte-compile-depth'
+          ;; by 1, not preserving it's value will cause it to potentially
+          ;; increase by one for every clause body compiled, causing
+          ;; depth/tag conflicts or violating asserts down the road.
+          ;; To make sure `byte-compile-body' itself doesn't violate this,
+          ;; we use `cl-assert'.
+          (byte-compile-body body byte-compile--for-effect)
+          (cl-assert (or (= byte-compile-depth init-depth)
+                         (= byte-compile-depth (1+ init-depth))))
+          (byte-compile-goto 'byte-goto donetag)
+          (setcdr (cdr donetag) nil)))
+
+      (byte-compile-out-tag default-tag)
+      (if default-case
+          (byte-compile-body-do-effect default-case)
+        (byte-compile-constant nil))
+      (byte-compile-out-tag donetag)
+      (push jump-table byte-compile-jump-tables))))
+
 (defun byte-compile-cond (clauses)
-  (let ((donetag (byte-compile-make-tag))
- nexttag clause)
-    (while (setq clauses (cdr clauses))
-      (setq clause (car clauses))
-      (cond ((or (eq (car clause) t)
- (and (eq (car-safe (car clause)) 'quote)
-      (car-safe (cdr-safe (car clause)))))
-     ;; Unconditional clause
-     (setq clause (cons t clause)
-   clauses nil))
-    ((cdr clauses)
-     (byte-compile-form (car clause))
-     (if (null (cdr clause))
- ;; First clause is a singleton.
- (byte-compile-goto-if t byte-compile--for-effect donetag)
-       (setq nexttag (byte-compile-make-tag))
-       (byte-compile-goto 'byte-goto-if-nil nexttag)
-       (byte-compile-maybe-guarded (car clause)
- (byte-compile-body (cdr clause) byte-compile--for-effect))
-       (byte-compile-goto 'byte-goto donetag)
-       (byte-compile-out-tag nexttag)))))
-    ;; Last clause
-    (let ((guard (car clause)))
-      (and (cdr clause) (not (eq guard t))
-   (progn (byte-compile-form guard)
-  (byte-compile-goto-if nil byte-compile--for-effect donetag)
-  (setq clause (cdr clause))))
-      (byte-compile-maybe-guarded guard
- (byte-compile-body-do-effect clause)))
-    (byte-compile-out-tag donetag)))
+  (or (and byte-compile-cond-use-jump-table
+           (byte-compile-cond-jump-table clauses))
+    (let ((donetag (byte-compile-make-tag))
+          nexttag clause)
+      (while (setq clauses (cdr clauses))
+        (setq clause (car clauses))
+        (cond ((or (eq (car clause) t)
+                   (and (eq (car-safe (car clause)) 'quote)
+                        (car-safe (cdr-safe (car clause)))))
+               ;; Unconditional clause
+               (setq clause (cons t clause)
+                     clauses nil))
+              ((cdr clauses)
+               (byte-compile-form (car clause))
+               (if (null (cdr clause))
+                   ;; First clause is a singleton.
+                   (byte-compile-goto-if t byte-compile--for-effect donetag)
+                 (setq nexttag (byte-compile-make-tag))
+                 (byte-compile-goto 'byte-goto-if-nil nexttag)
+                 (byte-compile-maybe-guarded (car clause)
+                   (byte-compile-body (cdr clause) byte-compile--for-effect))
+                 (byte-compile-goto 'byte-goto donetag)
+                 (byte-compile-out-tag nexttag)))))
+      ;; Last clause
+      (let ((guard (car clause)))
+        (and (cdr clause) (not (eq guard t))
+             (progn (byte-compile-form guard)
+                    (byte-compile-goto-if nil byte-compile--for-effect donetag)
+                    (setq clause (cdr clause))))
+        (byte-compile-maybe-guarded guard
+          (byte-compile-body-do-effect clause)))
+      (byte-compile-out-tag donetag))))

 (defun byte-compile-and (form)
   (let ((failtag (byte-compile-make-tag))
@@ -4528,7 +4706,7 @@ byte-compile-out-tag
  (and byte-compile-depth
              (not (= (cdr (cdr tag)) byte-compile-depth))
              (error "Compiler bug: depth conflict at tag %d" (car (cdr tag))))
- (setq byte-compile-depth (cdr (cdr tag))))
+         (setq byte-compile-depth (cdr (cdr tag))))
     (setcdr (cdr tag) byte-compile-depth)))

 (defun byte-compile-goto (opcode tag)
diff --git a/lisp/emacs-lisp/disass.el b/lisp/emacs-lisp/disass.el
index 97e45e070d..66673b4d26 100644
--- a/lisp/emacs-lisp/disass.el
+++ b/lisp/emacs-lisp/disass.el
@@ -221,9 +221,21 @@ disassemble-1
  ((memq op '(byte-constant byte-constant2))
  ;; it's a constant
  (setq arg (car arg))
- ;; but if the value of the constant is compiled code, then
- ;; recursively disassemble it.
- (cond ((or (byte-code-function-p arg)
+                 ;; if the succeeding op is byte-switch, display the jump table
+                 ;; used
+ (cond ((eq (car-safe (car-safe (cdr lap))) 'byte-switch)
+                         (insert (format "<jump-table-%s ("
(hash-table-test arg)))
+                         (let ((first-time t))
+                           (maphash #'(lambda (value tag)
+                                        (if first-time
+                                            (setq first-time nil)
+                                          (insert " "))
+                                        (insert (format "%s %s" value
(cadr tag))))
+                                    arg))
+                         (insert ")>"))
+                  ;; if the value of the constant is compiled code, then
+                  ;; recursively disassemble it.
+                  ((or (byte-code-function-p arg)
     (and (consp arg) (functionp arg)
  (assq 'byte-code arg))
     (and (eq (car-safe arg) 'macro)
diff --git a/src/bytecode.c b/src/bytecode.c
index 0f7420c19e..f9531761b3 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -267,6 +267,8 @@ DEFINE (Bstack_set,  0262) \
 DEFINE (Bstack_set2, 0263) \
 DEFINE (BdiscardN,   0266) \
  \
+DEFINE (Bswitch, 0267)                                                  \
+                                                                        \
 DEFINE (Bconstant, 0300)

 enum byte_code_op
@@ -1411,6 +1413,25 @@ exec_byte_code (Lisp_Object bytestr,
Lisp_Object vector, Lisp_Object maxdepth,
   DISCARD (op);
   NEXT;

+        CASE (Bswitch):
+          {
+            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
+            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;
+            }
+          }
+          NEXT;
+
  CASE_DEFAULT
  CASE (Bconstant):
   if (BYTE_CODE_SAFE

[-- Attachment #2: switch.diff --]
[-- Type: text/plain, Size: 22007 bytes --]

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 13f885448a..888a5f8500 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -185,6 +185,7 @@
 (require 'bytecomp)
 (eval-when-compile (require 'cl-lib))
 (require 'macroexp)
+(require 'subr-x)
 
 (defun byte-compile-log-lap-1 (format &rest args)
   ;; Newer byte codes for stack-ref make the slot 0 non-nil again.
@@ -1356,7 +1357,7 @@ byte-decompile-bytecode
 (defun byte-decompile-bytecode-1 (bytes constvec &optional make-spliceable)
   (let ((length (length bytes))
         (bytedecomp-ptr 0) optr tags bytedecomp-op offset
-	lap tmp)
+	lap tmp last-constant)
     (while (not (= bytedecomp-ptr length))
       (or make-spliceable
 	  (push bytedecomp-ptr lap))
@@ -1385,7 +1386,8 @@ byte-decompile-bytecode-1
 			    (or (assq tmp byte-compile-variables)
                                 (let ((new (list tmp)))
                                   (push new byte-compile-variables)
-                                  new)))))
+                                  new)))
+                   last-constant tmp))
 	    ((eq bytedecomp-op 'byte-stack-set2)
 	     (setq bytedecomp-op 'byte-stack-set))
 	    ((and (eq bytedecomp-op 'byte-discardN) (>= offset #x80))
@@ -1394,7 +1396,34 @@ byte-decompile-bytecode-1
 	     ;; lapcode, we represent this by using a different opcode
 	     ;; (with the flag removed from the operand).
 	     (setq bytedecomp-op 'byte-discardN-preserve-tos)
-	     (setq offset (- offset #x80))))
+	     (setq offset (- offset #x80)))
+            ((eq bytedecomp-op 'byte-switch)
+             (cl-assert (hash-table-p last-constant) nil
+                        "byte-switch used without preceeding hash table")
+             ;; We cannot use the original hash table referenced in the op,
+             ;; so we create a copy of it, and replace the addresses with
+             ;; TAGs.
+             (let ((orig-table last-constant))
+               (cl-loop for e across constvec
+                        when (eq e last-constant)
+                        do (setq last-constant (copy-hash-table e))
+                        and return nil)
+               ;; 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)
+                              (puthash value newtag last-constant)))
+                        last-constant)
+               ;; Replace the hash table referenced in the lapcode with our
+               ;; modified one.
+               (cl-loop for el in-ref lap
+                        when (and (listp el) ;; make sure we're at the correct op
+                                  (eq (nth 1 el) 'byte-constant)
+                                  (eq (nth 2 el) orig-table))
+                        do (setf (nth 2 el) last-constant) and return nil))))
       ;; lap = ( [ (pc . (op . arg)) ]* )
       (push (cons optr (cons bytedecomp-op (or offset 0)))
             lap)
@@ -1728,7 +1757,10 @@ byte-optimize-lapcode
 	      ;; unused-TAG: --> <deleted>
 	      ;;
 	      ((and (eq 'TAG (car lap0))
-		    (not (rassq lap0 lap)))
+		    (not (rassq lap0 lap))
+                    (cl-loop for table in byte-compile-jump-tables
+                             when (member lap0 (hash-table-values table))
+                             return nil finally return t))
 	       (and (memq byte-optimize-log '(t byte))
 		    (byte-compile-log "  unused tag %d removed" (nth 1 lap0)))
 	       (setq lap (delq lap0 lap)
@@ -1736,9 +1768,15 @@ byte-optimize-lapcode
 	      ;;
 	      ;; goto   ... --> goto   <delete until TAG or end>
 	      ;; return ... --> return <delete until TAG or end>
-	      ;;
+	      ;; (unless a jump-table is being used, where deleting may affect
+              ;; other valid case bodies)
+              ;;
 	      ((and (memq (car lap0) '(byte-goto byte-return))
-		    (not (memq (car lap1) '(TAG nil))))
+		    (not (memq (car lap1) '(TAG nil)))
+                    ;; FIXME: Instead of deferring simply when jump-tables are
+                    ;; being used, keep a list of tags used for switch tags and
+                    ;; use them instead (see `byte-compile-inline-lapcode').
+                    (not byte-compile-jump-tables))
 	       (setq tmp rest)
 	       (let ((i 0)
 		     (opt-p (memq byte-optimize-log '(t lap)))
diff --git a/lisp/emacs-lisp/bytecomp.el b/lisp/emacs-lisp/bytecomp.el
index 63be7e208b..d5a163e5fd 100644
--- a/lisp/emacs-lisp/bytecomp.el
+++ b/lisp/emacs-lisp/bytecomp.el
@@ -223,6 +223,11 @@ byte-compile-delete-errors
   :group 'bytecomp
   :type 'boolean)
 
+(defcustom byte-compile-cond-use-jump-table t
+  "Compile `cond' clauses to a jump table implementation (using a hash-table)."
+  :group 'bytecomp
+  :type 'boolean)
+
 (defvar byte-compile-dynamic nil
   "If non-nil, compile function bodies so they load lazily.
 They are hidden in comments in the compiled file,
@@ -412,6 +417,8 @@ byte-compile-call-tree-sort
 		 (const calls+callers) (const nil)))
 
 (defvar byte-compile-debug nil)
+(defvar byte-compile-jump-tables nil
+  "List of all jump tables used during compilation of this form.")
 (defvar byte-compile-constants nil
   "List of all constants encountered during compilation of this form.")
 (defvar byte-compile-variables nil
@@ -747,6 +754,10 @@ byte-extrude-byte-code-vectors
 ;; `byte-compile-lapcode').
 (defconst byte-discardN-preserve-tos byte-discardN)
 
+(byte-defop 183 -2 byte-switch
+ "to take a hash table and a value from the stack, and jump to the address
+the value maps to, if any.")
+
 ;; unused: 182-191
 
 (byte-defop 192  1 byte-constant	"for reference to a constant")
@@ -823,7 +834,7 @@ byte-compile-lapcode
 	op off			; Operation & offset
 	opcode			; numeric value of OP
 	(bytes '())		; Put the output bytes here
-	(patchlist nil))	; List of gotos to patch
+	(patchlist nil))        ; List of gotos to patch
     (dolist (lap-entry lap)
       (setq op (car lap-entry)
 	    off (cdr lap-entry))
@@ -905,6 +916,11 @@ byte-compile-lapcode
       ;; FIXME: Replace this by some workaround.
       (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))))
     (apply 'unibyte-string (nreverse bytes))))
 
 \f
@@ -1954,7 +1970,8 @@ byte-compile-from-buffer
 ;; 	(edebug-all-defs nil)
 ;; 	(edebug-all-forms nil)
 	;; Simulate entry to byte-compile-top-level
-	(byte-compile-constants nil)
+        (byte-compile-jump-tables nil)
+        (byte-compile-constants nil)
 	(byte-compile-variables nil)
 	(byte-compile-tag-number 0)
 	(byte-compile-depth 0)
@@ -2250,7 +2267,8 @@ byte-compile-flush-pending
 	      byte-compile-variables nil
 	      byte-compile-depth 0
 	      byte-compile-maxdepth 0
-	      byte-compile-output nil))))
+	      byte-compile-output nil
+              byte-compile-jump-tables nil))))
 
 (defvar byte-compile-force-lexical-warnings nil)
 
@@ -2862,7 +2880,8 @@ byte-compile-top-level
 	(byte-compile-maxdepth 0)
         (byte-compile--lexical-environment lexenv)
         (byte-compile-reserved-constants (or reserved-csts 0))
-	(byte-compile-output nil))
+	(byte-compile-output nil)
+        (byte-compile-jump-tables nil))
     (if (memq byte-optimize '(t source))
 	(setq form (byte-optimize-form form byte-compile--for-effect)))
     (while (and (eq (car-safe form) 'progn) (null (cdr (cdr form))))
@@ -3114,15 +3133,49 @@ byte-compile-inline-lapcode
   ;; happens to be true for byte-code generated by bytecomp.el without
   ;; lexical-binding, but it's not true in general, and it's not true for
   ;; code output by bytecomp.el with lexical-binding.
-  (let ((endtag (byte-compile-make-tag)))
+  ;; We also restore the value of `byte-compile-depth' and remove TAG depths
+  ;; accordingly when inlining byte-switch lap code, as documented in
+  ;; `byte-compile-cond-jump-table'.
+  (let ((endtag (byte-compile-make-tag))
+        last-jump-tag ;; last TAG we have jumped to
+        last-depth ;; last value of `byte-compile-depth'
+        last-constant ;; value of the last constant encountered
+        last-switch ;; whether the last op encountered was byte-switch
+        switch-tags ;; a list of tags that byte-switch could jump to
+        ;; a list of tags byte-switch will jump to, if the value doesn't
+        ;; match any entry in the hash table
+        switch-default-tags)
     (dolist (op lap)
       (cond
-       ((eq (car op) 'TAG) (byte-compile-out-tag op))
-       ((memq (car op) byte-goto-ops) (byte-compile-goto (car op) (cdr op)))
+       ((eq (car op) 'TAG)
+        (when (or (member op switch-tags) (member op switch-default-tags))
+          (when last-jump-tag
+            (setcdr (cdr last-jump-tag) nil))
+          (setq byte-compile-depth last-depth
+                last-jump-tag nil))
+        (byte-compile-out-tag op))
+       ((memq (car op) byte-goto-ops)
+        (setq last-depth byte-compile-depth
+              last-jump-tag (cdr op))
+        (byte-compile-goto (car op) (cdr op))
+        (when last-switch
+          (push (cdr op) switch-default-tags)
+          (setcdr (cdr (cdr op)) nil)
+          (setq byte-compile-depth last-depth
+                last-switch nil)))
        ((eq (car op) 'byte-return)
         (byte-compile-discard (- byte-compile-depth end-depth) t)
         (byte-compile-goto 'byte-goto endtag))
-       (t (byte-compile-out (car op) (cdr op)))))
+       (t
+        (when (eq (car op) 'byte-switch)
+          (push last-constant byte-compile-jump-tables)
+          (setq last-switch t)
+          (maphash #'(lambda (_k tag)
+                       (push tag switch-tags))
+                   last-constant))
+        (setq last-constant (and (eq (car op) 'byte-constant) (cadr op)))
+        (setq last-depth byte-compile-depth)
+        (byte-compile-out (car op) (cdr op)))))
     (byte-compile-out-tag endtag)))
 
 (defun byte-compile-unfold-bcf (form)
@@ -3951,37 +4004,162 @@ byte-compile-if
 	(byte-compile-out-tag donetag))))
   (setq byte-compile--for-effect nil))
 
+(defun byte-compile-cond-vars (obj1 obj2)
+  ;; We make sure that of OBJ1 and OBJ2, one of them is a symbol,
+  ;; and the other is a constant expression whose value can be
+  ;; compared with `eq' (with `macroexp-const-p').
+  (or
+   (and (symbolp obj1) (macroexp-const-p obj2) (cons obj1 obj2))
+   (and (symbolp obj2) (macroexp-const-p obj1) (cons obj2 obj1))))
+
+(defun byte-compile-cond-jump-table-info (clauses)
+  "If CLAUSES is a `cond' form where:
+The condition for each clause is of the form (TEST VAR VALUE).
+VAR is a variable.
+TEST and VAR are the same throughout all conditions.
+VALUE is either a constant or a quoted form.
+
+Return a list of the form ((TEST . VAR)  ((VALUE BODY) ...))"
+  (let ((cases '())
+        (ok t)
+        prev-var prev-test)
+    (and (catch 'break
+           (dolist (clause (cdr clauses) ok)
+             (let* ((condition (car clause))
+                    (test (car-safe condition))
+                    (vars (when (consp condition)
+                            (byte-compile-cond-vars (cadr condition) (cl-caddr condition))))
+                    (obj1 (car-safe vars))
+                    (obj2 (cdr-safe vars))
+                    (body (cdr-safe clause)))
+               (unless prev-var
+                 (setq prev-var obj1))
+               (unless prev-test
+                 (setq prev-test test))
+               (if (and obj1 (memq test '(eq eql equal))
+                        (consp condition)
+                        (eq test prev-test)
+                        (eq obj1 prev-var)
+                        ;; discard duplicate clauses
+                        (not (assq obj2 cases)))
+                   (push (list (if (consp obj2) (eval obj2) obj2) body) cases)
+                 (if (eq condition t)
+                     (progn (push (list 'default body) cases)
+                            (throw 'break t))
+                   (setq ok nil)
+                   (throw 'break nil))))))
+         (list (cons prev-test prev-var) (nreverse cases)))))
+
+(defun byte-compile-cond-jump-table (clauses)
+  (let* ((table-info (byte-compile-cond-jump-table-info clauses))
+         (test (caar table-info))
+         (var (cdar table-info))
+         (cases (cadr table-info))
+         jump-table test-obj body tag donetag default-tag default-case)
+    (when (and cases (not (= (length cases) 1)))
+      ;; TODO: Once :linear-search is implemented for `make-hash-table'
+      ;; set it to `t' for cond forms with a small number of cases.
+      (setq jump-table (make-hash-table :test test
+                                        :purecopy t
+                                        :size (if (assq 'default cases)
+                                                  (1- (length cases))
+                                                (length cases)))
+            default-tag (byte-compile-make-tag)
+            donetag (byte-compile-make-tag))
+      ;; The structure of byte-switch code:
+      ;;
+      ;; varref var
+      ;; constant #s(hash-table purecopy t data (val1 (TAG1) val2 (TAG2)))
+      ;; switch
+      ;; goto DEFAUT-TAG
+      ;; TAG1
+      ;; <clause body>
+      ;; goto DONETAG
+      ;; TAG2
+      ;; <clause body>
+      ;; goto DONETAG
+      ;; DEFAULT-TAG
+      ;; <body for `t' clause, if any (else `constant nil')>
+      ;; DONETAG
+
+      (byte-compile-variable-ref var)
+      (byte-compile-push-constant jump-table)
+      (byte-compile-out 'byte-switch)
+
+      ;; When the opcode argument is `byte-goto', `byte-compile-goto' sets
+      ;; `byte-compile-depth' to `nil'. However, we need `byte-compile-depth'
+      ;; to be non-nil for generating tags for all cases. Since
+      ;; `byte-compile-depth' will increase by atmost 1 after compiling
+      ;; all of the clause (which is further enforced by cl-assert below)
+      ;; it should be safe to preserve it's value.
+      (let ((byte-compile-depth byte-compile-depth))
+        (byte-compile-goto 'byte-goto default-tag))
+
+      (when (assq 'default cases)
+        (setq default-case (cadr (assq 'default cases))
+              cases (butlast cases 1)))
+
+      (dolist (case cases)
+        (setq tag (byte-compile-make-tag)
+              test-obj (nth 0 case)
+              body (nth 1 case))
+        (byte-compile-out-tag tag)
+        (puthash test-obj tag jump-table)
+
+        (let ((byte-compile-depth byte-compile-depth)
+              (init-depth byte-compile-depth))
+          ;; Since `byte-compile-body' might increase `byte-compile-depth'
+          ;; by 1, not preserving it's value will cause it to potentially
+          ;; increase by one for every clause body compiled, causing
+          ;; depth/tag conflicts or violating asserts down the road.
+          ;; To make sure `byte-compile-body' itself doesn't violate this,
+          ;; we use `cl-assert'.
+          (byte-compile-body body byte-compile--for-effect)
+          (cl-assert (or (= byte-compile-depth init-depth)
+                         (= byte-compile-depth (1+ init-depth))))
+          (byte-compile-goto 'byte-goto donetag)
+          (setcdr (cdr donetag) nil)))
+
+      (byte-compile-out-tag default-tag)
+      (if default-case
+          (byte-compile-body-do-effect default-case)
+        (byte-compile-constant nil))
+      (byte-compile-out-tag donetag)
+      (push jump-table byte-compile-jump-tables))))
+
 (defun byte-compile-cond (clauses)
-  (let ((donetag (byte-compile-make-tag))
-	nexttag clause)
-    (while (setq clauses (cdr clauses))
-      (setq clause (car clauses))
-      (cond ((or (eq (car clause) t)
-		 (and (eq (car-safe (car clause)) 'quote)
-		      (car-safe (cdr-safe (car clause)))))
-	     ;; Unconditional clause
-	     (setq clause (cons t clause)
-		   clauses nil))
-	    ((cdr clauses)
-	     (byte-compile-form (car clause))
-	     (if (null (cdr clause))
-		 ;; First clause is a singleton.
-		 (byte-compile-goto-if t byte-compile--for-effect donetag)
-	       (setq nexttag (byte-compile-make-tag))
-	       (byte-compile-goto 'byte-goto-if-nil nexttag)
-	       (byte-compile-maybe-guarded (car clause)
-		 (byte-compile-body (cdr clause) byte-compile--for-effect))
-	       (byte-compile-goto 'byte-goto donetag)
-	       (byte-compile-out-tag nexttag)))))
-    ;; Last clause
-    (let ((guard (car clause)))
-      (and (cdr clause) (not (eq guard t))
-	   (progn (byte-compile-form guard)
-		  (byte-compile-goto-if nil byte-compile--for-effect donetag)
-		  (setq clause (cdr clause))))
-      (byte-compile-maybe-guarded guard
-	(byte-compile-body-do-effect clause)))
-    (byte-compile-out-tag donetag)))
+  (or (and byte-compile-cond-use-jump-table
+           (byte-compile-cond-jump-table clauses))
+    (let ((donetag (byte-compile-make-tag))
+          nexttag clause)
+      (while (setq clauses (cdr clauses))
+        (setq clause (car clauses))
+        (cond ((or (eq (car clause) t)
+                   (and (eq (car-safe (car clause)) 'quote)
+                        (car-safe (cdr-safe (car clause)))))
+               ;; Unconditional clause
+               (setq clause (cons t clause)
+                     clauses nil))
+              ((cdr clauses)
+               (byte-compile-form (car clause))
+               (if (null (cdr clause))
+                   ;; First clause is a singleton.
+                   (byte-compile-goto-if t byte-compile--for-effect donetag)
+                 (setq nexttag (byte-compile-make-tag))
+                 (byte-compile-goto 'byte-goto-if-nil nexttag)
+                 (byte-compile-maybe-guarded (car clause)
+                   (byte-compile-body (cdr clause) byte-compile--for-effect))
+                 (byte-compile-goto 'byte-goto donetag)
+                 (byte-compile-out-tag nexttag)))))
+      ;; Last clause
+      (let ((guard (car clause)))
+        (and (cdr clause) (not (eq guard t))
+             (progn (byte-compile-form guard)
+                    (byte-compile-goto-if nil byte-compile--for-effect donetag)
+                    (setq clause (cdr clause))))
+        (byte-compile-maybe-guarded guard
+          (byte-compile-body-do-effect clause)))
+      (byte-compile-out-tag donetag))))
 
 (defun byte-compile-and (form)
   (let ((failtag (byte-compile-make-tag))
@@ -4528,7 +4706,7 @@ byte-compile-out-tag
 	(and byte-compile-depth
              (not (= (cdr (cdr tag)) byte-compile-depth))
              (error "Compiler bug: depth conflict at tag %d" (car (cdr tag))))
-	(setq byte-compile-depth (cdr (cdr tag))))
+         (setq byte-compile-depth (cdr (cdr tag))))
     (setcdr (cdr tag) byte-compile-depth)))
 
 (defun byte-compile-goto (opcode tag)
diff --git a/lisp/emacs-lisp/disass.el b/lisp/emacs-lisp/disass.el
index 97e45e070d..66673b4d26 100644
--- a/lisp/emacs-lisp/disass.el
+++ b/lisp/emacs-lisp/disass.el
@@ -221,9 +221,21 @@ disassemble-1
 		((memq op '(byte-constant byte-constant2))
 		 ;; it's a constant
 		 (setq arg (car arg))
-		 ;; but if the value of the constant is compiled code, then
-		 ;; recursively disassemble it.
-		 (cond ((or (byte-code-function-p arg)
+                 ;; if the succeeding op is byte-switch, display the jump table
+                 ;; used
+		 (cond ((eq (car-safe (car-safe (cdr lap))) 'byte-switch)
+                         (insert (format "<jump-table-%s (" (hash-table-test arg)))
+                         (let ((first-time t))
+                           (maphash #'(lambda (value tag)
+                                        (if first-time
+                                            (setq first-time nil)
+                                          (insert " "))
+                                        (insert (format "%s %s" value (cadr tag))))
+                                    arg))
+                         (insert ")>"))
+                  ;; if the value of the constant is compiled code, then
+                  ;; recursively disassemble it.
+                  ((or (byte-code-function-p arg)
 			    (and (consp arg) (functionp arg)
 				 (assq 'byte-code arg))
 			    (and (eq (car-safe arg) 'macro)
diff --git a/src/bytecode.c b/src/bytecode.c
index 0f7420c19e..f9531761b3 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -267,6 +267,8 @@ DEFINE (Bstack_set,  0262)						\
 DEFINE (Bstack_set2, 0263)						\
 DEFINE (BdiscardN,   0266)						\
 									\
+DEFINE (Bswitch, 0267)                                                  \
+                                                                        \
 DEFINE (Bconstant, 0300)
 
 enum byte_code_op
@@ -1411,6 +1413,25 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
 	  DISCARD (op);
 	  NEXT;
 
+        CASE (Bswitch):
+          {
+            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
+            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;
+            }
+          }
+          NEXT;
+
 	CASE_DEFAULT
 	CASE (Bconstant):
 	  if (BYTE_CODE_SAFE

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

[Stefan Monnier]

> The following patch adds support for a new op `switch` to the Emacs
> bytecode VM and compiler.

I guess the motivation is to speed up some code.
Did you make any measurements to see what kind of effect it has?

> However, since switch replaces all goto-if-nil code, I've used a few

Hmm... so goto-if-nil is never used any more?  Aren't there cases where
byte-switch results in slower code than goto-if-nil?


        Stefan

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

[Vibhav Pant]

On Tue, Feb 7, 2017 at 12:00 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> Hmm... so goto-if-nil is never used any more?  Aren't there cases where
> byte-switch results in slower code than goto-if-nil?

Once linear search for gethash when the number of keys are small is
implemented, byte-switch should still be faster, as all byte-goto-if-nil
and byte-goto-if-nil-else-pop bytecode is "replaced" with native linear
search code.

-- 
Vibhav Pant
vibhavp@gmail.com

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

[Stefan Monnier]

>> Hmm... so goto-if-nil is never used any more?  Aren't there cases where
>> byte-switch results in slower code than goto-if-nil?
> Once linear search for gethash when the number of keys are small is
> implemented, byte-switch should still be faster, as all byte-goto-if-nil
> and byte-goto-if-nil-else-pop bytecode is "replaced" with native linear
> search code.

Does that mean you answered "yes" to the first question?
I thought goto-if-nil is also used in other circumstances.


        Stefan

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

[Vibhav Pant]

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

On 07-Feb-2017 8:11 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:

>> Hmm... so goto-if-nil is never used any more?  Aren't there cases where
>> byte-switch results in slower code than goto-if-nil?
> Once linear search for gethash when the number of keys are small is
> implemented, byte-switch should still be faster, as all byte-goto-if-nil
> and byte-goto-if-nil-else-pop bytecode is "replaced" with native linear
> search code.

Does that mean you answered "yes" to the first question?
I thought goto-if-nil is also used in other circumstances.


No. goto-if-nil is still used to compile `if` and other conditional forms.
It's also used for cond forms which cannot use byte-switch, like:
(cond ((eq v 1) 'foo)
            ((stringp v) 'bar))
Or forms where some not all clauses use the same test function, since the
hash table can only use a single test.

[-- Attachment #2: Type: text/html, Size: 1490 bytes --]

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

[Vibhav Pant]

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

On Tue, Feb 7, 2017 at 12:00 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> The following patch adds support for a new op `switch` to the Emacs
>> bytecode VM and compiler.
>
> I guess the motivation is to speed up some code.
> Did you make any measurements to see what kind of effect it has?

The attached benchmark code took 9.409541956 seconds when compiled
without switch,
and 0.20807168799999998 seconds (97% speedup) when compiled with switch. It
generates a cond clause with a thousand clauses comparing a variable
with random integer values, with the last clause containing the actual
value. However,
since it's a synthetic benchmark, real world code should be better indicator of
performance improvement.

-- 
Vibhav Pant
vibhavp@gmail.com

[-- Attachment #2: switch-benchmark.el --]
[-- Type: text/x-emacs-lisp, Size: 291 bytes --]

(require 'cl-lib)
(require 'benchmark)

(defmacro random-cases (cases var actual-value)
  `(cond ,@(cl-loop for i from 0 to cases
		    collect `((eq ,var ,(random)) ,i))
	 ((eq ,var ,actual-value) t)))

(message "%s"
	 (benchmark-run-compiled 100000 (let ((v 2)) (random-cases 3000 v 2))))

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

[Clément Pit-Claudel]

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

On 2017-02-07 08:50, Vibhav Pant wrote:
> On Tue, Feb 7, 2017 at 12:00 AM, Stefan Monnier
> <monnier@iro.umontreal.ca> wrote:
>>> The following patch adds support for a new op `switch` to the Emacs
>>> bytecode VM and compiler.
>>
>> I guess the motivation is to speed up some code.
>> Did you make any measurements to see what kind of effect it has?
> 
> The attached benchmark code took 9.409541956 seconds when compiled
> without switch,
> and 0.20807168799999998 seconds (97% speedup) when compiled with switch. It
> generates a cond clause with a thousand clauses comparing a variable
> with random integer values, with the last clause containing the actual
> value. However,
> since it's a synthetic benchmark, real world code should be better indicator of
> performance improvement.

I've attached another benchmark, which evaluates arithmetic expressions.  On this, byte-switch seems to be a bit slower:

    $ rm -f *.elc; emacs-byte-switch -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs-byte-switch -Q --batch -L . -l benchmark-expr.el

    real	0m4.193s
    user	0m4.188s
    sys	0m0.000s

    $ rm -f *.elc; emacs-master -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs-master -Q --batch -L . -l benchmark-expr.el

    real	0m3.956s
    user	0m3.944s
    sys	0m0.008s

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 :)

Thanks for your work on this!

Cheers,
Clément.

[-- Attachment #2: benchmark-expr.el --]
[-- Type: text/x-emacs-lisp, Size: 67 bytes --]

(require 'eval-expr)
(~/init-exprs)
(dotimes (_ 20) (~/benchmark))

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: eval-expr.el --]
[-- Type: text/x-emacs-lisp; name="eval-expr.el", Size: 2822 bytes --]

;;; eval-expr.el --- Simple eval-expruation benchmark for byte-switch  -*- lexical-binding: t; -*-

;; Copyright (C) 2017  Clément Pit-Claudel

;; Author: Clément Pit-Claudel <clement.pitclaudel@live.com>

;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

;;; Commentary:

;;; Code:

(require 'cl-lib)

(defun ~/eval-expr (expr context)
  "Eval EXPR in CONTEXT."
  (pcase expr
    (`(const ,c)
     c)
    (`(var ,x)
     (alist-get x context))
    (`(unop ,op ,expr)
     (let ((res (~/eval-expr expr context)))
       (pcase op
         (`+ res)
         (`- (- res))
         (`! (lognot res)))))
    (`(binop ,op ,l ,r)
     (let ((lres (~/eval-expr l context))
           (rres (~/eval-expr r context)))
       (pcase op
         (`+ (+ lres rres))
         (`- (- lres rres))
         (`* (* lres rres)))))))

(defun ~/size (expr)
  "Compute the size of EXPR."
  (pcase expr
    ((or `(const ,_) `(var ,_)) 1)
    (`(unop ,_ ,expr)
     (1+ (~/size expr)))
    (`(binop ,_ ,l ,r)
     (+ 1 (~/size l) (~/size r)))))

(defun ~/mkexpr-1 (const-t var-t unop-t binop-t vars max-depth)
  (cl-decf max-depth)
  (let ((rnd (random binop-t)))
    (cond
     ((or (< rnd const-t) (= max-depth 0))
      `(const ,(random 1000)))
     ((< rnd var-t)
      `(var ,(aref vars (random (length vars)))))
     ((< rnd unop-t)
      `(unop ,(aref [+ - !] (random 3))
             ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth)))
     ((< rnd binop-t)
      `(binop ,(aref [+ - *] (random 3))
              ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth)
              ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth))))))

(defun ~/mkexpr (const-p var-p unop-p binop-p vars max-depth)
  (let* ((const-t const-p)
         (var-t (+ const-t var-p))
         (unop-t (+ var-t unop-p))
         (binop-t (+ unop-t binop-p)))
    (~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth)))

(defvar ~/exprs nil)

(defun ~/init-exprs ()
  (setq ~/exprs nil)
  (dotimes (_ 5000)
    (push (~/mkexpr 1 1 2 4 [a b c] 15) ~/exprs)))

(defun ~/benchmark ()
  (apply #'+ (mapcar #'~/size ~/exprs))
  (mapc (lambda (e) (~/eval-expr e '((a . 1) (b . 2) (c . 3)))) ~/exprs))

(provide 'eval-expr)
;;; eval-expr.el ends here

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

[Vibhav Pant]

[-- 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)

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

[Vibhav Pant]

On Wed, Feb 8, 2017 at 7:08 PM, Vibhav Pant <vibhavp@gmail.com> wrote:
> 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)

Looks like this is the incorrect way to linear-search a hash table, as
it's sometimes resulting
in duplicate hash table entries.

-- 
Vibhav Pant
vibhavp@gmail.com

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

[Vibhav Pant]

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

The jump address is stored in the hash table as (tag & 255 . tag >> 8),
where tag is the tag number from byte-compile-make-tah. The correct address
to jump to is thus calculated in the bytecode VM by car + cdr << 8. Is it
possible to make this calculation in bytecomp.el itself without the risk of
a potential overflow?

Vibhav Pant
vibhavp@gmail.com

[-- Attachment #2: Type: text/html, Size: 533 bytes --]

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

[Stefan Monnier]

>> +  if (HASH_TABLE_SIZE (h) <= 5 && h->test.cmpfn) {

Why not use the linear search when h->test.cmpfn is NULL
(i.e. for `eq` hash tables)?

>> +    /*Try doing a linear search first */

Nitpick: this should be 

        /* Try doing a linear search first.  */

Notice the space at the beginning and the double space after the end
of sentence.

>> +    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;
>> +  }

I think we should check hash_code before calling cmpfn.

> Looks like this is the incorrect way to linear-search a hash table, as
> it's sometimes resulting in duplicate hash table entries.

Maybe because it fails to set *hash ?


        Stefan

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

[Eli Zaretskii]

> From: Vibhav Pant <vibhavp@gmail.com>
> Date: Wed, 8 Feb 2017 19:08:12 +0530
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>,
> 	"emacs-devel@gnu.org" <emacs-devel@gnu.org>
> 
> 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.

Thanks.  Please mention in the comments that 5 is arbitrary, and
perhaps some considerations for choosing the value.

Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Tino Calancha]

Sorry if this is obvious, then just ignore.

I have a custom lib using `pcase' somewhere.  That lib is
compatible with Emacs25.
Usually i compile this lib against the master branch.  Then, i load
that very same resulting .elc in Emacs-25 and runs same as in Emacs-26.
(Maybe this is just wrong and i must keep separated .elc)

After the new bytecode those parts of the lib using pcase fail.
For instance, put the following in a file:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun test-case ()
   (let ((val "foo"))
     (pcase val
       ("foo" "foo")
       ("bar" "bar")
       (_ (error "Neither 'foo' nor 'bar'")))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
I) Compile under master branch.
II) Load the resultant .elc with Emacs-25
II) M-: (test-case)
;; Signal error: Invalid byte opcode: op=183, ptr=4

So, in conclusion:
From now on, we need to keep two separated .elc in such custom libs, 
right?

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Richard Copley]

On 23 February 2017 at 04:35, Tino Calancha <tino.calancha@gmail.com> wrote:
>
> Sorry if this is obvious, then just ignore.
>
> I have a custom lib using `pcase' somewhere.  That lib is
> compatible with Emacs25.
> Usually i compile this lib against the master branch.  Then, i load
> that very same resulting .elc in Emacs-25 and runs same as in Emacs-26.
> (Maybe this is just wrong and i must keep separated .elc)
>
> After the new bytecode those parts of the lib using pcase fail.
> For instance, put the following in a file:
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (defun test-case ()
>   (let ((val "foo"))
>     (pcase val
>       ("foo" "foo")
>       ("bar" "bar")
>       (_ (error "Neither 'foo' nor 'bar'")))))
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> I) Compile under master branch.
> II) Load the resultant .elc with Emacs-25
> II) M-: (test-case)
> ;; Signal error: Invalid byte opcode: op=183, ptr=4
>
> So, in conclusion:
> From now on, we need to keep two separated .elc in such custom libs, right?

Yes, ideally.

You need to arrange not to run byte-compiled libs in an earlier
version of Emacs than where they were compiled. This isn't a new
requirement. There has never been a guarantee that newer versions'
bytecode will run on older versions, but in reality incompatible
changes don't happen every day so at times you could get away with
ignoring the issue.

There are various options that avoid the problem.
* keep your `load-path' entries version specific
* don't byte compile libs that are shared between versions
* byte compile them with the earliest Emacs you'll use
* don't use different versions of Emacs

Eli recommended the first option (the same one you suggested) to me,
see #14513. In `emacs -Q' by default all `load-path' entries are in a
version-specific subdirectory.

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Tino Calancha]

On Thu, 23 Feb 2017, Richard Copley wrote:

> There are various options that avoid the problem.
> * keep your `load-path' entries version specific
> * don't byte compile libs that are shared between versions
> * byte compile them with the earliest Emacs you'll use
> * don't use different versions of Emacs
>
> Eli recommended the first option (the same one you suggested) to me,
> see #14513. In `emacs -Q' by default all `load-path' entries are in a
> version-specific subdirectory.
Thank very much for your clear answer!
I will be more careful with my initilizations.

Best regards,
Tino

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Vibhav Pant]

On Thu, Feb 23, 2017 at 2:06 PM Richard Copley <rcopley@gmail.com> wrote:
>
> On 23 February 2017 at 04:35, Tino Calancha <tino.calancha@gmail.com> wrote:
> >
> > Sorry if this is obvious, then just ignore.
> >
> > I have a custom lib using `pcase' somewhere.  That lib is
> > compatible with Emacs25.
> > Usually i compile this lib against the master branch.  Then, i load
> > that very same resulting .elc in Emacs-25 and runs same as in Emacs-26.
> > (Maybe this is just wrong and i must keep separated .elc)
> >
> > After the new bytecode those parts of the lib using pcase fail.
> > For instance, put the following in a file:
> > ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> > (defun test-case ()
> >   (let ((val "foo"))
> >     (pcase val
> >       ("foo" "foo")
> >       ("bar" "bar")
> >       (_ (error "Neither 'foo' nor 'bar'")))))
> > ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> > I) Compile under master branch.
> > II) Load the resultant .elc with Emacs-25
> > II) M-: (test-case)
> > ;; Signal error: Invalid byte opcode: op=183, ptr=4
> >
> > So, in conclusion:
> > From now on, we need to keep two separated .elc in such custom libs, right?
>
> Yes, ideally.
>
> You need to arrange not to run byte-compiled libs in an earlier
> version of Emacs than where they were compiled. This isn't a new
> requirement. There has never been a guarantee that newer versions'
> bytecode will run on older versions, but in reality incompatible
> changes don't happen every day so at times you could get away with
> ignoring the issue.
>
> There are various options that avoid the problem.
> * keep your `load-path' entries version specific
> * don't byte compile libs that are shared between versions
> * byte compile them with the earliest Emacs you'll use
> * don't use different versions of Emacs
>
Alternatively, in this case, you could compile your code with
`byte-compile-cond-use-jump-table' to nil.

> Eli recommended the first option (the same one you suggested) to me,
> see #14513. In `emacs -Q' by default all `load-path' entries are in a
> version-specific subdirectory.



-- 
Vibhav Pant
vibhavp@gmail.com
GPG: 7ED1 D48C 513C A024 BE3A  785F E3FB 28CB 6AB5 9598

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Stefan Monnier]

> I) Compile under master branch.
> II) Load the resultant .elc with Emacs-25

As explained by Richard, this is usually considered acceptable.
We don't really try to provide forward compatibility of byte-code files
between major versions.

This said, occasionally we try to reduce the pain a little: e.g. in
Emacs-25 a similar incompatibility was introduced for the compilation of
catch&condition-case, but the bytecodes were introduced a bit earlier.
IOW the incompatibility was fundamentally introduced in 24.4 (IIRC), but
the use of the this new feature was only enabled in Emacs-25.1, so files
compiled with 25.1 will usually work in 24.5 as well.


        Stefan

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Kaushal Modi]

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

I have this in my emacs config for a while now.

It works pretty well. It also allows you to use an older emacs version
without have to mess up the compiled elpa dir of the current version. The
only side-effect is that when switching major versions the package
updates/installs will happen independently.

(setq package-user-dir (format "%selpa_%s/"
                               user-emacs-directory emacs-major-version))

On Thu, Feb 23, 2017 at 8:42 AM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> > I) Compile under master branch.
> > II) Load the resultant .elc with Emacs-25
>
> As explained by Richard, this is usually considered acceptable.
> We don't really try to provide forward compatibility of byte-code files
> between major versions.
>
> This said, occasionally we try to reduce the pain a little: e.g. in
> Emacs-25 a similar incompatibility was introduced for the compilation of
> catch&condition-case, but the bytecodes were introduced a bit earlier.
> IOW the incompatibility was fundamentally introduced in 24.4 (IIRC), but
> the use of the this new feature was only enabled in Emacs-25.1, so files
> compiled with 25.1 will usually work in 24.5 as well.
>
>
>         Stefan
>
> --

Kaushal Modi

[-- Attachment #2: Type: text/html, Size: 2034 bytes --]

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Stefan Monnier]

> I have this in my emacs config for a while now.
> It works pretty well. It also allows you to use an older emacs version
> without have to mess up the compiled elpa dir of the current version. The
> only side-effect is that when switching major versions the package
> updates/installs will happen independently.
>
> (setq package-user-dir (format "%selpa_%s/"
>                                user-emacs-directory emacs-major-version))

If it works for you, that's great.  Personally I'd find it annoying to
have a different set of installed packages per Emacs version.

I hope Emacs can slowly move toward a model where Elisp is byte-compiled
automatically and kept in a version-specific place (call it a cache) so
users don't have to know about bytecode compatibility issues.


        Stefan

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Robert Weiner]

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

Hi Stefan:

I'm with you on your thoughts about removing the need for users to often
have to deal with byte-code or native-code compilation differences when
running different major versions of Emacs.  But it is now 2022 and the
situation seems to be much worse than it was five years ago.  Say you use
Emacs 27, 28 and 29, some with native compilation and some not.  But you
want to keep the same set of packages in use across all these
installations.  You can set your user package directory so you get
different package installs per Emacs version but we don't have a way to
synchronize the set so that any missing or removed ones are updated as you
move from version to version.

I just wanted to start some conversation on this and get people thinking
about how to make this easier on users of multiple Emacs versions.  It is
also an issue for package developers who want to test their package
compatibility across major versions.


On Thu, Feb 23, 2017 at 10:11 AM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> > I have this in my emacs config for a while now.
> > It works pretty well. It also allows you to use an older emacs version
> > without have to mess up the compiled elpa dir of the current version. The
> > only side-effect is that when switching major versions the package
> > updates/installs will happen independently.
> >
> > (setq package-user-dir (format "%selpa_%s/"
> >                                user-emacs-directory emacs-major-version))
>
> If it works for you, that's great.  Personally I'd find it annoying to
> have a different set of installed packages per Emacs version.
>
> I hope Emacs can slowly move toward a model where Elisp is byte-compiled
> automatically and kept in a version-specific place (call it a cache) so
> users don't have to know about bytecode compatibility issues.
>
>
>         Stefan
>
>

[-- Attachment #2: Type: text/html, Size: 2722 bytes --]

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Stefan Monnier]

> I'm with you on your thoughts about removing the need for users to often
> have to deal with byte-code or native-code compilation differences when
> running different major versions of Emacs.  But it is now 2022 and the
> situation seems to be much worse than it was five years ago.

What makes you think it is worse?

> Say you use Emacs 27, 28 and 29,

5 years ago, that would have been ... 25, 26, and 27, right?

> some with native compilation and some not.

AFAIK native compilation is fully transparent, so it shouldn't make
cause any extra trouble for the end-user (except maybe when it doesn't
work, but that's a separate issue).

> But you want to keep the same set of packages in use across all
> these installations.

The rule is that you need to compile with the oldest Emacs you're
still using.  Can you think of a package that can be compiled with
Emacs-27 but whose resulting .elc files won't work in Emacs-29?

AFAIK the only problem with a situation like the one you describe
is when the user install a package with Emacs-NN and then tries to use
this package with Emacs-MM where MM < NN.

Ideally, we should detect this situation and force a recompilation of
the package (the result of which should still work fine on Emacs-NN).
The .elc files already contain the needed info: they start with
";ELC<NN>" where <NN> is a char that represents the major version of
Emacs that compiled this file (char code 28 for both Emacs-28.1 and
Emacs-28.2).

So it's a "small matter" of adding code to detect when we load a file
that's been compiled by a "future Emacs" and then cause it to be recompiled.


        Stefan

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Vibhav Pant]

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

I think we should improve how compatibility checks are done with ELC files.
The current code is hardcoded only for adding a comment header denoting
that the bytecode uses dynamic docstrings and multibyte characters. IMO,
this should be replaced with a list of (FEATURE-NAME . COMPATIBLE-VERSION)
pairs that Emacs checks against while loading bytecode files.

Thoughts?


Vibhav Pant
vibhavp@gmail.com

On 23-Feb-2017 7:09 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:

> I) Compile under master branch.
> II) Load the resultant .elc with Emacs-25

As explained by Richard, this is usually considered acceptable.
We don't really try to provide forward compatibility of byte-code files
between major versions.

This said, occasionally we try to reduce the pain a little: e.g. in
Emacs-25 a similar incompatibility was introduced for the compilation of
catch&condition-case, but the bytecodes were introduced a bit earlier.
IOW the incompatibility was fundamentally introduced in 24.4 (IIRC), but
the use of the this new feature was only enabled in Emacs-25.1, so files
compiled with 25.1 will usually work in 24.5 as well.


        Stefan

[-- Attachment #2: Type: text/html, Size: 1763 bytes --]

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase

[Lars Brinkhoff]

Stefan Monnier wrote:
>> I) Compile under master branch.
>> II) Load the resultant .elc with Emacs-25
>
> As explained by Richard, this is usually considered acceptable.
> We don't really try to provide forward compatibility of byte-code files
> between major versions.
>
> This said, occasionally we try to reduce the pain a little: e.g. in
> Emacs-25 a similar incompatibility was introduced for the compilation of
> catch&condition-case, but the bytecodes were introduced a bit earlier.
> IOW the incompatibility was fundamentally introduced in 24.4 (IIRC), but
> the use of the this new feature was only enabled in Emacs-25.1, so files
> compiled with 25.1 will usually work in 24.5 as well.

It this something that should be done with records too?  E.g.  add the
new record functions to the emacs-25 branch, but not the changes to
cl-defstruct and defclass.

Re: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[raman]

Tino Calancha <tino.calancha@gmail.com> writes:

Likely related, I'm also noticing
 that code that compiles and run correctly against 25.1 and that used to
 compile and run error-free on Master just started breaking,
I'm still working on creating a small repro case.


But what I'm noticing:

With code compiled with lexical scoping,  defsubst forms appear to
behave differently when compiled vs evaled --- eval: no error, compile
and load == error.
> Sorry if this is obvious, then just ignore.
>
> I have a custom lib using `pcase' somewhere.  That lib is
> compatible with Emacs25.
> Usually i compile this lib against the master branch.  Then, i load
> that very same resulting .elc in Emacs-25 and runs same as in Emacs-26.
> (Maybe this is just wrong and i must keep separated .elc)
>
> After the new bytecode those parts of the lib using pcase fail.
> For instance, put the following in a file:
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (defun test-case ()
>   (let ((val "foo"))
>     (pcase val
>       ("foo" "foo")
>       ("bar" "bar")
>       (_ (error "Neither 'foo' nor 'bar'")))))
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> I) Compile under master branch.
> II) Load the resultant .elc with Emacs-25
> II) M-: (test-case)
> ;; Signal error: Invalid byte opcode: op=183, ptr=4
>
> So, in conclusion:
> From now on, we need to keep two separated .elc in such custom libs,
> right?
>

-- 

RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Drew Adams]

> With code compiled with lexical scoping,  defsubst forms appear to
> behave differently when compiled vs evaled

We should no longer be using defsubst anyway...

RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[T.V Raman]

Really? What should we be using, and when was defsubst deprecated? 

Drew Adams writes:
 > > With code compiled with lexical scoping,  defsubst forms appear to
 > > behave differently when compiled vs evaled
 > 
 > We should no longer be using defsubst anyway...

-- 

-- 

RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Drew Adams]

> Really? What should we be using, and when was defsubst deprecated?

defun or defmacro

It has not been deprecated.

I was expressing my opinion: It's rarely, if ever, needed,
and misguided uses of it instead of defun are bothersome.

RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[T.V Raman]

Please separate your personal opinion from fact. And asserting that
using defsubst is "misguided "  is not a useful way of carrying on a
conversation. 

Drew Adams writes:
 > > Really? What should we be using, and when was defsubst deprecated?
 > 
 > defun or defmacro
 > 
 > It has not been deprecated.
 > 
 > I was expressing my opinion: It's rarely, if ever, needed,
 > and misguided uses of it instead of defun are bothersome.

-- 

-- 

RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase [was: Add new bytecode op `switch' for implementing branch tables.]

[Drew Adams]

>  > > Really? What should we be using, and when was defsubst deprecated?
>  >
>  > defun or defmacro
>  >
>  > It has not been deprecated.
>  >
>  > I was expressing my opinion: It's rarely, if ever, needed,
>  > and misguided uses of it instead of defun are bothersome.
>
> Please separate your personal opinion from fact.

I just did.  But I should have added "IMHO" to my original message.
I agree that it could have been misinterpreted as a statement of
fact, that defsubst has been deprecated.  That's why I followed up
with a clarification.

> And asserting that using defsubst is "misguided "  is not a useful
> way of carrying on a conversation.

I did not say that defsubst is "misguided".  I said that misguided
uses of it instead of defun are bothersome.  Which they are (IMHO).

There may be uses of it that are still justified.  I'm not aware of
any, but it's not impossible that there still are some.

As a general guideline I think my suggestion (opinion) is reasonable:
We should no longer be using defsubst.  Feel free to point to specific
exceptions.

defsubst VS defun or defmacro [was RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase]

[Tino Calancha]

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



On Thu, 23 Feb 2017, T.V Raman wrote:

> Please separate your personal opinion from fact. And asserting that
> using defsubst is "misguided "  is not a useful way of carrying on a
> conversation.
>
> Drew Adams writes:
> > > Really? What should we be using, and when was defsubst deprecated?
> > > defun or defmacro
> > It has not been deprecated.
> > I was expressing my opinion: It's rarely, if ever, needed,
> > and misguided uses of it instead of defun are bothersome.

Hi Raman,
I guess Drew meant that defsubst makes debugging harder.  It also 
complicates advising.  I know he does extensively use of advising
in his own libraries.

The manual mention some disadvantages on using defsubst
in `(elisp) inline functions':

"Also, inline functions do not behave well with respect to debugging,
tracing, and advising (*note Advising Functions::).  Since ease of
debugging and the flexibility of redefining functions are important
features of Emacs, you should not make a function inline, even if it’s
small, unless its speed is really crucial, and you’ve timed the code to
verify that using ‘defun’ actually has performance problems."

I find worth to read the whole node.  I used to be confused about when
to use (to not) defsubst.

Re: defsubst VS defun or defmacro [was RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase]

[Eric Abrahamsen]

Tino Calancha <tino.calancha@gmail.com> writes:

> On Thu, 23 Feb 2017, T.V Raman wrote:
>
>> Please separate your personal opinion from fact. And asserting that
>> using defsubst is "misguided "  is not a useful way of carrying on a
>> conversation.
>>
>> Drew Adams writes:
>> > > Really? What should we be using, and when was defsubst deprecated?
>> > > defun or defmacro
>> > It has not been deprecated.
>> > I was expressing my opinion: It's rarely, if ever, needed,
>> > and misguided uses of it instead of defun are bothersome.
>
> Hi Raman,
> I guess Drew meant that defsubst makes debugging harder.  It also
> complicates advising.  I know he does extensively use of advising
> in his own libraries.
>
> The manual mention some disadvantages on using defsubst
> in `(elisp) inline functions':
>
> "Also, inline functions do not behave well with respect to debugging,
> tracing, and advising (*note Advising Functions::).  Since ease of
> debugging and the flexibility of redefining functions are important
> features of Emacs, you should not make a function inline, even if it’s
> small, unless its speed is really crucial, and you’ve timed the code to
> verify that using ‘defun’ actually has performance problems."
>
> I find worth to read the whole node.  I used to be confused about when
> to use (to not) defsubst.

I read that, and still have one question -- is there any practical
difference in the compiled performance of a defsubst vs a macro? I'd
been under the (probably unfounded) impression that if you were using a
macro just to DRY a code snippet, and not using any of its other
features, you'd get better performance with a defsubst.

But probably I just made that up? After byte compilation, is there any
difference between the two (again, assuming you're not using backquotes
or any special macro functionality)?

Eric

Re: defsubst VS defun or defmacro [was RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase]

[raman]

The rule of thumb I've used over the years:

1. Never use defmacro except when creating a special-form or special
notation AKA DSL 

2. Use defun except for short and often repeated forms that also need
speed, then I've used defsubst because they behave like functions for
all practical purposes such as mapcar.

3. I had done some timing in the early days of emacspeak, including
looking at what M-x disassemble produced, then tighten the inner loop of
emacspeak appropriately with defsubst.

4. What just broke is  calls to defsubst-defined functions from within
other defsubst --- independent of our various views on the misguidedness
or otherwise of defsubst, I believe this is a bug that might be worth
fixing since it breaks  working code in mysterious and unpredictable ways.
-- 

Re: defsubst VS defun or defmacro [was RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase]

[Eric Abrahamsen]

raman <raman@google.com> writes:

> The rule of thumb I've used over the years:
>
> 1. Never use defmacro except when creating a special-form or special
> notation AKA DSL 
>
> 2. Use defun except for short and often repeated forms that also need
> speed, then I've used defsubst because they behave like functions for
> all practical purposes such as mapcar.

Good, these were the principles I was working from, though in my case I
had no empirical data to support them :)

> 3. I had done some timing in the early days of emacspeak, including
> looking at what M-x disassemble produced, then tighten the inner loop of
> emacspeak appropriately with defsubst.
>
> 4. What just broke is  calls to defsubst-defined functions from within
> other defsubst --- independent of our various views on the misguidedness
> or otherwise of defsubst, I believe this is a bug that might be worth
> fixing since it breaks  working code in mysterious and unpredictable ways.

Okay, makes sense. I've never been tempted to use defsubsts for anything
more than two-liners, but I'll keep an eye on this.

Thanks!
Eric

Re: defsubst VS defun or defmacro [was RE: Compiled code in Emacs-26 will fail in Emacs-25 if use pcase]

[raman]

Tino Calancha <tino.calancha@gmail.com> writes:

:-) Emacspeak is probably one of the largest users of advice, so yes, I
know that particular downside.

The core of emacspeak uses defsubst in a number of places for speed ---
admittedly that was for speed in 1995, so it may well not be needed any
more.

I actually tried to change all defuns to defsubsts en-masse earlier
today -- but it broke things in strange and inexplicable ways  that
meant I had to revert that change.

I had never dug too deeply into this in emacs --- and my thought
initially after seeing the breakage in 26 was to say "just change all
defsubsts to defun " -- wish things were that simple.

> On Thu, 23 Feb 2017, T.V Raman wrote:
>
>> Please separate your personal opinion from fact. And asserting that
>> using defsubst is "misguided "  is not a useful way of carrying on a
>> conversation.
>>
>> Drew Adams writes:
>> > > Really? What should we be using, and when was defsubst deprecated?
>> > > defun or defmacro
>> > It has not been deprecated.
>> > I was expressing my opinion: It's rarely, if ever, needed,
>> > and misguided uses of it instead of defun are bothersome.
>
> Hi Raman,
> I guess Drew meant that defsubst makes debugging harder.  It also 
> complicates advising.  I know he does extensively use of advising
> in his own libraries.
>
> The manual mention some disadvantages on using defsubst
> in `(elisp) inline functions':
>
> "Also, inline functions do not behave well with respect to debugging,
> tracing, and advising (*note Advising Functions::).  Since ease of
> debugging and the flexibility of redefining functions are important
> features of Emacs, you should not make a function inline, even if it’s
> small, unless its speed is really crucial, and you’ve timed the code to
> verify that using ‘defun’ actually has performance problems."
>
> I find worth to read the whole node.  I used to be confused about when
> to use (to not) defsubst.
>

-- 

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

[Clément Pit-Claudel]

On 2017-02-08 08:38, Vibhav Pant wrote:
> On Tue, Feb 7, 2017 at 9:26 PM, Clément Pit-Claudel 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.

Thanks! Indeed, here are new timings:

$ rm -f *.elc; emacs-byte-switch -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs-byte-switch -Q --batch -L . -l benchmark-expr.el

real	0m3.703s
user	0m3.664s
sys	0m0.012s

$ rm -f *.elc; emacs -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs -Q --batch -L . -l benchmark-expr.el

real	0m3.878s
user	0m3.860s
sys	0m0.016s

Things still fluctuate, but the byte-switch branch is now consistently faster, by roughly 5% :)

Clément.

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

[Clément Pit-Claudel]

On 2017-02-08 08:38, Vibhav Pant wrote:
> 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.

Here's another test that your patch seems to improve a bit:

(defvar ~/maps nil)

(dotimes (n 50)
  (let ((map (make-hash-table :test #'eq)))
    (dotimes (k 2)
      (puthash k n map))
    (push map ~/maps)))

(benchmark-run-compiled 1000000
  (dolist (mp ~/maps)
    (gethash 1 mp)))

Are linear scans used on all small hash tables, then?

Clément.

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

[Vibhav Pant]

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

The linear search code has been shifted to bytecode.c, since there are a
couple of assumptions about the jump table that we can't make for a regular
hash table, so regular gethash shouldn't be affected.

Vibhav Pant
vibhavp@gmail.com

On 10-Feb-2017 12:45 AM, "Clément Pit-Claudel" <cpitclaudel@gmail.com>
wrote:

> On 2017-02-08 08:38, Vibhav Pant wrote:
> > 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.
>
> Here's another test that your patch seems to improve a bit:
>
> (defvar ~/maps nil)
>
> (dotimes (n 50)
>   (let ((map (make-hash-table :test #'eq)))
>     (dotimes (k 2)
>       (puthash k n map))
>     (push map ~/maps)))
>
> (benchmark-run-compiled 1000000
>   (dolist (mp ~/maps)
>     (gethash 1 mp)))
>
> Are linear scans used on all small hash tables, then?
>
> Clément.
>
>

[-- Attachment #2: Type: text/html, Size: 1878 bytes --]

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

[Clément Pit-Claudel]

On 2017-02-09 23:12, Vibhav Pant wrote:
> The linear search code has been shifted to bytecode.c, since there
> are a couple of assumptions about the jump table that we can't make
> for a regular hash table, so regular gethash shouldn't be affected.

That's unfortunate: linear scans for small hash tables sounded like a neat optimization.
What are the assumptions that make this unsuitable for regular gethash?

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

[Vibhav Pant]

On Fri, Feb 10, 2017 at 9:47 AM, Clément Pit-Claudel
<cpitclaudel@gmail.com> wrote:
> On 2017-02-09 23:12, Vibhav Pant wrote:
>> The linear search code has been shifted to bytecode.c, since there
>> are a couple of assumptions about the jump table that we can't make
>> for a regular hash table, so regular gethash shouldn't be affected.
>
> That's unfortunate: linear scans for small hash tables sounded like a neat optimization.
> What are the assumptions that make this unsuitable for regular gethash?


1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count directly
saves the cost of an array lookup.
2. Since the size equals the count, we don't need to check whether
HASH_HASH (h, i)
(the hash code) is non nil in every pass of the linear search loop
(maphash needs to
do this, before calling the providing function).


-- 
Vibhav Pant
vibhavp@gmail.com

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

[Stefan Monnier]

> 1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count
> directly saves the cost of an array lookup.

That doesn't invalidate the usefulness of a linear search.

> 2. Since the size equals the count, we don't need to check whether
> HASH_HASH (h, i) (the hash code) is non nil in every pass of the
> linear search loop (maphash needs to do this, before calling the
> providing function).

The linear search should compare HASH_HASH(h, i) to the search key's
hash anyway, so this comparison against nil is not needed.


        Stefan

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

[Vibhav Pant]

On Fri, Feb 10, 2017 at 11:37 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> 1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count
>> directly saves the cost of an array lookup.
>
> That doesn't invalidate the usefulness of a linear search.
Sure, but that makes it better (IMO) to have separate code for linear
searching the jump table.
>
>> 2. Since the size equals the count, we don't need to check whether
>> HASH_HASH (h, i) (the hash code) is non nil in every pass of the
>> linear search loop (maphash needs to do this, before calling the
>> providing function).
>
> The linear search should compare HASH_HASH(h, i) to the search key's
> hash anyway, so this comparison against nil is not needed.

Is that strictly needed, though? In the case of jump tables, there is
no extra space reserved
in h->key_and_value for more keys to be stored, so the vector looks like
`[:group 14 :version 20 :package-version 25 :link 30 :load 35 :tag 40
:set-after 46]`
(the jump table for (custom-handle-keyword)). IIUC, this negates the
need for comparing
HASH_HASH (h, i), as our linear search code is effectively

for i from 0 to h->count
 if h->key_and_value [2*i] == key_needed // HASH_KEY, the value we're
comparing against
  return h->key_and_value[2*i + 1]; // HASH_VALUE, the address switch
is to jump to

Having said that, I think `gethash` should have it's own linear search
code, with all the checks you mentioned.

-- 
Vibhav Pant
vibhavp@gmail.com

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

[Stefan Monnier]

>>> 1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count
>>> directly saves the cost of an array lookup.
>> That doesn't invalidate the usefulness of a linear search.
> Sure, but that makes it better (IMO) to have separate code for linear
> searching the jump table.

You mean to have a copy of the search in bytecode.c?  I guess that's
fine, I'm talking about the behavior of `gethash` only.

>> The linear search should compare HASH_HASH(h, i) to the search key's
>> hash anyway, so this comparison against nil is not needed.
> Is that strictly needed, though?

No, it's an optimisation to avoid calling Fequal unnecessarily.


        Stefan

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

[Vibhav Pant]

On Fri, Feb 10, 2017 at 8:42 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>>> The linear search should compare HASH_HASH(h, i) to the search key's
>>> hash anyway, so this comparison against nil is not needed.
>> Is that strictly needed, though?
>
> No, it's an optimisation to avoid calling Fequal unnecessarily.

Ah, I see, I've added this to the linear search code in bytecode.c.

-- 
Vibhav Pant
vibhavp@gmail.com

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

[Vibhav Pant]

Are there any other issues before I merge this into master?

On Fri, Feb 10, 2017 at 11:29 PM, Vibhav Pant <vibhavp@gmail.com> wrote:
> On Fri, Feb 10, 2017 at 8:42 PM, Stefan Monnier
> <monnier@iro.umontreal.ca> wrote:
>>>> The linear search should compare HASH_HASH(h, i) to the search key's
>>>> hash anyway, so this comparison against nil is not needed.
>>> Is that strictly needed, though?
>>
>> No, it's an optimisation to avoid calling Fequal unnecessarily.
>
> Ah, I see, I've added this to the linear search code in bytecode.c.
>
> --
> Vibhav Pant
> vibhavp@gmail.com



-- 
Vibhav Pant
vibhavp@gmail.com

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

[Paul Eggert]

On 02/10/2017 10:25 AM, Vibhav Pant wrote:
> Are there any other issues before I merge this into master?

For the C code, please use the usual style: space before paren in calls, 
GNU style indenting for curly braces, "/* " at start of comments, main 
operator like "||" at start of next line rather than at end of previous 
line.

One of the 'if's is overparenthesized, i.e., "if ((E))" where E is an 
ordinary expression and "if (E)" will do.

Prefer "if (BYTE_CODE_SAFE)" to "#ifdef BYTE_CODE_SAFE", as these days 
it's better to avoid the preprocessor when it's easy.

This comment:

                     /* Hash tables for switch are declared with :size 
set to the
                        exact number of cases, thus
                        HASH_TABLE_SIZE (h) == h->count.  */

is something that could be checked, no? Perhaps replace the comment with 
"if (BYTE_CODE_SAFE) eassert (HASH_TABLE_SIZE (h) == h->count);" and do 
the latter even with large hash tables?

If you change the loop from "for (i = 0; i < h->count; i++)" to "for (i 
= h->count; 0 <= --i; )", then you can merge the two copies of "op = 
XINT (HASH_VALUE (h, i)); goto ob_branch;" into one copy that is after 
the surrounding "if".

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

[Stefan Monnier]

>                     /* Hash tables for switch are declared with :size set to
> the
>                        exact number of cases, thus
>                        HASH_TABLE_SIZE (h) == h->count.  */

> is something that could be checked, no?

The code doesn't need this property.  All it assumes is that h->count is
not ridiculously larger than HASH_TABLE_SIZE(h), or that in case it is,
the user doesn't care about utmost performance.


        Stefan

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

[Vibhav Pant]

On Sat, Feb 11, 2017 at 2:17 AM, Paul Eggert <eggert@cs.ucla.edu> wrote:
> On 02/10/2017 10:25 AM, Vibhav Pant wrote:
>>
>> Are there any other issues before I merge this into master?
>
>
> For the C code, please use the usual style: space before paren in calls, GNU
> style indenting for curly braces, "/* " at start of comments, main operator
> like "||" at start of next line rather than at end of previous line.
>
> One of the 'if's is overparenthesized, i.e., "if ((E))" where E is an
> ordinary expression and "if (E)" will do.
>
> Prefer "if (BYTE_CODE_SAFE)" to "#ifdef BYTE_CODE_SAFE", as these days it's
> better to avoid the preprocessor when it's easy.
>
> This comment:
>
>                     /* Hash tables for switch are declared with :size set to
> the
>                        exact number of cases, thus
>                        HASH_TABLE_SIZE (h) == h->count.  */
>
> is something that could be checked, no? Perhaps replace the comment with "if
> (BYTE_CODE_SAFE) eassert (HASH_TABLE_SIZE (h) == h->count);" and do the
> latter even with large hash tables?
Done.
>
> If you change the loop from "for (i = 0; i < h->count; i++)" to "for (i =
> h->count; 0 <= --i; )", then you can merge the two copies of "op = XINT
> (HASH_VALUE (h, i)); goto ob_branch;" into one copy that is after the
> surrounding "if".
>

Done, thanks.


-- 
Vibhav Pant
vibhavp@gmail.com

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

[Vibhav Pant]

Is there anything else to be done?

On Sat, Feb 11, 2017 at 8:37 PM, Vibhav Pant <vibhavp@gmail.com> wrote:
> On Sat, Feb 11, 2017 at 2:17 AM, Paul Eggert <eggert@cs.ucla.edu> wrote:
>> On 02/10/2017 10:25 AM, Vibhav Pant wrote:
>>>
>>> Are there any other issues before I merge this into master?
>>
>>
>> For the C code, please use the usual style: space before paren in calls, GNU
>> style indenting for curly braces, "/* " at start of comments, main operator
>> like "||" at start of next line rather than at end of previous line.
>>
>> One of the 'if's is overparenthesized, i.e., "if ((E))" where E is an
>> ordinary expression and "if (E)" will do.
>>
>> Prefer "if (BYTE_CODE_SAFE)" to "#ifdef BYTE_CODE_SAFE", as these days it's
>> better to avoid the preprocessor when it's easy.
>>
>> This comment:
>>
>>                     /* Hash tables for switch are declared with :size set to
>> the
>>                        exact number of cases, thus
>>                        HASH_TABLE_SIZE (h) == h->count.  */
>>
>> is something that could be checked, no? Perhaps replace the comment with "if
>> (BYTE_CODE_SAFE) eassert (HASH_TABLE_SIZE (h) == h->count);" and do the
>> latter even with large hash tables?
> Done.
>>
>> If you change the loop from "for (i = 0; i < h->count; i++)" to "for (i =
>> h->count; 0 <= --i; )", then you can merge the two copies of "op = XINT
>> (HASH_VALUE (h, i)); goto ob_branch;" into one copy that is after the
>> surrounding "if".
>>
>
> Done, thanks.
>
>
> --
> Vibhav Pant
> vibhavp@gmail.com



-- 
Vibhav Pant
vibhavp@gmail.com

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

[Vibhav Pant]

I'll push this to master after adding a few more tests for byte-switch
to test/lisp/emacs-lisp/bytecode-tests.el

On Sun, Feb 12, 2017 at 8:40 AM, Vibhav Pant <vibhavp@gmail.com> wrote:
> Is there anything else to be done?
>
> On Sat, Feb 11, 2017 at 8:37 PM, Vibhav Pant <vibhavp@gmail.com> wrote:
>> On Sat, Feb 11, 2017 at 2:17 AM, Paul Eggert <eggert@cs.ucla.edu> wrote:
>>> On 02/10/2017 10:25 AM, Vibhav Pant wrote:
>>>>
>>>> Are there any other issues before I merge this into master?
>>>
>>>
>>> For the C code, please use the usual style: space before paren in calls, GNU
>>> style indenting for curly braces, "/* " at start of comments, main operator
>>> like "||" at start of next line rather than at end of previous line.
>>>
>>> One of the 'if's is overparenthesized, i.e., "if ((E))" where E is an
>>> ordinary expression and "if (E)" will do.
>>>
>>> Prefer "if (BYTE_CODE_SAFE)" to "#ifdef BYTE_CODE_SAFE", as these days it's
>>> better to avoid the preprocessor when it's easy.
>>>
>>> This comment:
>>>
>>>                     /* Hash tables for switch are declared with :size set to
>>> the
>>>                        exact number of cases, thus
>>>                        HASH_TABLE_SIZE (h) == h->count.  */
>>>
>>> is something that could be checked, no? Perhaps replace the comment with "if
>>> (BYTE_CODE_SAFE) eassert (HASH_TABLE_SIZE (h) == h->count);" and do the
>>> latter even with large hash tables?
>> Done.
>>>
>>> If you change the loop from "for (i = 0; i < h->count; i++)" to "for (i =
>>> h->count; 0 <= --i; )", then you can merge the two copies of "op = XINT
>>> (HASH_VALUE (h, i)); goto ob_branch;" into one copy that is after the
>>> surrounding "if".
>>>
>>
>> Done, thanks.
>>
>>
>> --
>> Vibhav Pant
>> vibhavp@gmail.com
>
>
>
> --
> Vibhav Pant
> vibhavp@gmail.com



-- 
Vibhav Pant
vibhavp@gmail.com

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

[Vibhav Pant]

With the latest changes to feature/byte-switch, the switch code now takes 13.21
seconds (compared to 16.10 seconds for the non-switch code).

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

[Eli Zaretskii]

> From: Vibhav Pant <vibhavp@gmail.com>
> Date: Mon, 6 Feb 2017 23:20:06 +0530
> 
> The code for this feature is in the branch 'feature/byte-switch',
> feedback would be appreciated.

Thank you for working on this.

Is it possible to add some tests that would ensure that code which
will use this bytecode will still yield the same results as with
previous byte compiler and interpreter?

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

[Vibhav Pant]

On Tue, Feb 7, 2017 at 1:02 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> Is it possible to add some tests that would ensure that code which
> will use this bytecode will still yield the same results as with
> previous byte compiler and interpreter?

I've added a few tests to test/lisp/emacs-lisp/bytecomp-tests.el

-- 
Vibhav Pant
vibhavp@gmail.com

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

[Eli Zaretskii]

> From: Vibhav Pant <vibhavp@gmail.com>
> Date: Tue, 7 Feb 2017 19:56:23 +0530
> Cc: "emacs-devel@gnu.org" <emacs-devel@gnu.org>
> 
> On Tue, Feb 7, 2017 at 1:02 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> > Is it possible to add some tests that would ensure that code which
> > will use this bytecode will still yield the same results as with
> > previous byte compiler and interpreter?
> 
> I've added a few tests to test/lisp/emacs-lisp/bytecomp-tests.el

Thank you!