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