[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Elisp performance
From: |
Daniel Kraft |
Subject: |
Re: Elisp performance |
Date: |
Fri, 31 Jul 2009 08:02:34 +0200 |
User-agent: |
Thunderbird 2.0.0.0 (X11/20070425) |
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