1// Copyright 2012 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// These tests used to time out before this was fixed. 29 30var LEN = 2e4; 31 32function short() { 33 var sum = 0; 34 for (var i = 0; i < 1000; i++) { 35 var a = [1, 4, 34, 23, 6, 123, 3, 2, 11, 515, 4, 33, 22, 2, 2, 1, 0, 123, 36 23, 42, 43, 1002, 44, 43, 101, 23, 55, 11, 101, 102, 45, 11, 404, 37 31415, 34, 53, 453, 45, 34, 5, 2, 35, 5, 345, 36, 45, 345, 3, 45, 38 3, 5, 5, 2, 2342344, 2234, 23, 2718, 1500, 2, 19, 22, 43, 41, 0, 39 -1, 33, 45, 78]; 40 a.sort(function(a, b) { return a - b; }); 41 sum += a[0]; 42 } 43 return sum; 44} 45 46function short_bench(name, array) { 47 var start = new Date(); 48 short(); 49 var end = new Date(); 50 var ms = end - start; 51 print("Short " + Math.floor(ms) + "ms"); 52} 53 54function sawseq(a, tooth) { 55 var count = 0; 56 while (true) { 57 for (var i = 0; i < tooth; i++) { 58 a.push(i); 59 if (++count >= LEN) return a; 60 } 61 } 62} 63 64function sawseq2(a, tooth) { 65 var count = 0; 66 while (true) { 67 for (var i = 0; i < tooth; i++) { 68 a.push(i); 69 if (++count >= LEN) return a; 70 } 71 for (var i = 0; i < tooth; i++) { 72 a.push(tooth - i); 73 if (++count >= LEN) return a; 74 } 75 } 76} 77 78function sawseq3(a, tooth) { 79 var count = 0; 80 while (true) { 81 for (var i = 0; i < tooth; i++) { 82 a.push(tooth - i); 83 if (++count >= LEN) return a; 84 } 85 } 86} 87 88function up(a) { 89 for (var i = 0; i < LEN; i++) { 90 a.push(i); 91 } 92 return a; 93} 94 95function down(a) { 96 for (var i = 0; i < LEN; i++) { 97 a.push(LEN - i); 98 } 99 return a; 100} 101 102function ran(a) { 103 for (var i = 0; i < LEN; i++) { 104 a.push(Math.floor(Math.random() * LEN)); 105 } 106 return a; 107} 108 109var random = ran([]); 110var asc = up([]); 111var desc = down([]); 112var asc_desc = down(up([])); 113var desc_asc = up(down([])); 114var asc_asc = up(up([])); 115var desc_desc = down(down([])); 116var saw1 = sawseq([], 1000); 117var saw2 = sawseq([], 500); 118var saw3 = sawseq([], 200); 119var saw4 = sawseq2([], 200); 120var saw5 = sawseq3([], 200); 121 122function bench(name, array) { 123 var start = new Date(); 124 array.sort(function(a, b) { return a - b; }); 125 var end = new Date(); 126 for (var i = 0; i < array.length - 1; i++) { 127 if (array[i] > array[i + 1]) throw name + " " + i; 128 } 129 var ms = end - start; 130 print(name + " " + Math.floor(ms) + "ms"); 131} 132 133short_bench(); 134bench("random", random); 135bench("up", asc); 136bench("down", desc); 137bench("saw 1000", saw1); 138bench("saw 500", saw2); 139bench("saw 200", saw3); 140bench("saw 200 symmetric", saw4); 141bench("saw 200 down", saw4); 142bench("up, down", asc_desc); 143bench("up, up", asc_asc); 144bench("down, down", desc_desc); 145bench("down, up", desc_asc); 146