A "Very Fast" Brainf*ck Self-Interpreter

After a week or so of frying my brain, I'm pleased to present "version 1" of my (self-described) "very fast" BF self-interpreter!

As far as I know, this is currently the fastest BF self-interpreter available (published) so far. But please feel free to prove me wrong by pointing out a faster version or by writing your own. And yes, that is meant to sound like a challenge!

[Update: My later Mark II Self-Interpreter is faster!]

I've compared its performance against three others that I am aware of and (except for a handful of very small target programs) my interpreter runs other BF code faster. That is, it executes less instructions than the others when interpreting the same top level program. Of course a "very fast BF self-interpreter" really is a bit of an oxymoron! Also, I'm sure the other authors were not necessarily trying to achieve "high performance" - in fact smaller size or even just showing such a thing was possible at all was more likely their primary motivation.

The other interpreters that I have used in my comparisons are by Frans Faase, NYYRIKKI and the one already described previously in the paper by Oleg Mazonka and Daniel Cristofani. This last one is the smallest and fastest of these three, and it is also much smaller than the one I have written - about half the size. My main goal was to try to get a faster version rather than smaller size although in this case there is a relationship. To be more precise, I was hoping for a lower eigenratio, and it may be that "faster" and "lower eigenratio" do not have to go together. Anyway, it is faster, but I'm still not sure about the eigenratio!

In addition the interpreter presented here uses only a slightly changed version of the loading routine from Daniel and Oleg's version. It was mind boggling enough for me to even try to understand their code, let alone change it. But as I mainly wanted something very compact for that part of my interpreter, it was easier to use some existing code that was already highly optimised in terms of size. Unfortunately, my brutal "minor changes" probably almost doubled its size. I will be revisiting that when I get to version 2! Anyway, a big "thank you" to Oleg and Daniel.

I am also very sure further improvements can be made to what I've done so far. But while it is tempting to keep wallowing in this particular Turing tar pit for a little longer, I've already been through about six iterations since I got the first "working" version up and running a couple of days ago. A little break now would probably be a good idea!

Having said all this, when stacking up multiple copies (but still only up to three) this version is not performing as well as I had hoped. It may be that the eigenratio is not that much lower despite its considerably better performance (in general) when used to run only one other BF program directly. Some more investigation and thinking on that front is probably required.

So finally, here is the "source code" including some comments. Note that the comments don't include any BF instructions so you should be able (if you wish) run it as it stands with most other bottom level BF interpeters.

Brainfuck Self Interpreter: by Clive Gifford

Version 1:  1 December 2006

The code to parse/load the input to the interpreter is almost exactly the same
as that in the interpreter described in the Nov 2003 paper by Oleg Mazonka and
Daniel Cristofani but the main interpreter loop is "new"
The main change in the loader code is to leave every second cell free for
working storage

The goal for this interpreter was to be more efficient with the main change in
approach being to only make one round trip between the emulated code and data
memory location for each instruction executed instead of multiple round trips
(according to the value of the internal coding scheme which for example is 8
for the "plus" instruction)

Other info:
An exclamation mark MUST be used to delimit the end of the input (code) to be
interpreted and any other "higher level" data ~ you can stack multiple copies
if you wish as long as they are all separated by exclamation marks also
Input is BF codes (with comments also if desired except for exclamation mark)
The underlying interpreter determines the possible range of data cell values
Does not use wrapping of data values

>>>>                      leave a little extra space before the program code
>+                        start in right hand cell of first program code pair
[
  ->>
  ++>+>+++++++            setup differences and read char as per dbfi
  [<++++>>++<-]++>>+>+>
  +++++[>++>++++++<<-]
  +>>>,<++
  [
    [>[->>]<[>>]<<-]      section 3
     <[<]<+>>[>]>
    [                     section 4
      <+>-
      [[<+>-]>]           section 5
      <                   section 6
      [
        [[-]<]            scan left and zero the differences
        ++<-              section 7
        [
          <+++++++++>[<->-]>>
        ]
        >>
      ]
    ]
    <<
  ]

 *** switch to handle three possibilities and spacing of instruction codes ***
 
  >[-]+<<                 set "done" flag and position to value
  [
    --
    [
      [-]
      >>- >+< <<
    ]
    >> [- <<<<[>+<-]>>>>> >+<] <<
  ]
  >> [- 0] <<
  >>>[<<<+>>>-]<<<
  
]

>>>+<<<<[<<]>>            go to first instruction

                          ********** MAIN INTERPRETER LOOPS STARTS HERER **********

