Add a third benchmark to TailBench
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 6 Nov 2017 12:58:42 +0000 (12:58 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 6 Nov 2017 12:58:42 +0000 (12:58 +0000)
https://bugs.webkit.org/show_bug.cgi?id=178815

Reviewed by Saam Barati.

Add a new benchmark to TailBench: a BF interpreter written in a weird kinda functional style

PerformanceTests:

* TailBench9000/bf-interpreter.js: Added.
(lookForMatchingBracket):
(evalRec):
(infiniteTape):
(evalShort):

Tools:

* Scripts/run-jsc-benchmarks:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@224486 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/ChangeLog
PerformanceTests/TailBench9000/bf-interpreter.js [new file with mode: 0644]
Tools/ChangeLog
Tools/Scripts/run-jsc-benchmarks

index 84a2a96..7862c7b 100644 (file)
@@ -1,5 +1,20 @@
 2017-11-06  Robin Morisset  <rmorisset@apple.com>
 
+        Add a third benchmark to TailBench
+        https://bugs.webkit.org/show_bug.cgi?id=178815
+
+        Reviewed by Saam Barati.
+
+        Add a new benchmark to TailBench: a BF interpreter written in a weird kinda functional style
+
+        * TailBench9000/bf-interpreter.js: Added.
+        (lookForMatchingBracket):
+        (evalRec):
+        (infiniteTape):
+        (evalShort):
+
+2017-11-06  Robin Morisset  <rmorisset@apple.com>
+
         PerformanceTests/TailBench9000/merge-sort.js does not actually sort any of the large arrays it allocates
         https://bugs.webkit.org/show_bug.cgi?id=178817
 
diff --git a/PerformanceTests/TailBench9000/bf-interpreter.js b/PerformanceTests/TailBench9000/bf-interpreter.js
new file mode 100644 (file)
index 0000000..818c81a
--- /dev/null
@@ -0,0 +1,79 @@
+"use strict";
+
+function lookForMatchingBracket(program, pc, level) {
+    if (pc >= program.length)
+        throw "Error: Unbalanced brackets in the BF program, too many opening brackets";
+    
+    switch(program[pc]) {
+        case '[':
+            return lookForMatchingBracket(program, pc+1, level+1);
+        case ']':
+            if (level == 1)
+                return pc;
+            return lookForMatchingBracket(program, pc+1, level-1);
+        default:
+            return lookForMatchingBracket(program, pc+1, level);
+    }
+}
+
+// (leftTape, tapeCursor, rightTape) form a zipper:
+// leftTape is the (infinite) list of all values to the left of the cursor (from right to left),
+// while rightTape is the (infinite) list of all values to the right of the cursor (from left to right).
+// These lists are represented as functions that return an object with the first value, and a function for the rest of the list.
+function evalRec(program, pc, input, output, leftTape, tapeCursor, rightTape, loopContinuation)
+{
+    if (pc >= program.length)
+        return output;
+
+    switch(program[pc]) {
+    case '.':
+        const newOutput = output.concat(String.fromCharCode(tapeCursor));
+        return evalRec(program, pc+1, input, newOutput, leftTape, tapeCursor, rightTape, loopContinuation);
+    case ',':
+        return evalRec(program, pc+1, input.slice(1), output, leftTape, input.charCodeAt(0), rightTape, loopContinuation);
+    case '+':
+        return evalRec(program, pc+1, input, output, leftTape, tapeCursor+1, rightTape, loopContinuation);
+    case '-':
+        return evalRec(program, pc+1, input, output, leftTape, tapeCursor-1, rightTape, loopContinuation);
+    case '>':
+        const evaluatedRightTape = rightTape();
+        return evalRec(program, pc+1, input, output, ()=>({cursor: tapeCursor, rest: leftTape}), evaluatedRightTape.cursor, evaluatedRightTape.rest, loopContinuation);
+    case '<':
+        const evaluatedLeftTape = leftTape();
+        return evalRec(program, pc+1, input, output, evaluatedLeftTape.rest, evaluatedLeftTape.cursor, ()=>({cursor: tapeCursor, rest: rightTape}), loopContinuation);
+    case '[':
+        const matchingPC = lookForMatchingBracket(program, pc, 0);
+        if (tapeCursor == 0)
+            return evalRec(program, matchingPC+1, input, output, leftTape, tapeCursor, rightTape, loopContinuation);
+        return evalRec(program, pc+1, input, output, leftTape, tapeCursor, rightTape, (...varargs) => evalRec(program, pc, ...varargs, loopContinuation));
+    case ']':
+        return loopContinuation(input, output, leftTape, tapeCursor, rightTape);
+    default:
+        throw "Unsupported character: " + program[pc] + " at pc " + pc;
+    }
+}
+
+function infiniteTape()
+{
+    return {cursor: 0, rest: infiniteTape};
+}
+
+function evalShort(program, input)
+{
+    return evalRec(program, 0, input, "", infiniteTape, 0, infiniteTape, ()=>{throw "Error: Unbalanced brackets in the BF program, too many closing brackets";});
+}
+
+function test(program, input, expectedOutput)
+{
+    const result = evalShort(program, input);
+    if (result != expectedOutput)
+        throw ("Wrong result, program: " + program + " on input " + input + " had output " + result + " instead of " + expectedOutput);
+}
+
+for (var i = 0; i < 50000; ++i) {
+    test(",...", "A", "AAA");
+    test(",..+..--.", "C", "CCDDB");
+    test(",<,>..<..", "EF", "EEFF");
+    // The following program is taken from the Wikipedia brainfuck page:
+    test("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.", "", "Hello World!\n")
+}
index d4c8b36..5a7b483 100644 (file)
@@ -1,3 +1,14 @@
+2017-11-06  Robin Morisset  <rmorisset@apple.com>
+
+        Add a third benchmark to TailBench
+        https://bugs.webkit.org/show_bug.cgi?id=178815
+
+        Reviewed by Saam Barati.
+
+        Add a new benchmark to TailBench: a BF interpreter written in a weird kinda functional style
+
+        * Scripts/run-jsc-benchmarks:
+
 2017-11-04  Michael Catanzaro  <mcatanzaro@igalia.com>
 
         [GTK] Fix gtk-doc generation with gtk-doc master
index c34f1cb..1bb4eb5 100755 (executable)
@@ -3037,7 +3037,7 @@ begin
   }
 
   TAILBENCH = BenchmarkSuite.new("TailBench", :geometricMean, 0)
-  ["n-body", "merge-sort"].each {
+  ["n-body", "merge-sort", "bf-interpreter"].each {
     | name |
     TAILBENCH.add TailBenchBenchmark.new(name);
   }