Re: Elisp performance

[Daniel Kraft]

Hi Neil,

Neil Jerram wrote:
> Daniel Kraft <address@hidden> writes: 
> > Lambda arguments are still always dynamically bound, which is quite a
> > pity as it inhibits tail-call optimization;
>
> This prompted me to wonder if using fluids is the best way to
> implement dynamic binding.
>
> Perhaps I'm forgetting something basic, but surely it's using
> `dynamic-wind' that gives us dynamic binding semantics, not fluids.

I also thought about this yesterday; and I think you're right, just as I 
propose to do for function bindnigs we could also do for values. 
Somehow I had the impression in the back of my head that fluids are 
meant to provide dynamic binding as we need it and with-fluid* does some 
"magic" to do it most efficiently.

However, as I now see it, the dynamic state is meant to apply to threads 
and not between different with-fluid*'s, right?  So instead of 
with-fluid* using just a dynamic-wind will be faster (or at least on 
par)...?

If so, I think we should get rid of the fluids and switch to directly 
using dynamic-wind.  The point about future multi-threading might be 
interesting, though...  If we did switch elisp to multi-threading at 
some point, what would become of dynamic binding?  I guess we can't do 
this across threads, so each dynamically bound variable would also be 
thread local?  I think this is the most reasonable concept, trying to 
make dynamic bindnig work across threads looks really messy to me. 
Then, the fluid concept will be just what we need again;  but we 
probably also want to find a way for shared global variables -- which 
has time until then, of course ;)

Another thing:  If we use dynamic-wind directly instead of the current 
fluid system, we could get rid of void as special value and instead just 
unbind the symbol from our module in case of void; then, on access Guile 
would complain itself and we wouldn't need the special checks for void. 
 With dynamic-wind, we could ensure that variables are re-bound or 
unbound to their previous state when leaving the dynamic scope.  This 
rebinding would, however, be more expensive as we would have to care for 
a lot more special cases.  With regards to void, I like the current 
implementation with the possibility to disable the access check if not 
needed and then get full speed.  So I'm not sure if I would change void 
handling at all even if we switched away from fluids and it became possible.

> (Note that `with-fluids', which is probably the closest thing in Guile
> Scheme to a dynamic let, is a combination of `dynamic-wind' and
> `fluid-set!'.)

Yes, I agree; and with-fluids is quite nice to use, also.  But as the 
compiler handles dynamic binding in our case, I also don't care about 
explicitly setting/reverting the variables with dynamic-wind.  If 
with-fluids uses dynamic-wind internally, we can only win on performance 
and all we lose seems to be the thread-locality for the future.  But 
this may still be a point, I'm not sure...

> So what's my point?  I'm not sure, just musing.  As far as performance
> and tail-call optimization are concerned, I would guess that the main
> thing that needs to be addressed in order to reinstate tail-call
> optimization would be the dynamic wind - i.e. the compiler knowing
> that it isn't necessary to set up another dynamic-wind frame, it can
> just jump with the current variables.

Hm, I'm not sure if I got your point correctly, but I think that dynamic 
binding and tail-call optimization are difficult to combine in general, 
no matter if the dynamic binding is done with fluids or dynamic-wind.

As you said, the point is about the compiler or VM handling the 
"unwinding" (i.e. resetting changed dynamic bindings to their old 
values) and doing this in a way to allow tail-call optimization.  I 
don't think a tail-call is possible in general at all if the caller's 
body is executed inside a dynamic wind (well, at least for recursive 
calls, each level will have to create it's own unwinding-context and 
thus grow the stack despite tail-calls)...?  I'm not very much into 
theoretical considerations in this topic, so maybe you know more about 
if/how/when tail optimization is possible together with dynamic binding 
or dynamic-wind; but some ideas below.

For dynamic binding however, I think one could do tail-call 
optimization, at least in some cases like when the callee binds a 
superset of the symbols bound by the callee (which would suffice for 
optimization of recursive calls).  But then we would need to do dynamic 
binding in some other way than with dynamic-wind (i.e. with some 
stack-like data structure where we can push/pop values for the symbols) 
and also have to know about tail-calls in the elisp compiler directly; I 
don't think we should go for this...  When I implement the option to 
"always" bind certain symbols lexically, at least for lambda's with 
lexically bound arguments tail-call optimization will again be available 
for free.

But if we want to work on this, a not-so-bad idea could be thinking 
about dynamic-binding support directly by the VM (with something like 
the special data structure I mentioned; we could even look at how emacs 
does it exactly); then, the VM (or a lower-level compiler) which already 
knows about tail-calls could be taught to also handle the dynamic 
binding aspects.

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

> (Also, if I get time, I'll try this with the old translation code
> too.  Just for fun, and hopefully for confirmation that the new
> approach is much better!)

That would be cool!

> > 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?
>
> See above.  I'm not sure why fluid access should be significantly
> slower than non-fluid access, so I would guess that the performance
> cost is coming from the dynamic-wind part.

I don't know about fluid access; dynamic-winding should not take place 
(at least not repeatedly) in my loop because there are no let's within 
it...  However, as I wrote in another message, I think now that the 
difference between the naive elisp version and the guile-ref one might 
also be the boolean translation #f -> %nil in elisp's < built-in vs. 
calling Guile's primitive directly and not caring about translation.

Some testing however:

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

(define (test2 to)
  (let ((i (make-fluid)))
    (fluid-set! i 0)
    (while (< (fluid-ref i) to)
      (fluid-set! i (1+ (fluid-ref i))))))

(define global-i)
(define (test3 to)
  (set! global-i 0)
  (while (< global-i to)
    (set! global-i (1+ global-i))))

And calling all three versions with 1000000 iterations gave about 0.71s 
for test1 and test3 (so lexical i and module i seem to be the same 
speed) but 2.5s for test2.  Thus I think that the fluids are indeed 
slower (I've no idea how they are implemented, but these results seem to 
indicate 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.

Yours,
Daniel

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