[Jruby-devel] Performance enhancement: use InstructionBundles as a linked list

[Charles O Nutter]

Internally, the interpreter creates an InstructionBundle for each node encountered in the AST. This allows it to link an executable instruction, a specific node from the AST, and a couple flags for ensured, breakable, etc into a single nugget. This is then pushed on to an "instruction stack" to maintain the current instruction and to handle nested flow-control structures.

It would seem that the guess that all this stack pushing and popping is a problem is at least partially true. The attached EvaluationState.java makes the InstructionBundle itself into a linked list node, eliminating much of the list management previously required. The results are very positive; in a few algorithms this speeds up JRuby by over 10%.

I ran three tests from the Language Shootout: nsieve, binary-trees, and recursive. The results are below. After a bit more testing (and after SF.NET's project CVS is back online), I will commit this fix, and get back into bugs and enhancements. It is very promising that small changes like this can improve performance so much.

nsieve 1
with fix: 16.25, 16.25, 16.313, 16.187, 16.265; 16.253, 1.8% faster
without fix: 16.578, 16.547, 16.531, 16.579; 16.558

binary-trees 11
with fix: 30.922, 30.719; 30.82, 10% faster
without: 34.359, 34.547; 34.453

recursive 4
with fix: 69.953, 69.578; 69.765, 12% faster
without: 79.906, 79.937; 79.921

--
Charles Oliver Nutter @ headius.blogspot.com
JRuby Developer @ jruby.sourceforge.net
Application Architect @ www.ventera.com

EvaluationState.java
Description: Binary data