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 30 var LEN = 2e4; 31 32 function 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 46 function 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 54 function 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 64 function 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 78 function 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 88 function up(a) { 89 for (var i = 0; i < LEN; i++) { 90 a.push(i); 91 } 92 return a; 93 } 94 95 function down(a) { 96 for (var i = 0; i < LEN; i++) { 97 a.push(LEN - i); 98 } 99 return a; 100 } 101 102 function ran(a) { 103 for (var i = 0; i < LEN; i++) { 104 a.push(Math.floor(Math.random() * LEN)); 105 } 106 return a; 107 } 108 109 var random = ran([]); 110 var asc = up([]); 111 var desc = down([]); 112 var asc_desc = down(up([])); 113 var desc_asc = up(down([])); 114 var asc_asc = up(up([])); 115 var desc_desc = down(down([])); 116 var saw1 = sawseq([], 1000); 117 var saw2 = sawseq([], 500); 118 var saw3 = sawseq([], 200); 119 var saw4 = sawseq2([], 200); 120 var saw5 = sawseq3([], 200); 121 122 function 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 133 short_bench(); 134 bench("random", random); 135 bench("up", asc); 136 bench("down", desc); 137 bench("saw 1000", saw1); 138 bench("saw 500", saw2); 139 bench("saw 200", saw3); 140 bench("saw 200 symmetric", saw4); 141 bench("saw 200 down", saw4); 142 bench("up, down", asc_desc); 143 bench("up, up", asc_asc); 144 bench("down, down", desc_desc); 145 bench("down, up", desc_asc); 146