source: doc/theses/mike_brooks_MMath/benchmarks/list/driver.c@ eaee33e

Last change on this file since eaee33e was 9d3dc40, checked in by Michael Brooks <mlbrooks@…>, 3 months ago

Various changes motivated by improving CFA score on len-1 queues.

No such CFA score improvement achieved. Each change helped only on stripped-down, "try to isolate an important factor" tests. Generally, the changes are benign refactorings. (Results substantiating "don't hurt" are forthcoming.)

Libcfa changes are

  • move a read action from between the memory breaks to before them
  • make the memory breaks conditionally excluded (default included, as before)

Harness changes are

  • add width, a compiled-in number of lists to use in round-robin order; defaults to 1, which is what was happening all along
  • make the analysis scripts tolerate (so far, ignore) the width column
  • rename CLI arg NumNodes to Length (now NumNodes is Length * Width)
  • factor core testing loops into helper function runtest
  • switch to signal-based termination (and add uC++ work-around)
  • put "iterator threading" into ITERS_SAVE, joining preexisting "save iter into elem's self ref"; make iterator threading conditional on iterators-active
  • disable insertion loop counter and obs_*-variable declarations (and thus writes) when observation disabled
  • generalize observation to work on multiple lists
  • make observation and assertion-check-enabled mode work on stripped CFA list implementations like tagging-disabled
  • through this observation, ensure correctness of multi-list versions
  • Property mode set to 100644
