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

stuck-waitfor-destruct
Last change on this file since 5a95560 was 78bc398, checked in by Michael Brooks <mlbrooks@…>, 7 months ago

LL perf: small fixes

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