JSArray::sortNumeric should handle ArrayWithUndecided
[WebKit-https.git] / LayoutTests / js / regress / script-tests / sorting-benchmark.js
1 function log(s)
2 {
3 }
4
5 // FIXME: Clean up.
6 // FIXME: Can't use global resolve or built-in functions by name.
7 // FIXME: Rules about integer truncation.
8 // FIXME: Need to support missing comparator.
9 var bottom_up_merge_sort = (function () {
10         return function bottom_up_merge_sort(comparator)
11         {
12                 var array = this;
13                 var length = array.length;
14                 var copy = [ ];
15
16                 // Remove holes and undefineds.
17                 var undefinedCount = 0;
18                 for (var p in array) {
19                         var value = array[p];
20                         if (value === undefined) {
21                                 ++undefinedCount;
22                                 continue;
23                         }
24                         copy[copy.length] = value;
25                 }
26
27                 var n = copy.length;
28                 var a = copy;
29                 var b = array;
30
31                 for (var width = 1; width < n; width = 2 * width) {
32                         for (var i = 0; i < n; i = i + 2 * width) {
33                                 var iLeft = i;
34                                 var iRight = Math.min(i + width, n);
35                                 var iEnd = Math.min(i + 2 * width, n);
36                                 var i0 = iLeft;
37                                 var i1 = iRight;
38                                 var j;
39
40                                 for (j = iLeft; j < iEnd; j++) {
41                                         if (i0 < iRight && (i1 >= iEnd || comparator(a[i0], a[i1]) < 0)) {
42                                                 b[j] = a[i0];
43                                                 i0 = i0 + 1;
44                                         } else {
45                                                 b[j] = a[i1];
46                                                 i1 = i1 + 1;
47                                         }
48                                 }
49                         }
50
51                         var tmp = a;
52                         a = b;
53                         b = tmp;
54                 }
55
56             if (a != array) {
57                     for(var i = 0; i < a.length; i++)
58                         array[i] = a[i];
59             }
60
61                 // Restore holes and undefineds. Result should be [ values..., undefines..., holes... ].
62                 for (var i = 0; i < undefinedCount; ++i)
63                         array[array.length] = undefined;
64                 array.length = length;
65         }
66 })();
67
68 function obfuscatedAMinusB(a, b)
69 {
70         var A = a;
71         var B = b;
72         return A - B;
73 }
74
75 function aMinusB(a, b)
76 {
77         return a - b;
78 }
79
80 var sortFunctions = [ Array.prototype.sort, bottom_up_merge_sort ];
81 var comparators = [ aMinusB, obfuscatedAMinusB ];
82
83 function verify(reference, array)
84 {
85         for (var i in reference) {
86                 if (array[i] !== reference[i]) {
87                         log("SORT FAIL:");
88                         log("reference: " + reference);
89                         log("array: " + array);
90                         return;
91                 }
92         }
93
94         if (reference.length != array.length) {
95                         log("SORT FAIL:");
96                         log("reference.length: " + reference.length);
97                         log("array.length: " + array.length);
98         }
99 }
100
101 function benchmark(f, c, array)
102 {
103         var start = new Date;
104         f.call(array, c);
105         var end = new Date;
106
107         // Our time resolution is not very good, so we round down small numbers to
108         // zero in order to show that they are not meaningful.
109         var result = end - start;
110         if (result < 2)
111                 result = 0;
112
113         log(array.length / 1024 + "k:\t" + result + "ms");
114 }
115
116 function makeArrays()
117 {
118         var arrays = [ ];
119         var min = 1024;
120         var max = 4 * 1024;
121         for (var count = min; count <= max; count *= 2) {
122                 var array = [ ];
123                 for (var i = 0; i < count; ++i)
124                         array[i] = Math.floor(Math.random() * count);
125                 arrays.push(array);
126         }
127
128         arrays.push(new Array(max));
129
130         arrays.push((function() {
131                 var a = [ ];
132                 a[max - 1] = 1;
133                 return a;
134         })());
135
136 //      arrays.push((function() {
137 //              var a = [ ];
138 //              a[Math.pow(2, 21) - 1] = 1;
139 //              return a;
140 //      })());
141
142         return arrays;
143 }
144
145 (function main() {
146         var arrays = makeArrays();
147         for (var c of comparators) {
148                 log("\n" + "===== " + c.name + " =====");
149
150                 for (var f of sortFunctions) {
151                         log("\n" + f.name);
152
153                         for (var array of arrays) {
154                                 var copy = array.slice();
155                                 benchmark(f, c, copy);
156                                 verify(Array.prototype.sort.call(array.slice(), c), copy);
157                         }
158                 }
159         }
160 })();