Add JetStream to PerformanceTests
[WebKit-https.git] / PerformanceTests / JetStream / simple / container.cpp
1 /* Standard Container Benchmark 
2
3
4    Version 0.9, May 23, 2003 
5
6
7 The primary purpose of this benchmark is to show how different standard 
8 containers are in terms of performance. We have observed that programmers 
9 often use sets, multisets, deques in the situations where sorted vectors 
10 are the optimal solutions. Similarly, programmers often choose lists simply 
11 because they do a few insertions and deletions without knowing that vectors 
12 are more efficient at that for small containers. 
13
14
15 Frequently, of course, performance does not matter, 
16 but it is important that programmers are aware of the consequences of their 
17 choices. We are not saying that only vectors should be used, there are 
18 cases when one really needs a more complicated data structure, but one needs to 
19 understand the price for additional functionality. 
20
21
22 The secondary purpose of the benchmark is to encourage compiler and library vendors to 
23 keep improving performance. For example, it is not acceptable that some compilers give 
24 you a sizable penalty for using vector iterators instead of pointer. It is also quite 
25 clear that  performance of other standard containers could be improved. 
26
27
28 The benchmark is doing the same task 7 times using different data structures: 
29 array, vector (using a pointer as iterator), vector (using the defailt cector iterator), 
30 list, deque, set and multiset. The task is to remove duplicates from a sequence of doubles. 
31 This is a simple test, but it illustrates the performance of containers. 
32
33
34 It is clear that the benchmark needs to be eventually extended 
35 to slists and even to hash-sets and hash-maps, but we decided that at present it 
36 should work only with the standard containers. As the standard grows, so can 
37 the benchmark. The additional benefit of not including hash based containers is 
38 that now all the test have identical asymptotic complexity and, even more 
39 importantly, do almost the same number of comparisons. The difference is only 
40 in data structure overhead and cache behavior. 
41
42
43 The number of times that a given test is run inversly proportional to NlogN where N is the 
44 size of the sequence.  This allows one to see how containers of different size behave. 
45 The instructive values used for the benchmark are: 10, 100, 1000, 10000, 100000, 1000000. 
46
47
48 The time taken for a run of the benchmark depends on the machine used, the compiler used, 
49 the compiler and optimizer settings used, as well as the standard library. Please note that 
50 the time taken could be several minutes - and much more if you use a slow debug mode. 
51
52
53 The output is a table where columns are separated by tabs and rows by newlines. This is 
54 barely ok for a human reader, but ideal for feeding into a program, such as a spreadsheet 
55 for display or analysis. 
56
57
58 If you want to add your own test of a container, add the name of your container to 
59 the "header string, write a test function like the existing ones, e.g. vector_test, 
60 and add a call of "run" for your test in "run_tests". 
61
62
63 Alex Stepanov 
64 stepa...@adobe.com 
65
66
67 Bjarne Stroustrup 
68 b...@cs.tamu.edu 
69
70
71 */ 
72
73
74 #include <stddef.h>       // some older implementations lack <cstddef> 
75 #include <time.h> 
76 #include <math.h> 
77 #include <stdlib.h> 
78
79
80 #include <vector> 
81 #include <algorithm> 
82 #include <list> 
83 #include <deque> 
84 #include <set> 
85
86
87 #include <iostream> 
88 #include <iomanip> 
89
90
91 typedef double element_t; 
92
93
94 using namespace std; 
95
96
97 vector<double> result_times; // results are puched into this vector 
98
99
100 typedef void(*Test)(element_t*, element_t*, int); 
101 void run(Test f, element_t* first, element_t* last, int number_of_times) 
102
103         while (number_of_times-- > 0) f(first,last,number_of_times); 
104
105
106
107 void array_test(element_t* first, element_t* last, int number_of_times) 
108
109        element_t* array = new element_t[last - first]; 
110        copy(first, last, array); 
111        sort(array, array + (last - first)); 
112        unique(array, array + (last - first)); 
113        delete [] array;   
114
115
116
117
118
119 void vector_pointer_test(element_t* first, element_t* last, int number_of_times) 
120
121        vector<element_t> container(first, last); 
122            // &*container.begin() gets us a pointer to the first element 
123        sort(&*container.begin(), &*container.end()); 
124        unique(&*container.begin(), &*container.end()); 
125
126
127
128
129
130 void vector_iterator_test(element_t* first, element_t* last, int number_of_times) 
131
132        vector<element_t> container(first, last); 
133        sort(container.begin(), container.end()); 
134        unique(container.begin(), container.end()); 
135
136
137
138
139
140 void deque_test(element_t* first, element_t* last, int number_of_times) 
141 {   
142 //       deque<element_t> container(first, last); CANNOT BE USED BECAUSE OF MVC++ 6 
143         deque<element_t> container(size_t(last - first), 0.0); 
144         copy(first, last, container.begin()); 
145         sort(container.begin(), container.end()); 
146         unique(container.begin(), container.end()); 
147
148
149
150
151
152 void list_test(element_t* first, element_t* last, int number_of_times) 
153
154        list<element_t> container(first, last); 
155        container.sort(); 
156            container.unique(); 
157
158
159
160
161
162 void set_test(element_t* first, element_t* last, int number_of_times) 
163
164        set<element_t> container(first, last); 
165
166
167
168
169
170 void multiset_test(element_t* first, element_t* last, int number_of_times) 
171
172        multiset<element_t> container(first, last); 
173        typedef multiset<element_t>::iterator iterator; 
174            { 
175                         iterator first = container.begin(); 
176                         iterator last = container.end(); 
177
178                         while (first != last) { 
179                                 iterator next = first; 
180                                 if (++next == last) break; 
181                                 if (*first == *next) 
182                                         container.erase(next); 
183                                 else 
184                                         ++first; 
185                         } 
186            } 
187
188
189
190
191
192
193 void initialize(element_t* first, element_t* last) 
194
195   element_t value = 0.0; 
196   while (first != last) { 
197          *first++ = value; 
198          value += 1.; 
199   } 
200
201
202
203
204
205 double logtwo(double x) 
206
207   return log(x)/log((double) 2.0); 
208
209
210
211
212
213 const int largest_size = 1000000; 
214
215 int number_of_tests(int size) { 
216         double n = size; 
217         double largest_n = largest_size; 
218         return int(floor((largest_n * logtwo(largest_n)) / (n * logtwo(n)))); 
219
220
221
222
223
224
225 void run_tests(int size) 
226
227         const int n = number_of_tests(size); 
228         const size_t length = 2*size; 
229         result_times.clear(); 
230
231 // make a random test set of the chosen size: 
232   vector<element_t> buf(length); 
233   element_t* buffer = &buf[0]; 
234   element_t* buffer_end = &buf[length]; 
235   initialize(buffer, buffer + size);            // elements 
236   initialize(buffer + size, buffer_end);        // duplicate elements 
237   random_shuffle(buffer, buffer_end); 
238
239
240 // test the containers: 
241   run(array_test, buffer, buffer_end, n); 
242   run(vector_pointer_test, buffer, buffer_end, n); 
243   run(vector_iterator_test, buffer, buffer_end, n); 
244   run(deque_test, buffer, buffer_end, n); 
245   run(list_test, buffer, buffer_end, n); 
246   run(set_test, buffer, buffer_end, n); 
247   run(multiset_test, buffer, buffer_end, n); 
248
249
250
251
252
253
254 int main() 
255
256   const int sizes [] = { 100000 }; 
257   const int n = sizeof(sizes)/sizeof(int); 
258   for (int i = 0; i < n; ++i) run_tests(sizes[i]);
259 }