Elisp performance

[Daniel Kraft]

Hi all,

as promised, here are some performance results for the current elisp 
compiler.  BTW, it supports now to disable checks for void-value on 
variable access via compiler options as well as the 
lexical-let/lexical-let* constructs that should mimic the ones from 
emacs' cl package (but in emacs they degrade performance, in Guile they 
improve it).

Lambda arguments are still always dynamically bound, which is quite a 
pity as it inhibits tail-call optimization; I'll work on a compiler 
option to always bind certain or all symbols lexically, including lambda 
arguments to counter this (and there's also an emacs branch doing this, 
so we're ultimatly even trying to be compatible...).

For the timings, I used a simple prime sieve implemented imperatively 
with while and set's, because the recursive one would put elisp without 
tail-calls at a disadvantage (and because lexical binding does not yet 
work for lambda arguments); the code is attached.  Both Scheme and Elisp 
version are identical with just syntax changed (set! -> setq, define -> 
defun, begin -> progn).  Additionally, for lexical let all let's were 
replaced by lexical-let's in the elisp version.  Here are the results:

Iterative prime sieve, (length (find-primes-to 5000)):
  Scheme: 0.42s
  Elisp, no void checks, lexical let: 3.40s
  Elisp, no void checks, dynamic let: 4.43s
  Elisp, void checks, dynamic let: 5.12s
  Elisp, void checks, lexical let: 4.06s

So it apparent that both disabling void checks and using lexical let's 
instead of the standard dynamic ones improve performance notably. 
However, were quite out of reach of the Scheme version.

My conjecture is that the remaining bottle-neck are the primitive calls, 
as they are still resolved using the dynamic-binding and fluid 
mechanisms; so maybe it is really a good idea to change function 
bindings to just global ones without dynamic scoping, and implement 
flet/flet* with dynamic-wind.  In contrast to variables, for functions 
access performance is a lot more important than let performance, I 
guess, so this might be the way to go.  What do you think?

As another test I implemented just a small loop, again both in Scheme 
and Elisp with identical code (also attached).  Here are the timing results:

Tight loop, (test 1000000):
  Scheme: 0.72s
  Elisp, no void checks, lexical let: 2.33s
  Elisp, no void checks, lexical let, guile-ref: 1.29s
  Elisp, no void checks, lexical let, guile-primitive: 0.92s

In the guile-ref and guile-primitive runs, I replaced both primitives (< 
and 1+) using the extension constructs (guile-ref (guile) </1+), which 
is like (@ (guile) </1+) in Scheme, or (guile-primitive </1+) which 
builds a (make-primitive-ref) in TreeIL.  The guile-ref timing is what 
we would also get if we changed function bindings like I suggested above.

Obviously, it would help a lot to do so.  On the other hand, switching 
to primitive-ref's would help even more, but I fear we can not easily do 
so, because we can not know if a symbol targets a primitive or was 
rebound at compile time...  BTW, a quick test with Scheme:

scheme@(guile-user)> (set! + (lambda (a b) 42))
scheme@(guile-user)> +
#<program b700a790 at <unknown port>:0:8 (a b)>
scheme@(guile-user)> (+ 1 2)
3
scheme@(guile-user)> (let ((+ (lambda (a b) 42)))
... (+ 1 2))
42

So it seems that the Scheme compiler just ignores this possibility... 
Is (set! + ...) and expecting (+ 1 2) to change invalid, or should this 
strictly be regarded as a bug?

In any case, because of dynamic scoping and the expected behaviour of 
flet to change possibly primitives during its extent, I think we can't 
do anything like that for Elisp (except providing guile-primitive for 
hand-optimizing such calls).

Yours,
Daniel

--
Done:  Arc-Bar-Cav-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Kni-Mon-Pri

; Imperative prime sieve in Elisp.

(defun sieve-out (pivot number-list)
  (lexical-let ((i number-list)
        (result '())
        (result-tail '()))
    (while (not (null i))
      (if (not (zerop (% (car i) pivot)))
        (if (consp result)
          (progn
            (setcdr result-tail (cons (car i) '()))
            (setq result-tail (cdr result-tail)))
          (progn
            (setq result (cons (car i) '()))
            (setq result-tail result))))
      (setq i (cdr i)))
    result))

(defun sieve (number-list)
  (lexical-let ((i number-list)
        (result '())
        (result-tail '()))
    (while (not (null i))
      (if (consp result)
        (progn
          (setcdr result-tail (cons (car i) '()))
          (setq result-tail (cdr result-tail)))
        (progn
          (setq result (list (car i)))
          (setq result-tail result)))
      (setq i (sieve-out (car i) i)))
    result))

(defun find-primes-to (to)
  (lexical-let ((numbers '())
        (i to))
    (while (> i 2)
      (setq numbers (cons i numbers))
      (setq i (1- i)))
    (sieve numbers)))

; Imperative prime sieve in Scheme.

(define (sieve-out pivot number-list)
  (let ((i number-list)
        (result '())
        (result-tail '()))
    (while (not (null? i))
      (if (not (zero? (modulo (car i) pivot)))
        (if (pair? result)
          (begin
            (set-cdr! result-tail (cons (car i) '()))
            (set! result-tail (cdr result-tail)))
          (begin
            (set! result (list (car i)))
            (set! result-tail result))))
      (set! i (cdr i)))
    result))

(define (sieve number-list)
  (let ((i number-list)
        (result '())
        (result-tail '()))
    (while (not (null? i))
      (if (pair? result)
        (begin
          (set-cdr! result-tail (cons (car i) '()))
          (set! result-tail (cdr result-tail)))
        (begin
          (set! result (cons (car i) '()))
          (set! result-tail result)))
      (set! i (sieve-out (car i) i)))
    result))

(define (find-primes-to to)
  (let ((numbers '())
        (i to))
    (while (> i 2)
      (set! numbers (cons i numbers))
      (set! i (1- i)))
    (sieve numbers)))

; Just a tight loop in Elisp

(defun test (to)
  (lexical-let ((i 0))
    (while ((guile-primitive <) i to)
      (setq i ((guile-primitive 1+) i)))))

; Just a tight loop in Scheme.

(define (test to)
  (let ((i 0))
    (while (< i to)
      (set! i (1+ i)))))