Expressions evaluation at (almost) native speed

Finally I found a bit of time this weekend to do some other tests with expressions evaluation.

The results are pretty interesting, even if obvious from some point of view. I took the ExpressionEvaluator I wrote as example for the first post about this topic, and then I edited a bit the code adding just in time AS Bytecode compilation.
Thanks to that, expressions evaluation is much more fast and always safe because it runs in its own ApplicationDomain.

You can download the sources here, that includes the edited code and a test file. The test file runs 1 milion of iterations and may hang your browser or at worst case your system. Reduce the value of the ITERATIONS constant if you are not sure about the power of you machine.

If you want to read a bit more details about that, click on the link below to continue reading.

I did some simple modification to the existing classes:

  • Added a compile method to the IExpression interface;
  • Added the symbolNames getter to the SymbolTable class, to retrieve a list of all the symbols defined inside the symbol table.
  • Converted hxasm to Actionscript (finxing some small issues to avoid to include all the Haxe support classes);
  • Implemented the compile method on all the AST nodes using HxASM;
  • Added an SWFCompile class that takes an IExpression and a SymbolTable and produces an SWF;
  • Edited the CompiledExpression class adding a compile method that generates an SWF starting from an IExpression.

Adding just in time compilation was easy a really quick thanks to HxASM. HxASM is an Haxe library written by Haxe’s author (Nicolas Cannasse) that makes you able to write low level bytecode instructions in ActionScript an generate a ByteArray that contains an (hopefully) valid SWF. The SWF can then be loaded by Loader.loadBytes and executed.

It have been easy to port HxASM to ActionScript too, thanks again to the Haxe compiler which is able to generate AS3 code starting from Haxe code.

Compilation was achieved easilly because the expressions we are compiling are really simple. The compiler generates a class called CompiledExpression that has a method execute that can be called to execute the expression. All the values inside the symbol table are exposed as public properties.

Just to make you understand better, givin this expression:

sin( x * 10 + y - 11 )

SWFCompiler will generate the bytecode for this class:
class CompiledExpression
{
public var sin: *;
public var x: *;
public var y: *;
public function execute(): Number
{
return sin( x * 10 + y - 11 );
}
}

As you can see the type of the class variables is generic, but you can improve the generator to understand if a variable should contain a number or a function.

The generated SWF can be loaded and run easilly:
var loader: Loader = new Loader();
var parser: Parser = new Parser(
new Scanner( "sin( x / ( 4 / 2 * 2 - 2 + 2 * x / x ) ) * 100" ) );
var compiled: CompiledExpression = parser.parse();
var data: ByteArray = compiled.compile();
loader.contentLoaderInfo.addEventListener( Event.COMPLETE,
function( event: Event ): void
{
var info: LoaderInfo = ( event.target as LoaderInfo );
var klass: Class = (
info.applicationDomain.getDefinition( "CompiledExpression" ) as Class );
var cp: Object = new klass();
cp.x = 10;
cp.sin = Math.sin;
trace( "Result", cp.execute() );
} );
loader.loadBytes( data, new LoaderContext( false,
new ApplicationDomain( ApplicationDomain.currentDomain ) ) );

I build a simple test (shipped with the sources) that runs 1 milion times an expression using 3 methods: Evaluation, Compiled and Native.

Results (on my Mac Pro 8 Core, 4GB ram) are obvious:

eval 1000000 iterations: 12939
compiled 1000000 iterations: 848
native 1000000 iterations: 371

As you can see native execution is faster, but compiled version runs really well (you might want to optimize the generated code to make it run faster) and it is many times faster then AST evaluation.

If you want to run a complex expression many times and dont want to stress your Flash Plugin, you can use the compiled version.

Gotta run, see u next time!

Share with...