JetStream should include a JavaScript version of the CDx real-time benchmark
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 19 Jun 2015 23:49:38 +0000 (23:49 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 19 Jun 2015 23:49:38 +0000 (23:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=146156

Reviewed by Geoffrey Garen.

This adds a JavaScript port of the CDx real-time benchmark to JetStream, and retires
the cordic test because it was previously the smallest and probably least interesting.

The new test, "cdjs", is mostly a faithful rewrite of the Java code into JavaScript.
I got the Java code from https://www.cs.purdue.edu/sss/projects/cdx/.

There are some differences:

- It uses RedBlackTree's for all sets and maps rather than hashtables. This is clearly
  more in the spirit of real-time than the CDx benchmark. FWIW, CDx used to use trees
  and I don't know why that changed in the latest version.

- CDjs doesn't attempt to avoid memory allocations, unlike the real-time Java version.
  I wrote the code that I wanted to write for aesthetics, rather than the code that I
  would have written if I tried to write the fastest code possible. Again, I believe
  that this is in the spirit of CDj - it's meant to test what would happen if you wrote
  real-timey stuff in a high level language and actually took advantage of that
  language to be more productive.

The test score reflects the average latency of the worst 10 samples out of 200 samples.
The simulation uses 1000 aircraft, flying along paths that result in some detected
collisions every once in a while. The benchmark validates its results by checking the
total number of collisions detected.

Apart from the integration into the JetStream harness, the CDjs directory contains a
fully self-contained benchmark that could be run either in the jsc shell or in browser.

This new code uses the same 3-clause BSD license as the Purdue code, and gives
attribution to Purdue in almost all files. I believe that is appropriate since I wrote
most of the JS files by looking at the Purdue Java code and trascribing to JavaScript.
In some cases, I even copy-pasted the Java code, like the complicated math for
four-dimensional intersections and voxel hashing.

* JetStream/CDjsSetup.js: Added.
* JetStream/Octane2Setup.js:
* JetStream/Reference.js:
* JetStream/cdjs: Added.
* JetStream/cdjs/benchmark.js: Added.
(benchmark):
* JetStream/cdjs/call_sign.js: Added.
(CallSign):
(CallSign.prototype.compareTo):
(CallSign.prototype.toString):
* JetStream/cdjs/collision.js: Added.
(Collision):
(Collision.prototype.toString):
* JetStream/cdjs/collision_detector.js: Added.
(CollisionDetector):
(CollisionDetector.prototype.handleNewFrame.get for):
(CollisionDetector.prototype.handleNewFrame):
* JetStream/cdjs/constants.js: Added.
* JetStream/cdjs/main.html: Added.
* JetStream/cdjs/main.js: Added.
* JetStream/cdjs/motion.js: Added.
(Motion):
(Motion.prototype.toString):
(Motion.prototype.delta):
(Motion.prototype.findIntersection):
* JetStream/cdjs/motion_test.js: Added.
(checkDoesIntersect):
(checkDoesNotIntersect):
(makeMotion):
* JetStream/cdjs/red_black_tree.js: Added.
(RedBlackTree):
(RedBlackTree.):
* JetStream/cdjs/red_black_tree_test.js: Added.
(test):
(test.):
* JetStream/cdjs/reduce_collision_set.js: Added.
(drawMotionOnVoxelMap):
(drawMotionOnVoxelMap.):
(.get reduceCollisionSet):
* JetStream/cdjs/reduce_collision_set_test.js: Added.
(makeMotion):
(keys):
(test):
* JetStream/cdjs/simulator.js: Added.
(Simulator):
(Simulator.prototype.simulate):
* JetStream/cdjs/util.js: Added.
(compareNumbers):
(averageAbovePercentile):
(currentTime):
(else.currentTime):
* JetStream/cdjs/vector_2d.js: Added.
(Vector2D):
(Vector2D.prototype.plus):
(Vector2D.prototype.minus):
(Vector2D.prototype.toString):
(Vector2D.prototype.compareTo):
* JetStream/cdjs/vector_3d.js: Added.
(Vector3D):
(Vector3D.prototype.plus):
(Vector3D.prototype.minus):
(Vector3D.prototype.dot):
(Vector3D.prototype.squaredMagnitude):
(Vector3D.prototype.magnitude):
(Vector3D.prototype.times):
(Vector3D.prototype.as2D):
(Vector3D.prototype.toString):
* JetStream/create.rb:
* JetStream/index-TEMPLATE.html:
* JetStream/sunspider/cordic.js: Removed.

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

24 files changed:
PerformanceTests/ChangeLog
PerformanceTests/JetStream/CDjsSetup.js [new file with mode: 0644]
PerformanceTests/JetStream/Octane2Setup.js
PerformanceTests/JetStream/Reference.js
PerformanceTests/JetStream/cdjs/benchmark.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/call_sign.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/collision.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/collision_detector.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/constants.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/main.html [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/main.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/motion.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/motion_test.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/red_black_tree.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/red_black_tree_test.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/reduce_collision_set.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/simulator.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/util.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/vector_2d.js [new file with mode: 0644]
PerformanceTests/JetStream/cdjs/vector_3d.js [new file with mode: 0644]
PerformanceTests/JetStream/create.rb
PerformanceTests/JetStream/index-TEMPLATE.html
PerformanceTests/JetStream/sunspider/cordic.js [deleted file]

index 84e3d19..0bbb923 100644 (file)
@@ -1,3 +1,114 @@
+2015-06-19  Filip Pizlo  <fpizlo@apple.com>
+
+        JetStream should include a JavaScript version of the CDx real-time benchmark
+        https://bugs.webkit.org/show_bug.cgi?id=146156
+
+        Reviewed by Geoffrey Garen.
+        
+        This adds a JavaScript port of the CDx real-time benchmark to JetStream, and retires
+        the cordic test because it was previously the smallest and probably least interesting.
+        
+        The new test, "cdjs", is mostly a faithful rewrite of the Java code into JavaScript.
+        I got the Java code from https://www.cs.purdue.edu/sss/projects/cdx/.
+        
+        There are some differences:
+        
+        - It uses RedBlackTree's for all sets and maps rather than hashtables. This is clearly
+          more in the spirit of real-time than the CDx benchmark. FWIW, CDx used to use trees
+          and I don't know why that changed in the latest version.
+        
+        - CDjs doesn't attempt to avoid memory allocations, unlike the real-time Java version.
+          I wrote the code that I wanted to write for aesthetics, rather than the code that I
+          would have written if I tried to write the fastest code possible. Again, I believe
+          that this is in the spirit of CDj - it's meant to test what would happen if you wrote
+          real-timey stuff in a high level language and actually took advantage of that
+          language to be more productive.
+        
+        The test score reflects the average latency of the worst 10 samples out of 200 samples.
+        The simulation uses 1000 aircraft, flying along paths that result in some detected
+        collisions every once in a while. The benchmark validates its results by checking the
+        total number of collisions detected.
+        
+        Apart from the integration into the JetStream harness, the CDjs directory contains a
+        fully self-contained benchmark that could be run either in the jsc shell or in browser.
+        
+        This new code uses the same 3-clause BSD license as the Purdue code, and gives
+        attribution to Purdue in almost all files. I believe that is appropriate since I wrote
+        most of the JS files by looking at the Purdue Java code and trascribing to JavaScript.
+        In some cases, I even copy-pasted the Java code, like the complicated math for
+        four-dimensional intersections and voxel hashing.
+
+        * JetStream/CDjsSetup.js: Added.
+        * JetStream/Octane2Setup.js:
+        * JetStream/Reference.js:
+        * JetStream/cdjs: Added.
+        * JetStream/cdjs/benchmark.js: Added.
+        (benchmark):
+        * JetStream/cdjs/call_sign.js: Added.
+        (CallSign):
+        (CallSign.prototype.compareTo):
+        (CallSign.prototype.toString):
+        * JetStream/cdjs/collision.js: Added.
+        (Collision):
+        (Collision.prototype.toString):
+        * JetStream/cdjs/collision_detector.js: Added.
+        (CollisionDetector):
+        (CollisionDetector.prototype.handleNewFrame.get for):
+        (CollisionDetector.prototype.handleNewFrame):
+        * JetStream/cdjs/constants.js: Added.
+        * JetStream/cdjs/main.html: Added.
+        * JetStream/cdjs/main.js: Added.
+        * JetStream/cdjs/motion.js: Added.
+        (Motion):
+        (Motion.prototype.toString):
+        (Motion.prototype.delta):
+        (Motion.prototype.findIntersection):
+        * JetStream/cdjs/motion_test.js: Added.
+        (checkDoesIntersect):
+        (checkDoesNotIntersect):
+        (makeMotion):
+        * JetStream/cdjs/red_black_tree.js: Added.
+        (RedBlackTree):
+        (RedBlackTree.):
+        * JetStream/cdjs/red_black_tree_test.js: Added.
+        (test):
+        (test.):
+        * JetStream/cdjs/reduce_collision_set.js: Added.
+        (drawMotionOnVoxelMap):
+        (drawMotionOnVoxelMap.):
+        (.get reduceCollisionSet):
+        * JetStream/cdjs/reduce_collision_set_test.js: Added.
+        (makeMotion):
+        (keys):
+        (test):
+        * JetStream/cdjs/simulator.js: Added.
+        (Simulator):
+        (Simulator.prototype.simulate):
+        * JetStream/cdjs/util.js: Added.
+        (compareNumbers):
+        (averageAbovePercentile):
+        (currentTime):
+        (else.currentTime):
+        * JetStream/cdjs/vector_2d.js: Added.
+        (Vector2D):
+        (Vector2D.prototype.plus):
+        (Vector2D.prototype.minus):
+        (Vector2D.prototype.toString):
+        (Vector2D.prototype.compareTo):
+        * JetStream/cdjs/vector_3d.js: Added.
+        (Vector3D):
+        (Vector3D.prototype.plus):
+        (Vector3D.prototype.minus):
+        (Vector3D.prototype.dot):
+        (Vector3D.prototype.squaredMagnitude):
+        (Vector3D.prototype.magnitude):
+        (Vector3D.prototype.times):
+        (Vector3D.prototype.as2D):
+        (Vector3D.prototype.toString):
+        * JetStream/create.rb:
+        * JetStream/index-TEMPLATE.html:
+        * JetStream/sunspider/cordic.js: Removed.
+
 2015-06-17  Javier Fernandez  <jfernandez@igalia.com>
 
         [CSS Grid Layout] We should add performance tests for stretching logic
diff --git a/PerformanceTests/JetStream/CDjsSetup.js b/PerformanceTests/JetStream/CDjsSetup.js
new file mode 100644 (file)
index 0000000..3914411
--- /dev/null
@@ -0,0 +1,60 @@
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
+// 1. Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+// 2. Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//
+// THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+// BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+// THE POSSIBILITY OF SUCH DAMAGE.
+
+var CDjsFiles = [
+    "constants.js",
+    "util.js",
+    "red_black_tree.js",
+    "call_sign.js",
+    "vector_2d.js",
+    "vector_3d.js",
+    "motion.js",
+    "reduce_collision_set.js",
+    "simulator.js",
+    "collision.js",
+    "collision_detector.js",
+    "benchmark.js"
+];
+
+var code = "";
+for (var i = 0; i < CDjsFiles.length; ++i)
+    code += "<script src=\"cdjs/" + CDjsFiles[i] + "\"></script>\n";
+code += "<script>\n";
+code += "console.log(\"running...\");\n";
+code += "var __result = benchmark();\n";
+code += "console.log(\"got result: \" + __result);\n";
+code += "top.JetStream.reportResult(__result);\n";
+code += "</script>";
+
+console.log("code = " + code);
+
+JetStream.addPlan({
+    name: "cdjs",
+    benchmarks: [{
+        name: "cdjs",
+        category: "Latency",
+        unit: "ms"
+    }],
+    code: code
+});
+
index 58aa5ba..6729d24 100644 (file)
@@ -1,4 +1,4 @@
-// Copyright (C) 2014 Apple Inc. All rights reserved.
+// Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions
@@ -49,7 +49,7 @@ for (var i = 0; i < Octane2Suites.length; ++i) {
     if (suite.latency) {
         myBenchmarks.push({
             name: suite.name + "-latency",
-            prefix: "&sigma; = ",
+            unit: "ms",
             category: "Latency"
         });
     }
index a18c344..3b7ff84 100644 (file)
@@ -1,4 +1,4 @@
-// Copyright (C) 2014 Apple Inc. All rights reserved.
+// Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions
@@ -25,7 +25,6 @@ JetStream.addReferences({
     "3d-cube": 7.3,
     "3d-raytrace": 8.05,
     "base64": 4.2,
-    "cordic": 3,
     "crypto-aes": 6.6,
     "crypto-md5": 3,
     "crypto-sha1": 2.05,
@@ -65,5 +64,6 @@ JetStream.addReferences({
     "zlib": 887.666666666666,
     "typescript": 1149.9999999999993,
     "lua": 29858,
+    "cdjs": 14,
     "geomean": 31.556451704472156,
 });
diff --git a/PerformanceTests/JetStream/cdjs/benchmark.js b/PerformanceTests/JetStream/cdjs/benchmark.js
new file mode 100644 (file)
index 0000000..9f8d108
--- /dev/null
@@ -0,0 +1,80 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function benchmark() {
+    var verbosity = 0;
+    var numAircraft = 1000;
+    var numFrames = 200;
+    var expectedCollisions = 14484;
+    var percentile = 95;
+
+    var simulator = new Simulator(numAircraft);
+    var detector = new CollisionDetector();
+    var lastTime = currentTime();
+    var results = [];
+    for (var i = 0; i < numFrames; ++i) {
+        var time = i / 10;
+        
+        var collisions = detector.handleNewFrame(simulator.simulate(time));
+        
+        var before = lastTime;
+        var after = currentTime();
+        lastTime = after;
+        var result = {
+            time: after - before,
+            numCollisions: collisions.length
+        };
+        if (verbosity >= 2)
+            result.collisions = collisions;
+        results.push(result);
+    }
+
+    if (verbosity >= 1) {
+        for (var i = 0; i < results.length; ++i) {
+            var string = "Frame " + i + ": " + results[i].time + " ms.";
+            if (results[i].numCollisions)
+                string += " (" + results[i].numCollisions + " collisions.)";
+            print(string);
+            if (verbosity >= 2 && results[i].collisions.length)
+                print("    Collisions: " + results[i].collisions);
+        }
+    }
+
+    // Check results.
+    var actualCollisions = 0;
+    for (var i = 0; i < results.length; ++i)
+        actualCollisions += results[i].numCollisions;
+    if (actualCollisions != expectedCollisions) {
+        throw new Error("Bad number of collisions: " + actualCollisions + " (expected " +
+                        expectedCollisions + ")");
+    }
+
+    // Find the worst 5% 
+    var times = [];
+    for (var i = 0; i < results.length; ++i)
+        times.push(results[i].time);
+    
+    return averageAbovePercentile(times, percentile);
+}
diff --git a/PerformanceTests/JetStream/cdjs/call_sign.js b/PerformanceTests/JetStream/cdjs/call_sign.js
new file mode 100644 (file)
index 0000000..e83ed8b
--- /dev/null
@@ -0,0 +1,37 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function CallSign(value) {
+    this._value = value;
+}
+
+CallSign.prototype.compareTo = function(other) {
+    return this._value.localeCompare(other._value);
+}
+
+CallSign.prototype.toString = function() {
+    return this._value;
+}
+
diff --git a/PerformanceTests/JetStream/cdjs/collision.js b/PerformanceTests/JetStream/cdjs/collision.js
new file mode 100644 (file)
index 0000000..7fd615d
--- /dev/null
@@ -0,0 +1,34 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function Collision(aircraft, position) {
+    this.aircraft = aircraft;
+    this.position = position;
+}
+
+Collision.prototype.toString = function() {
+    return "Collision(" + this.aircraft + " at " + this.position + ")";
+};
+
diff --git a/PerformanceTests/JetStream/cdjs/collision_detector.js b/PerformanceTests/JetStream/cdjs/collision_detector.js
new file mode 100644 (file)
index 0000000..4f4181e
--- /dev/null
@@ -0,0 +1,74 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function CollisionDetector() {
+    this._state = new RedBlackTree();
+}
+
+CollisionDetector.prototype.handleNewFrame = function(frame) {
+    var motions = [];
+    var seen = new RedBlackTree();
+    
+    for (var i = 0; i < frame.length; ++i) {
+        var aircraft = frame[i];
+        
+        var oldPosition = this._state.put(aircraft.callsign, aircraft.position);
+        var newPosition = aircraft.position;
+        seen.put(aircraft.callsign, true);
+        
+        if (!oldPosition) {
+            // Treat newly introduced aircraft as if they were stationary.
+            oldPosition = newPosition;
+        }
+        
+        motions.push(new Motion(aircraft.callsign, oldPosition, newPosition));
+    }
+    
+    // Remove aircraft that are no longer present.
+    var toRemove = [];
+    this._state.forEach(function(callsign, position) {
+        if (!seen.get(callsign))
+            toRemove.push(callsign);
+    });
+    for (var i = 0; i < toRemove.length; ++i)
+        this._state.remove(toRemove[i]);
+    
+    var allReduced = reduceCollisionSet(motions);
+    var collisions = [];
+    for (var reductionIndex = 0; reductionIndex < allReduced.length; ++reductionIndex) {
+        var reduced = allReduced[reductionIndex];
+        for (var i = 0; i < reduced.length; ++i) {
+            var motion1 = reduced[i];
+            for (var j = i + 1; j < reduced.length; ++j) {
+                var motion2 = reduced[j];
+                var collision = motion1.findIntersection(motion2);
+                if (collision)
+                    collisions.push(new Collision([motion1.callsign, motion2.callsign], collision));
+            }
+        }
+    }
+    
+    return collisions;
+};
diff --git a/PerformanceTests/JetStream/cdjs/constants.js b/PerformanceTests/JetStream/cdjs/constants.js
new file mode 100644 (file)
index 0000000..aba312f
--- /dev/null
@@ -0,0 +1,34 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+var Constants = {};
+Constants.MIN_X = 0;
+Constants.MIN_Y = 0;
+Constants.MAX_X = 1000;
+Constants.MAX_Y = 1000;
+Constants.MIN_Z = 0;
+Constants.MAX_Z = 10;
+Constants.PROXIMITY_RADIUS = 1;
+Constants.GOOD_VOXEL_SIZE = Constants.PROXIMITY_RADIUS * 2;
diff --git a/PerformanceTests/JetStream/cdjs/main.html b/PerformanceTests/JetStream/cdjs/main.html
new file mode 100644 (file)
index 0000000..5eec1d9
--- /dev/null
@@ -0,0 +1,58 @@
+<!--
+ Copyright (c) 2001-2010, Purdue University. All rights reserved.
+ Copyright (C) 2015 Apple Inc. All rights reserved.
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+  * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+  * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+  * Neither the name of the Purdue University nor the
+    names of its contributors may be used to endorse or promote products
+    derived from this software without specific prior written permission.
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+ DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+-->
+
+<html>
+<head>
+<title>CDjs</title>
+<script src="constants.js"></script>
+<script src="util.js"></script>
+<script src="red_black_tree.js"></script>
+<script src="call_sign.js"></script>
+<script src="vector_2d.js"></script>
+<script src="vector_3d.js"></script>
+<script src="motion.js"></script>
+<script src="reduce_collision_set.js"></script>
+<script src="simulator.js"></script>
+<script src="collision.js"></script>
+<script src="collision_detector.js"></script>
+<script src="benchmark.js"></script>
+<script>
+    function runTest() {
+        var result = benchmark();
+        document.getElementById("result-summary").innerHTML = "Average worst case: " + result;
+    }
+</script>
+</head>
+<body>
+<h1>CDjs</h1>
+<p>
+  <div id="result-summary"></div>
+  <div><a href="javascript:runTest()">Start Test</a></div>
+</p>
+</body>
+</html>
+
diff --git a/PerformanceTests/JetStream/cdjs/main.js b/PerformanceTests/JetStream/cdjs/main.js
new file mode 100644 (file)
index 0000000..78fc90c
--- /dev/null
@@ -0,0 +1,42 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+load("constants.js");
+load("util.js");
+load("red_black_tree.js");
+load("call_sign.js");
+load("vector_2d.js");
+load("vector_3d.js");
+load("motion.js");
+load("reduce_collision_set.js");
+load("simulator.js");
+load("collision.js");
+load("collision_detector.js");
+load("benchmark.js");
+
+var result = benchmark();
+
+print("Average worst case: " + result + " ms.");
+
diff --git a/PerformanceTests/JetStream/cdjs/motion.js b/PerformanceTests/JetStream/cdjs/motion.js
new file mode 100644 (file)
index 0000000..515341a
--- /dev/null
@@ -0,0 +1,136 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function Motion(callsign, posOne, posTwo) {
+    this.callsign = callsign;
+    this.posOne = posOne;
+    this.posTwo = posTwo;
+}
+
+Motion.prototype.toString = function() {
+    return "Motion(" + this.callsign + " from " + this.posOne + " to " + this.posTwo + ")";
+};
+
+Motion.prototype.delta = function() {
+    return this.posTwo.minus(this.posOne);
+};
+
+Motion.prototype.findIntersection = function(other) {
+    var init1 = this.posOne;
+    var init2 = other.posOne;
+    var vec1 = this.delta();
+    var vec2 = other.delta();
+    var radius = Constants.PROXIMITY_RADIUS;
+    
+    // this test is not geometrical 3-d intersection test, it takes the fact that the aircraft move
+    // into account ; so it is more like a 4d test
+    // (it assumes that both of the aircraft have a constant speed over the tested interval)
+    
+    // we thus have two points, each of them moving on its line segment at constant speed ; we are looking
+    // for times when the distance between these two points is smaller than r 
+    
+    // vec1 is vector of aircraft 1
+    // vec2 is vector of aircraft 2
+    
+    // a = (V2 - V1)^T * (V2 - V1)
+    var a = vec2.minus(vec1).squaredMagnitude();
+    
+    if (a != 0) {
+        // we are first looking for instances of time when the planes are exactly r from each other
+        // at least one plane is moving ; if the planes are moving in parallel, they do not have constant speed
+
+        // if the planes are moving in parallel, then
+        //   if the faster starts behind the slower, we can have 2, 1, or 0 solutions
+        //   if the faster plane starts in front of the slower, we can have 0 or 1 solutions
+
+        // if the planes are not moving in parallel, then
+
+
+        // point P1 = I1 + vV1
+        // point P2 = I2 + vV2
+        //   - looking for v, such that dist(P1,P2) = || P1 - P2 || = r
+
+        // it follows that || P1 - P2 || = sqrt( < P1-P2, P1-P2 > )
+        //   0 = -r^2 + < P1 - P2, P1 - P2 >
+        //  from properties of dot product
+        //   0 = -r^2 + <I1-I2,I1-I2> + v * 2<I1-I2, V1-V2> + v^2 *<V1-V2,V1-V2>
+        //   so we calculate a, b, c - and solve the quadratic equation
+        //   0 = c + bv + av^2
+
+        // b = 2 * <I1-I2, V1-V2>
+
+        var b = 2 * init1.minus(init2).dot(vec1.minus(vec2));
+
+        // c = -r^2 + (I2 - I1)^T * (I2 - I1)
+        var c = -radius * radius + init2.minus(init1).squaredMagnitude();
+
+        var discr = b * b - 4 * a * c;
+        if (discr < 0)
+            return null;
+
+        var v1 = (-b - Math.sqrt(discr)) / (2 * a);
+        var v2 = (-b + Math.sqrt(discr)) / (2 * a);
+
+        if (v1 <= v2 && ((v1 <= 1 && 1 <= v2) ||
+                         (v1 <= 0 && 0 <= v2) ||
+                         (0 <= v1 && v2 <= 1))) {
+            // Pick a good "time" at which to report the collision.
+            var v;
+            if (v1 <= 0) {
+                // The collision started before this frame. Report it at the start of the frame.
+                v = 0;
+            } else {
+                // The collision started during this frame. Report it at that moment.
+                v = v1;
+            }
+            
+            var result1 = init1.plus(vec1.times(v));
+            var result2 = init2.plus(vec2.times(v));
+            
+            var result = result1.plus(result2).times(0.5);
+            if (result.x >= Constants.MIN_X &&
+                result.x <= Constants.MAX_X &&
+                result.y >= Constants.MIN_Y &&
+                result.y <= Constants.MAX_Y &&
+                result.z >= Constants.MIN_Z &&
+                result.z <= Constants.MAX_Z)
+                return result;
+        }
+
+return null;
+    }
+    
+    // the planes have the same speeds and are moving in parallel (or they are not moving at all)
+    // they  thus have the same distance all the time ; we calculate it from the initial point
+    
+    // dist = || i2 - i1 || = sqrt(  ( i2 - i1 )^T * ( i2 - i1 ) )
+    
+    var dist = init2.minus(init1).magnitude();
+    if (dist <= radius)
+        return init1.plus(init2).times(0.5);
+    
+    return null;
+};
+
diff --git a/PerformanceTests/JetStream/cdjs/motion_test.js b/PerformanceTests/JetStream/cdjs/motion_test.js
new file mode 100644 (file)
index 0000000..2e5db7d
--- /dev/null
@@ -0,0 +1,93 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+load("constants.js");
+load("util.js");
+load("call_sign.js");
+load("vector_2d.js");
+load("vector_3d.js");
+load("motion.js");
+
+var epsilon = 0.000001;
+
+function checkDoesIntersect(motionOne, motionTwo, expected) {
+    print(motionOne + " and " + motionTwo + ":");
+    var actual = motionOne.findIntersection(motionTwo);
+    if (!actual)
+        throw new Error("Was supposed to intersect at " + expected + " but didn't");
+    
+    var delta = actual.minus(expected).magnitude();
+    if (delta > epsilon) {
+        throw new Error("Was supposed to intersect at " + expected + " but intersected at " +
+                        actual + ", which is " + delta + " away");
+    }
+    
+    print("    Intersected at " + actual + ", which is " + delta + " away from " + expected + ".");
+}
+
+function checkDoesNotIntersect(motionOne, motionTwo) {
+    print(motionOne + " and " + motionTwo + ":");
+    var actual = motionOne.findIntersection(motionTwo);
+    if (actual)
+        throw new Error("Was not supposed to intersect but intersected at " + actual);
+    
+    print("    No intersection, as expected.");
+}
+
+var makeMotion = (function() {
+    var counter = 0;
+    return function(x1, y1, z1, x2, y2, z2) {
+        return new Motion(new CallSign("foo" + (++counter)),
+                          new Vector3D(x1, y1, z1),
+                          new Vector3D(x2, y2, z2));
+    }
+})();
+
+checkDoesNotIntersect(
+    makeMotion(0, 0, 0, 10, 0, 0),
+    makeMotion(0, 10, 0, 10, 10, 0));
+
+checkDoesNotIntersect(
+    makeMotion(0, 0, 0, 10, 0, 0),
+    makeMotion(0, 1 + epsilon, 0, 10, 1 + epsilon, 0));
+
+checkDoesIntersect(
+    makeMotion(0, 0, 0, 10, 0, 0),
+    makeMotion(0, 1, 0, 10, 1, 0),
+    new Vector3D(0, 0.5, 0));
+
+checkDoesIntersect(
+    makeMotion(0, 0, 0, 10, 0, 0),
+    makeMotion(0, 10, 0, 10, 0, 0),
+    new Vector3D(9, 0.5, 0));
+
+checkDoesIntersect(
+    makeMotion(0, 0, 0, 9.5, 0, 0),
+    makeMotion(0, 10, 0, 9.65, 0.35, 0),
+    new Vector3D(8.939830722446178, 0.49507224691354423, 0));
+
+// FIXME: Add more tests here. Sadly, the original Java code for this benchmark had an extensive
+// JUnit test suite for intersections, but this didn't get included in any of the releases and I no
+// longer have access to the original CVS repository (yes, CVS).
diff --git a/PerformanceTests/JetStream/cdjs/red_black_tree.js b/PerformanceTests/JetStream/cdjs/red_black_tree.js
new file mode 100644 (file)
index 0000000..79f3aa4
--- /dev/null
@@ -0,0 +1,409 @@
+/*
+ * Copyright (C) 2010, 2011, 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+var RedBlackTree = (function(){
+    function compare(a, b) {
+        return a.compareTo(b);
+    }
+    
+    function treeMinimum(x) {
+        while (x.left)
+            x = x.left;
+        return x;
+    }
+    
+    function treeMaximum(x) {
+        while (x.right)
+            x = x.right;
+        return x;
+    }
+    
+    function Node(key, value) {
+        this.key = key;
+        this.value = value;
+        this.left = null;
+        this.right = null;
+        this.parent = null;
+        this.color = "red";
+    }
+    
+    Node.prototype.successor = function() {
+        var x = this;
+        if (x.right)
+            return treeMinimum(x.right);
+        var y = x.parent;
+        while (y && x == y.right) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    };
+    
+    Node.prototype.predecessor = function() {
+        var x = this;
+        if (x.left)
+            return treeMaximum(x.left);
+        var y = x.parent;
+        while (y && x == y.left) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    };
+    
+    Node.prototype.toString = function() {
+        return this.key + "=>" + this.value + " (" + this.color + ")";
+    };
+    
+    function RedBlackTree() {
+        this._root = null;
+    }
+    
+    RedBlackTree.prototype.put = function(key, value) {
+        var insertionResult = this._treeInsert(key, value);
+        if (!insertionResult.isNewEntry)
+            return insertionResult.oldValue;
+        var x = insertionResult.newNode;
+        
+        while (x != this._root && x.parent.color == "red") {
+            if (x.parent == x.parent.parent.left) {
+                var y = x.parent.parent.right;
+                if (y && y.color == "red") {
+                    // Case 1
+                    x.parent.color = "black";
+                    y.color = "black";
+                    x.parent.parent.color = "red";
+                    x = x.parent.parent;
+                } else {
+                    if (x == x.parent.right) {
+                        // Case 2
+                        x = x.parent;
+                        this._leftRotate(x);
+                    }
+                    // Case 3
+                    x.parent.color = "black";
+                    x.parent.parent.color = "red";
+                    this._rightRotate(x.parent.parent);
+                }
+            } else {
+                // Same as "then" clause with "right" and "left" exchanged.
+                var y = x.parent.parent.left;
+                if (y && y.color == "red") {
+                    // Case 1
+                    x.parent.color = "black";
+                    y.color = "black";
+                    x.parent.parent.color = "red";
+                    x = x.parent.parent;
+                } else {
+                    if (x == x.parent.left) {
+                        // Case 2
+                        x = x.parent;
+                        this._rightRotate(x);
+                    }
+                    // Case 3
+                    x.parent.color = "black";
+                    x.parent.parent.color = "red";
+                    this._leftRotate(x.parent.parent);
+                }
+            }
+        }
+        
+        this._root.color = "black";
+        return null;
+    };
+    
+    RedBlackTree.prototype.remove = function(key) {
+        var z = this._findNode(key);
+        if (!z)
+            return null;
+        
+        // Y is the node to be unlinked from the tree.
+        var y;
+        if (!z.left || !z.right)
+            y = z;
+        else
+            y = z.successor();
+
+        // Y is guaranteed to be non-null at this point.
+        var x;
+        if (y.left)
+            x = y.left;
+        else
+            x = y.right;
+        
+        // X is the child of y which might potentially replace y in the tree. X might be null at
+        // this point.
+        var xParent;
+        if (x) {
+            x.parent = y.parent;
+            xParent = x.parent;
+        } else
+            xParent = y.parent;
+        if (!y.parent)
+            this._root = x;
+        else {
+            if (y == y.parent.left)
+                y.parent.left = x;
+            else
+                y.parent.right = x;
+        }
+        
+        if (y != z) {
+            if (y.color == "black")
+                this._removeFixup(x, xParent);
+            
+            y.parent = z.parent;
+            y.color = z.color;
+            y.left = z.left;
+            y.right = z.right;
+            
+            if (z.left)
+                z.left.parent = y;
+            if (z.right)
+                z.right.parent = y;
+            if (z.parent) {
+                if (z.parent.left == z)
+                    z.parent.left = y;
+                else
+                    z.parent.right = y;
+            } else
+                this._root = y;
+        } else if (y.color == "black")
+            this._removeFixup(x, xParent);
+        
+        return z.value;
+    };
+    
+    RedBlackTree.prototype.get = function(key) {
+        var node = this._findNode(key);
+        if (!node)
+            return null;
+        return node.value;
+    };
+    
+    RedBlackTree.prototype.forEach = function(callback) {
+        if (!this._root)
+            return;
+        for (var current = treeMinimum(this._root); current; current = current.successor())
+            callback(current.key, current.value);
+    };
+    
+    RedBlackTree.prototype.asArray = function() {
+        var result = [];
+        this.forEach(function(key, value) {
+            result.push({key: key, value: value});
+        });
+        return result;
+    };
+    
+    RedBlackTree.prototype.toString = function() {
+        var result = "[";
+        var first = true;
+        this.forEach(function(key, value) {
+            if (first)
+                first = false;
+            else
+                result += ", ";
+            result += key + "=>" + value;
+        });
+        return result + "]";
+    };
+    
+    RedBlackTree.prototype._findNode = function(key) {
+        for (var current = this._root; current;) {
+            var comparisonResult = compare(key, current.key);
+            if (!comparisonResult)
+                return current;
+            if (comparisonResult < 0)
+                current = current.left;
+            else
+                current = current.right;
+        }
+        return null;
+    };
+    
+    RedBlackTree.prototype._treeInsert = function(key, value) {
+        var y = null;
+        var x = this._root;
+        while (x) {
+            y = x;
+            var comparisonResult = key.compareTo(x.key);
+            if (comparisonResult < 0)
+                x = x.left;
+            else if (comparisonResult > 0)
+                x = x.right;
+            else {
+                var oldValue = x.value;
+                x.value = value;
+                return {isNewEntry:false, oldValue:oldValue};
+            }
+        }
+        var z = new Node(key, value);
+        z.parent = y;
+        if (!y)
+            this._root = z;
+        else {
+            if (key.compareTo(y.key) < 0)
+                y.left = z;
+            else
+                y.right = z;
+        }
+        return {isNewEntry:true, newNode:z};
+    };
+    
+    RedBlackTree.prototype._leftRotate = function(x) {
+        var y = x.right;
+        
+        // Turn y's left subtree into x's right subtree.
+        x.right = y.left;
+        if (y.left)
+            y.left.parent = x;
+        
+        // Link x's parent to y.
+        y.parent = x.parent;
+        if (!x.parent)
+            this._root = y;
+        else {
+            if (x == x.parent.left)
+                x.parent.left = y;
+            else
+                x.parent.right = y;
+        }
+        
+        // Put x on y's left.
+        y.left = x;
+        x.parent = y;
+        
+        return y;
+    };
+    
+    RedBlackTree.prototype._rightRotate = function(y) {
+        var x = y.left;
+        
+        // Turn x's right subtree into y's left subtree.
+        y.left = x.right;
+        if (x.right)
+            x.right.parent = y;
+        
+        // Link y's parent to x;
+        x.parent = y.parent;
+        if (!y.parent)
+            this._root = x;
+        else {
+            if (y == y.parent.left)
+                y.parent.left = x;
+            else
+                y.parent.right = x;
+        }
+        
+        x.right = y;
+        y.parent = x;
+        
+        return x;
+    };
+    
+    RedBlackTree.prototype._removeFixup = function(x, xParent) {
+        while (x != this._root && (!x || x.color == "black")) {
+            if (x == xParent.left) {
+                // Note: the text points out that w cannot be null. The reason is not obvious from
+                // simply looking at the code; it comes about from the properties of the red-black
+                // tree.
+                var w = xParent.right;
+                if (w.color == "red") {
+                    // Case 1
+                    w.color = "black";
+                    xParent.color = "red";
+                    this._leftRotate(xParent);
+                    w = xParent.right;
+                }
+                if ((!w.left || w.left.color == "black")
+                    && (!w.right || w.right.color == "black")) {
+                    // Case 2
+                    w.color = "red";
+                    x = xParent;
+                    xParent = x.parent;
+                } else {
+                    if (!w.right || w.right.color == "black") {
+                        // Case 3
+                        w.left.color = "black";
+                        w.color = "red";
+                        this._rightRotate(w);
+                        w = xParent.right;
+                    }
+                    // Case 4
+                    w.color = xParent.color;
+                    xParent.color = "black";
+                    if (w.right)
+                        w.right.color = "black";
+                    this._leftRotate(xParent);
+                    x = this._root;
+                    xParent = x.parent;
+                }
+            } else {
+                // Same as "then" clause with "right" and "left" exchanged.
+                
+                var w = xParent.left;
+                if (w.color == "red") {
+                    // Case 1
+                    w.color = "black";
+                    xParent.color = "red";
+                    this._rightRotate(xParent);
+                    w = xParent.left;
+                }
+                if ((!w.right || w.right.color == "black")
+                    && (!w.left || w.left.color == "black")) {
+                    // Case 2
+                    w.color = "red";
+                    x = xParent;
+                    xParent = x.parent;
+                } else {
+                    if (!w.left || w.left.color == "black") {
+                        // Case 3
+                        w.right.color = "black";
+                        w.color = "red";
+                        this._leftRotate(w);
+                        w = xParent.left;
+                    }
+                    // Case 4
+                    w.color = xParent.color;
+                    xParent.color = "black";
+                    if (w.left)
+                        w.left.color = "black";
+                    this._rightRotate(xParent);
+                    x = this._root;
+                    xParent = x.parent;
+                }
+            }
+        }
+        if (x)
+            x.color = "black";
+    };
+    
+    return RedBlackTree;
+})();
+
diff --git a/PerformanceTests/JetStream/cdjs/red_black_tree_test.js b/PerformanceTests/JetStream/cdjs/red_black_tree_test.js
new file mode 100644 (file)
index 0000000..193eba4
--- /dev/null
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2010, 2011, 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+load("red_black_tree.js");
+
+// The control string is a list of commands. Each command is two characters, with the first
+// identifying the operation and the second giving a key.
+var test = (function(){
+    function PairVector() {
+        this._vector = [];
+    }
+
+    PairVector.prototype.put = function(key, value) {
+        for (var i = 0; i < this._vector.length; ++i) {
+            if (!this._vector[i].key.compareTo(key)) {
+                var result = this._vector[i].value;
+                this._vector[i].value = value;
+                return result;
+            }
+        }
+        this._vector.push({key: key, value: value});
+        return null;
+    };
+
+    PairVector.prototype.remove = function(key, value) {
+        for (var i = 0; i < this._vector.length; ++i) {
+            if (!this._vector[i].key.compareTo(key)) {
+                var result = this._vector[i].value;
+                this._vector[i] = this._vector[this._vector.length - 1];
+                this._vector.pop();
+                return result;
+            }
+        }
+        return null;
+    };
+
+    PairVector.prototype.get = function(key, value) {
+        for (var i = 0; i < this._vector.length; ++i) {
+            if (!this._vector[i].key.compareTo(key))
+                return this._vector[i].value;
+        }
+        return null;
+    };
+    
+    PairVector.prototype.toString = function() {
+        var copy = this._vector.concat();
+        copy.sort(function(a, b) {
+            return a.key.compareTo(b.key);
+        });
+        var result = "[";
+        for (var i = 0; i < copy.length; ++i) {
+            if (i)
+                result += ", ";
+            result += copy[i].key + "=>" + copy[i].value;
+        }
+        return result + "]";
+    };
+    
+    String.prototype.compareTo = String.prototype.localeCompare;
+
+    var counter = 0;
+    
+    return function(controlString) {
+        print("Running " + JSON.stringify(controlString) + ":");
+        var asVector = new PairVector();
+        var asTree = new RedBlackTree();
+        
+        function fail(when) {
+            throw new Error(
+                "FAIL: " + when + ", tree = " + asTree + ", vector = " + asVector);
+        }
+        
+        for (var index = 0; index < controlString.length; index += 2) {
+            var command = controlString[index];
+            var key = controlString[index + 1];
+            var value = ++counter;
+            
+            switch (command) {
+            case "+":
+                var oldVectorValue = asVector.put(key, value);
+                var oldTreeValue = asTree.put(key, value);
+                if (oldVectorValue !== oldTreeValue) {
+                    fail("Adding " + key + "=>" + value + ", vector got " +
+                         oldVectorValue + " but tree got " + oldTreeValue);
+                }
+                break;
+                
+            case "*":
+                var oldVectorValue = asVector.get(key);
+                var oldTreeValue = asTree.get(key);
+                if (oldVectorValue !== oldTreeValue) {
+                    fail("Getting " + key + ", vector got " +
+                         oldVectorValue + " but tree got " + oldTreeValue);
+                }
+                break;
+                
+            case "!":
+                var oldVectorValue = asVector.remove(key);
+                var oldTreeValue = asTree.remove(key);
+                if (oldVectorValue !== oldTreeValue) {
+                    fail("Removing " + key + ", vector got " +
+                         oldVectorValue + " but tree got " + oldTreeValue);
+                }
+                break;
+                
+            default:
+                throw Error("Bad command: " + command);
+            }
+        }
+        
+        if ("" + asVector != "" + asTree)
+            fail("Bad result at end");
+        
+        print("    Success, tree is: " + asTree);
+    };
+})();
+
+test("");
+test("+a");
+test("*x!z");
+test("+a*x!z");
+test("+a*a!a");
+test("+a+b");
+test("+a+b+c");
+test("+a+b+c+d");
+test("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d");
+test("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z");
+test("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z");
+
diff --git a/PerformanceTests/JetStream/cdjs/reduce_collision_set.js b/PerformanceTests/JetStream/cdjs/reduce_collision_set.js
new file mode 100644 (file)
index 0000000..cc73f24
--- /dev/null
@@ -0,0 +1,148 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+var drawMotionOnVoxelMap = (function() {
+    var voxelSize = Constants.GOOD_VOXEL_SIZE;
+    var horizontal = new Vector2D(voxelSize, 0);
+    var vertical = new Vector2D(0, voxelSize);
+    
+    function voxelHash(position) {
+        var xDiv = (position.x / voxelSize) | 0;
+        var yDiv = (position.y / voxelSize) | 0;
+        
+        var result = new Vector2D();
+        result.x = voxelSize * xDiv;
+        result.y = voxelSize * yDiv;
+        
+        if (position.x < 0)
+            result.x -= voxelSize;
+        if (position.y < 0)
+            result.y -= voxelSize;
+        
+        return result;
+    }
+    
+    return function(voxelMap, motion) {
+        var seen = new RedBlackTree();
+        
+        function putIntoMap(voxel) {
+            var array = voxelMap.get(voxel);
+            if (!array)
+                voxelMap.put(voxel, array = []);
+            array.push(motion);
+        }
+        
+        function isInVoxel(voxel) {
+            if (voxel.x > Constants.MAX_X ||
+                voxel.x < Constants.MIN_X ||
+                voxel.y > Constants.MAX_Y ||
+                voxel.y < Constants.MIN_Y)
+                return false;
+            
+            var init = motion.posOne;
+            var fin = motion.posTwo;
+            
+            var v_s = voxelSize;
+            var r = Constants.PROXIMITY_RADIUS / 2;
+            
+            var v_x = voxel.x;
+            var x0 = init.x;
+            var xv = fin.x - init.x;
+            
+            var v_y = voxel.y;
+            var y0 = init.y;
+            var yv = fin.y - init.y;
+            
+            var low_x, high_x;
+            low_x = (v_x - r - x0) / xv;
+            high_x = (v_x + v_s + r - x0) / xv;
+            
+            if (xv < 0) {
+                var tmp = low_x;
+                low_x = high_x;
+                high_x = tmp;
+            }
+            
+            var low_y, high_y;
+            low_y = (v_y - r - y0) / yv;
+            high_y = (v_y + v_s + r - y0) / yv;
+            
+            if (yv < 0) {
+                var tmp = low_y;
+                low_y = high_y;
+                high_y = tmp;
+            }
+            
+            if (false) {
+                print("v_x = " + v_x + ", x0 = " + x0 + ", xv = " + xv + ", v_y = " + v_y + ", y0 = " + y0 + ", yv = " + yv + ", low_x = " + low_x + ", low_y = " + low_y + ", high_x = " + high_x + ", high_y = " + high_y);
+            }
+            
+            return (((xv == 0 && v_x <= x0 + r && x0 - r <= v_x + v_s) /* no motion in x */ || 
+                     ((low_x <= 1 && 1 <= high_x) || (low_x <= 0 && 0 <= high_x) ||
+                      (0 <= low_x && high_x <= 1))) && 
+                    ((yv == 0 && v_y <= y0 + r && y0 - r <= v_y + v_s) /* no motion in y */ || 
+                     ((low_y <= 1 && 1 <= high_y) || (low_y <= 0 && 0 <= high_y) ||
+                      (0 <= low_y && high_y <= 1))) && 
+                    (xv == 0 || yv == 0 || /* no motion in x or y or both */
+                     (low_y <= high_x && high_x <= high_y) ||
+                     (low_y <= low_x && low_x <= high_y) ||
+                     (low_x <= low_y && high_y <= high_x)));
+        }
+        
+        function recurse(nextVoxel) {
+            if (!isInVoxel(nextVoxel, motion))
+                return;
+            if (seen.put(nextVoxel, true))
+                return;
+            
+            putIntoMap(nextVoxel);
+            
+            recurse(nextVoxel.minus(horizontal));
+            recurse(nextVoxel.plus(horizontal));
+            recurse(nextVoxel.minus(vertical));
+            recurse(nextVoxel.plus(vertical));
+            recurse(nextVoxel.minus(horizontal).minus(vertical));
+            recurse(nextVoxel.minus(horizontal).plus(vertical));
+            recurse(nextVoxel.plus(horizontal).minus(vertical));
+            recurse(nextVoxel.plus(horizontal).plus(vertical));
+        }
+        
+        recurse(voxelHash(motion.posOne));
+    };
+})();
+
+function reduceCollisionSet(motions) {
+    var voxelMap = new RedBlackTree();
+    for (var i = 0; i < motions.length; ++i)
+        drawMotionOnVoxelMap(voxelMap, motions[i]);
+        
+    var result = [];
+    voxelMap.forEach(function(key, value) {
+        if (value.length > 1)
+            result.push(value);
+    });
+    return result;
+}
+
diff --git a/PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js b/PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js
new file mode 100644 (file)
index 0000000..992dbb0
--- /dev/null
@@ -0,0 +1,82 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+load("constants.js");
+load("util.js");
+load("red_black_tree.js");
+load("call_sign.js");
+load("vector_2d.js");
+load("vector_3d.js");
+load("motion.js");
+load("reduce_collision_set.js");
+
+var makeMotion = (function() {
+    var counter = 0;
+    return function(x1, y1, z1, x2, y2, z2) {
+        return new Motion(new CallSign("foo" + (++counter)),
+                          new Vector3D(x1, y1, z1),
+                          new Vector3D(x2, y2, z2));
+    }
+})();
+
+function drawMotion(motion) {
+    var voxelMap = new RedBlackTree();
+    drawMotionOnVoxelMap(voxelMap, motion);
+    return voxelMap;
+}
+
+function keys(voxelMap) {
+    var result = "[";
+    var first = true;
+    voxelMap.forEach(function(key, value) {
+        if (first)
+            first = false;
+        else
+            result += ", ";
+        result += key;
+    });
+    return result + "]";
+}
+
+function test(x1, y1, z1, x2, y2, z2, expected) {
+    var motion = makeMotion(x1, y1, z1, x2, y2, z2);
+    print(motion + ":");
+    var actual = keys(drawMotion(motion));
+    if (expected != actual)
+        throw new Error("Wrong voxel map: " + actual);
+    print("    Got: " + actual);
+}
+
+test(0, 0, 0, 1, 1, 1, "[[0, 0]]");
+test(0, 0, 0, 2, 2, 2, "[[0, 0], [0, 2], [2, 0], [2, 2]]");
+test(0, 0, 0, 4, 4, 4, "[[0, 0], [0, 2], [2, 0], [2, 2], [2, 4], [4, 2], [4, 4]]");
+test(0, 0, 0, 10, 0, 0, "[[0, 0], [2, 0], [4, 0], [6, 0], [8, 0], [10, 0]]");
+test(2, 0, 0, 0, 2, 2, "[[0, 0], [0, 2], [2, 0]]");
+test(0, 2, 0, 2, 0, 2, "[[0, 0], [0, 2], [2, 0]]");
+test(2, 2, 0, 0, 0, 2, "[[0, 0], [0, 2], [2, 0], [2, 2]]");
+test(0, 0, 0, 2, 0, 0, "[[0, 0], [2, 0]]");
+test(0, 0, 0, 0, 2, 0, "[[0, 0], [0, 2]]");
+test(2, 0, 0, 0, 0, 0, "[[0, 0], [2, 0]]");
+test(0, 2, 0, 0, 0, 0, "[[0, 0], [0, 2]]");
diff --git a/PerformanceTests/JetStream/cdjs/simulator.js b/PerformanceTests/JetStream/cdjs/simulator.js
new file mode 100644 (file)
index 0000000..62939f0
--- /dev/null
@@ -0,0 +1,46 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function Simulator(numAircraft) {
+    this._aircraft = [];
+    for (var i = 0; i < numAircraft; ++i)
+        this._aircraft.push(new CallSign("foo" + i));
+}
+
+Simulator.prototype.simulate = function(time) {
+    var frame = [];
+    for (var i = 0; i < this._aircraft.length; i += 2) {
+        frame.push({
+            callsign: this._aircraft[i],
+            position: new Vector3D(time, Math.cos(time) * 2 + i * 3, 10)
+        });
+        frame.push({
+            callsign: this._aircraft[i + 1],
+            position: new Vector3D(time, Math.sin(time) * 2 + i * 3, 10)
+        });
+    }
+    return frame;
+};
+
diff --git a/PerformanceTests/JetStream/cdjs/util.js b/PerformanceTests/JetStream/cdjs/util.js
new file mode 100644 (file)
index 0000000..69542e8
--- /dev/null
@@ -0,0 +1,82 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function compareNumbers(a, b) {
+    if (a == b)
+        return 0;
+    if (a < b)
+        return -1;
+    if (a > b)
+        return 1;
+    
+    // We say that NaN is smaller than non-NaN.
+    if (a == a)
+        return 1;
+    return -1;
+}
+
+function averageAbovePercentile(numbers, percentile) {
+    // Don't change the original array.
+    numbers = numbers.slice();
+    
+    // Sort in ascending order.
+    numbers.sort(function(a, b) { return a - b; });
+    
+    // Now the elements we want are at the end. Keep removing them until the array size shrinks too much.
+    // Examples assuming percentile = 99:
+    //
+    // - numbers.length starts at 100: we will remove just the worst entry and then not remove anymore,
+    //   since then numbers.length / originalLength = 0.99.
+    //
+    // - numbers.length starts at 1000: we will remove the ten worst.
+    //
+    // - numbers.length starts at 10: we will remove just the worst.
+    var numbersWeWant = [];
+    var originalLength = numbers.length;
+    while (numbers.length / originalLength > percentile / 100)
+        numbersWeWant.push(numbers.pop());
+    
+    var sum = 0;
+    for (var i = 0; i < numbersWeWant.length; ++i)
+        sum += numbersWeWant[i];
+    
+    var result = sum / numbersWeWant.length;
+    
+    // Do a sanity check.
+    if (numbers.length && result < numbers[numbers.length - 1]) {
+        throw "Sanity check fail: the worst case result is " + result +
+            " but we didn't take into account " + numbers;
+    }
+    
+    return result;
+}
+
+var currentTime;
+if (this.performance && performance.now)
+    currentTime = function() { return performance.now() };
+else if (preciseTime)
+    currentTime = function() { return preciseTime() * 1000; };
+else
+    currentTime = function() { return 0 + new Date(); };
diff --git a/PerformanceTests/JetStream/cdjs/vector_2d.js b/PerformanceTests/JetStream/cdjs/vector_2d.js
new file mode 100644 (file)
index 0000000..4b7262a
--- /dev/null
@@ -0,0 +1,51 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function Vector2D(x, y) {
+    this.x = x;
+    this.y = y;
+}
+
+Vector2D.prototype.plus = function(other) {
+    return new Vector2D(this.x + other.x,
+                        this.y + other.y);
+};
+
+Vector2D.prototype.minus = function(other) {
+    return new Vector2D(this.x - other.x,
+                        this.y - other.y);
+};
+
+Vector2D.prototype.toString = function() {
+    return "[" + this.x + ", " + this.y + "]";
+};
+
+Vector2D.prototype.compareTo = function(other) {
+    var result = compareNumbers(this.x, other.x);
+    if (result)
+        return result;
+    return compareNumbers(this.y, other.y);
+};
+
diff --git a/PerformanceTests/JetStream/cdjs/vector_3d.js b/PerformanceTests/JetStream/cdjs/vector_3d.js
new file mode 100644 (file)
index 0000000..0827a15
--- /dev/null
@@ -0,0 +1,70 @@
+// Copyright (c) 2001-2010, Purdue University. All rights reserved.
+// Copyright (C) 2015 Apple Inc. All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//  * Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+//  * Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+//  * Neither the name of the Purdue University nor the
+//    names of its contributors may be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
+// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function Vector3D(x, y, z) {
+    this.x = x;
+    this.y = y;
+    this.z = z;
+}
+
+Vector3D.prototype.plus = function(other) {
+    return new Vector3D(this.x + other.x,
+                        this.y + other.y,
+                        this.z + other.z);
+};
+
+Vector3D.prototype.minus = function(other) {
+    return new Vector3D(this.x - other.x,
+                        this.y - other.y,
+                        this.z - other.z);
+};
+
+Vector3D.prototype.dot = function(other) {
+    return this.x * other.x + this.y * other.y + this.z * other.z;
+};
+
+Vector3D.prototype.squaredMagnitude = function() {
+    return this.dot(this);
+};
+
+Vector3D.prototype.magnitude = function() {
+    return Math.sqrt(this.squaredMagnitude());
+};
+
+Vector3D.prototype.times = function(amount) {
+    return new Vector3D(this.x * amount,
+                        this.y * amount,
+                        this.z * amount);
+};
+
+Vector3D.prototype.as2D = function() {
+    return new Vector2D(this.x, this.y);
+};
+
+Vector3D.prototype.toString = function() {
+    return "[" + this.x + ", " + this.y + ", " + this.z + "]";
+};
+
+
index c5812fc..f6c1bca 100755 (executable)
@@ -26,7 +26,7 @@
 require "pathname"
 require "shellwords"
 
