3 ms·
The implementation described here is inspired by Lua. Even if you already know what a closure is, it might still be a worthwile read, since it probably implemen
by ufo 7y ago
The implementation described here is inspired by Lua. Even if you already know what a closure is, it might still be a worthwile read, since it probably implements them very differently from what you are thinking!
Instead of always heap-allocating variables that are used by closures, it starts by stack-allocating them and only moves them to the heap if the closure outlives its parent function. In order for this to work, the inner function always accesses the outer variables through an indirection (upvalue).
The main advantage of this approach is that it is compatible with a single-pass compiler, without sacrificing performance in the common case where closures are not present. Since the generated code for using a variable is the same no matter whether it is used by inner functions or not, the compiler can start emitting code as soon as it sees the variable declaration, without needing to look ahead to find where the variables are going to be used.
- chrisseaton 7y agoAnother approach is to do the opposite - always store all local variables in the heap, and rely on scalar replacement of aggregates to put them back onto the stack where possible. This is what I do in my Ruby interpreter. That’s definitely not compatible with a single-pass though!
- munificent 7y agoVery interesting! Have you written anything about your implementation? I'm always keen to learn new techniques. I don't have much back end optimization experience (yet).
- chrisseaton 7y agoSection 4.2 of http://lafo.ssw.uni-linz.ac.at/papers/2013_Onward_OneVMToRuleThemAll.pdf http://lafo.ssw.uni-linz.ac.at/papers/2013_Onward_OneVMToRul... describes it. > We ensure this by forcing an escape analysis ... of the array containing the values of local variables. This eliminates every access to the array and instead connects the read of the variable with the last write. ... After conversion to SSA form, guest-language local variables have no performance disadvantage compared to host language local variables. Then if the closure escapes (stored into the heap or something), the escape analysis just naturally fails and the frame is stored on the heap again.
- vore 7y agoA third option that can still be single pass is the Smalltalk way, where the stack frames themselves are first-class objects: the closures then keep a reference to the stack frame and the GC won't collect any live stack frames, which will contain closed-over variables.
- chrisseaton 7y agoYes that's really what I'm talking about, but plus the (really required for practical performance) optimisation of virtualising the frames onto the stack if they don't escape an activation.