1 // Copyright 2009 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 // This benchmark is based on a JavaScript log processing module used 29 // by the V8 profiler to generate execution time profiles for runs of 30 // JavaScript applications, and it effectively measures how fast the 31 // JavaScript engine is at allocating nodes and reclaiming the memory 32 // used for old nodes. Because of the way splay trees work, the engine 33 // also has to deal with a lot of changes to the large tree object 34 // graph. 35 36 var Splay = new BenchmarkSuite('Splay', 126125, [ 37 new Benchmark("Splay", SplayRun, SplaySetup, SplayTearDown) 38 ]); 39 40 41 // Configuration. 42 var kSplayTreeSize = 8000; 43 var kSplayTreeModifications = 80; 44 var kSplayTreePayloadDepth = 5; 45 46 var splayTree = null; 47 48 49 function GeneratePayloadTree(depth, key) { 50 if (depth == 0) { 51 return { 52 array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], 53 string : 'String for key ' + key + ' in leaf node' 54 }; 55 } else { 56 return { 57 left: GeneratePayloadTree(depth - 1, key), 58 right: GeneratePayloadTree(depth - 1, key) 59 }; 60 } 61 } 62 63 64 function GenerateKey() { 65 // The benchmark framework guarantees that Math.random is 66 // deterministic; see base.js. 67 return Math.random(); 68 } 69 70 71 function InsertNewNode() { 72 // Insert new node with a unique key. 73 var key; 74 do { 75 key = GenerateKey(); 76 } while (splayTree.find(key) != null); 77 splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key)); 78 return key; 79 } 80 81 82 83 function SplaySetup() { 84 splayTree = new SplayTree(); 85 for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode(); 86 } 87 88 89 function SplayTearDown() { 90 // Allow the garbage collector to reclaim the memory 91 // used by the splay tree no matter how we exit the 92 // tear down function. 93 var keys = splayTree.exportKeys(); 94 splayTree = null; 95 96 // Verify that the splay tree has the right size. 97 var length = keys.length; 98 if (length != kSplayTreeSize) { 99 throw new Error("Splay tree has wrong size"); 100 } 101 102 // Verify that the splay tree has sorted, unique keys. 103 for (var i = 0; i < length - 1; i++) { 104 if (keys[i] >= keys[i + 1]) { 105 throw new Error("Splay tree not sorted"); 106 } 107 } 108 } 109 110 111 function SplayRun() { 112 // Replace a few nodes in the splay tree. 113 for (var i = 0; i < kSplayTreeModifications; i++) { 114 var key = InsertNewNode(); 115 var greatest = splayTree.findGreatestLessThan(key); 116 if (greatest == null) splayTree.remove(key); 117 else splayTree.remove(greatest.key); 118 } 119 } 120 121 122 /** 123 * Constructs a Splay tree. A splay tree is a self-balancing binary 124 * search tree with the additional property that recently accessed 125 * elements are quick to access again. It performs basic operations 126 * such as insertion, look-up and removal in O(log(n)) amortized time. 127 * 128 * @constructor 129 */ 130 function SplayTree() { 131 }; 132 133 134 /** 135 * Pointer to the root node of the tree. 136 * 137 * @type {SplayTree.Node} 138 * @private 139 */ 140 SplayTree.prototype.root_ = null; 141 142 143 /** 144 * @return {boolean} Whether the tree is empty. 145 */ 146 SplayTree.prototype.isEmpty = function() { 147 return !this.root_; 148 }; 149 150 151 /** 152 * Inserts a node into the tree with the specified key and value if 153 * the tree does not already contain a node with the specified key. If 154 * the value is inserted, it becomes the root of the tree. 155 * 156 * @param {number} key Key to insert into the tree. 157 * @param {*} value Value to insert into the tree. 158 */ 159 SplayTree.prototype.insert = function(key, value) { 160 if (this.isEmpty()) { 161 this.root_ = new SplayTree.Node(key, value); 162 return; 163 } 164 // Splay on the key to move the last node on the search path for 165 // the key to the root of the tree. 166 this.splay_(key); 167 if (this.root_.key == key) { 168 return; 169 } 170 var node = new SplayTree.Node(key, value); 171 if (key > this.root_.key) { 172 node.left = this.root_; 173 node.right = this.root_.right; 174 this.root_.right = null; 175 } else { 176 node.right = this.root_; 177 node.left = this.root_.left; 178 this.root_.left = null; 179 } 180 this.root_ = node; 181 }; 182 183 184 /** 185 * Removes a node with the specified key from the tree if the tree 186 * contains a node with this key. The removed node is returned. If the 187 * key is not found, an exception is thrown. 188 * 189 * @param {number} key Key to find and remove from the tree. 190 * @return {SplayTree.Node} The removed node. 191 */ 192 SplayTree.prototype.remove = function(key) { 193 if (this.isEmpty()) { 194 throw Error('Key not found: ' + key); 195 } 196 this.splay_(key); 197 if (this.root_.key != key) { 198 throw Error('Key not found: ' + key); 199 } 200 var removed = this.root_; 201 if (!this.root_.left) { 202 this.root_ = this.root_.right; 203 } else { 204 var right = this.root_.right; 205 this.root_ = this.root_.left; 206 // Splay to make sure that the new root has an empty right child. 207 this.splay_(key); 208 // Insert the original right child as the right child of the new 209 // root. 210 this.root_.right = right; 211 } 212 return removed; 213 }; 214 215 216 /** 217 * Returns the node having the specified key or null if the tree doesn't contain 218 * a node with the specified key. 219 * 220 * @param {number} key Key to find in the tree. 221 * @return {SplayTree.Node} Node having the specified key. 222 */ 223 SplayTree.prototype.find = function(key) { 224 if (this.isEmpty()) { 225 return null; 226 } 227 this.splay_(key); 228 return this.root_.key == key ? this.root_ : null; 229 }; 230 231 232 /** 233 * @return {SplayTree.Node} Node having the maximum key value that 234 * is less or equal to the specified key value. 235 */ 236 SplayTree.prototype.findGreatestLessThan = function(key) { 237 if (this.isEmpty()) { 238 return null; 239 } 240 // Splay on the key to move the node with the given key or the last 241 // node on the search path to the top of the tree. 242 this.splay_(key); 243 // Now the result is either the root node or the greatest node in 244 // the left subtree. 245 if (this.root_.key <= key) { 246 return this.root_; 247 } else if (this.root_.left) { 248 return this.findMax(this.root_.left); 249 } else { 250 return null; 251 } 252 }; 253 254 255 /** 256 * @return {Array<*>} An array containing all the keys of tree's nodes. 257 */ 258 SplayTree.prototype.exportKeys = function() { 259 var result = []; 260 if (!this.isEmpty()) { 261 this.root_.traverse_(function(node) { result.push(node.key); }); 262 } 263 return result; 264 }; 265 266 267 /** 268 * Perform the splay operation for the given key. Moves the node with 269 * the given key to the top of the tree. If no node has the given 270 * key, the last node on the search path is moved to the top of the 271 * tree. This is the simplified top-down splaying algorithm from: 272 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 273 * 274 * @param {number} key Key to splay the tree on. 275 * @private 276 */ 277 SplayTree.prototype.splay_ = function(key) { 278 if (this.isEmpty()) { 279 return; 280 } 281 // Create a dummy node. The use of the dummy node is a bit 282 // counter-intuitive: The right child of the dummy node will hold 283 // the L tree of the algorithm. The left child of the dummy node 284 // will hold the R tree of the algorithm. Using a dummy node, left 285 // and right will always be nodes and we avoid special cases. 286 var dummy, left, right; 287 dummy = left = right = new SplayTree.Node(null, null); 288 var current = this.root_; 289 while (true) { 290 if (key < current.key) { 291 if (!current.left) { 292 break; 293 } 294 if (key < current.left.key) { 295 // Rotate right. 296 var tmp = current.left; 297 current.left = tmp.right; 298 tmp.right = current; 299 current = tmp; 300 if (!current.left) { 301 break; 302 } 303 } 304 // Link right. 305 right.left = current; 306 right = current; 307 current = current.left; 308 } else if (key > current.key) { 309 if (!current.right) { 310 break; 311 } 312 if (key > current.right.key) { 313 // Rotate left. 314 var tmp = current.right; 315 current.right = tmp.left; 316 tmp.left = current; 317 current = tmp; 318 if (!current.right) { 319 break; 320 } 321 } 322 // Link left. 323 left.right = current; 324 left = current; 325 current = current.right; 326 } else { 327 break; 328 } 329 } 330 // Assemble. 331 left.right = current.left; 332 right.left = current.right; 333 current.left = dummy.right; 334 current.right = dummy.left; 335 this.root_ = current; 336 }; 337 338 339 /** 340 * Constructs a Splay tree node. 341 * 342 * @param {number} key Key. 343 * @param {*} value Value. 344 */ 345 SplayTree.Node = function(key, value) { 346 this.key = key; 347 this.value = value; 348 }; 349 350 351 /** 352 * @type {SplayTree.Node} 353 */ 354 SplayTree.Node.prototype.left = null; 355 356 357 /** 358 * @type {SplayTree.Node} 359 */ 360 SplayTree.Node.prototype.right = null; 361 362 363 /** 364 * Performs an ordered traversal of the subtree starting at 365 * this SplayTree.Node. 366 * 367 * @param {function(SplayTree.Node)} f Visitor function. 368 * @private 369 */ 370 SplayTree.Node.prototype.traverse_ = function(f) { 371 var current = this; 372 while (current) { 373 var left = current.left; 374 if (left) left.traverse_(f); 375 f(current); 376 current = current.right; 377 } 378 }; 379