Well I managed to get it only 20 x slower (using fib(6000) with byte-calcs as benchmark). I can't get it any faster (and don't want to resort to assembly).
Attached the sketch for anyone interested. (Main file is Interpreter_RegBased_FullOpset.ino)
A blink program for the builtin led is autoloaded. Type 'run' to try it.
Ide.ino (19 KB)
Interpreter_RegBased_FullOpset.ino (50.4 KB)
PreloadASM.ino (2.8 KB)