1 | /* |
---|
2 | |
---|
3 | $cfa is the result of building this configuration: |
---|
4 | ../cfa-cc/configure --with-target-hosts=host:nodebug |
---|
5 | |
---|
6 | |
---|
7 | Make it fixed duration and report mean time/op. |
---|
8 | |
---|
9 | I want the field of competitors to include |
---|
10 | STL-reference |
---|
11 | STL-value |
---|
12 | u++ intrusive |
---|
13 | LQ intrusive |
---|
14 | Something from Boost? |
---|
15 | |
---|
16 | Insert-remove tests |
---|
17 | ------------------- |
---|
18 | |
---|
19 | These are the fundamental list operations. |
---|
20 | |
---|
21 | The basic end-managed shapes: |
---|
22 | First-First stack |
---|
23 | Last-Last stack |
---|
24 | First-to-last queue |
---|
25 | Last-to-first queue |
---|
26 | Rando Deque |
---|
27 | |
---|
28 | Do the basic shapes, using the head for both operations. |
---|
29 | Repeat the basic shapes, using the head for one operation and an element accessor for the other. |
---|
30 | |
---|
31 | Fix a baseline basic shape |
---|
32 | - probably first-first stack |
---|
33 | - intent: the best and simplest |
---|
34 | Varying the fun operation across insert, remove |
---|
35 | Do the fun operation as item-oriented random middle. |
---|
36 | Do the boring operation (probably) using head-provided accessors |
---|
37 | |
---|
38 | All the above on a subsequent list direction |
---|
39 | |
---|
40 | Probably want to vary |
---|
41 | - am linking nodes in memory order |
---|
42 | - random access |
---|
43 | |
---|
44 | |
---|
45 | |
---|
46 | Traversal tests |
---|
47 | --------------- |
---|
48 | |
---|
49 | Set up a large bunch of inter-linked nodes. Walk the list. |
---|
50 | |
---|
51 | Cases |
---|
52 | - am walking in memory order |
---|
53 | - am walking doing random access |
---|
54 | |
---|
55 | |
---|
56 | |
---|
57 | Measures of overhead |
---|
58 | -------------------- |
---|
59 | |
---|
60 | Example motivations |
---|
61 | - some scenarios need running an RNG each iteration |
---|
62 | - don't assume I'm getting the same RNG on each platform |
---|
63 | - don't report time in RNG as a slowdown of the scenario that needs it |
---|
64 | - slowdowns due to random accesses (inevitable cache misses) are the user's fault |
---|
65 | - slowdowns due to memory allocation are the SUT's fault |
---|
66 | - slowdowns due to cache churn because SUT uses more memory than necessary are SUT's fault |
---|
67 | - these are also unlikely |
---|
68 | - I haven't designed experiments to catch it |
---|
69 | |
---|
70 | Actual RNG uses |
---|
71 | - for the rando-deque scenario: coin toss to work at head or tail |
---|
72 | - for the insert/remove-at-middle operations: index of item (in master array) to work on next |
---|
73 | - can be a precomputed master array |
---|
74 | > It almost all generalizes into a precomputed master array |
---|
75 | - Except: choice of head-oriented at-front/at-back implies different control flow (branch prediction, FP indirection) |
---|
76 | - While an element-oriented operation is always the same control flow |
---|
77 | - [control flow within the harness; point is to reveal penalties due to control-flow in SUT] |
---|
78 | |
---|
79 | ===================== |
---|
80 | |
---|
81 | Attic of early attempts to give the taxonomy above |
---|
82 | |
---|
83 | |
---|
84 | I want times for the basic operations, as applicable, in their various cases. |
---|
85 | - head-end-provided insert/remove |
---|
86 | exercising one end (stack) |
---|
87 | exercising both ends (queue; rando-deque) |
---|
88 | - item-relative insert/remove |
---|
89 | in middle/random |
---|
90 | at a head-managed end |
---|
91 | at a head-unmanaged end |
---|
92 | - mashup head-provided insert with item-relative remove, and vice-versa |
---|
93 | - iterating through |
---|
94 | |
---|
95 | |
---|
96 | Insert Remove |
---|
97 | Head:First Head:Same |
---|
98 | Head:First Head:Opposite |
---|
99 | |
---|
100 | [Insert] |
---|
101 | Head:First |
---|
102 | Head:Last |
---|
103 | Head:Randomly-Either |
---|
104 | Item:First |
---|
105 | Item:Last |
---|
106 | Item:Randomly-Middle |
---|
107 | |
---|
108 | [Remove] |
---|
109 | Head:Same / Head:First |
---|
110 | ^^ If Insertion does Head:x then Removal does Head:x; else Removal does Head:First |
---|
111 | Head:Opposite / Head:Last |
---|
112 | ^^ Ditto; not applicable for Randomly-Either |
---|
113 | |
---|
114 | |
---|
115 | */ |
---|
116 | |
---|
117 | |
---|
118 | #include <time.h> |
---|
119 | #include <stdio.h> |
---|
120 | |
---|
121 | #if defined IMPL_LQ |
---|
122 | |
---|
123 | #include <sys/queue.h> |
---|
124 | struct S { |
---|
125 | volatile int f[64]; |
---|
126 | TAILQ_ENTRY(S) x; |
---|
127 | }; |
---|
128 | TAILQ_HEAD(SL, S); |
---|
129 | |
---|
130 | |
---|
131 | #elif defined IMPL_STL |
---|
132 | |
---|
133 | #include <list> |
---|
134 | struct S { |
---|
135 | volatile int f[64]; |
---|
136 | }; |
---|
137 | |
---|
138 | #elif defined IMPL_UPP |
---|
139 | |
---|
140 | #include <uC++.h> |
---|
141 | #include <uSequence.h> |
---|
142 | struct S : public uSeqable { |
---|
143 | volatile int f[64]; |
---|
144 | }; |
---|
145 | |
---|
146 | #elif defined IMPL_CFA |
---|
147 | |
---|
148 | #include <containers/list.hfa> |
---|
149 | struct S { |
---|
150 | int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD |
---|
151 | inline dlink(S); |
---|
152 | }; |
---|
153 | P9_EMBEDDED( S, dlink(S) ) |
---|
154 | |
---|
155 | #elif defined IMPL_CFA_UPP_PORT |
---|
156 | |
---|
157 | #include <bits/sequence.hfa> |
---|
158 | struct S { |
---|
159 | inline Seqable; |
---|
160 | int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD |
---|
161 | }; |
---|
162 | static inline S *& Back( S * n ) { |
---|
163 | return (S *)Back( (Seqable *)n ); |
---|
164 | } |
---|
165 | static inline S *& Next( S * n ) { |
---|
166 | return (S *)Next( (Colable *)n ); |
---|
167 | } |
---|
168 | |
---|
169 | #else |
---|
170 | #error bad impl |
---|
171 | #endif |
---|
172 | |
---|
173 | volatile unsigned int t = 0; |
---|
174 | volatile unsigned int i_official = 0; |
---|
175 | |
---|
176 | #define Repeat( op ) for ( unsigned int i = 0; (i_official = i, i < NoOfNodes); i += 1 ) { op; } |
---|
177 | |
---|
178 | int main() { |
---|
179 | enum { NoOfNodes = 1000, Times = 100000 }; // Times supposed to be 100000 |
---|
180 | struct S s[NoOfNodes]; |
---|
181 | clock_t start, end; |
---|
182 | const char * impl = 0; |
---|
183 | |
---|
184 | #define STATS |
---|
185 | #define REPORT do { \ |
---|
186 | double elapsed = ((double) (end - start)) / CLOCKS_PER_SEC; \ |
---|
187 | printf("%s %f sec\n", impl, elapsed); \ |
---|
188 | STATS \ |
---|
189 | } while(0); |
---|
190 | |
---|
191 | #if defined IMPL_LQ |
---|
192 | do { |
---|
193 | struct SL lst; |
---|
194 | TAILQ_INIT(&lst); |
---|
195 | start = clock(); |
---|
196 | for ( t = 0; t < Times; t += 1 ) { |
---|
197 | Repeat( TAILQ_INSERT_TAIL( &lst, &s[i], x ) ); |
---|
198 | Repeat( TAILQ_REMOVE( &lst, TAILQ_FIRST( &lst ), x ) ); |
---|
199 | } |
---|
200 | end = clock(); |
---|
201 | impl = "LQ, TAILQ"; |
---|
202 | REPORT |
---|
203 | } while (0); |
---|
204 | #elif defined IMPL_STL |
---|
205 | do { |
---|
206 | std::list<S *> lst; |
---|
207 | start = clock(); |
---|
208 | for ( t = 0; t < Times; t += 1 ) { |
---|
209 | Repeat( lst.push_back( &s[i] ) ); |
---|
210 | Repeat( lst.pop_front() ); |
---|
211 | } |
---|
212 | end = clock(); |
---|
213 | impl = "STL list, pointer"; |
---|
214 | REPORT |
---|
215 | } while (0); |
---|
216 | #elif defined IMPL_UPP |
---|
217 | do { |
---|
218 | uSequence<S> lst; |
---|
219 | start = clock(); |
---|
220 | for ( t = 0; t < Times; t += 1 ) { |
---|
221 | Repeat( lst.addTail( &s[i] ) ); |
---|
222 | Repeat( lst.dropHead() ); |
---|
223 | } |
---|
224 | end = clock(); |
---|
225 | impl = "u++ intrusive list"; |
---|
226 | REPORT |
---|
227 | } while (0); |
---|
228 | #elif defined IMPL_CFA |
---|
229 | do { |
---|
230 | dlist(S) lst; |
---|
231 | start = clock(); |
---|
232 | for ( t = 0; t < Times; t += 1 ) { |
---|
233 | Repeat( insert_last( lst, s[i] ) ); |
---|
234 | Repeat( remove( lst`first ) ); |
---|
235 | } |
---|
236 | end = clock(); |
---|
237 | impl = "cfa mike-new intrusive list"; |
---|
238 | REPORT |
---|
239 | } while (0); |
---|
240 | #elif defined IMPL_CFA_UPP_PORT |
---|
241 | do { |
---|
242 | Sequence(S) lst; |
---|
243 | start = clock(); |
---|
244 | for ( t = 0; t < Times; t += 1 ) { |
---|
245 | Repeat( addHead( lst, s[i] ) ); |
---|
246 | Repeat( dropTail( lst ) ); |
---|
247 | } |
---|
248 | end = clock(); |
---|
249 | impl = "cfa colby intrusive list"; |
---|
250 | REPORT |
---|
251 | } while (0); |
---|
252 | |
---|
253 | #endif |
---|
254 | } |
---|