-VERSION = "1.1-alpha1"
+VERSION = "1.1-alpha2"
 DIRECTORY_NAME = "JetStream-#{VERSION}"
 
 raise unless system("rm -rf " + DIRECTORY_NAME)
@@ -34,7 +34,7 @@ raise unless system("mkdir -p " + DIRECTORY_NAME)
 raise unless system("mkdir -p #{DIRECTORY_NAME}/sunspider")
 raise unless system("mkdir -p #{DIRECTORY_NAME}/sources")
 raise unless system("cp sunspider/*.js #{DIRECTORY_NAME}/sunspider")
-raise unless system("cp -r JetStream.css JetStreamDriver.js LLVM-test-suite-LICENSE.txt simple Octane2 Octane2Setup.js SimpleSetup.js SunSpiderSetup.js Octane OctaneSetup.js Reference.js TestingSetup.js JetStream-Logo.png JetStream-Logo@2x.png Swoosh.png Swoosh@2x.png " + DIRECTORY_NAME)
+raise unless system("cp -r JetStream.css JetStreamDriver.js LLVM-test-suite-LICENSE.txt simple Octane2 Octane2Setup.js SimpleSetup.js SunSpiderSetup.js Octane OctaneSetup.js CDjsSetup.js cdjs Reference.js TestingSetup.js JetStream-Logo.png JetStream-Logo@2x.png Swoosh.png Swoosh@2x.png " + DIRECTORY_NAME)
 
 def detemplatize(basename)
     File.open(DIRECTORY_NAME + "/#{basename}.html", "w") {
@@ -116,6 +116,7 @@ transferSource("code-first-load", "Octane2/code-load.js")
 transferSource("box2d", "Octane2/box2d.js")
 transferSource("zlib", "Octane2/zlib.js", "Octane2/zlib-data.js")
 transferSource("typescript", "Octane2/typescript.js", "Octane2/typescript-compiler.js", "Octane2/typescript-input.js")
+transferSource("cdjs", "cdjs/constants.js", "cdjs/util.js", "cdjs/red_black_tree.js", "cdjs/call_sign.js", "cdjs/vector_2d.js", "cdjs/vector_3d.js", "cdjs/motion.js", "cdjs/reduce_collision_set.js", "cdjs/simulator.js", "cdjs/collision.js", "cdjs/collision_detector.js", "cdjs/benchmark.js")
 
 puts "You can now run JetStream by navigating to file://" + (Pathname.new(DIRECTORY_NAME) + "index.html").realpath.to_s
 
index 46fe884..cbd635a 100644 (file)
@@ -48,6 +48,7 @@
     <script src="SimpleSetup.js"></script>
     <script src="OctaneSetup.js"></script>
     <script src="Octane2Setup.js"></script>
+    <script src="CDjsSetup.js"></script>
     <script src="Reference.js"></script>
 </head>
 <body onload="initialize()">
diff --git a/PerformanceTests/JetStream/sunspider/cordic.js b/PerformanceTests/JetStream/sunspider/cordic.js
deleted file mode 100644 (file)
index f71bd11..0000000
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * Copyright (C) Rich Moore.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
- */
-
-/////. Start CORDIC
-
-var AG_CONST = 0.6072529350;
-
-function FIXED(X)
-{
-  return X * 65536.0;
-}
-
-function FLOAT(X)
-{
-  return X / 65536.0;
-}
-
-function DEG2RAD(X)
-{
-  return 0.017453 * (X);
-}
-
-var Angles = [
-  FIXED(45.0), FIXED(26.565), FIXED(14.0362), FIXED(7.12502),
-  FIXED(3.57633), FIXED(1.78991), FIXED(0.895174), FIXED(0.447614),
-  FIXED(0.223811), FIXED(0.111906), FIXED(0.055953),
-  FIXED(0.027977) 
-              ];
-
-var Target = 28.027;
-
-function cordicsincos(Target) {
-    var X;
-    var Y;
-    var TargetAngle;
-    var CurrAngle;
-    var Step;
-    X = FIXED(AG_CONST);         /* AG_CONST * cos(0) */
-    Y = 0;                       /* AG_CONST * sin(0) */
-
-    TargetAngle = FIXED(Target);
-    CurrAngle = 0;
-    for (Step = 0; Step < 12; Step++) {
-        var NewX;
-        if (TargetAngle > CurrAngle) {
-            NewX = X - (Y >> Step);
-            Y = (X >> Step) + Y;
-            X = NewX;
-            CurrAngle += Angles[Step];
-        } else {
-            NewX = X + (Y >> Step);
-            Y = -(X >> Step) + Y;
-            X = NewX;
-            CurrAngle -= Angles[Step];
-        }
-    }
-
-    return FLOAT(X) * FLOAT(Y);
-}
-
-///// End CORDIC
-
-var total = 0;
-
-function cordic( runs ) {
-  var start = new Date();
-
-  for ( var i = 0 ; i < runs ; i++ ) {
-      total += cordicsincos(Target);
-  }
-
-  var end = new Date();
-
-  return end.getTime() - start.getTime();
-}
-
-cordic(25000);
-
-var expected = 10362.570468755888;
-
-if (total != expected)
-    throw "ERROR: bad result: expected " + expected + " but got " + total;
-