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