Entries tagged optimization

I've recently spent some time working with a simple scripting language. Today I spent parts of the day trying to make it faster. As a broad overview we'll be considering this example script:

  if ( 1 + 2 * 3 == 7 ) { return true; }

  return false;

This gets compiled into a simple set of bytecode instructions, which can refer to a small collection of constants - which are identified by offset/ID:

  000000	    OpConstant	0	// load constant: &{1}
  000003	    OpConstant	1	// load constant: &{2}
  000006	    OpConstant	2	// load constant: &{3}
  000009	         OpMul
  000010	         OpAdd
  000011	    OpConstant	3	// load constant: &{7}
  000014	       OpEqual
  000015	 OpJumpIfFalse	20
  000018	        OpTrue
  000019	      OpReturn
  000020	       OpFalse
  000021	      OpReturn


Constants:
  000000 Type:INTEGER Value:1
  000001 Type:INTEGER Value:2
  000002 Type:INTEGER Value:3
  000003 Type:INTEGER Value:7

The OpConstant instruction means to load the value with the given ID from the constant pool and place it onto the top of the stack. The multiplication and addition operations both pop values from the stack, apply the appropriate operation and push the result back. All standard stuff.

Of course these constants are constant so it seemed obvious to handle the case of integers as a special case. Rather than storing them in the constant-pool, where booleans, strings, etc live, we just store them inline. That meant our program would look like this:

  000000	        OpPush	1
  000003	        OpPush	2
  000006	        OpPush	3
  000009	         OpMul
  000010	         OpAdd
  ...

At this point the magic begins: we can scan the program from start to finish. Every time we find "OpPush", "OpPush", then "Maths" we can rewrite the program to contain the appropriate result already. So this concrete fragment:

OpPush 2
OpPush 3
OpMul

is now replaced by:

OpPush	6
OpNop     ; previous opconstant
OpNop     ; previous arg1
OpNop     ; previous arg2
OpNop     ; previous OpMul

Repeating the process, and applying the same transformation to our comparision operation we now have the updated bytecode of:

  000000	         OpNop
  000001	         OpNop
  000002	         OpNop
  000003	         OpNop
  000004	         OpNop
  000005	         OpNop
  000006	         OpNop
  000007	         OpNop
  000008	         OpNop
  000009	         OpNop
  000010	         OpNop
  000011	         OpNop
  000012	         OpNop
  000013	         OpNop
  000014	        OpTrue
  000015	 OpJumpIfFalse	20
  000018	        OpTrue
  000019	      OpReturn
  000020	       OpFalse
  000021	      OpReturn

The OpTrue instruction pushes a "true" value to the stack, while the OpJumpIfFalse only jumps to the given program offset if the value popped off the stack is non-true. So we can remove those two instructions.

Our complete program is now:

  000000	         OpNop
  000001	         OpNop
  000002	         OpNop
  000003	         OpNop
  000004	         OpNop
  000005	         OpNop
  000006	         OpNop
  000007	         OpNop
  000008	         OpNop
  000009	         OpNop
  000010	         OpNop
  000011	         OpNop
  000012	         OpNop
  000013	         OpNop
  000014	         OpNop
  000015	         OpNop
  000018	        OpTrue
  000019	      OpReturn
  000020	       OpFalse
  000021	      OpReturn

There are two remaining obvious steps:

• Remove all the OpNop instructions.
• Recognize the case that there are zero jumps in the generated bytecode.
  • In that case we can stop processing code once we hit the first OpReturn

With that change made our input program:

if ( 1 + 2 * 3 == 7 ) { return true; } return false;

Now becomes this compiled bytecode:

  000000	        OpTrue
  000001	      OpReturn

Which now runs a lot faster than it did in the past. Of course this is completely artificial, but it was a fun process to work through regardless.

Tags: bytecode, evalfilter, golang, optimization | No comments