diff options
author | Ryan Dahl <ry@tinyclouds.org> | 2011-12-05 16:29:01 -0800 |
---|---|---|
committer | Ryan Dahl <ry@tinyclouds.org> | 2011-12-05 16:29:01 -0800 |
commit | 21d081fd7f83aa168ea0bef0870c7f1fed410a63 (patch) | |
tree | 23a04eef49364b1cbee204a87fd0904be2430c2e /deps/v8/benchmarks/spinning-balls | |
parent | e90623edc2befb06602ff8c3e01809ba0a21d593 (diff) | |
download | android-node-v8-21d081fd7f83aa168ea0bef0870c7f1fed410a63.tar.gz android-node-v8-21d081fd7f83aa168ea0bef0870c7f1fed410a63.tar.bz2 android-node-v8-21d081fd7f83aa168ea0bef0870c7f1fed410a63.zip |
Upgrade V8 to 3.7.12
Diffstat (limited to 'deps/v8/benchmarks/spinning-balls')
-rw-r--r-- | deps/v8/benchmarks/spinning-balls/index.html | 11 | ||||
-rw-r--r-- | deps/v8/benchmarks/spinning-balls/splay-tree.js | 326 | ||||
-rw-r--r-- | deps/v8/benchmarks/spinning-balls/v.js | 498 |
3 files changed, 835 insertions, 0 deletions
diff --git a/deps/v8/benchmarks/spinning-balls/index.html b/deps/v8/benchmarks/spinning-balls/index.html new file mode 100644 index 0000000000..d01f31f373 --- /dev/null +++ b/deps/v8/benchmarks/spinning-balls/index.html @@ -0,0 +1,11 @@ +<html> +<head> + <style> + body { text-align: center; } + </style> +</head> +<body> + <script type="text/javascript" src="splay-tree.js"></script> + <script type="text/javascript" src="v.js"></script> +</body> +</html> diff --git a/deps/v8/benchmarks/spinning-balls/splay-tree.js b/deps/v8/benchmarks/spinning-balls/splay-tree.js new file mode 100644 index 0000000000..a88e4cbce1 --- /dev/null +++ b/deps/v8/benchmarks/spinning-balls/splay-tree.js @@ -0,0 +1,326 @@ +// Copyright 2011 the V8 project authors. 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 Google Inc. 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 +// OWNER 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. + +/** + * Constructs a Splay tree. A splay tree is a self-balancing binary + * search tree with the additional property that recently accessed + * elements are quick to access again. It performs basic operations + * such as insertion, look-up and removal in O(log(n)) amortized time. + * + * @constructor + */ +function SplayTree() { +}; + + +/** + * Pointer to the root node of the tree. + * + * @type {SplayTree.Node} + * @private + */ +SplayTree.prototype.root_ = null; + + +/** + * @return {boolean} Whether the tree is empty. + */ +SplayTree.prototype.isEmpty = function() { + return !this.root_; +}; + + +/** + * Inserts a node into the tree with the specified key and value if + * the tree does not already contain a node with the specified key. If + * the value is inserted, it becomes the root of the tree. + * + * @param {number} key Key to insert into the tree. + * @param {*} value Value to insert into the tree. + */ +SplayTree.prototype.insert = function(key, value) { + if (this.isEmpty()) { + this.root_ = new SplayTree.Node(key, value); + return; + } + // Splay on the key to move the last node on the search path for + // the key to the root of the tree. + this.splay_(key); + if (this.root_.key == key) { + return; + } + var node = new SplayTree.Node(key, value); + if (key > this.root_.key) { + node.left = this.root_; + node.right = this.root_.right; + this.root_.right = null; + } else { + node.right = this.root_; + node.left = this.root_.left; + this.root_.left = null; + } + this.root_ = node; +}; + + +/** + * Removes a node with the specified key from the tree if the tree + * contains a node with this key. The removed node is returned. If the + * key is not found, an exception is thrown. + * + * @param {number} key Key to find and remove from the tree. + * @return {SplayTree.Node} The removed node. + */ +SplayTree.prototype.remove = function(key) { + if (this.isEmpty()) { + throw Error('Key not found: ' + key); + } + this.splay_(key); + if (this.root_.key != key) { + throw Error('Key not found: ' + key); + } + var removed = this.root_; + if (!this.root_.left) { + this.root_ = this.root_.right; + } else { + var right = this.root_.right; + this.root_ = this.root_.left; + // Splay to make sure that the new root has an empty right child. + this.splay_(key); + // Insert the original right child as the right child of the new + // root. + this.root_.right = right; + } + return removed; +}; + + +/** + * Returns the node having the specified key or null if the tree doesn't contain + * a node with the specified key. + * + * @param {number} key Key to find in the tree. + * @return {SplayTree.Node} Node having the specified key. + */ +SplayTree.prototype.find = function(key) { + if (this.isEmpty()) { + return null; + } + this.splay_(key); + return this.root_.key == key ? this.root_ : null; +}; + + +/** + * @return {SplayTree.Node} Node having the maximum key value. + */ +SplayTree.prototype.findMax = function(opt_startNode) { + if (this.isEmpty()) { + return null; + } + var current = opt_startNode || this.root_; + while (current.right) { + current = current.right; + } + return current; +}; + + +/** + * @return {SplayTree.Node} Node having the maximum key value that + * is less than the specified key value. + */ +SplayTree.prototype.findGreatestLessThan = function(key) { + if (this.isEmpty()) { + return null; + } + // Splay on the key to move the node with the given key or the last + // node on the search path to the top of the tree. + this.splay_(key); + // Now the result is either the root node or the greatest node in + // the left subtree. + if (this.root_.key < key) { + return this.root_; + } else if (this.root_.left) { + return this.findMax(this.root_.left); + } else { + return null; + } +}; + + +/** + * @return {Array<*>} An array containing all the keys of tree's nodes. + */ +SplayTree.prototype.exportKeys = function() { + var result = []; + if (!this.isEmpty()) { + this.root_.traverse_(function(node) { result.push(node.key); }); + } + return result; +}; + + +/** + * Perform the splay operation for the given key. Moves the node with + * the given key to the top of the tree. If no node has the given + * key, the last node on the search path is moved to the top of the + * tree. This is the simplified top-down splaying algorithm from: + * "Self-adjusting Binary Search Trees" by Sleator and Tarjan + * + * @param {number} key Key to splay the tree on. + * @private + */ +SplayTree.prototype.splay_ = function(key) { + if (this.isEmpty()) { + return; + } + // Create a dummy node. The use of the dummy node is a bit + // counter-intuitive: The right child of the dummy node will hold + // the L tree of the algorithm. The left child of the dummy node + // will hold the R tree of the algorithm. Using a dummy node, left + // and right will always be nodes and we avoid special cases. + var dummy, left, right; + dummy = left = right = new SplayTree.Node(null, null); + var current = this.root_; + while (true) { + if (key < current.key) { + if (!current.left) { + break; + } + if (key < current.left.key) { + // Rotate right. + var tmp = current.left; + current.left = tmp.right; + tmp.right = current; + current = tmp; + if (!current.left) { + break; + } + } + // Link right. + right.left = current; + right = current; + current = current.left; + } else if (key > current.key) { + if (!current.right) { + break; + } + if (key > current.right.key) { + // Rotate left. + var tmp = current.right; + current.right = tmp.left; + tmp.left = current; + current = tmp; + if (!current.right) { + break; + } + } + // Link left. + left.right = current; + left = current; + current = current.right; + } else { + break; + } + } + // Assemble. + left.right = current.left; + right.left = current.right; + current.left = dummy.right; + current.right = dummy.left; + this.root_ = current; +}; + + +/** + * Constructs a Splay tree node. + * + * @param {number} key Key. + * @param {*} value Value. + */ +SplayTree.Node = function(key, value) { + this.key = key; + this.value = value; +}; + + +/** + * @type {SplayTree.Node} + */ +SplayTree.Node.prototype.left = null; + + +/** + * @type {SplayTree.Node} + */ +SplayTree.Node.prototype.right = null; + + +/** + * Performs an ordered traversal of the subtree starting at + * this SplayTree.Node. + * + * @param {function(SplayTree.Node)} f Visitor function. + * @private + */ +SplayTree.Node.prototype.traverse_ = function(f) { + var current = this; + while (current) { + var left = current.left; + if (left) left.traverse_(f); + f(current); + current = current.right; + } +}; + +SplayTree.prototype.traverseBreadthFirst = function (f) { + if (f(this.root_.value)) return; + + var stack = [this.root_]; + var length = 1; + + while (length > 0) { + var new_stack = new Array(stack.length * 2); + var new_length = 0; + for (var i = 0; i < length; i++) { + var n = stack[i]; + var l = n.left; + var r = n.right; + if (l) { + if (f(l.value)) return; + new_stack[new_length++] = l; + } + if (r) { + if (f(r.value)) return; + new_stack[new_length++] = r; + } + } + stack = new_stack; + length = new_length; + } +}; diff --git a/deps/v8/benchmarks/spinning-balls/v.js b/deps/v8/benchmarks/spinning-balls/v.js new file mode 100644 index 0000000000..5ae11948d6 --- /dev/null +++ b/deps/v8/benchmarks/spinning-balls/v.js @@ -0,0 +1,498 @@ +// Copyright 2011 the V8 project authors. 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 Google Inc. 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 +// OWNER 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. + + +/** + * This function provides requestAnimationFrame in a cross browser way. + * http://paulirish.com/2011/requestanimationframe-for-smart-animating/ + */ +if ( !window.requestAnimationFrame ) { + window.requestAnimationFrame = ( function() { + return window.webkitRequestAnimationFrame || + window.mozRequestAnimationFrame || + window.oRequestAnimationFrame || + window.msRequestAnimationFrame || + function(callback, element) { + window.setTimeout( callback, 1000 / 60 ); + }; + } )(); +} + +var kNPoints = 8000; +var kNModifications = 20; +var kNVisiblePoints = 200; +var kDecaySpeed = 20; + +var kPointRadius = 4; +var kInitialLifeForce = 100; + +var livePoints = void 0; +var dyingPoints = void 0; +var scene = void 0; +var renderingStartTime = void 0; +var scene = void 0; +var pausePlot = void 0; +var splayTree = void 0; +var numberOfFrames = 0; +var sumOfSquaredPauses = 0; +var benchmarkStartTime = void 0; +var benchmarkTimeLimit = void 0; +var autoScale = void 0; +var pauseDistribution = []; + + +function Point(x, y, z, payload) { + this.x = x; + this.y = y; + this.z = z; + + this.next = null; + this.prev = null; + this.payload = payload; + this.lifeForce = kInitialLifeForce; +} + + +Point.prototype.color = function () { + return "rgba(0, 0, 0, " + (this.lifeForce / kInitialLifeForce) + ")"; +}; + + +Point.prototype.decay = function () { + this.lifeForce -= kDecaySpeed; + return this.lifeForce <= 0; +}; + + +function PointsList() { + this.head = null; + this.count = 0; +} + + +PointsList.prototype.add = function (point) { + if (this.head !== null) this.head.prev = point; + point.next = this.head; + this.head = point; + this.count++; +} + + +PointsList.prototype.remove = function (point) { + if (point.next !== null) { + point.next.prev = point.prev; + } + if (point.prev !== null) { + point.prev.next = point.next; + } else { + this.head = point.next; + } + this.count--; +} + + +function GeneratePayloadTree(depth, tag) { + if (depth == 0) { + return { + array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], + string : 'String for key ' + tag + ' in leaf node' + }; + } else { + return { + left: GeneratePayloadTree(depth - 1, tag), + right: GeneratePayloadTree(depth - 1, tag) + }; + } +} + + +// To make the benchmark results predictable, we replace Math.random +// with a 100% deterministic alternative. +Math.random = (function() { + var seed = 49734321; + return function() { + // Robert Jenkins' 32 bit integer hash function. + seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; + seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; + seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; + seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; + seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; + seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; + return (seed & 0xfffffff) / 0x10000000; + }; +})(); + + +function GenerateKey() { + // The benchmark framework guarantees that Math.random is + // deterministic; see base.js. + return Math.random(); +} + +function CreateNewPoint() { + // Insert new node with a unique key. + var key; + do { key = GenerateKey(); } while (splayTree.find(key) != null); + + var point = new Point(Math.random() * 40 - 20, + Math.random() * 40 - 20, + Math.random() * 40 - 20, + GeneratePayloadTree(5, "" + key)); + + livePoints.add(point); + + splayTree.insert(key, point); + return key; +} + +function ModifyPointsSet() { + if (livePoints.count < kNPoints) { + for (var i = 0; i < kNModifications; i++) { + CreateNewPoint(); + } + } else if (kNModifications === 20) { + kNModifications = 80; + kDecay = 30; + } + + for (var i = 0; i < kNModifications; i++) { + var key = CreateNewPoint(); + var greatest = splayTree.findGreatestLessThan(key); + if (greatest == null) { + var point = splayTree.remove(key).value; + } else { + var point = splayTree.remove(greatest.key).value; + } + livePoints.remove(point); + point.payload = null; + dyingPoints.add(point); + } +} + + +function PausePlot(width, height, size, scale) { + var canvas = document.createElement("canvas"); + canvas.width = this.width = width; + canvas.height = this.height = height; + document.body.appendChild(canvas); + + this.ctx = canvas.getContext('2d'); + + if (typeof scale !== "number") { + this.autoScale = true; + this.maxPause = 0; + } else { + this.autoScale = false; + this.maxPause = scale; + } + + this.size = size; + + // Initialize cyclic buffer for pauses. + this.pauses = new Array(this.size); + this.start = this.size; + this.idx = 0; +} + + +PausePlot.prototype.addPause = function (p) { + if (this.idx === this.size) { + this.idx = 0; + } + + if (this.idx === this.start) { + this.start++; + } + + if (this.start === this.size) { + this.start = 0; + } + + this.pauses[this.idx++] = p; +}; + + +PausePlot.prototype.iteratePauses = function (f) { + if (this.start < this.idx) { + for (var i = this.start; i < this.idx; i++) { + f.call(this, i - this.start, this.pauses[i]); + } + } else { + for (var i = this.start; i < this.size; i++) { + f.call(this, i - this.start, this.pauses[i]); + } + + var offs = this.size - this.start; + for (var i = 0; i < this.idx; i++) { + f.call(this, i + offs, this.pauses[i]); + } + } +}; + + +PausePlot.prototype.draw = function () { + var first = null; + + if (this.autoScale) { + this.iteratePauses(function (i, v) { + if (first === null) { + first = v; + } + this.maxPause = Math.max(v, this.maxPause); + }); + } + + var dx = this.width / this.size; + var dy = this.height / this.maxPause; + + this.ctx.save(); + this.ctx.clearRect(0, 0, this.width, this.height); + this.ctx.beginPath(); + this.ctx.moveTo(1, dy * this.pauses[this.start]); + var p = first; + this.iteratePauses(function (i, v) { + var delta = v - p; + var x = 1 + dx * i; + var y = dy * v; + this.ctx.lineTo(x, y); + if (delta > 2 * (p / 3)) { + this.ctx.font = "bold 12px sans-serif"; + this.ctx.textBaseline = "bottom"; + this.ctx.fillText(v + "ms", x + 2, y); + } + p = v; + }); + this.ctx.strokeStyle = "black"; + this.ctx.stroke(); + this.ctx.restore(); +} + + +function Scene(width, height) { + var canvas = document.createElement("canvas"); + canvas.width = width; + canvas.height = height; + document.body.appendChild(canvas); + + this.ctx = canvas.getContext('2d'); + this.width = canvas.width; + this.height = canvas.height; + + // Projection configuration. + this.x0 = canvas.width / 2; + this.y0 = canvas.height / 2; + this.z0 = 100; + this.f = 1000; // Focal length. + + // Camera is rotating around y-axis. + this.angle = 0; +} + + +Scene.prototype.drawPoint = function (x, y, z, color) { + // Rotate the camera around y-axis. + var rx = x * Math.cos(this.angle) - z * Math.sin(this.angle); + var ry = y; + var rz = x * Math.sin(this.angle) + z * Math.cos(this.angle); + + // Perform perspective projection. + var px = (this.f * rx) / (rz - this.z0) + this.x0; + var py = (this.f * ry) / (rz - this.z0) + this.y0; + + this.ctx.save(); + this.ctx.fillStyle = color + this.ctx.beginPath(); + this.ctx.arc(px, py, kPointRadius, 0, 2 * Math.PI, true); + this.ctx.fill(); + this.ctx.restore(); +}; + + +Scene.prototype.drawDyingPoints = function () { + var point_next = null; + for (var point = dyingPoints.head; point !== null; point = point_next) { + // Rotate the scene around y-axis. + scene.drawPoint(point.x, point.y, point.z, point.color()); + + point_next = point.next; + + // Decay the current point and remove it from the list + // if it's life-force ran out. + if (point.decay()) { + dyingPoints.remove(point); + } + } +}; + + +Scene.prototype.draw = function () { + this.ctx.save(); + this.ctx.clearRect(0, 0, this.width, this.height); + this.drawDyingPoints(); + this.ctx.restore(); + + this.angle += Math.PI / 90.0; +}; + + +function updateStats(pause) { + numberOfFrames++; + if (pause > 20) { + sumOfSquaredPauses += (pause - 20) * (pause - 20); + } + pauseDistribution[Math.floor(pause / 10)] |= 0; + pauseDistribution[Math.floor(pause / 10)]++; +} + + +function renderStats() { + var msg = document.createElement("p"); + msg.innerHTML = "Score " + + Math.round(numberOfFrames * 1000 / sumOfSquaredPauses); + var table = document.createElement("table"); + table.align = "center"; + for (var i = 0; i < pauseDistribution.length; i++) { + if (pauseDistribution[i] > 0) { + var row = document.createElement("tr"); + var time = document.createElement("td"); + var count = document.createElement("td"); + time.innerHTML = i*10 + "-" + (i+1)*10 + "ms"; + count.innerHTML = " => " + pauseDistribution[i]; + row.appendChild(time); + row.appendChild(count); + table.appendChild(row); + } + } + div.appendChild(msg); + div.appendChild(table); +} + + +function render() { + if (typeof renderingStartTime === 'undefined') { + renderingStartTime = Date.now(); + benchmarkStartTime = renderingStartTime; + } + + ModifyPointsSet(); + + scene.draw(); + + var renderingEndTime = Date.now(); + var pause = renderingEndTime - renderingStartTime; + pausePlot.addPause(pause); + renderingStartTime = renderingEndTime; + + pausePlot.draw(); + + updateStats(pause); + + div.innerHTML = + livePoints.count + "/" + dyingPoints.count + " " + + pause + "(max = " + pausePlot.maxPause + ") ms " + + numberOfFrames + " frames"; + + if (renderingEndTime < benchmarkStartTime + benchmarkTimeLimit) { + // Schedule next frame. + requestAnimationFrame(render); + } else { + renderStats(); + } +} + + +function Form() { + function create(tag) { return document.createElement(tag); } + function text(value) { return document.createTextNode(value); } + + this.form = create("form"); + this.form.setAttribute("action", "javascript:start()"); + + var table = create("table"); + table.setAttribute("style", "margin-left: auto; margin-right: auto;"); + + function col(a) { + var td = create("td"); + td.appendChild(a); + return td; + } + + function row(a, b) { + var tr = create("tr"); + tr.appendChild(col(a)); + tr.appendChild(col(b)); + return tr; + } + + this.timelimit = create("input"); + this.timelimit.setAttribute("value", "60"); + + table.appendChild(row(text("Time limit in seconds"), this.timelimit)); + + this.autoscale = create("input"); + this.autoscale.setAttribute("type", "checkbox"); + this.autoscale.setAttribute("checked", "true"); + table.appendChild(row(text("Autoscale pauses plot"), this.autoscale)); + + var button = create("input"); + button.setAttribute("type", "submit"); + button.setAttribute("value", "Start"); + this.form.appendChild(table); + this.form.appendChild(button); + + document.body.appendChild(this.form); +} + + +Form.prototype.remove = function () { + document.body.removeChild(this.form); +}; + + +function init() { + livePoints = new PointsList; + dyingPoints = new PointsList; + + splayTree = new SplayTree(); + + scene = new Scene(640, 480); + + div = document.createElement("div"); + document.body.appendChild(div); + + pausePlot = new PausePlot(480, autoScale ? 240 : 500, 160, autoScale ? void 0 : 500); +} + +function start() { + benchmarkTimeLimit = form.timelimit.value * 1000; + autoScale = form.autoscale.checked; + form.remove(); + init(); + render(); +} + +var form = new Form(); |