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