A faster stack

1 minute read

I’m back in the country now and starting to work on Ludicrous again. A number of YARV instructions have now been implemented and very simple methods can be executed.

Stack manipulation is tricky. As mentioned before, the first pass of JIT-compiling YARV bytecode actually allocated a Ruby array for every method invocation, calling rb_ary_push() and rb_ary_pop() to manipulate the stack. As you can imagine, this is quite slow.

The next pass tried to actually use the real YARV stack. This meant directly accessing Ruby’s thread structure to get a pointer to the stack. It was faster than using an array, but there were too many edge cases where the stack pointer wasn’t being manipulated properly.

The current solution uses a static stack instead of a dynamic stack, pushing and popping the stack at compile time rather than at run time. This means that stack operations can actually be optimized into register operations. It obviously doesn’t work with all possible YARV bytecode, but I don’t know of any cases where Ruby generates bytecode that needs a run-time stack (e.g. pushing a value onto the stack in a loop). In any case there are some rudimentary checks for such code, e.g. that the stack size is the same at the beginning and end of a detected loop.

The next challenge to tackle is to implement rescue and ensure. I’ve already got PUSH_TAG, POP_TAG, and EXEC_TAG implemented in ruby-jit (impossible on 1.8, since the current tag is private in eval.c), and the rest should come relatively easily.