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
|
#include <util/datetime/cputimer.h>
#include <library/cpp/getopt/last_getopt.h>
#include <deque>
int main(int argc, char** argv) {
NLastGetopt::TOpts opts = NLastGetopt::TOpts::Default();
ui32 nIters = 100000000;
ui32 nRows = 100000000;
ui32 nRepeats = 10;
ui32 nPrefetch = 0;
ui32 nSpin = 0;
bool shuffle = true;
opts.AddLongOption('r', "rows", "# of rows").StoreResult(&nRows);
opts.AddLongOption('i', "iter", "# of iterations").StoreResult(&nIters);
opts.AddLongOption('t', "repeats", "# of repeats").StoreResult(&nRepeats);
opts.AddLongOption('p', "prefetch", "# of prefetch").StoreResult(&nPrefetch);
opts.AddLongOption('h', "shuffle", "randomize").StoreResult(&shuffle);
opts.AddLongOption('s', "spin", "spin count").StoreResult(&nSpin);
opts.SetFreeArgsMax(0);
NLastGetopt::TOptsParseResult res(&opts, argc, argv);
std::vector<ui32> v(nRows);
std::vector<ui32> data(nRows);
std::iota(v.begin(), v.end(), 0);
if (shuffle) {
std::random_shuffle(v.begin(), v.end());
}
std::vector<ui32> prefetchQueue(nPrefetch);
ui32 queueBegin = 0;
ui32 queueEnd = 0;
ui32 queueSize = 0;
volatile ui64 tmp = 0;
std::vector<double> durations;
for (ui32 j = 0; j < nRepeats; ++j) {
TSimpleTimer timer;
ui32 index = 0;
if (nPrefetch == 0) {
for (ui32 i = 0; i < nIters; ++i) {
data[v[index++]]+=1;
if (index == nRows) {
index = 0;
}
for (ui32 j = 0; j < nSpin; ++j) {
++tmp;
}
}
} else {
auto handle = [&]() {
auto prevJ = prefetchQueue[queueBegin++];
--queueSize;
if (queueBegin == nPrefetch) {
queueBegin = 0;
}
data[prevJ]+=1;
for (ui32 j = 0; j < nSpin; ++j) {
++tmp;
}
};
for (ui32 i = 0; i < nIters; ++i) {
auto j = v[index++];
if (index == nRows) {
index = 0;
}
__builtin_prefetch(data.data() + j, 1, 3);
prefetchQueue[queueEnd++] = j;
++queueSize;
if (queueEnd == nPrefetch) {
queueEnd = 0;
}
if (queueSize == nPrefetch) {
handle();
}
}
while (queueSize > 0) {
handle();
}
}
auto duration = timer.Get();
durations.push_back(1e-6*duration.MicroSeconds());
}
// remove 1/3 of worst measurements
Sort(durations.begin(), durations.end());
durations.erase(durations.begin() + nRepeats * 2 / 3, durations.end());
nRepeats = durations.size();
double sumDurations = 0.0, sumDurationsQ = 0.0;
for (auto d : durations) {
sumDurations += d;
sumDurationsQ += d * d;
}
double avgDuration = sumDurations / nRepeats;
double dispDuration = sqrt(sumDurationsQ / nRepeats - avgDuration * avgDuration);
Cerr << "Elapsed: " << avgDuration << ", noise: " << 100*dispDuration/avgDuration << "%\n";
Cerr << "Speed: " << 1e-6 * (ui64(nIters) / avgDuration) << " M iters/sec\n";
return 0;
}
|
