Add clear cell optimization, make instruction list order more logical

[super-continent]

A common programming pattern in BF is to use [-] to reset the current memory cell to 0, this commit adds a Clear instruction which will replace detected instances of this pattern with an instruction that essentially ignores the loop and immediately sets the current cell to 0. This can impact performance greatly for some programs.

This commit also changes the order of the instruction list to put all instructions that do not contain values at the bottom, making the list slightly more readable and organized.

[dmitmel]

this commit adds

Pull requests can contain as many commits as you want, so I suggest you splitting up your commits in the future.

This can impact performance greatly for some programs

Idk, my benchmark yields almost zero difference.

This commit also changes the order of the instruction list to put all instructions that do not contain values at the bottom, making the list slightly more readable and organized.

I initially put instructions in the raising complexity order, like in the table in the README. I personally consider this more readable and organized.

---

Also, your implementation of this optimization contains a serious bug. Consider this test case:

  test!(
    test_clear_pattern,
    [Add(5), JumpIfZero(3), Add(-1), JumpIfNonZero(1), Print],
    [Add(5), Clear, Print]
  );

Your code will fail here because on every JumpIfZero instruction it compares all other instructions to a 2-element array, which obviously is going to fail when there are more than 2 instructions there. I've written my own optimization, here's a patch for ya:

diff --git a/src/optimizer.rs b/src/optimizer.rs
index 124a39b..dcf6469 100644
--- a/src/optimizer.rs
+++ b/src/optimizer.rs
@@ -48,15 +48,17 @@ pub fn optimize(program: &[Instruction]) -> Result<Vec<Instruction>> {
         Move(total)
       }

-    JumpIfZero(_) => {
-        match program[index + 1 .. program.len()] {
-            [Add(-1), JumpIfNonZero(_)] => {
-                skip_chars += 2;
-                Clear
-            },
-            _ => instruction,
+      JumpIfZero(jump1_address) => {
+        match (program.get(index + 1), program.get(index + 2)) {
+          (Some(Add(-1)), Some(JumpIfNonZero(jump2_address)))
+            if jump1_address == index + 2 && *jump2_address == index =>
+          {
+            skip_chars += 2;
+            Clear
+          }
+          _ => instruction,
         }
-    },
+      }

       _ => instruction,
     });
@@ -141,14 +143,9 @@ mod tests {
   );

   test!(
-      test_clear_pattern,
-      [
-      Add(1),
-      JumpIfZero(0),
-      Add(-1),
-      JumpIfNonZero(0),
-      ],
-      [Add(1), Clear]
+    test_clear_pattern,
+    [Add(5), JumpIfZero(3), Add(-1), JumpIfNonZero(1), Print],
+    [Add(5), Clear, Print]
   );

   test!(

---

Anyway, do you have interest in this project? I don't, but I have lots of time, so feel free to open PRs and I'll merge them as fast as I can (I live in GMT+3). There's a ton of work which can be done here, e.g. ideally parser must emit some kind of assembly and optimizer must work on this without knowledge of the original BF code, so that link_jumps isn't called twice. And please use rustfmt and document optimizations in the README.

[super-continent]

I do have interest in this project, I plan on committing more changes once I get a better understanding of BF optimizations I will fix the error in the optimization code and start documenting changes I make.

Also, the program you use for benchmarking may not contain the pattern, it varies quite a lot, I'm going to try and add optimizations that will cover other common patterns though, so hopefully speed will improve for a wider range of programs.

[super-continent]

Sorry about the mild commit spam, that should be everything though, I ran rustfmt on the code and fixed the range errors, I tried not to restrict it to a range of index..index+2 because I plan on adding more optimizations to specific loop patterns later on.

[super-continent]

I got around to benchmarking the performance of this optimization with certain programs and it does have an effect, so the program you're using to benchmark most likely lacks this pattern, the variation in program code makes it hard to predict what the performance impact will look like per-file, but I used hyperfine to compare the optimized/unoptimized clearloop performance on various programs, and it gave me these results:

hanoi.bf 18.96 ± 0.39 times faster (hanoi.bf is VERY susceptible to simple loop optimizations like this, most programs only use a few of these loops at most) golden-ratio.bf 1.20 ± 0.13 times faster prttab.bf 1.19 ± 0.46 times faster

Seems that most of the programs i looked at use this pattern, but sparingly enough to only give the interpreter a ~1.2 times speedup, copy/multiplication loop optimization is probably much more important

[dmitmel]

Sorry for late response. I'm in a summer camp right now, we didn't have Internet for the past 4 days.

[super-continent]

No issue, thanks for the help with my code, hoping I can contribute more later on.

[dmitmel]

Can you please document this optimization? (possibly in another PR)

[super-continent]

Ok, I'll work on that soon