Context
Wait, wait, we said the interpreter was over, didn't we?Well, yes, we have a working interpreter that uses 1137 instructions, and performs about 80k operations for one interpreted instruction.
We can do better !
The most expensive part of our interpreter is memory accesses: moving all items (blocks of 2 cells) to the left, then back to the right, takes time, moreover it's used by all operations but > and <.
The second most expensive part we can improve is the instruction access, for the same reason.
Let's see how we can get rid of instruction and memory pointers
Global idea: here is what our memory map should be
0 {instr_before} 0 0 {instr_after} 0/bit_else 1/instruction_copy inactive_counter direction_flag 0 0 {mem_before} 0 0 {mem_after}
No pointer here. But 2 arrays for instructions and same for memory.
Then, as a convention, we can define current instruction or current memory cell as the first item in the corresponding x_after array.
Thanks to this:
- Instruction can be accessed more quickly (no need to move X items back and forth)
- Same for memory
- Drawbacks
- Incrementing the instruction pointer is done by moving one element from one array to the other
- And instructions > and < are executed by moving one memory cell from one array to the other
- However, these drawbacks are nothing compared to the improvement of fetch or all other operations
One last thing we can improve is the evaluation of while and loop. There is no real need to copy memory cell outside the memory array to evaluate it. It was a quick and dirty way to have all our variables closed together, but it's actually useless as we can directly check the value at it's original location.
Initial state
- Memory: empty
- Cursor: on first cell
- Input: code to execute#input of interpreted program
Code (minified - only 695 instructions - 38% shorter !!!)
>>>,[>+++++[-<------->]+<[>,>]>[->]<<]>+[-<<[<]>[-<+<+>>]<[->+<]<[->>[>]>+<<[<]<]>>[>]+>>[<<++++++[->--------<]+>[--[<->[-]]<[->>-<<]>]<[->>+<<]>+>[<->[->>+<<]]<[->>-<<]+>]>>[-<<+>>]<<<[--------[-[-[-[<+[->-------<]+>[--[<+++[->-------<]+>-[--[<->[-]]<[->>>>>>[>>]>>>[<<<<<[<<]<+<->>>>[>>]>]<[<<]<<[<<]>[-<<<+>>>]<<<<<]>]<[->>>>>+>[>>]>>>[<<<<<[<<]>->[>>]>]<[<<]<<[<<]>[-<<<+>>>]<<<<<]>]<[->>>>>>[>>]+>>[-]>[-<<+>>]>[-]+<<<<[<<]<<<<]>]<[->>>>>>[>>]+<[->>+<<]<-<<[<<]<<<<]>]<[->>>>>>[>>]>>>.<<<<<[<<]<<<<]>]<[->>>>>>[>>]>>>-<<<<<[<<]<<<<]>]<[->>>>>>[>>]>>>,<<<<<[<<]<<<<]>]<[->>>>>>[>>]>>>+<<<<<[<<]<<<<]>[-]<]>>>>+<[<<<<[<]<<[->>+<<]>>[>]>>>>-]>[-<<<<<[<]>[-<<+>>]>[>]>>>>>]<<<<<<[<]>[[>]>+<]>]
Code - with comments, character codes and memory map
separator 35/0
inc 43/8
read 44/9
dec 45/10
print 46/11
left 60/25
right 62/27
while 91/56
loop 93/58
0 {instructions_before} 0 0 {instructions_after} 0 1/instruction_copy inactive_counter direction_flag 0 0 {memory_before} 0 0 {memory_after}
>>>,[>+++++[-<------->]+<[>,>]>[->]<<]>+
[-
fetch
<<[<]>[-<+<+>>]<[->+<]<[->>[>]>+<<[<]<]>>[>]
inactive check processing
+>>[
check instruction
<<++++++[->--------<]+>
[
--
[
not while nor loop
reset else bit
<->[-]
]<[-
instruction loop
decrease inactive_counter
>>-<<
]>
]<[-
instruction while
increase inactive_counter
>>+<<
]>
reset instruction (but not null)
+
>[
if counter is not null
copy inactive_counter (to break loop)
<->[->>+<<]
]<[
else reset direction_flag
->>-<<
]+>
]
reload inactive_counter
>>[-<<+>>]<<
<[
Execute instructions
--------
[
-
[
-
[
-
[
<+[->-------<]+>
[
--
[
<+++[->-------<]+>-
[
--
[
not an instruction
<->[-]
]<[-
instruction loop
>>>>>>[>>]>>>[<<<<<[<<]<+<->>>>[>>]>]<[<<]<<[<<]>[-<<<+>>>]<<<<<
]>
]<[-
instruction while
>>>>>+>[>>]>>>[<<<<<[<<]>->[>>]>]<[<<]<<[<<]>[-<<<+>>>]<<<<<
]>
]<[-
instruction right
>>>>>>[>>]+>>[-]>[-<<+>>]>[-]+<<<<[<<]<<<<
]>
]<[-
instruction left
>>>>>>[>>]+<[->>+<<]<[-]<<[<<]<<<<
]>
]<[-
instruction print
>>>>>>[>>]>>>.<<<<<[<<]<<<<
]>
]<[-
instruction dec
>>>>>>[>>]>>>-<<<<<[<<]<<<<
]>
]<[-
instruction read
>>>>>>[>>]>>>,<<<<<[<<]<<<<
]>
]<[-
instruction inc
>>>>>>[>>]>>>+<<<<<[<<]<<<<
]>
clear instruction
[-]
<
]
>>>>+<
check direction
[
<<<<[<]<<[->>+<<]>>[>]>>>>-
]>
[
-<<<<<[<]>[-<<+>>]>[>]>>>>>
]
<<<<<
<[<]>[[>]>+<]>
]
Final state
- Memory: see above
- Cursor: on instruction, next to inst_ptr
- Input: unchanged
- Output: unchanged
Example
Live BF Interpreter.
Be careful not to execute too long code: one single BrainFuck operation to interpret is rather long (parsing, processing, ...). This version still allows you to run longer code (in theory).
With the same code sample than previous interpreter version:
This gives an average ratio of 16.107 operations to execute one instruction.
Again, this ratio is definitely not accurate, as operations are also used to read program, or in inactive mode, ... but it's still a good indicator of execution complexity.
Conclusion: this num interpreter needs 38% less code, and is 5x faster to execute !
Back to previous step
(No more next step this time 😅)
Be careful not to execute too long code: one single BrainFuck operation to interpret is rather long (parsing, processing, ...). This version still allows you to run longer code (in theory).
With the same code sample than previous interpreter version:
,.---.>+++[-<++>]<+..+++.>++++[->++[->++++<]<]>>.<<<[->+>+<<]++[->++++<]>.>.+++.<<++[->-----<]>-.<++[->----<]>.#HThis new interpreter can execute the code in only 13.675.534 operations, which is really good compared to the 65.622.379 operations for same input using previous interpreter code !!!
This gives an average ratio of 16.107 operations to execute one instruction.
Again, this ratio is definitely not accurate, as operations are also used to read program, or in inactive mode, ... but it's still a good indicator of execution complexity.
Conclusion: this num interpreter needs 38% less code, and is 5x faster to execute !
Back to previous step
(No more next step this time 😅)
