Store SOM variables on the SOM stack.

ltratt commented 4 years ago

Previously each function call allocated memory for variables on the heap. This commit moves things so that most variables live and die on the SOM stack. This then enables doing many more operations on the stack, including passing function arguments in on the stack rather than through intermediate Vecs (see the comment in somtack.rs). This is a substantial speed-up (a little under 2x).

The scheme we use is, more-or-less, that of Lua's. The most approachable explanation I know of is:

http://www.craftinginterpreters.com/closures.html

though it's not something I'd expect anyone to understand in 5 minutes. The basic idea is that methods (and blocks which don't reference variables in outer methods / closures) don't require any heap allocation of variables. Blocks which reference variables in outer methods / closures pre-allocate memory on the heap and, if necessary, move variables into that memory when the outer method / block completes. More sophisticated schemes are possible, but this scheme has the advantage of relative simplicity.

Note that there is a known case of UB in this code (which Jake and I are musing how best to solve in the longer term): we currently don't have a way of sensibly allowing mutation in interior pointers to Gc things, which makes the UpVar struct dangerous. In practise, at the moment, I can't observe the UB causing us problems, and I think we'll have a fix for it before it becomes a bigger problem. I think, for the time being, it's probably easiest to review this commit as if that wasn't an issue, as the enabling fix will have to happen in external libraries.

ltratt commented 4 years ago

bors try