File size: 27.3 KB
Line 
1#include <time.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5#include <stdint.h>
6#include <assert.h>
7#include <signal.h> // signal
8#include <unistd.h> // alarm
9#include <sys/param.h> // MIN
10
11#ifdef DISABLE_OBSERVATION
12#include "proglang.h"
13#define bobs_init(...)
14#else
15#include "observation.h"
16#endif
17
18#ifdef HUGE_USER_ITEMS
19 #define UDATA_T float
20 #define UDATA_LEN 17
21#endif
22
23#ifndef DISABLE_INTERLEAVING
24#error You must disable interleaving---no longer maintained
25#endif
26
27// canonical insertion order means the order of traversing B_UserItem.{succ|pred}_pos references
28// outer v middle action: as at (just after) inserting or (just before) removing the element in question...
29// - outer-action node: one that is at the front or back of the list
30// - middle-action node: otherwise
31// outer action is
32// - typical/default: middle action happens only when InterleaveFrac > 0, and only on this fraction
33// - logically first: a prefix of items, in canonical insertion order, gets outer action; a suffix gets middle action
34// regardless of interleaving, canonical insertion order is the same as linked-list element order in the final built-up state, up to polarity
35// nontrivial interleaving makes the time oder of insertion/removal _operation_invocations_ different from canonical
36typedef enum InterleaveAction { OuterActn = 0, InnerActn = 1 } InterleaveAction;
37enum { N_INTERLEAVE_ACTION = 2 } ;
38
39typedef
40struct __attribute__(( aligned(64) )) B_UserItem
41 BFX_EXTRUSION_DECL(B_UserItem)
42{
43 BFX_INTRUSION(B_UserItem)
44 #ifndef DISABLE_SHUFFLING_INDIRECTION
45 size_t succ_pos;
46 size_t pred_pos;
47 #endif
48 size_t self_ord;
49 #ifndef DISABLE_INTERLEAVING
50 InterleaveAction later_flip;
51 #endif
52 #ifndef DISABLE_ITERS
53 BFX_LISTED_ELEM_T(struct B_UserItem) selfListed;
54 #endif
55 #ifdef HUGE_USER_ITEMS
56 UDATA_T udata[UDATA_T] __attribute__((unused));
57 #endif
58}
59B_UserItem;
60
61BFX_EXTRUSION_FOLLOWUP(B_UserItem)
62
63#if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__))
64 enum { DefaultListLen = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 };
65 const double DefaultInterleaveFrac = 0.0;
66 #define TRACE(tp)
67#else
68 enum { DefaultListLen = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 };
69 const double DefaultInterleaveFrac = 0.0;
70 static const char * tp_filter
71 // = "";
72 // = "+ea";
73 = "*";
74 #define TRACE(tp) \
75 if (strcmp("*", tp_filter) == 0 || strchr(tp_filter, tp)) { \
76 printf("%c", tp); \
77 bobs_report(); \
78 }
79#endif
80
81// Number of lists used in experiment
82// General tests use one
83// Greater values help explain away poor len-1 IPC
84// Value always compiled in
85#ifndef WIDTH
86#define WIDTH 1
87#endif
88
89static B_UserItem *ui = NULL;
90
91static BFX_LISTED_ELEM_T(B_UserItem) observedItem;
92
93static BFX_LIST_HEAD_T(B_UserItem) lst[ WIDTH ];
94
95B_UserItem * seekUi( size_t i ) {
96 #ifdef DISABLE_SHUFFLING_INDIRECTION
97 return & ui[i];
98 #else
99 B_UserItem * cur = & ui[0];
100 for (; i > 0; i--) cur = & ui[ cur->succ_pos ];
101 return cur;
102 #endif
103}
104
105#ifdef DISABLE_OBSERVATION
106MAYBE_EXTERN_C (
107 void bobs_seek(size_t i) {}
108 void bobs_moveNext() {}
109 void bobs_movePrev() {}
110 bool bobs_hasCurrent() { return 0; }
111 void * bobs_getCurrentLoc() { return NULL; }
112 size_t bobs_getCurrentVal() { return 0; }
113 // enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT;
114 // enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY;
115)
116
117#else
118
119MAYBE_EXTERN_C (
120
121 volatile size_t bobs_ops_completed = 0;
122 volatile size_t bobs_prog_inserting = 0;
123 volatile size_t bobs_prog_removing = 0;
124 volatile size_t bobs_prog_removing_end = 0;
125 volatile size_t bobs_prog_rollover_flag = 0;
126 // bobs_prog_rem_pos (declared obs.h; defined after BOP_REMPROGEND_IS_REMNO_BASED)
127
128 volatile size_t bobs_priv_active_list_no = -1;
129 volatile size_t bobs_priv_list_len = -1;
130
131 void bobs_seek(size_t i) {
132 #ifndef DISABLE_ITERS
133 observedItem = seekUi(i)->selfListed;
134 #endif
135 }
136
137 void bobs_moveNext() {
138 observedItem = BFX_GET_AFTER(B_UserItem, lst[bobs_priv_active_list_no], observedItem);
139 }
140
141 void bobs_movePrev() {
142 observedItem = BFX_GET_BEFORE(B_UserItem, lst[bobs_priv_active_list_no], observedItem);
143 }
144
145 bool bobs_hasCurrent() {
146 return BFX_IS_VALID_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem);
147 }
148
149 void * bobs_getCurrentLoc() {
150 return BFX_DEREF_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem);
151 }
152 size_t bobs_getCurrentVal() {
153 B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem);
154 return curUI->self_ord;
155 }
156
157 enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT;
158 enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY;
159
160 static inline ssize_t signDiv( ssize_t num, size_t denom ) {
161 if ( num >= 0 ) return num / denom;
162 else return -1 - ( ((-num)-1) / denom );
163 }
164
165 // Abstracts progress on all insertions and on queue removals into one treatment.
166 // `nodeProgress` is a count of nodes inserted or removed, stepping (quickly) through [0..NumNodes]
167 // (rather than steppling slowly through [0..Length]).
168 // Returns the position congruent to the active list number (mod WIDTH)
169 // that is maximally less than `nodeProgress`.
170 // A negative return means no such position is yet reached.
171 // Interpreting this result as last listed (last inserted) vs first unlisted (last removed),
172 // and interpreting `nodeProgress` as advancing from 0 (eg inslast-stack remove) vs
173 // receding from NumNodes-1 (eg insfirst-stack remove), are left to the caller.
174 static ssize_t lastActiveNodeReached( size_t nodeProgress ) {
175 assert( signDiv( 20, 5 ) == 4 );
176 assert( signDiv( 19, 5 ) == 3 );
177 assert( signDiv( 6, 5 ) == 1 );
178 assert( signDiv( 5, 5 ) == 1 );
179 assert( signDiv( 4, 5 ) == 0 );
180 assert( signDiv( 3, 5 ) == 0 );
181 assert( signDiv( 2, 5 ) == 0 );
182 assert( signDiv( 1, 5 ) == 0 );
183 assert( signDiv( 0, 5 ) == 0 );
184 assert( signDiv( -1, 5 ) == -1 );
185 assert( signDiv( -2, 5 ) == -1 );
186 assert( signDiv( -2, 5 ) == -1 );
187 assert( signDiv( -3, 5 ) == -1 );
188 assert( signDiv( -4, 5 ) == -1 );
189 assert( signDiv( -6, 5 ) == -2 );
190 assert( signDiv( -7, 5 ) == -2 );
191 assert( signDiv( -20, 5 ) == -4 );
192 assert( signDiv( -21, 5 ) == -5 );
193 ssize_t activeLenProgress = signDiv( (ssize_t)nodeProgress - (ssize_t)bobs_priv_active_list_no, WIDTH ); // IDW
194 ssize_t activeNodeProgress = activeLenProgress * WIDTH + (ssize_t)bobs_priv_active_list_no; // IWA
195 if ( activeNodeProgress == nodeProgress ) return activeNodeProgress - WIDTH;
196 else return activeNodeProgress;
197 }
198
199 ssize_t bobs_first_valid() {
200 switch(bobs_op_movement) {
201 case stack: return (ssize_t)bobs_priv_active_list_no;
202 case queue: return lastActiveNodeReached( *bobs_prog_rem_pos ) + WIDTH;
203 }
204 assert(0 && "unsupported bobs_op_movement value");
205 return -1;
206 }
207 ssize_t bobs_last_valid() {
208 switch(bobs_op_movement) {
209 case stack: return lastActiveNodeReached( MIN( (ssize_t)bobs_prog_inserting - (ssize_t)WIDTH, (ssize_t)bobs_priv_list_len - (ssize_t)*bobs_prog_rem_pos - (ssize_t)WIDTH ) ) + WIDTH;
210 case queue: return lastActiveNodeReached( bobs_prog_inserting );
211 }
212 assert(0 && "unsupported bobs_op_movement value");
213 return -1;
214 }
215)
216#endif
217
218
219#ifndef DISABLE_OBSERVATION
220
221// Remove progress end (as in, outer) (number) is based (upon) remove-number
222// True when an OP's REMELEM used remNo to choose which element to remove
223// False otherwise; notably including when REMELEM just bases upon first/last
224// Default to false.
225#ifndef BOP_REMPROGEND_IS_REMNO_BASED
226#define BOP_REMPROGEND_IS_REMNO_BASED false
227#endif
228MAYBE_EXTERN_C (
229 volatile size_t const * bobs_prog_rem_pos =
230 #ifdef DISABLE_INTERLEAVING
231 & bobs_prog_removing
232 #else
233 BOP_REMPROGEND_IS_REMNO_BASED ? & bobs_prog_removing_end : & bobs_prog_removing
234 #endif
235 ;
236)
237
238#endif // ndef DISABLE_OBSERVATION
239
240// size_t uDefaultPreemption() {
241// return 0;
242// }
243
244#ifdef DISABLE_ITERS
245// Saves on memory accesses, makes element-oriented removals and observation impossible (instead, they crash)
246static inline BFX_LISTED_ELEM_T(B_UserItem) buhrdice_pass( BFX_LISTED_ELEM_T(B_UserItem) v ) { // prevent eliding, cheaper than volatile
247 __asm__ __volatile__ ( "" : "+r"(v) );
248 return v ;
249} // pass
250#define ITERS_SAVE(i, insertElemExpr) buhrdice_pass(insertElemExpr)
251#endif
252
253// begin: copied from https://stackoverflow.com/a/33021408
254#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
255#define RAND_MAX_WIDTH IMAX_BITS(RAND_MAX)
256static_assert((RAND_MAX & (RAND_MAX + 1u)) == 0, "RAND_MAX not a Mersenne number");
257
258uint64_t rand64(void) {
259 uint64_t r = 0;
260 for (int i = 0; i < 64; i += RAND_MAX_WIDTH) {
261 r <<= RAND_MAX_WIDTH;
262 r ^= (unsigned) rand();
263 }
264 return r;
265}
266// end: copied from https://stackoverflow.com/a/33021408
267
268#ifdef DISABLE_OBSERVATION
269#define OBS(...)
270#else
271#define OBS(...) __VA_ARGS__
272#endif
273
274static volatile bool stop = false;
275static void sigAlarm( int p __attribute__(( unused )) ) { stop = true; }
276
277void runtest(const char * argv0, size_t NumNodes, size_t ExperimentDurOpCount );
278
279int main(int argc, const char *argv[]) {
280
281 const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [ListLen [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]";
282 const int static_arg_posns = 6;
283
284 size_t ExperimentDurSec = DefaultExperimentDurSec;
285 size_t CheckDonePeriod = DefaultCheckDonePeriod;
286 size_t ListLen = DefaultListLen;
287 size_t ExperimentDurOpCount = DefaultExperimentDurOpCount;
288 size_t Seed = DefaultSeed;
289 double InterleaveFrac = DefaultInterleaveFrac;
290
291 switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) {
292 case 6: InterleaveFrac = atof(argv[6]);
293 case 5: Seed = atoi(argv[5]);
294 case 4: ExperimentDurOpCount = atol(argv[4]);
295 case 3: ListLen = atoi(argv[3]);
296 case 2: CheckDonePeriod = atoi(argv[2]);
297 case 1: ExperimentDurSec = atoi(argv[1]);
298 }
299
300 // printf("ExperimentDurSec=%d, CheckDonePeriod=%d, ListLen=%d, ExperimentDurOpCount=%zd, Seed=%d,\n",
301 // ExperimentDurSec, CheckDonePeriod, ListLen, ExperimentDurOpCount, Seed );
302
303 if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || ListLen == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) {
304 printf("usage: %s %s\n", argv[0], usage_args);
305 return -1;
306 }
307
308 #ifdef DISABLE_CLOCK_RECHECK
309 if (ExperimentDurSec != -1) {
310 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);
311 return -1;
312 }
313 #endif
314
315 OBS( bobs_priv_list_len = ListLen );
316 const size_t NumNodes = ListLen * WIDTH;
317
318 ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) );
319 if (!ui) {
320 printf("malloc request for %zd bytes for ui refused\n", (size_t)NumNodes * (size_t)sizeof(B_UserItem));
321 return 1;
322 }
323 memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem));
324 // Construct
325 #ifdef __cforall
326 for (size_t i = 0; i < NumNodes; i++) {
327 B_UserItem * curUI = & ui[i];
328 (*curUI){};
329 }
330 #endif
331
332 // Shuffling makes listed items' physical order in memory different from their order within to the list.
333 // Affects insertion: next item to insert picked through insertOrdShuf.
334 #ifdef DISABLE_SHUFFLING_INDIRECTION
335 for ( size_t insertOrdinal = 0; insertOrdinal < NumNodes; insertOrdinal += 1 ) {
336 ui[insertOrdinal].self_ord = insertOrdinal;
337 }
338 #else
339 // To ensure random memory order of nodes being inserted, do so according to a shuffled ordering of them.
340 {
341 // insertOrdShuf is a temporary list of integers; once the order is generated, we'll write its consequence into the elements
342 size_t * insertOrdShuf = (size_t *) malloc( sizeof( size_t ) * NumNodes );
343 if (!insertOrdShuf) {
344 printf("malloc request for %zd bytes for insertOrdShuf refused\n", (size_t)NumNodes * (size_t)sizeof(size_t));
345 return 1;
346 }
347 // Dummy "Seed" of -1 means skip the shuffle: measure overhead of shuffling indirection
348 if (Seed == -1) {
349 // Fill with the ordinals, shifted left (iota+1)
350 // The specific single-cyle permutation that visits each item in order
351 for (size_t i = 0; i < NumNodes; i++) {
352 insertOrdShuf[i] = (i+1) % NumNodes;
353 }
354 } else {
355 // Fill with the ordinals (iota)
356 for (size_t i = 0; i < NumNodes; i++) {
357 insertOrdShuf[i] = i;
358 }
359 // Shuffle per https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm
360 // Don't want to draw from all permutations, only single-cycle permutations
361 srand(Seed);
362 for (size_t i = NumNodes - 1; i > 0; --i) {
363 size_t j = rand64() % i; // j in [0, i-1]
364 size_t tmp = insertOrdShuf[i];
365 insertOrdShuf[i] = insertOrdShuf[j];
366 insertOrdShuf[j] = tmp;
367 }
368 }
369 // take inserOrdShuf as successor-index; write consequences of this traversal into the elements
370 size_t lastPos = 0;
371 size_t curPos = 0;
372 for ( size_t insertOrdinal = 0; insertOrdinal < NumNodes; insertOrdinal += 1 ) {
373 B_UserItem * curItem = & ui[ curPos ];
374 curItem->succ_pos = insertOrdShuf[ curPos ];
375 curItem->pred_pos = lastPos;
376 curItem->self_ord = insertOrdinal;
377 lastPos = curPos;
378 curPos = curItem->succ_pos;
379 }
380 assert( curPos == 0 ); // completed sole cycle
381 ui[0].pred_pos = lastPos;
382 free(insertOrdShuf);
383 }
384 #define INSERTPOS(insertNum) insertOrdShuf[insertNum]
385 #endif
386
387
388 /*
389
390
391
392
393
394 TO FIX
395
396
397
398
399
400 clarify self_ord meaning insertion order or physical-adjacency order
401
402
403
404
405
406
407
408
409
410 */
411
412
413 // Interleaving affects the list position where an element-oriented operation occurs: at an outer vs. inner node.
414 // Perterbs the sequence of logical insert/remove numbers presented to the OP cartridge, e.g. from [0 1 2 3 4 5 6]
415 // to [3 0 4 1 5 2 6], which is [inner outer inner outer inner outer solo], for a perfect-alternation interleave; except that the
416 // outer/inner interleave is atually selected randomly.
417 #ifndef DISABLE_INTERLEAVING
418 // see InterleaveAction comments near top
419
420 size_t numNodesItlv[N_INTERLEAVE_ACTION] = {}; // logically const, complex init
421
422 //
423 // begin: specific to a two-fingered interleave
424 //
425 static_assert( OuterActn == 0 && InnerActn == 1 && N_INTERLEAVE_ACTION == 2 );
426
427 const size_t iactSplitPos = NumNodes - NumNodes * InterleaveFrac;
428
429 // initialize numNodesItlv
430 numNodesItlv[InnerActn] = (NumNodes-1) * InterleaveFrac; // inner, later: usual outer-inner order revd for data dep
431 numNodesItlv[OuterActn] = (NumNodes-1) - numNodesItlv[InnerActn]; // outer, earlier: ditto
432 assert( (numNodesItlv[InnerActn] + numNodesItlv[OuterActn] == NumNodes - 1) &&
433 "The two modes are meant to cover all items but one, which is left for bop_setup/bop_teardown" );
434
435 B_UserItem * const iactFwdStartItem[N_INTERLEAVE_ACTION] = { seekUi(0), (iactSplitPos == NumNodes) ? NULL : seekUi(iactSplitPos) };
436 B_UserItem * const iactRevStartItem[N_INTERLEAVE_ACTION] = { seekUi(NumNodes-1), (iactSplitPos == NumNodes) ? NULL : seekUi(NumNodes - iactSplitPos -1) };
437
438 {
439 // Not all nodes'interleave invalues are random. Need bookending nodes set to specific values.
440 // Last node seen in outer handling
441 // - must refer to inner mode
442 // - is near the split position (middle of list)
443 // - forward outer processing goes first to middle
444 // - reverse outer processing goes last to middle
445 // Last node seen in inner handling
446 // - must refer to outer mode
447 // - is at a leaf (first or last of list)
448 // - forward inner processing goes middle to last
449 // - reverse inner processing goes middle to first
450 // One of these cross references gets navigated, when its mode is the one that finishes first.
451 // (By then, all references "back" into this mode have been used up, so it's a termination condition for the mode that finishes first.)
452 // When the other mode exhausts its stash, the global ternimation condition (handled all non setup/teardown nodes) overrides its cross reference.
453 // Call out these four nodes as special (equal number, 2, referring to each mode); fill the rest randomly.
454
455 assert( InterleaveFrac >= 0.0 && InterleaveFrac <= 1.0 );
456 // no action required on no-interleave
457 if ( InterleaveFrac > 0.0 ) {
458 assert(false && "interleaving was abandoned; always run with InterleaveFrac=0.0");
459
460 // assert( ( NumNodes >= 2 * N_INTERLEAVE_ACTION)
461 // && "Don't feel like dealing with interleave edge cases on tiny lists");
462
463 if ( NumNodes >= 2 * N_INTERLEAVE_ACTION ) {
464 InterleaveAction * interleaveKey = (InterleaveAction *) malloc( sizeof(InterleaveAction) * NumNodes );
465
466 const size_t iactStartPos [N_INTERLEAVE_ACTION] = { 0, iactSplitPos };
467 const size_t iactFinshPos [N_INTERLEAVE_ACTION] = { iactSplitPos, NumNodes };
468
469 // generate randomly drawn ikey values
470 static_assert( 1 && "sorry, not checkable" && "values of InterleaveAction are enumerable" );
471 for ( unsigned char kk = 0; kk < (unsigned char) N_INTERLEAVE_ACTION; kk++ ) { // fill to the fractions
472 InterleaveAction k = (InterleaveAction) kk;
473 for ( int i = iactStartPos[k]; i < iactFinshPos[k]; i++ ) {
474 interleaveKey[i] = k;
475 }
476 }
477 for (size_t i = 0; i < NumNodes; i++) { // shuffle
478 size_t nodesRemaining = NumNodes - i;
479 size_t swapWith = i + (rand64() % nodesRemaining);
480 InterleaveAction tempValue = interleaveKey[swapWith];
481 interleaveKey[swapWith] = interleaveKey[i];
482 interleaveKey[i] = tempValue;
483 }
484 for (size_t i = 0; i < NumNodes; i++) { // record inside items
485 ui[i].later_flip = interleaveKey[i];
486 }
487 // set bookened positions
488 // FIXME: still incorrect; can't simply overwrite like done here;
489 // need to find an oppositely actioned node to swap with;
490 // as is,
491 // ./perfexp--upp-upp--queue-inslast-remelem 5 100000 37 -1 3 .50
492 // gets one too many outers;
493 // this extra outer reenables the outer cursor at ordinal 18
494 // after the inner cursor already remvoed ordinal 18
495 assert(false && "need to fix bookends");
496 seekUi( iactStartPos[OuterActn] )->later_flip = OuterActn;
497 seekUi( iactStartPos[InnerActn] )->later_flip = InnerActn;
498 seekUi( iactFinshPos[OuterActn] -1 )->later_flip = InnerActn;
499 seekUi( iactFinshPos[InnerActn] -1 )->later_flip = OuterActn;
500 //
501 // end: specific to a two-fingered interleave
502 //
503 free(interleaveKey);
504 } else {
505 // makefile targets call it, not easy to disable
506 // so just fill as if no interleave
507 for (size_t i = 0; i < NumNodes; i++) {
508 ui[i].later_flip = OuterActn;
509 }
510 }
511 }
512
513 }
514 #endif
515
516 #ifndef DISABLE_ITERS
517 #define ITERS_SAVE(lastInsertedElemPtr, lastInsertedIter) \
518 lastInserted[listno] = (lastInsertedElemPtr)->selfListed = lastInsertedIter
519 #endif
520
521 for ( size_t listno = 0; listno < WIDTH; listno ++ )
522 BFX_INIT(B_UserItem, lst[ listno ]);
523
524 bobs_init(NumNodes);
525
526 // BOP_ADDFOO(lst, iters, insNo, item)
527 // BOP_REMFOO(lst, iters, remNo)
528 // lst lvalue of the list head being added to / removed from
529 // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo)
530 // insNo interleave-perterbed counter of the ADD calls (logical insert number)
531 // remNo interleave-perterbed counter of the REM calls (logical remove number)
532 // item lvalue of the item being added
533 // Logical insert number 0 and remove number n-1 are given with a distinguished hook.
534 // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks.
535 // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list.
536 // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.)
537 // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.)
538
539 // Default init/teardown is insert/remove
540 // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
541 #ifndef BOP_INIT
542 #define BOP_INIT(lst, item) BOP_INSERT(lst, ERROR_REQD_ITER_NOT_PROVIDED, item)
543 #endif
544 #ifndef BOP_TEARDOWN
545 #define BOP_TEARDOWN(lst) BOP_REMOVE(lst, ERROR_REQD_ITER_NOT_PROVIDED)
546 #endif
547
548 #ifdef __U_CPLUSPLUS__
549 // uC++ doesn't implement `alarm`---it crashes with "not implemented" at runtime
550 // so, here is an equivalent timer task
551 _Task timer_t {
552 size_t alarmDurSec;
553 void main() {
554 _Accept( ~timer_t );
555 or _Timeout( uDuration( alarmDurSec ) ) { sigAlarm(0); }
556 }
557 public:
558 timer_t( size_t alarmDurSec ) : alarmDurSec(alarmDurSec) {}
559 };
560 timer_t timer ( ExperimentDurSec );
561 #else
562 signal( SIGALRM, sigAlarm ); // setup signal handler
563 alarm( ExperimentDurSec ); // trigger in N seconds
564 #endif
565
566 runtest( argv[0], NumNodes, ExperimentDurOpCount );
567
568 free(ui);
569}
570
571
572void runtest(const char * argv0, const size_t NumNodes, size_t ExperimentDurOpCount ) {
573
574 assert( NumNodes >= WIDTH );
575 assert( NumNodes % WIDTH == 0 );
576
577 size_t privateOpsCompleted = 0;
578
579 double elapsed_sec = 0;
580 clock_t start = clock();
581
582 while ( ! stop && privateOpsCompleted < ExperimentDurOpCount ) {
583
584 B_UserItem * insertNow = & ui[ 0 ];
585
586 #ifdef DISABLE_ITERS
587 #define INSERTION_NEIGHBOUR NOT_SUPPORTED
588 #else
589 BFX_LISTED_ELEM_T(B_UserItem) lastInserted[ WIDTH ];
590 #define INSERTION_NEIGHBOUR lastInserted[ listno ]
591 #endif
592
593 #ifdef DISABLE_SHUFFLING_INDIRECTION
594 #define HAS_NEXT ( (void*)insertNow < (void*)&ui[NumNodes] )
595 #define MOVE_NEXT ( insertNow++ )
596 #else
597 #define HAS_NEXT ( insertNow->self_ord != 0 )
598 #define MOVE_NEXT ( insertNow = & ui[ insertNow->succ_pos ] )
599 #endif
600
601 // insert special first
602 for ( size_t listno = 0; listno < WIDTH; listno ++ ) {
603 OBS( bobs_priv_active_list_no = bobs_prog_inserting = listno; )
604 TRACE('a')
605 ITERS_SAVE( insertNow,
606 BOP_INIT( lst[listno], (*insertNow) ) );
607 MOVE_NEXT;
608 TRACE('b')
609 }
610 // insert general
611 for ( OBS( size_t privateCurInsert = WIDTH ); HAS_NEXT; ) {
612 for ( size_t listno = 0; listno < WIDTH; (listno ++) ) {
613 OBS( bobs_prog_inserting = privateCurInsert; )
614 OBS( bobs_priv_active_list_no = listno; )
615 TRACE('-')
616 ITERS_SAVE( insertNow,
617 BOP_INSERT( lst[listno], INSERTION_NEIGHBOUR, (*insertNow) ) );
618 TRACE('+')
619 OBS( privateCurInsert += 1; )
620 MOVE_NEXT;
621 }
622 OBS( bobs_prog_inserting = privateCurInsert; )
623 }
624 #ifndef DISABLE_ITERS
625 BFX_LISTED_ELEM_T(B_UserItem) nextRemoval = BOP_SWITCH_REMDIR (
626 ui[0].selfListed, // forward starts from first insert
627 lastInserted[ WIDTH - 1 ] // backward starts from last insert
628 );
629 #endif
630 for ( size_t listno = 0; listno < WIDTH; listno += 1 ) {
631 OBS( bobs_priv_active_list_no = listno; )
632 TRACE('c')
633 }
634 // remove general
635 size_t privateCurRemove = 1; // count 1/<= to observe from the item not yet being removed
636 while ( privateCurRemove <= NumNodes - WIDTH ) // -WIDTH to stop before special last
637 for ( size_t listno = 0; listno < WIDTH; listno += 1 ) {
638 OBS( bobs_prog_removing = privateCurRemove; )
639 OBS( bobs_priv_active_list_no = listno; )
640 #ifdef DISABLE_ITERS
641 #define curRemovalI ERROR_REQD_ITER_NOT_PROVIDED
642 #else
643 BFX_LISTED_ELEM_T(B_UserItem) curRemovalI = nextRemoval;
644 B_UserItem * curRemovalE = BFX_DEREF_POS(B_UserItem, lst[listno], nextRemoval);
645 #ifdef DISABLE_SHUFFLING_INDIRECTION
646 nextRemoval = (BOP_SWITCH_REMDIR( curRemovalE + 1, curRemovalE - 1 ))->selfListed;
647 #else
648 nextRemoval = ui[ curRemovalE->BOP_SWITCH_REMDIR(succ_pos, pred_pos) ].selfListed;
649 #endif
650 #endif
651 TRACE('-')
652 BOP_REMOVE( lst[listno], curRemovalI );
653 TRACE('+')
654 privateCurRemove += 1;
655 }
656 // remove special last
657 for ( size_t listno = 0; listno < WIDTH; listno += 1 ) {
658 OBS( bobs_prog_removing = privateCurRemove; )
659 OBS( bobs_priv_active_list_no = listno; )
660 TRACE('D')
661 BOP_TEARDOWN(lst[listno]);
662 TRACE('d')
663 privateCurRemove += 1;
664 }
665 OBS( bobs_prog_removing = privateCurRemove; )
666
667 privateOpsCompleted += NumNodes;
668 OBS(
669 bobs_prog_rollover_flag = 1;
670 TRACE('e')
671 bobs_prog_inserting = 0;
672 bobs_prog_removing = 0;
673 bobs_prog_removing_end = 0;
674 bobs_ops_completed = privateOpsCompleted;
675 TRACE('f')
676 bobs_prog_rollover_flag = 0;
677 TRACE('g') )
678 }
679
680 clock_t end = clock();
681 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
682
683 double mean_op_dur_ns = elapsed_sec / ((double)privateOpsCompleted) * 1000 * 1000 * 1000;
684 printf("%s,%d,%zd,%f,%f\n", argv0, WIDTH, privateOpsCompleted, elapsed_sec, mean_op_dur_ns);
685}
Note: See TracBrowser for help on using the repository browser.