From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- js/src/jit-test/tests/v8-v5/check-splay.js | 392 +++++++++++++++++++++++++++++ 1 file changed, 392 insertions(+) create mode 100644 js/src/jit-test/tests/v8-v5/check-splay.js (limited to 'js/src/jit-test/tests/v8-v5/check-splay.js') diff --git a/js/src/jit-test/tests/v8-v5/check-splay.js b/js/src/jit-test/tests/v8-v5/check-splay.js new file mode 100644 index 000000000..117a421af --- /dev/null +++ b/js/src/jit-test/tests/v8-v5/check-splay.js @@ -0,0 +1,392 @@ +// Copyright 2009 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 benchmark is based on a JavaScript log processing module used +// by the V8 profiler to generate execution time profiles for runs of +// JavaScript applications, and it effectively measures how fast the +// JavaScript engine is at allocating nodes and reclaiming the memory +// used for old nodes. Because of the way splay trees work, the engine +// also has to deal with a lot of changes to the large tree object +// graph. + +//var Splay = new BenchmarkSuite('Splay', 126125, [ +// new Benchmark("Splay", SplayRun, SplaySetup, SplayTearDown) +//]); + +// This is the best random number generator available to mankind ;) +var MyMath = { + seed: 49734321, + random: function() { + // Robert Jenkins' 32 bit integer hash function. + this.seed = ((this.seed + 0x7ed55d16) + (this.seed << 12)) & 0xffffffff; + this.seed = ((this.seed ^ 0xc761c23c) ^ (this.seed >>> 19)) & 0xffffffff; + this.seed = ((this.seed + 0x165667b1) + (this.seed << 5)) & 0xffffffff; + this.seed = ((this.seed + 0xd3a2646c) ^ (this.seed << 9)) & 0xffffffff; + this.seed = ((this.seed + 0xfd7046c5) + (this.seed << 3)) & 0xffffffff; + this.seed = ((this.seed ^ 0xb55a4f09) ^ (this.seed >>> 16)) & 0xffffffff; + return (this.seed & 0xfffffff) / 0x10000000; + }, +}; + +// Configuration. +var kSplayTreeSize = 8000; +var kSplayTreeModifications = 80; +var kSplayTreePayloadDepth = 5; + +var splayTree = null; + + +function GeneratePayloadTree(depth, key) { + if (depth == 0) { + return { + array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], + string : 'String for key ' + key + ' in leaf node' + }; + } else { + return { + left: GeneratePayloadTree(depth - 1, key), + right: GeneratePayloadTree(depth - 1, key) + }; + } +} + + +function GenerateKey() { + // The benchmark framework guarantees that Math.random is + // deterministic; see base.js. + // base.js isn't pulled in for jit-tests + return MyMath.random(); +} + + +function InsertNewNode() { + // Insert new node with a unique key. + var key; + do { + key = GenerateKey(); + } while (splayTree.find(key) != null); + splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key)); + return key; +} + + +function SplaySetup() { + splayTree = new SplayTree(); + for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode(); +} + + +function SplayTearDown() { + // Allow the garbage collector to reclaim the memory + // used by the splay tree no matter how we exit the + // tear down function. + var keys = splayTree.exportKeys(); + splayTree = null; + + // Verify that the splay tree has the right size. + var length = keys.length; + assertEq(length, kSplayTreeSize); + + // Verify that the splay tree has sorted, unique keys. + for (var i = 0; i < length - 1; i++) { + assertEq(keys[i] < keys[i + 1], true); + } +} + + +function SplayRun() { + // Replace a few nodes in the splay tree. + for (var i = 0; i < kSplayTreeModifications; i++) { + var key = InsertNewNode(); + var greatest = splayTree.findGreatestLessThan(key); + if (greatest == null) splayTree.remove(key); + else splayTree.remove(greatest.key); + } +} + + +/** + * 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 that + * is less or equal to 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; + } +}; + +SplaySetup(); +SplayRun(); +SplayTearDown(); -- cgit v1.2.3