Diff
Modified: trunk/PerformanceTests/ChangeLog (185779 => 185780)
--- trunk/PerformanceTests/ChangeLog 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/ChangeLog 2015-06-19 23:49:38 UTC (rev 185780)
@@ -1,3 +1,114 @@
+2015-06-19 Filip Pizlo <fpi...@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 <jfernan...@igalia.com>
[CSS Grid Layout] We should add performance tests for stretching logic
Added: trunk/PerformanceTests/JetStream/CDjsSetup.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/CDjsSetup.js (rev 0)
+++ trunk/PerformanceTests/JetStream/CDjsSetup.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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="" + 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
+});
+
Modified: trunk/PerformanceTests/JetStream/Octane2Setup.js (185779 => 185780)
--- trunk/PerformanceTests/JetStream/Octane2Setup.js 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/JetStream/Octane2Setup.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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 @@
if (suite.latency) {
myBenchmarks.push({
name: suite.name + "-latency",
- prefix: "σ = ",
+ unit: "ms",
category: "Latency"
});
}
Modified: trunk/PerformanceTests/JetStream/Reference.js (185779 => 185780)
--- trunk/PerformanceTests/JetStream/Reference.js 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/JetStream/Reference.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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 @@
"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 @@
"zlib": 887.666666666666,
"typescript": 1149.9999999999993,
"lua": 29858,
+ "cdjs": 14,
"geomean": 31.556451704472156,
});
Added: trunk/PerformanceTests/JetStream/cdjs/benchmark.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/benchmark.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/benchmark.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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);
+}
Added: trunk/PerformanceTests/JetStream/cdjs/call_sign.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/call_sign.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/call_sign.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+}
+
Added: trunk/PerformanceTests/JetStream/cdjs/collision.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/collision.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/collision.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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 + ")";
+};
+
Added: trunk/PerformanceTests/JetStream/cdjs/collision_detector.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/collision_detector.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/collision_detector.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+};
Added: trunk/PerformanceTests/JetStream/cdjs/constants.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/constants.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/constants.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
Added: trunk/PerformanceTests/JetStream/cdjs/main.html (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/main.html (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/main.html 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+<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="" Test</a></div>
+</p>
+</body>
+</html>
+
Added: trunk/PerformanceTests/JetStream/cdjs/main.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/main.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/main.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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.");
+
Added: trunk/PerformanceTests/JetStream/cdjs/motion.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/motion.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/motion.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+};
+
Added: trunk/PerformanceTests/JetStream/cdjs/motion_test.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/motion_test.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/motion_test.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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).
Added: trunk/PerformanceTests/JetStream/cdjs/red_black_tree.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/red_black_tree.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/red_black_tree.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+})();
+
Added: trunk/PerformanceTests/JetStream/cdjs/red_black_tree_test.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/red_black_tree_test.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/red_black_tree_test.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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");
+
Added: trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+}
+
Added: trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/reduce_collision_set_test.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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]]");
Added: trunk/PerformanceTests/JetStream/cdjs/simulator.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/simulator.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/simulator.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
+};
+
Added: trunk/PerformanceTests/JetStream/cdjs/util.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/util.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/util.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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(); };
Added: trunk/PerformanceTests/JetStream/cdjs/vector_2d.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/vector_2d.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/vector_2d.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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);
+};
+
Added: trunk/PerformanceTests/JetStream/cdjs/vector_3d.js (0 => 185780)
--- trunk/PerformanceTests/JetStream/cdjs/vector_3d.js (rev 0)
+++ trunk/PerformanceTests/JetStream/cdjs/vector_3d.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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 + "]";
+};
+
+
Modified: trunk/PerformanceTests/JetStream/create.rb (185779 => 185780)
--- trunk/PerformanceTests/JetStream/create.rb 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/JetStream/create.rb 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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}/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-l...@2x.png Swoosh.png swo...@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-l...@2x.png Swoosh.png swo...@2x.png " + DIRECTORY_NAME)
def detemplatize(basename)
File.open(DIRECTORY_NAME + "/#{basename}.html", "w") {
@@ -116,6 +116,7 @@
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
Modified: trunk/PerformanceTests/JetStream/index-TEMPLATE.html (185779 => 185780)
--- trunk/PerformanceTests/JetStream/index-TEMPLATE.html 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/JetStream/index-TEMPLATE.html 2015-06-19 23:49:38 UTC (rev 185780)
@@ -48,6 +48,7 @@
<script src=""
<script src=""
<script src=""
+ <script src=""
<script src=""
</head>
<body _onload_="initialize()">
Deleted: trunk/PerformanceTests/JetStream/sunspider/cordic.js (185779 => 185780)
--- trunk/PerformanceTests/JetStream/sunspider/cordic.js 2015-06-19 23:45:35 UTC (rev 185779)
+++ trunk/PerformanceTests/JetStream/sunspider/cordic.js 2015-06-19 23:49:38 UTC (rev 185780)
@@ -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;
-
