1 | #include <time.h>
|
---|
2 | #include <stdio.h>
|
---|
3 | #include <stdlib.h>
|
---|
4 | #include <string.h>
|
---|
5 |
|
---|
6 | #include "observation.h"
|
---|
7 |
|
---|
8 | #ifdef TINY_USER_ITEMS
|
---|
9 | #define UDATA_T char
|
---|
10 | #define UDATA_LEN 1
|
---|
11 | #define UDATA_USE_POS 0
|
---|
12 | #else
|
---|
13 | #define UDATA_T int
|
---|
14 | #define UDATA_LEN 64
|
---|
15 | #define UDATA_USE_POS 17
|
---|
16 | #endif
|
---|
17 |
|
---|
18 | typedef struct B_UserItem
|
---|
19 | BFX_EXTRUSION_DECL(B_UserItem)
|
---|
20 | {
|
---|
21 | BFX_INTRUSION(B_UserItem)
|
---|
22 | UDATA_T userdata[ UDATA_LEN ];
|
---|
23 | }
|
---|
24 | B_UserItem;
|
---|
25 |
|
---|
26 | BFX_EXTRUSION_FOLLOWUP(B_UserItem)
|
---|
27 |
|
---|
28 | #if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__))
|
---|
29 | enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 };
|
---|
30 | const double DefaultInterleaveFrac = 0.0;
|
---|
31 | #define TRACE(tp)
|
---|
32 | #else
|
---|
33 | enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 };
|
---|
34 | const double DefaultInterleaveFrac = 0.5;
|
---|
35 | static const char * tp_filter
|
---|
36 | // = "";
|
---|
37 | // = "+ea";
|
---|
38 | = "*";
|
---|
39 | #define TRACE(tp) \
|
---|
40 | if (strcmp("*", tp_filter) == 0 || strchr(tp_filter, tp)) { \
|
---|
41 | printf("%c", tp); \
|
---|
42 | bobs_report(); \
|
---|
43 | }
|
---|
44 | #endif
|
---|
45 |
|
---|
46 | static B_UserItem *ui = NULL;
|
---|
47 |
|
---|
48 | static BFX_LISTED_ELEM_T(B_UserItem) *listedItems = NULL;
|
---|
49 | static BFX_LISTED_ELEM_T(B_UserItem) observedItem;
|
---|
50 |
|
---|
51 | static BFX_LIST_HEAD_T(B_UserItem) lst;
|
---|
52 |
|
---|
53 | MAYBE_EXTERN_C (
|
---|
54 |
|
---|
55 | volatile size_t bobs_ops_completed = 0;
|
---|
56 | volatile unsigned int bobs_prog_inserting = 0;
|
---|
57 | volatile unsigned int bobs_prog_removing = 0;
|
---|
58 | volatile unsigned int bobs_prog_removing_end = 0;
|
---|
59 | volatile unsigned int bobs_prog_rollover_flag = 0;
|
---|
60 | // bobs_prog_rem_pos (defined after BOP_REMPROGEND_IS_REMNO_BASED)
|
---|
61 |
|
---|
62 | void bobs_seek(unsigned int i) {
|
---|
63 | observedItem = listedItems[i];
|
---|
64 | }
|
---|
65 |
|
---|
66 | void bobs_moveNext() {
|
---|
67 | observedItem = BFX_GET_AFTER(B_UserItem, lst, observedItem);
|
---|
68 | }
|
---|
69 |
|
---|
70 | void bobs_movePrev() {
|
---|
71 | observedItem = BFX_GET_BEFORE(B_UserItem, lst, observedItem);
|
---|
72 | }
|
---|
73 |
|
---|
74 | int bobs_hasCurrent() {
|
---|
75 | return BFX_IS_VALID_POS(B_UserItem, lst, observedItem);
|
---|
76 | }
|
---|
77 |
|
---|
78 | void * bobs_getCurrentLoc() {
|
---|
79 | return BFX_DEREF_POS(B_UserItem, lst, observedItem);
|
---|
80 | }
|
---|
81 | int bobs_getCurrentVal() {
|
---|
82 | B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem);
|
---|
83 | return curUI->userdata[ UDATA_USE_POS ];
|
---|
84 | }
|
---|
85 |
|
---|
86 | enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT;
|
---|
87 | enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY;
|
---|
88 | )
|
---|
89 |
|
---|
90 |
|
---|
91 | // Remove progress end (number) is based (upon) remove-number
|
---|
92 | // True when an OP's REMELEM used remNo to choose which element to remove
|
---|
93 | // False otherwise; notably including when REMELEM just bases upon first/last
|
---|
94 | // Default to false.
|
---|
95 | #ifndef BOP_REMPROGEND_IS_REMNO_BASED
|
---|
96 | #define BOP_REMPROGEND_IS_REMNO_BASED false
|
---|
97 | #endif
|
---|
98 | MAYBE_EXTERN_C (
|
---|
99 | volatile unsigned int const * bobs_prog_rem_pos
|
---|
100 | = BOP_REMPROGEND_IS_REMNO_BASED ? & bobs_prog_removing_end : & bobs_prog_removing;
|
---|
101 | )
|
---|
102 |
|
---|
103 | unsigned int uDefaultPreemption() {
|
---|
104 | return 0;
|
---|
105 | }
|
---|
106 |
|
---|
107 | int main(int argc, const char *argv[]) {
|
---|
108 |
|
---|
109 | const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]";
|
---|
110 | const int static_arg_posns = 6;
|
---|
111 |
|
---|
112 | unsigned int ExperimentDurSec = DefaultExperimentDurSec;
|
---|
113 | unsigned int CheckDonePeriod = DefaultCheckDonePeriod;
|
---|
114 | unsigned int NumNodes = DefaultNumNodes;
|
---|
115 | size_t ExperimentDurOpCount = DefaultExperimentDurOpCount;
|
---|
116 | unsigned int Seed = DefaultSeed;
|
---|
117 | double InterleaveFrac = DefaultInterleaveFrac;
|
---|
118 |
|
---|
119 | switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) {
|
---|
120 | case 6: InterleaveFrac = atof(argv[6]);
|
---|
121 | case 5: Seed = atoi(argv[5]);
|
---|
122 | case 4: ExperimentDurOpCount = atol(argv[4]);
|
---|
123 | case 3: NumNodes = atoi(argv[3]);
|
---|
124 | case 2: CheckDonePeriod = atoi(argv[2]);
|
---|
125 | case 1: ExperimentDurSec = atoi(argv[1]);
|
---|
126 | }
|
---|
127 |
|
---|
128 | // printf("ExperimentDurSec=%d, CheckDonePeriod=%d, NumNodes=%d, ExperimentDurOpCount=%zd, Seed=%d,\n",
|
---|
129 | // ExperimentDurSec, CheckDonePeriod, NumNodes, ExperimentDurOpCount, Seed );
|
---|
130 |
|
---|
131 | if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) {
|
---|
132 | printf("usage: %s %s\n", argv[0], usage_args);
|
---|
133 | return -1;
|
---|
134 | }
|
---|
135 |
|
---|
136 | #ifdef DISABLE_CLOCK_RECHECK
|
---|
137 | if (ExperimentDurSec != -1) {
|
---|
138 | printf("Error: experiment compiled as fixed-work only. ExperimentDurSec (currently %d) must be set to -1.\nUsage: %s %s\n", ExperimentDurSec, argv[0], usage_args);
|
---|
139 | return -1;
|
---|
140 | }
|
---|
141 | #endif
|
---|
142 |
|
---|
143 | // Shuffling makes listed items' physical order in memory different from their order within to the list.
|
---|
144 | // Affects insertion: next item to insert picked through insertOrdShuf.
|
---|
145 | #ifdef DISABLE_SHUFFLING_INDIRECTION
|
---|
146 | #define INSERTPOS(insertNum) insertNum
|
---|
147 | #else
|
---|
148 | // To ensure random memory order of nodes being inserted, do so according to a shuffled ordering of them.
|
---|
149 | unsigned int * insertOrdShuf = (unsigned int *) malloc( (size_t)NumNodes * sizeof(unsigned int) );
|
---|
150 | if (!insertOrdShuf) {
|
---|
151 | printf("malloc request for %zd bytes for insertOrdShuf refused\n", (size_t)NumNodes * (size_t)sizeof(unsigned int));
|
---|
152 | return 1;
|
---|
153 | }
|
---|
154 | // Fill with the ordinals (iota)
|
---|
155 | for (int i = 0; i < NumNodes; i++) {
|
---|
156 | insertOrdShuf[i] = i;
|
---|
157 | }
|
---|
158 | // Dummy "Seed" of -1 means skip the shuffle: measure overhead of insertOrdShuf indirection
|
---|
159 | if (Seed != -1) {
|
---|
160 | // Shuffle
|
---|
161 | srand(Seed);
|
---|
162 | for (unsigned int i = 0; i < NumNodes; i++) {
|
---|
163 | unsigned int nodesRemaining = NumNodes - i;
|
---|
164 | unsigned int swapWith = i + rand() % nodesRemaining;
|
---|
165 | unsigned int tempValue = insertOrdShuf[swapWith];
|
---|
166 | insertOrdShuf[swapWith] = insertOrdShuf[i];
|
---|
167 | insertOrdShuf[i] = tempValue;
|
---|
168 | }
|
---|
169 | }
|
---|
170 | #define INSERTPOS(insertNum) insertOrdShuf[insertNum]
|
---|
171 | #endif
|
---|
172 |
|
---|
173 | // Interleaving affects the list position where an element-oriented operation occurs: at an end vs. in the middle.
|
---|
174 | // Perterbs the sequence of logical insert/remove numbers presented to the OP cartridge, e.g. from [0 1 2 3 4 5 6]
|
---|
175 | // to [3 0 4 1 5 2 6], which is [mid end mid end mid end solo], for a perfect-alternation interleave; except that the
|
---|
176 | // end/mid interleave is atually selected randomly.
|
---|
177 | #ifdef DISABLE_INTERLEAVING
|
---|
178 | #define nextInterleave 0
|
---|
179 | #else
|
---|
180 | const unsigned int INTRL_KEYLEN = 64;
|
---|
181 | unsigned char interleaveKey[INTRL_KEYLEN];
|
---|
182 | unsigned char nextInterleavePos = 0;
|
---|
183 | {
|
---|
184 | unsigned int numOnes = INTRL_KEYLEN * InterleaveFrac;
|
---|
185 | unsigned int numZeros = INTRL_KEYLEN - numOnes;
|
---|
186 | // generate randomly drawn 0/1
|
---|
187 | memset( interleaveKey , 0, numZeros ); // zeros then ones
|
---|
188 | memset( interleaveKey+numZeros, 1, numOnes );
|
---|
189 | for (unsigned int i = 0; i < 64; i++) { // shuffle it
|
---|
190 | unsigned int nodesRemaining = 64 - i;
|
---|
191 | unsigned int swapWith = i + rand() % nodesRemaining;
|
---|
192 | unsigned char tempValue = interleaveKey[swapWith];
|
---|
193 | interleaveKey[swapWith] = interleaveKey[i];
|
---|
194 | interleaveKey[i] = tempValue;
|
---|
195 | }
|
---|
196 | #define nextInterleave (interleaveKey[nextInterleavePos = (nextInterleavePos + 1) % 64])
|
---|
197 | }
|
---|
198 | {
|
---|
199 | unsigned int z = 0, o = 0;
|
---|
200 | for ( int i = 0; i < INTRL_KEYLEN; i++ ) {
|
---|
201 | if (interleaveKey[i]) o++;
|
---|
202 | else z++;
|
---|
203 | }
|
---|
204 | // printf("Interleaving with %u in middle and %u at end\n", o, z);
|
---|
205 | }
|
---|
206 | // printf("interleave key begins %016llx\n", *(unsigned long long*)interleaveKey);
|
---|
207 | // printf("interleave key begins %016llx\n", *(unsigned long long*)(interleaveKey+8));
|
---|
208 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
209 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
210 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
211 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
212 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
213 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
214 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
215 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
216 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
217 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
218 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
219 | // printf("sample interleave value %d\n", nextInterleave);
|
---|
220 | #endif
|
---|
221 |
|
---|
222 | ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) );
|
---|
223 | if (!ui) {
|
---|
224 | printf("malloc request for %zd bytes for ui refused\n", (size_t)NumNodes * (size_t)sizeof(B_UserItem));
|
---|
225 | return 1;
|
---|
226 | }
|
---|
227 | memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem));
|
---|
228 |
|
---|
229 | listedItems = (BFX_LISTED_ELEM_T(B_UserItem)*)malloc( (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)) );
|
---|
230 | if (!listedItems) {
|
---|
231 | printf("malloc request for %zd bytes for listedItems refused\n", (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
|
---|
232 | return 1;
|
---|
233 | }
|
---|
234 | memset(listedItems, 0, (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
|
---|
235 |
|
---|
236 | // Construct and fill with demo data
|
---|
237 | for (unsigned int i = 0; i < NumNodes; i++) {
|
---|
238 | B_UserItem * curUI = & ui[INSERTPOS(i)];
|
---|
239 | #ifdef __cforall
|
---|
240 | (*curUI){};
|
---|
241 | #endif
|
---|
242 | curUI->userdata[ UDATA_USE_POS ] = i;
|
---|
243 | }
|
---|
244 |
|
---|
245 | BFX_INIT(B_UserItem, lst);
|
---|
246 |
|
---|
247 | bobs_init(NumNodes);
|
---|
248 |
|
---|
249 | // BOP_ADDFOO(lst, iters, insNo, item)
|
---|
250 | // BOP_REMFOO(lst, iters, remNo)
|
---|
251 | // lst lvalue of the list head being added to / removed from
|
---|
252 | // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo)
|
---|
253 | // insNo interleave-perterbed counter of the ADD calls (logical insert number)
|
---|
254 | // remNo interleave-perterbed counter of the REM calls (logical remove number)
|
---|
255 | // item lvalue of the item being added
|
---|
256 | // Logical insert number 0 and remove number n-1 are given with a distinguished hook.
|
---|
257 | // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks.
|
---|
258 | // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list.
|
---|
259 | // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.)
|
---|
260 | // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.)
|
---|
261 |
|
---|
262 | // Default init/teardown is insert/remove
|
---|
263 | // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
|
---|
264 | #ifndef BOP_INIT
|
---|
265 | #define BOP_INIT(lst, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
|
---|
266 | #endif
|
---|
267 | #ifndef BOP_TEARDOWN
|
---|
268 | #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
|
---|
269 | #endif
|
---|
270 |
|
---|
271 | double elapsed_sec = 0;
|
---|
272 | clock_t start = clock();
|
---|
273 |
|
---|
274 | const unsigned int numMiddleNodes = (NumNodes-1) * InterleaveFrac;
|
---|
275 | const unsigned int numEndNodes = NumNodes - numMiddleNodes - 1;
|
---|
276 |
|
---|
277 | // printf("Running with %u in the middle and %u at end\n", numMiddleNodes, numEndNodes);
|
---|
278 |
|
---|
279 | const unsigned int removeBase[] = {0, numEndNodes};
|
---|
280 | const unsigned int removeLimit[] = {numEndNodes, numMiddleNodes};
|
---|
281 |
|
---|
282 | size_t privateOpsCompleted = 0;
|
---|
283 |
|
---|
284 | while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
|
---|
285 | for ( int t = 0; t < CheckDonePeriod; t += 1 ) {
|
---|
286 | TRACE('a') // insert special first
|
---|
287 | listedItems[0] =
|
---|
288 | BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]);
|
---|
289 | TRACE('b') // insert general
|
---|
290 | for ( int privateCurInsert = 1;
|
---|
291 | (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
|
---|
292 | privateCurInsert += 1
|
---|
293 | ) {
|
---|
294 | TRACE('-')
|
---|
295 | listedItems[privateCurInsert] =
|
---|
296 | BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] );
|
---|
297 | TRACE('+')
|
---|
298 | }
|
---|
299 | TRACE('c') // remove general
|
---|
300 | int removeProgress[] = { 0, 0 };
|
---|
301 | for ( int flip = 0;
|
---|
302 | (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
|
---|
303 | bobs_prog_removing_end = removeProgress[0] + 1,
|
---|
304 | flip = nextInterleave,
|
---|
305 | removeProgress[0] < removeLimit[0] && removeProgress[1] < removeLimit[1] );
|
---|
306 | removeProgress[flip] += 1
|
---|
307 | ) {
|
---|
308 | TRACE('-')
|
---|
309 | BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
|
---|
310 | TRACE('+')
|
---|
311 | }
|
---|
312 | TRACE('X') // remove imbalanced
|
---|
313 | // most work done under general; it stops when either flip-side's work finishes
|
---|
314 | // now drain any any stragglers so both flip-sides' work finishes
|
---|
315 | for ( int flip = 0; flip < 2; flip ++ ) {
|
---|
316 | for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
|
---|
317 | bobs_prog_removing_end = removeProgress[0] + 1,
|
---|
318 | removeProgress[flip] < removeLimit[flip] )
|
---|
319 | ; removeProgress[flip] += 1
|
---|
320 | ) {
|
---|
321 | TRACE('-')
|
---|
322 | BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
|
---|
323 | TRACE('+')
|
---|
324 | }
|
---|
325 | }
|
---|
326 | TRACE('D') // remove special last
|
---|
327 | BOP_TEARDOWN(lst, listedItems, NumNodes-1);
|
---|
328 | TRACE('d')
|
---|
329 |
|
---|
330 | privateOpsCompleted += NumNodes;
|
---|
331 |
|
---|
332 | bobs_prog_rollover_flag = 1;
|
---|
333 | TRACE('e')
|
---|
334 | bobs_prog_inserting = 0;
|
---|
335 | bobs_prog_removing = 0;
|
---|
336 | bobs_prog_removing_end = 0;
|
---|
337 | bobs_ops_completed = privateOpsCompleted;
|
---|
338 | TRACE('f')
|
---|
339 | bobs_prog_rollover_flag = 0;
|
---|
340 | TRACE('g')
|
---|
341 | }
|
---|
342 | #ifndef DISABLE_CLOCK_RECHECK
|
---|
343 | clock_t end = clock();
|
---|
344 | elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
|
---|
345 | #endif
|
---|
346 | }
|
---|
347 | #ifdef DISABLE_CLOCK_RECHECK
|
---|
348 | {
|
---|
349 | clock_t end = clock();
|
---|
350 | elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
|
---|
351 | }
|
---|
352 | #endif
|
---|
353 |
|
---|
354 | double mean_op_dur_ns = elapsed_sec / ((double)bobs_ops_completed) * 1000 * 1000 * 1000;
|
---|
355 | printf("%s,%zd,%f,%f\n", argv[0], bobs_ops_completed, elapsed_sec, mean_op_dur_ns);
|
---|
356 |
|
---|
357 | free(ui);
|
---|
358 | free(listedItems);
|
---|
359 | #ifndef DISABLE_SHUFFLING_INDIRECTION
|
---|
360 | free(insertOrdShuf);
|
---|
361 | #endif
|
---|
362 | }
|
---|