[                         start on current instruction code
                          below is a big switch statement to decode instructions
  [<+>>+<-]               first need to move/copy instruction code and set flag so can
  +<-                     start with '(i less 1) (1) (i) where i is instruction code
  [
   -[
     -[
       -[
         -[
           -[
             -[
                -        can't be anything but 1 so bracketing not needed
                >- >> [>>] >> [>>]< + <[<<] << [<<] <    increment
              ]
              >[- >> [>>] >> [>>]< , <[<<] << [<<]] <    input
            ]
            >[- >> [>>] >> [>>]< - <[<<] << [<<]]<       decrement
          ]
          >[- >> [>>] >> [>>]< . <[<<] << [<<]]<         output
        ]
        >[- >> [>>] >> [>>] <<-<< [<<] << [<<]]<         move left
      ]
      >[- >> [>>] >> [>>] + [<<] << [<<]]<               move right
    ]
    >
    [-                      left hand bracket
      >> [>>] >> [>>]<      move to data cell
      [>+>>+<<<-]>          make double copy and move to first
      [<+>-]                restore original data cell value
      >>[<<+>>[-]]+         This and the following achieves
      <<[>>-<<-]            x = not x
      >>                    go to flag cell (0 or 1)

      Some tricky stuff here: set up (not flag) also so we can later choose
      appropriate instruction sequence to get back to code area in one pass
      In one case we set flags at the other end (data greater than 0) but
      for the other we just go back without setting any flags (data equals 0)

      [<<+>>>>+<<-]         make two copes of flag
      >>[<<+>>-]
      <<[>>+<<-]+           This and the following achieves
      >>[<<->>-]<<          x = not x

      <<                    so we now have (data) '(flag) (?) (not flag)

      [                     if flag set then
        -<< [<<] << [<<]<   clear and return to code section where we save
        << << ++            a 2 meaning we need (later) to match left bracket
        >>                  stop in zero cell for now
      ]

      >>                    if we executed code above then now at switch flag
                            else it will put us ready to return from data area

      [-<<<<<<[<<]<<[<<]<]  move back to switch flag without setting anything

      >
    ]
    <
  ]
  >
  [-                        right hand bracket
    >> [>>] >> [>>]<        move to data cell
    [>+>>+<<<-]>            make double copy and move to first
    [[<+>-]>>[-]+<<]        restore data from first then zero second and set flag
    >>                      go to flag cell (0 or 1)

    Some tricky stuff here: set up (not flag) also so we can later choose
    appropriate instruction sequence to get back to code area in one pass
    In one case we set flags at the other end (data greater than 0) but
    for the other we just go back without setting any flags (data equals 0)

    [<<+>>>>+<<-]           make two copes of flag
    >>[<<+>>-]
    <<[>>+<<-]+             This and the following achieves
    >>[<<->>-]<<            x = not x
       
    <<                      so we now have (data) '(flag) (?) (not flag)
    
    [                       if flag set then
      -<< [<<] << [<<]<     clear and return to code section where we save
      << << +               a 1 meaning we need (later) to match right bracket
      >>                    stop in zero cell for now
    ]

    >>                      if we executed code above then now at switch flag
                            else it will put us ready to return from data area
                          
    [-<<<<<<[<<]<<[<<]<]    move back to switch flag without setting anything
    
    >
  ]

  >[<+>-]                   restore original instruction code

  *** We are positioned in the cell immediately to the right of the   ***
  *** instruction that has just been "executed" in the switch above   ***
  *** The following code is to handle finding matching brackets       ***
  *** because code above has only set a cell value to 1 or 2 to show  ***
  *** what kind of loop scanning is required (1=scan left 2 = right)  ***
  
  << << <<                  position to cell showing if matching required
  [                         if non zero we need to find a matching bracket
    >> +                    set up "done" flag for switch and
    << -                    decrement switch value so now is 0 or 1
    [                       if 1 we are looking for matching right bracket
      - >> - >> +           clear switch value & "done" & set level to 1
      [                     while level is more than 0
        >>>[-<+>>+<]        double copy
        +<-                 set flag and prepare for switch
        [
         -[
            [-]
            > [- other] <   do nothing except clear flag
          ]
          > [- 1 <<< + >>>] < increment level
        ]
        > [- 0 <<< - >>>]   decrement level

        >[-<+>]<<           restore instruction code

        <<                  go to level
        [>>+<<-]            if level then move right one instruction
        >>
      ]
      << << <<              go back to switch value cell
    ]
    >>                      go to switch done flag and if still set then
    [                       we must be looking for a matching left bracket
      - << +                clear switch value & "done" & set level to 1
      [                     repeat while level is more than 0
        >>>[-<+>>+<]        double copy
        +<-                 set flag and prepare for switch
        [
         -[
            [-]
            > [- other] <   do nothing except clear flag
          ]
          > [- 1 <<< - >>>] < decrement level
        ]
        > [- 0 <<< + >>>]   increment level

        >[-<+>]<<           restore instruction code

        <<                  go to level
        [<<+>>-]            if level then move left one instruction
        <<
      ]
    ]
  ]

  >> >> >>

  >                         move forward to next instruction
]