Re: Elisp performance

[Andy Wingo <wingo@pobox.com>]

Hello Daniel,

On Fri 31 Jul 2009 08:02, Daniel Kraft <d@domob.eu> writes:

> Hi Neil,
>
> Neil Jerram wrote:
>> Daniel Kraft <d@domob.eu> 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)...?

It will be on par. Here's the deal.

In Guile, be it in Scheme or in other languages, variables that are
`set!' need to be allocated on the heap. This is so that different
closures can see the "same" variable. It is also so that reinstated
continuations can see the result of mutations of lexically captured
variables.

Now, this imposes two penalties. The one is that because the variable is
allocated on the heap -- actually in a "variable" object, like in
`make-variable' -- lexically binding a variable that is `set!' causes a
cons. Occasionally this will cause a GC, and Guile's GC is slow, so this
causes speed penalties.

That's a penalty at binding time -- e.g. when entering a `let'
expression. There is also a penalty at access time, because referencing
or setting the value has to go through an indirection, into the heap.
This matters, but it doesn't matter as much as the cons.

Using fluids, you never actually `set!' a fluid -- you `fluid-set!' a
fluid. Heap-wise, fluids are a bit heavier than variables, as they are
double cells instead of single cells. I think this is rather silly, and
we should probably fix this -- the number can go into the smob flags,
and the next loc (if we still need it) into the data word. 64K fluids
might be enough... otherwise we could make fluids tc7 objects. Surely
16M fluids are enough.

So, let's assume we manage to make fluids single-cell objects at some
point. (Note that a cell is two words.) Then the heap "load" of fluids
is basically the same as variables. There is the fluid vector too, so
that's 2 words per fluid, plus 1 word per fluid per thread -- but the
vector is easier on the GC.

Indirection-wise, since we can cache actual fluid values in Elisp
functions instead of the variable objects that contain them -- because
the variables that contain the fluids are never set!, it's just the
fluids themselves that are fluid-set! -- *the access cost of fluids is
the same*. It might even be better, due to memory locality of the fluid
vector.

So fluids are not the problem, given sufficient support from the VM.

                              * * *

Dynamic-wind, on the other hand, does pose a problem. The problem is
that dynamic-wind is a primitive -- to call it, the VM saves its
registers, conses together its arguments, and passes them to the
evaluator. The evaluator destructures the consed list, eventually finds
the C function, and calls scm_dynamic_wind, which conses on the guards
to the current wind list, recursively calls the VM for the enter, body,
and exit thunks, and then resets the wind list.

All this entering and leaving the VM is expensive and unnecessary. It
would be better to add VM ops for entering and leaving dynamic contexts,
but you still have to cons the handlers onto the wind list -- at least
with Guile's current dynwind implementation.

But... I have been meaning for a long time to implement dynwind and
`catch' in the VM so we wouldn't need these recursive VM invocations.
(These days, dynwind is the largest reason for recursive VM invocation,
besides map and for-each which are still implemented as primitives.)

Does that give you a better insight to the performance implications?

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

Simply disabling multithreading so you wouldn't have to use fluids would
not be sufficient -- as I showed above, the cost of fluids versus `set!'
values is the same. You could get a win via disallowing captured
continuations, which would allow you to use `with-throw-handler' instead
of `dynamic-wind', but the performance impact of the two is currently
the same, basically.

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

The VM handles unbound values in a few places. See the code for
local-ref, local-boxed-ref, and closure-boxed-ref, for example. It uses
SCM_UNDEFINED, which answers to SCM_UNBNDP. (An irritating lack of
symmetry, I know. There is also SCM_UNBOUND, I think... grrr....)

>> (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...

We should be using VM ops at some point, I would think... at least for
looking up and caching the fluid values, and for reffing and setting
dynamically bound vars.

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

Yes, I agree. The unbinding is a continuation that is not from the
parent call, whereas a tail call from a procedure without dynamic
bindings has no such continuation.

Regards,

Andy
-- 
http://wingolog.org/