Diff
Modified: trunk/PerformanceTests/ChangeLog (221684 => 221685)
--- trunk/PerformanceTests/ChangeLog 2017-09-06 17:47:29 UTC (rev 221684)
+++ trunk/PerformanceTests/ChangeLog 2017-09-06 18:16:56 UTC (rev 221685)
@@ -1,3 +1,43 @@
+2017-08-19 Filip Pizlo <[email protected]>
+
+ 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 <[email protected]>
Compute the final score using geometric mean in Speedometer 2.0
Added: trunk/PerformanceTests/TailBench9000/merge-sort-run.js (0 => 221685)
--- trunk/PerformanceTests/TailBench9000/merge-sort-run.js (rev 0)
+++ trunk/PerformanceTests/TailBench9000/merge-sort-run.js 2017-09-06 18:16:56 UTC (rev 221685)
@@ -0,0 +1,4 @@
+load("merge-sort.js");
+
+for (var i = 0; i < 3000; ++i)
+ TEST_mergeSort();
Added: trunk/PerformanceTests/TailBench9000/merge-sort.js (0 => 221685)
--- trunk/PerformanceTests/TailBench9000/merge-sort.js (rev 0)
+++ trunk/PerformanceTests/TailBench9000/merge-sort.js 2017-09-06 18:16:56 UTC (rev 221685)
@@ -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);
+}
Added: trunk/PerformanceTests/TailBench9000/n-body-run.js (0 => 221685)
--- trunk/PerformanceTests/TailBench9000/n-body-run.js (rev 0)
+++ trunk/PerformanceTests/TailBench9000/n-body-run.js 2017-09-06 18:16:56 UTC (rev 221685)
@@ -0,0 +1,4 @@
+load("n-body.js");
+
+for (var i = 0; i < 300; ++i)
+ TEST_nBody();
Added: trunk/PerformanceTests/TailBench9000/n-body.js (0 => 221685)
--- trunk/PerformanceTests/TailBench9000/n-body.js (rev 0)
+++ trunk/PerformanceTests/TailBench9000/n-body.js 2017-09-06 18:16:56 UTC (rev 221685)
@@ -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;
+}
