We should have more tests of tail calls
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 6 Sep 2017 18:16:56 +0000 (18:16 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 6 Sep 2017 18:16:56 +0000 (18:16 +0000)
https://bugs.webkit.org/show_bug.cgi?id=175754

Reviewed by Sam Weinig.

This introduces a new test suite called TailBench9000, which will have benchmarks written in
JavaScript that avoid all looping except by tail call. As a warmup, I wrote a mergesort
benchmark and I proted n-body to use tail calls instead of for loops.

* TailBench9000: Added.
* TailBench9000/merge-sort-run.js: Added.
* TailBench9000/merge-sort.js: Added.
(TEST_mergeSort.createRNG):
(TEST_mergeSort.):
(TEST_mergeSort.merge):
(TEST_mergeSort.mergeSorted):
(TEST_mergeSort.checkSorted.check):
(TEST_mergeSort.checkSorted):
(TEST_mergeSort.add):
(TEST_mergeSort.build):
(TEST_mergeSort.compare):
(TEST_mergeSort.checkSpectrum):
(TEST_mergeSort.buildArray):
(TEST_mergeSort):
* TailBench9000/n-body-run.js: Added.
* TailBench9000/n-body.js: Added.
(TEST_nBody.Body):
(TEST_nBody.Body.prototype.offsetMomentum):
(TEST_nBody.Jupiter):
(TEST_nBody.Saturn):
(TEST_nBody.Uranus):
(TEST_nBody.Neptune):
(TEST_nBody.Sun):
(TEST_nBody.NBodySystem):
(TEST_nBody.NBodySystem.prototype.advance):
(TEST_nBody.NBodySystem.prototype.energy):
(TEST_nBody):

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

PerformanceTests/ChangeLog
PerformanceTests/TailBench9000/merge-sort-run.js [new file with mode: 0644]
PerformanceTests/TailBench9000/merge-sort.js [new file with mode: 0644]
PerformanceTests/TailBench9000/n-body-run.js [new file with mode: 0644]
PerformanceTests/TailBench9000/n-body.js [new file with mode: 0644]

index 75ed920..7328132 100644 (file)
@@ -1,3 +1,43 @@
+2017-08-19  Filip Pizlo  <fpizlo@apple.com>
+
+        We should have more tests of tail calls
+        https://bugs.webkit.org/show_bug.cgi?id=175754
+
+        Reviewed by Sam Weinig.
+        
+        This introduces a new test suite called TailBench9000, which will have benchmarks written in
+        JavaScript that avoid all looping except by tail call. As a warmup, I wrote a mergesort
+        benchmark and I proted n-body to use tail calls instead of for loops.
+
+        * TailBench9000: Added.
+        * TailBench9000/merge-sort-run.js: Added.
+        * TailBench9000/merge-sort.js: Added.
+        (TEST_mergeSort.createRNG):
+        (TEST_mergeSort.):
+        (TEST_mergeSort.merge):
+        (TEST_mergeSort.mergeSorted):
+        (TEST_mergeSort.checkSorted.check):
+        (TEST_mergeSort.checkSorted):
+        (TEST_mergeSort.add):
+        (TEST_mergeSort.build):
+        (TEST_mergeSort.compare):
+        (TEST_mergeSort.checkSpectrum):
+        (TEST_mergeSort.buildArray):
+        (TEST_mergeSort):
+        * TailBench9000/n-body-run.js: Added.
+        * TailBench9000/n-body.js: Added.
+        (TEST_nBody.Body):
+        (TEST_nBody.Body.prototype.offsetMomentum):
+        (TEST_nBody.Jupiter):
+        (TEST_nBody.Saturn):
+        (TEST_nBody.Uranus):
+        (TEST_nBody.Neptune):
+        (TEST_nBody.Sun):
+        (TEST_nBody.NBodySystem):
+        (TEST_nBody.NBodySystem.prototype.advance):
+        (TEST_nBody.NBodySystem.prototype.energy):
+        (TEST_nBody):
+
 2017-09-05  Ryosuke Niwa  <rniwa@webkit.org>
 
         Compute the final score using geometric mean in Speedometer 2.0
diff --git a/PerformanceTests/TailBench9000/merge-sort-run.js b/PerformanceTests/TailBench9000/merge-sort-run.js
new file mode 100644 (file)
index 0000000..30c7ee4
--- /dev/null
@@ -0,0 +1,4 @@
+load("merge-sort.js");
+
+for (var i = 0; i < 3000; ++i)
+    TEST_mergeSort();
diff --git a/PerformanceTests/TailBench9000/merge-sort.js b/PerformanceTests/TailBench9000/merge-sort.js
new file mode 100644 (file)
index 0000000..3725954
--- /dev/null
@@ -0,0 +1,154 @@
+"use strict";
+
+function TEST_mergeSort()
+{
+    function createRNG(seed)
+    {
+        return function() {
+            // Robert Jenkins' 32 bit integer hash function.
+            seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
+            seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
+            seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
+            seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
+            seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
+            seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
+            return (seed & 0xfffffff) / 0x10000000;
+        };
+    }
+    
+    let random = createRNG(0x7a11bec8);
+
+    function mergeSorted(array, compare)
+    {
+        if (array.length <= 1)
+            return array;
+        
+        let midIndex = Math.floor(array.length / 2);
+        let left = mergeSorted(array.slice(0, midIndex), compare);
+        let right = mergeSorted(array.slice(midIndex), compare);
+        
+        let result = [];
+        
+        function finish(source, index)
+        {
+            if (index >= source.length)
+                return;
+            result.push(source[index]);
+            return finish(source, index + 1);
+        }
+        
+        function merge(leftIndex, rightIndex)
+        {
+            if (leftIndex >= left.length)
+                return finish(right, rightIndex);
+            if (rightIndex >= right.length)
+                return finish(left, leftIndex);
+            
+            let leftValue = left[leftIndex];
+            let rightValue = right[rightIndex];
+            let comparisonResult = compare(leftValue, rightValue);
+            if (comparisonResult < 0) {
+                result.push(leftValue);
+                return merge(leftIndex + 1, rightIndex);
+            }
+            result.push(rightValue);
+            return merge(leftIndex, rightIndex + 1);
+        }
+        
+        merge(0, 0);
+        
+        return result;
+    }
+    
+    function checkSorted(array)
+    {
+        function check(index)
+        {
+            if (index >= array.length - 1)
+                return;
+            
+            if (array[index] > array[index + 1])
+                throw new Error("array not sorted at index " + index + ": " + array);
+            
+            return check(index + 1);
+        }
+        
+        check(0);
+    }
+    
+    function checkSpectrum(a, b)
+    {
+        var aMap = new Map();
+        var bMap = new Map();
+        
+        function add(map, value)
+        {
+            let existing = map.get(value);
+            if (existing == null)
+                existing = 0;
+            map.set(value, existing + 1);
+        }
+        
+        function build(map, array, index)
+        {
+            if (index >= array.length)
+                return;
+            
+            add(map, array[index]);
+            return build(map, array, index + 1);
+        }
+        
+        build(aMap, a, 0);
+        build(bMap, b, 0);
+        
+        function compare(keys)
+        {
+            let entry = keys.next();
+            if (entry.done)
+                return;
+            if (aMap.get(entry.value) != bMap.get(entry.value))
+                throw new Error("arrays don't have the same number of: " + entry.value + " (a = " + a + ", b = " + b + ")");
+            return compare(keys);
+        }
+        
+        compare(aMap.keys());
+    }
+    
+    function buildArray(length, value)
+    {
+        let array = [];
+        
+        function build()
+        {
+            if (array.length >= length)
+                return;
+            array.push(value(array.length));
+            return build();
+        }
+        
+        build();
+        
+        return array;
+    }
+    
+    let arrays = [
+        buildArray(10, x => x),
+        buildArray(10, x => -x),
+        buildArray(1000, x => x),
+        buildArray(10000, x => -x),
+        buildArray(10000, x => random())
+    ];
+    
+    function test(index)
+    {
+        if (index >= arrays.length)
+            return;
+        
+        let array = arrays[index];
+        let sorted = mergeSorted(array, (a, b) => a < b ? -1 : a > b ? 1 : 0);
+        checkSorted(sorted);
+        checkSpectrum(array, sorted);
+    }
+    
+    test(0);
+}
diff --git a/PerformanceTests/TailBench9000/n-body-run.js b/PerformanceTests/TailBench9000/n-body-run.js
new file mode 100644 (file)
index 0000000..e957111
--- /dev/null
@@ -0,0 +1,4 @@
+load("n-body.js");
+
+for (var i = 0; i < 300; ++i)
+    TEST_nBody();
diff --git a/PerformanceTests/TailBench9000/n-body.js b/PerformanceTests/TailBench9000/n-body.js
new file mode 100644 (file)
index 0000000..ace12ab
--- /dev/null
@@ -0,0 +1,237 @@
+"use strict";
+
+function TEST_nBody()
+{
+    /* The Great Computer Language Shootout
+       http://shootout.alioth.debian.org/
+       contributed by Isaac Gouy */
+
+    var PI = 3.141592653589793;
+    var SOLAR_MASS = 4 * PI * PI;
+    var DAYS_PER_YEAR = 365.24;
+
+    function Body(x,y,z,vx,vy,vz,mass){
+        this.x = x;
+        this.y = y;
+        this.z = z;
+        this.vx = vx;
+        this.vy = vy;
+        this.vz = vz;
+        this.mass = mass;
+    }
+
+    Body.prototype.offsetMomentum = function(px,py,pz) {
+        this.vx = -px / SOLAR_MASS;
+        this.vy = -py / SOLAR_MASS;
+        this.vz = -pz / SOLAR_MASS;
+        return this;
+    }
+
+    function Jupiter(){
+        return new Body(
+            4.84143144246472090e+00,
+                -1.16032004402742839e+00,
+                -1.03622044471123109e-01,
+            1.66007664274403694e-03 * DAYS_PER_YEAR,
+            7.69901118419740425e-03 * DAYS_PER_YEAR,
+                -6.90460016972063023e-05 * DAYS_PER_YEAR,
+            9.54791938424326609e-04 * SOLAR_MASS
+        );
+    }
+
+    function Saturn(){
+        return new Body(
+            8.34336671824457987e+00,
+            4.12479856412430479e+00,
+                -4.03523417114321381e-01,
+                -2.76742510726862411e-03 * DAYS_PER_YEAR,
+            4.99852801234917238e-03 * DAYS_PER_YEAR,
+            2.30417297573763929e-05 * DAYS_PER_YEAR,
+            2.85885980666130812e-04 * SOLAR_MASS
+        );
+    }
+
+    function Uranus(){
+        return new Body(
+            1.28943695621391310e+01,
+                -1.51111514016986312e+01,
+                -2.23307578892655734e-01,
+            2.96460137564761618e-03 * DAYS_PER_YEAR,
+            2.37847173959480950e-03 * DAYS_PER_YEAR,
+                -2.96589568540237556e-05 * DAYS_PER_YEAR,
+            4.36624404335156298e-05 * SOLAR_MASS
+        );
+    }
+
+    function Neptune(){
+        return new Body(
+            1.53796971148509165e+01,
+                -2.59193146099879641e+01,
+            1.79258772950371181e-01,
+            2.68067772490389322e-03 * DAYS_PER_YEAR,
+            1.62824170038242295e-03 * DAYS_PER_YEAR,
+                -9.51592254519715870e-05 * DAYS_PER_YEAR,
+            5.15138902046611451e-05 * SOLAR_MASS
+        );
+    }
+
+    function Sun(){
+        return new Body(0.0, 0.0, 0.0, 0.0, 0.0, 0.0, SOLAR_MASS);
+    }
+
+
+    function NBodySystem(bodies){
+        this.bodies = bodies;
+        var px = 0.0;
+        var py = 0.0;
+        var pz = 0.0;
+        var size = this.bodies.length;
+        
+        let iterate = i => {
+            if (i >= size)
+                return;
+            var b = this.bodies[i];
+            var m = b.mass;
+            px += b.vx * m;
+            py += b.vy * m;
+            pz += b.vz * m;
+            return iterate(i + 1);
+        }
+        
+        iterate(0);
+
+        this.bodies[0].offsetMomentum(px,py,pz);
+    }
+
+    NBodySystem.prototype.advance = function(dt){
+        var dx, dy, dz, distance, mag;
+        var size = this.bodies.length;
+        
+        let outerIterate = i => {
+            if (i >= size)
+                return;
+            
+            var bodyi = this.bodies[i];
+            
+            let innerIterate = j => {
+                if (j >= size)
+                    return;
+                
+                var bodyj = this.bodies[j];
+                dx = bodyi.x - bodyj.x;
+                dy = bodyi.y - bodyj.y;
+                dz = bodyi.z - bodyj.z;
+
+                distance = Math.sqrt(dx*dx + dy*dy + dz*dz);
+                mag = dt / (distance * distance * distance);
+
+                bodyi.vx -= dx * bodyj.mass * mag;
+                bodyi.vy -= dy * bodyj.mass * mag;
+                bodyi.vz -= dz * bodyj.mass * mag;
+
+                bodyj.vx += dx * bodyi.mass * mag;
+                bodyj.vy += dy * bodyi.mass * mag;
+                bodyj.vz += dz * bodyi.mass * mag;
+
+                return innerIterate(j + 1);
+            }
+            
+            innerIterate(i + 1);
+
+            return outerIterate(i + 1);
+        }
+        
+        outerIterate(0);
+
+        let iterate = i => {
+            if (i >= size)
+                return;
+
+            var body = this.bodies[i];
+            body.x += dt * body.vx;
+            body.y += dt * body.vy;
+            body.z += dt * body.vz;
+            
+            return iterate(i + 1);
+        }
+
+        iterate(0);
+    }
+
+    NBodySystem.prototype.energy = function(){
+        var dx, dy, dz, distance;
+        var e = 0.0;
+        var size = this.bodies.length;
+
+        let outerIterate = i => {
+            if (i >= size)
+                return;
+            
+            var bodyi = this.bodies[i];
+
+            e += 0.5 * bodyi.mass *
+                ( bodyi.vx * bodyi.vx
+                  + bodyi.vy * bodyi.vy
+                  + bodyi.vz * bodyi.vz );
+            
+            let innerIterate = j => {
+                if (j >= size)
+                    return;
+                
+                var bodyj = this.bodies[j];
+                dx = bodyi.x - bodyj.x;
+                dy = bodyi.y - bodyj.y;
+                dz = bodyi.z - bodyj.z;
+
+                distance = Math.sqrt(dx*dx + dy*dy + dz*dz);
+                e -= (bodyi.mass * bodyj.mass) / distance;
+
+                return innerIterate(j + 1);
+            }
+            
+            innerIterate(i + 1);
+            
+            return outerIterate(i + 1);
+        }
+        
+        outerIterate(0);
+        
+        return e;
+    }
+
+    var ret = 0;
+
+    let problem = n => {
+        if (n > 24)
+            return;
+        
+        (function(){
+            var bodies = new NBodySystem( Array(
+                Sun(),Jupiter(),Saturn(),Uranus(),Neptune()
+            ));
+            var max = n * 100;
+            
+            ret += bodies.energy();
+            
+            let iterate = i => {
+                if (i >= max)
+                    return;
+                
+                bodies.advance(0.01);
+
+                return iterate(i + 1);
+            };
+            iterate(0);
+
+            ret += bodies.energy();
+        })();
+
+        return problem(n * 2);
+    }
+
+    problem(3);
+
+    var expected = -1.3524862408537381;
+    if (ret != expected)
+        throw "ERROR: bad result: expected " + expected + " but got " + ret;
+}