Re: Elisp performance

[Ken Raeburn]

On Jul 31, 2009, at 02:02, Daniel Kraft wrote:
> > > 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
> > As Ken says, it would be good to see an Emacs timing too.
>
> I'd like to provide one, but have no idea how to do so...  I just  
> managed to find out how to evaluate elisp code from a buffer, but it  
> would be cool to get some elisp REPL if possible (maybe even without  
> starting emacs itself and just from a shell?) -- and how to I time?   
> As well as byte-compile and time then?

Easy -- M-x ielm RET starts "interactive emacs lisp mode" in a buffer!

The function (current-time) provides the current timestamp with  
microsecond resolution (if supported by the OS) as a list of three  
numbers (working around Emacs integer representation limitations), so  
you can invoke it before and after and compute the difference.

So add something like this to your elisp code, and save it in a file:

(defun time-diff (t1 t2)
  (+ (* 65536.0 (- (nth 0 t1) (nth 0 t2)))
     (* 1.0 (- (nth 1 t1) (nth 1 t2)))
     (* 1.0e-6 (- (nth 2 t1) (nth 2 t2)))))

(defun time-test (exp)
  (let ((start (current-time)))
    (eval exp)
    (time-diff (current-time) start)))

Eval that code, then in ielm run:

 (time-test '(length (find-primes-to 5000)))

Be sure to quote the expression, or it'll be evaluated before the  
start time is computed... I made that mistake a couple of times. :-)   
And you can use

  (byte-compile 'sieve)

to compile an individual function, or M-x byte-compile-file followed  
by M-x load-file to load the compiled version of all the functions so  
you can run them.  After byte-compiling, try M-x disassemble RET sieve  
RET if you're curious about what Emacs does with it.

> Ok, I guess a quick summary is in order:  I think implementing  
> dynamic binding directly using dynamic-wind instead of with fluids  
> is a good idea, as long as we don't already want to keep the fluids  
> for future multi-threading.  If this ever comes, we are probably  
> again forced back to fluids.  Do you think we should switch or not?   
> Regarding tail calls, my opinion is that there's no "easy" way to  
> make them work with dynamically bound arguments (as arguments are in  
> elisp), if there is at all -- and that we should not bother.  I  
> don't think emacs does general tail-call optimization (does it?),  
> and there will be a way to switch lambda arguments back to lexical  
> scoping, so that for those lambda's tail-calls will be optimized  
> just fine with the current compiler/VM infrastructure.

If the new thread keeps running while the creating thread exits the  
scope that created a dynamic binding, while the new thread wants to  
keep using or updating it... ugh.

I can imagine cases where you might want to carry bindings across into  
a new thread -- consider a function calling a multithreaded variant of  
mapcar on a long list of inputs, passing a function or lambda  
expression that wants to refer to arguments of the enclosing  
function.  (E.g., "grep" on a list of strings, the applied function  
taking an individual string as its argument, and finding the regexp  
via dynamic scope; with a worker thread per CPU or per core, a long  
list can be processed much faster.)  But, if the new thread is started  
with no dynamic bindings, I think you can fudge it with lexical  
bindings:

  ...
  (mt-mapcar (lexical-let ((regexp regexp))
                (lambda (s) (if (string-match regexp s) s nil)))
             huge-list-o-strings)

Since there's a way to work around it for specific cases that need  
other behavior, I think it's probably reasonable for the new thread to  
start with global bindings only.

Ken