Optimising ETA interpreter
Copyright © Stephen Sykes, 2002.
After writing my Befunge to ETA converter, I had a lot of code that ran ok but was very slow under the fastest interpreter available. I wanted to run Befunge chess under ETA much faster than this. So I wrote a new interpreter.
This ETA interpreter reads the ETA code, and optimises it into a compressed form where all constants and common short ETA sequences are represented by a single character. Then the interpreter part runs this code. It is especially quick when running converted Befunge code because I was using analysis of that ETA code when writing this.
One other thing to note is the interesting implementation of the ETA stack - I use a doubly linked list. This is much better than a flat array of some sort because I can halibut deep into the stack without having to shift all the elements. Also, I implemented a kind of memory, so in cases where we are doing many halibuts in a row to retrieve and set a value deep in the stack, there is no overhead in finding the correct stack item to shift to the top.
When running Befunge chess on this interpreter on my Linux box, the computer makes its first move in about 55 seconds. Actually it's kind of funny to use this on converted Befunge code. This optimiser tries its hardest combine the ETA into larger operations that can be implemented in a quick way in C. Which is taking a step back towards the Befunge source we started with...
S.D.Sykes Feb 2002