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
|
#include <stdio.h>
#include <time.h>
#define i_static
#include <stc/crandom.h>
#ifdef __cplusplus
#include <deque>
#include <algorithm>
#endif
enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS};
const char* operations[] = {"insert", "erase", "find", "iter", "destruct"};
typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range;
typedef struct { const char* name; Range test[N_TESTS]; } Sample;
enum {SAMPLES = 2, N = 100000000, S = 0x3ffc, R = 4};
uint64_t seed = 1, mask1 = 0xfffffff, mask2 = 0xffff;
static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; }
#define i_tag x
#define i_val size_t
#include <stc/cdeq.h>
#ifdef __cplusplus
Sample test_std_deque() {
typedef std::deque<size_t> container;
Sample s = {"std,deque"};
{
s.test[INSERT].t1 = clock();
container con;
csrandom(seed);
c_FORRANGE (N/3) con.push_front(crandom() & mask1);
c_FORRANGE (N/3) {con.push_back(crandom() & mask1); con.pop_front();}
c_FORRANGE (N/3) con.push_back(crandom() & mask1);
s.test[INSERT].t2 = clock();
s.test[INSERT].sum = con.size();
s.test[ERASE].t1 = clock();
c_FORRANGE (con.size()/2) { con.pop_front(); con.pop_back(); }
s.test[ERASE].t2 = clock();
s.test[ERASE].sum = con.size();
}{
container con;
csrandom(seed);
c_FORRANGE (N) con.push_back(crandom() & mask2);
s.test[FIND].t1 = clock();
size_t sum = 0;
// Iteration - not inherent find - skipping
//container::iterator it;
//c_FORRANGE (S) if ((it = std::find(con.begin(), con.end(), crandom() & mask2)) != con.end()) sum += *it;
s.test[FIND].t2 = clock();
s.test[FIND].sum = sum;
s.test[ITER].t1 = clock();
sum = 0;
c_FORRANGE (R) c_FORRANGE (i, N) sum += con[i];
s.test[ITER].t2 = clock();
s.test[ITER].sum = sum;
s.test[DESTRUCT].t1 = clock();
}
s.test[DESTRUCT].t2 = clock();
s.test[DESTRUCT].sum = 0;
return s;
}
#else
Sample test_std_deque() { Sample s = {"std-deque"}; return s;}
#endif
Sample test_stc_deque() {
typedef cdeq_x container;
Sample s = {"STC,deque"};
{
s.test[INSERT].t1 = clock();
container con = cdeq_x_init();
//cdeq_x_reserve(&con, N);
csrandom(seed);
c_FORRANGE (N/3) cdeq_x_push_front(&con, crandom() & mask1);
c_FORRANGE (N/3) {cdeq_x_push_back(&con, crandom() & mask1); cdeq_x_pop_front(&con);}
c_FORRANGE (N/3) cdeq_x_push_back(&con, crandom() & mask1);
s.test[INSERT].t2 = clock();
s.test[INSERT].sum = cdeq_x_size(&con);
s.test[ERASE].t1 = clock();
c_FORRANGE (cdeq_x_size(&con)/2) { cdeq_x_pop_front(&con); cdeq_x_pop_back(&con); }
s.test[ERASE].t2 = clock();
s.test[ERASE].sum = cdeq_x_size(&con);
cdeq_x_drop(&con);
}{
csrandom(seed);
container con = cdeq_x_init();
c_FORRANGE (N) cdeq_x_push_back(&con, crandom() & mask2);
s.test[FIND].t1 = clock();
size_t sum = 0;
//cdeq_x_iter it, end = cdeq_x_end(&con);
//c_FORRANGE (S) if ((it = cdeq_x_find(&con, crandom() & mask2)).ref != end.ref) sum += *it.ref;
s.test[FIND].t2 = clock();
s.test[FIND].sum = sum;
s.test[ITER].t1 = clock();
sum = 0;
c_FORRANGE (R) c_FORRANGE (i, N) sum += con.data[i];
s.test[ITER].t2 = clock();
s.test[ITER].sum = sum;
s.test[DESTRUCT].t1 = clock();
cdeq_x_drop(&con);
}
s.test[DESTRUCT].t2 = clock();
s.test[DESTRUCT].sum = 0;
return s;
}
int main(int argc, char* argv[])
{
Sample std_s[SAMPLES + 1], stc_s[SAMPLES + 1];
c_FORRANGE (i, SAMPLES) {
std_s[i] = test_std_deque();
stc_s[i] = test_stc_deque();
if (i > 0) c_FORRANGE (j, N_TESTS) {
if (secs(std_s[i].test[j]) < secs(std_s[0].test[j])) std_s[0].test[j] = std_s[i].test[j];
if (secs(stc_s[i].test[j]) < secs(stc_s[0].test[j])) stc_s[0].test[j] = stc_s[i].test[j];
if (stc_s[i].test[j].sum != stc_s[0].test[j].sum) printf("Error in sum: test %lld, sample %lld\n", i, j);
}
}
const char* comp = argc > 1 ? argv[1] : "test";
bool header = (argc > 2 && argv[2][0] == '1');
float std_sum = 0, stc_sum = 0;
c_FORRANGE (j, N_TESTS) {
std_sum += secs(std_s[0].test[j]);
stc_sum += secs(stc_s[0].test[j]);
}
if (header) printf("Compiler,Library,C,Method,Seconds,Ratio\n");
c_FORRANGE (j, N_TESTS)
printf("%s,%s n:%d,%s,%.3f,%.3f\n", comp, std_s[0].name, N, operations[j], secs(std_s[0].test[j]), 1.0f);
printf("%s,%s n:%d,%s,%.3f,%.3f\n", comp, std_s[0].name, N, "total", std_sum, 1.0f);
c_FORRANGE (j, N_TESTS)
printf("%s,%s n:%d,%s,%.3f,%.3f\n", comp, stc_s[0].name, N, operations[j], secs(stc_s[0].test[j]), secs(std_s[0].test[j]) ? secs(stc_s[0].test[j])/secs(std_s[0].test[j]) : 1.0f);
printf("%s,%s n:%d,%s,%.3f,%.3f\n", comp, stc_s[0].name, N, "total", stc_sum, stc_sum/std_sum);
}
|
