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

Last change on this file since 7a8de40 was 6c58850, checked in by Michael Brooks <mlbrooks@…>, 3 months ago

Revise data in linked-list plots with streamlined harness and data from runs on swift.

No change to text discussing the plots, so some of that discussion is now stale.

Harness changes allow more ifdef feature disabling and eliminate side-array usage, keeping all per-node harness state inside the list nodes.

Completely disable the interleaving experiment, which was not giving discernable data.
  • Property mode set to 100644
File size: 24.6 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.5;
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 // Fill with the ordinals (iota)
269 for (size_t i = 0; i < NumNodes; i++) {
270 insertOrdShuf[i] = i;
271 }
272 // Dummy "Seed" of -1 means skip the shuffle: measure overhead of shuffling indirection
273 if (Seed != -1) {
274 // Shuffle per https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm
275 // Don't want to draw from all permutations, only single-cycle permutations
276 srand(Seed);
277 for (size_t i = NumNodes - 1; i > 0; --i) {
278 size_t j = rand64() % i; // j in [0, i-1]
279 size_t tmp = insertOrdShuf[i];
280 insertOrdShuf[i] = insertOrdShuf[j];
281 insertOrdShuf[j] = tmp;
282 }
283 }
284 // take inserOrdShuf as successor-index; write consequences of this traversal into the elements
285 size_t lastPos = 0;
286 size_t curPos = 0;
287 for ( size_t insertOrdinal = 0; insertOrdinal < NumNodes; insertOrdinal += 1 ) {
288 B_UserItem * curItem = & ui[ curPos ];
289 curItem->succ_pos = insertOrdShuf[ curPos ];
290 curItem->pred_pos = lastPos;
291 curItem->self_ord = insertOrdinal;
292 lastPos = curPos;
293 curPos = curItem->succ_pos;
294 }
295 assert( curPos == 0 ); // completed sole cycle
296 ui[0].pred_pos = lastPos;
297 free(insertOrdShuf);
298 }
299 #define INSERTPOS(insertNum) insertOrdShuf[insertNum]
300 #endif
301
302
303 /*
304
305
306
307
308
309 TO FIX
310
311
312
313
314
315 clarify self_ord meaning insertion order or physical-adjacency order
316
317
318
319
320
321
322
323
324
325 */
326
327
328 // Interleaving affects the list position where an element-oriented operation occurs: at an outer vs. inner node.
329 // Perterbs the sequence of logical insert/remove numbers presented to the OP cartridge, e.g. from [0 1 2 3 4 5 6]
330 // 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
331 // outer/inner interleave is atually selected randomly.
332 #ifndef DISABLE_INTERLEAVING
333 // see InterleaveAction comments near top
334
335 size_t numNodesItlv[N_INTERLEAVE_ACTION] = {}; // logically const, complex init
336
337 //
338 // begin: specific to a two-fingered interleave
339 //
340 static_assert( OuterActn == 0 && InnerActn == 1 && N_INTERLEAVE_ACTION == 2 );
341
342 const size_t iactSplitPos = NumNodes - NumNodes * InterleaveFrac;
343
344 // initialize numNodesItlv
345 numNodesItlv[InnerActn] = (NumNodes-1) * InterleaveFrac; // inner, later: usual outer-inner order revd for data dep
346 numNodesItlv[OuterActn] = (NumNodes-1) - numNodesItlv[InnerActn]; // outer, earlier: ditto
347 assert( (numNodesItlv[InnerActn] + numNodesItlv[OuterActn] == NumNodes - 1) &&
348 "The two modes are meant to cover all items but one, which is left for bop_setup/bop_teardown" );
349
350 B_UserItem * const iactFwdStartItem[N_INTERLEAVE_ACTION] = { seekUi(0), (iactSplitPos == NumNodes) ? NULL : seekUi(iactSplitPos) };
351 B_UserItem * const iactRevStartItem[N_INTERLEAVE_ACTION] = { seekUi(NumNodes-1), (iactSplitPos == NumNodes) ? NULL : seekUi(NumNodes - iactSplitPos -1) };
352
353 {
354 // Not all nodes'interleave invalues are random. Need bookending nodes set to specific values.
355 // Last node seen in outer handling
356 // - must refer to inner mode
357 // - is near the split position (middle of list)
358 // - forward outer processing goes first to middle
359 // - reverse outer processing goes last to middle
360 // Last node seen in inner handling
361 // - must refer to outer mode
362 // - is at a leaf (first or last of list)
363 // - forward inner processing goes middle to last
364 // - reverse inner processing goes middle to first
365 // One of these cross references gets navigated, when its mode is the one that finishes first.
366 // (By then, all references "back" into this mode have been used up, so it's a termination condition for the mode that finishes first.)
367 // When the other mode exhausts its stash, the global ternimation condition (handled all non setup/teardown nodes) overrides its cross reference.
368 // Call out these four nodes as special (equal number, 2, referring to each mode); fill the rest randomly.
369
370 assert( InterleaveFrac >= 0.0 && InterleaveFrac <= 1.0 );
371 // no action required on no-interleave
372 if ( InterleaveFrac > 0.0 ) {
373
374 // assert( ( NumNodes >= 2 * N_INTERLEAVE_ACTION)
375 // && "Don't feel like dealing with interleave edge cases on tiny lists");
376
377 if ( NumNodes >= 2 * N_INTERLEAVE_ACTION ) {
378 InterleaveAction * interleaveKey = (InterleaveAction *) malloc( sizeof(InterleaveAction) * NumNodes );
379
380 const size_t iactStartPos [N_INTERLEAVE_ACTION] = { 0, iactSplitPos };
381 const size_t iactFinshPos [N_INTERLEAVE_ACTION] = { iactSplitPos, NumNodes };
382
383 // generate randomly drawn ikey values
384 static_assert( 1 && "sorry, not checkable" && "values of InterleaveAction are enumerable" );
385 for ( unsigned char kk = 0; kk < (unsigned char) N_INTERLEAVE_ACTION; kk++ ) { // fill to the fractions
386 InterleaveAction k = (InterleaveAction) kk;
387 for ( int i = iactStartPos[k]; i < iactFinshPos[k]; i++ ) {
388 interleaveKey[i] = k;
389 }
390 }
391 for (size_t i = 0; i < NumNodes; i++) { // shuffle
392 size_t nodesRemaining = NumNodes - i;
393 size_t swapWith = i + (rand64() % nodesRemaining);
394 InterleaveAction tempValue = interleaveKey[swapWith];
395 interleaveKey[swapWith] = interleaveKey[i];
396 interleaveKey[i] = tempValue;
397 }
398 for (size_t i = 0; i < NumNodes; i++) { // record inside items
399 ui[i].later_flip = interleaveKey[i];
400 }
401 // set bookened positions
402 // FIXME: still incorrect; can't simply overwrite like done here;
403 // need to find an oppositely actioned node to swap with;
404 // as is,
405 // ./perfexp--upp-upp--queue-inslast-remelem 5 100000 37 -1 3 .50
406 // gets one too many outers;
407 // this extra outer reenables the outer cursor at ordinal 18
408 // after the inner cursor already remvoed ordinal 18
409 assert(false && "need to fix bookends");
410 seekUi( iactStartPos[OuterActn] )->later_flip = OuterActn;
411 seekUi( iactStartPos[InnerActn] )->later_flip = InnerActn;
412 seekUi( iactFinshPos[OuterActn] -1 )->later_flip = InnerActn;
413 seekUi( iactFinshPos[InnerActn] -1 )->later_flip = OuterActn;
414 //
415 // end: specific to a two-fingered interleave
416 //
417 free(interleaveKey);
418 } else {
419 // makefile targets call it, not easy to disable
420 // so just fill as if no interleave
421 for (size_t i = 0; i < NumNodes; i++) {
422 ui[i].later_flip = OuterActn;
423 }
424 }
425 }
426
427 }
428 #endif
429
430 #ifndef DISABLE_ITERS
431 #define ITERS_SAVE(lastInsertedElemPtr, lastInsertedIter) (lastInsertedElemPtr)->selfListed = lastInsertedIter
432 #endif
433
434 BFX_INIT(B_UserItem, lst);
435
436 bobs_init(NumNodes);
437
438 // BOP_ADDFOO(lst, iters, insNo, item)
439 // BOP_REMFOO(lst, iters, remNo)
440 // lst lvalue of the list head being added to / removed from
441 // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo)
442 // insNo interleave-perterbed counter of the ADD calls (logical insert number)
443 // remNo interleave-perterbed counter of the REM calls (logical remove number)
444 // item lvalue of the item being added
445 // Logical insert number 0 and remove number n-1 are given with a distinguished hook.
446 // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks.
447 // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list.
448 // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.)
449 // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.)
450
451 // Default init/teardown is insert/remove
452 // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
453 #ifndef BOP_INIT
454 #define BOP_INIT(lst, item) BOP_INSERT(lst, ERROR_REQD_ITER_NOT_PROVIDED, item)
455 #endif
456 #ifndef BOP_TEARDOWN
457 #define BOP_TEARDOWN(lst) BOP_REMOVE(lst, ERROR_REQD_ITER_NOT_PROVIDED)
458 #endif
459
460
461 size_t privateOpsCompleted = 0;
462
463 double elapsed_sec = 0;
464 clock_t start = clock();
465
466 while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
467 for ( size_t t = 0; t < CheckDonePeriod; t += 1 ) {
468 TRACE('a') // insert special first
469 ITERS_SAVE( &ui[0],
470 BOP_INIT(lst, ui[0]) );
471 TRACE('b') // insert general
472 // Keep lastInserted even on DISABLE_ITERS because it's communication to the remove phase
473 BFX_LISTED_ELEM_T(B_UserItem) lastInserted = BFX_GET_FIRST(B_UserItem, lst);
474 B_UserItem * insertNow = seekUi(1);
475 for ( size_t privateCurInsert = 1;
476 (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
477 privateCurInsert += 1
478 ) {
479 assert( insertNow->self_ord == privateCurInsert );
480 TRACE('-')
481 lastInserted =
482 BOP_INSERT( lst, lastInserted, (*insertNow) );
483 TRACE('+')
484 ITERS_SAVE( insertNow, lastInserted );
485 #ifdef DISABLE_SHUFFLING_INDIRECTION
486 insertNow++;
487 #else
488 insertNow = & ui[ insertNow->succ_pos ];
489 #endif
490 }
491 #ifdef DISABLE_INTERLEAVING
492 // interleaving off, simple removes
493 // (remove logic of 2b01f8eb0956)
494 #ifndef DISABLE_ITERS
495 BFX_LISTED_ELEM_T(B_UserItem) nextRemoval = BOP_SWITCH_REMDIR (
496 ui[0].selfListed, // forward starts from first insert
497 lastInserted // backward starts from last insert
498 );
499 #endif
500 TRACE('c')
501 for ( size_t privateCurRemove = 1;
502 (bobs_prog_removing = privateCurRemove, privateCurRemove < NumNodes);
503 privateCurRemove += 1
504 ) {
505 #ifdef DISABLE_ITERS
506 #define curRemovalI ERROR_REQD_ITER_NOT_PROVIDED
507 #else
508 BFX_LISTED_ELEM_T(B_UserItem) curRemovalI = nextRemoval;
509 B_UserItem * curRemovalE = BFX_DEREF_POS(B_UserItem, lst, nextRemoval);
510 #ifdef DISABLE_SHUFFLING_INDIRECTION
511 nextRemoval = (BOP_SWITCH_REMDIR( curRemovalE + 1, curRemovalE - 1 ))->selfListed;
512 #else
513 nextRemoval = ui[ curRemovalE->BOP_SWITCH_REMDIR(succ_pos, pred_pos) ].selfListed;
514 #endif
515 #endif
516 TRACE('-')
517 BOP_REMOVE( lst, curRemovalI );
518 TRACE('+')
519 }
520 #else
521 // interleaving on, complex removes
522 TRACE('c') // remove general
523 size_t removeProgress [N_INTERLEAVE_ACTION] = { 0, 0 };
524 #define startItem BOP_SWITCH_REMDIR( iactFwdStartItem, iactRevStartItem )
525 B_UserItem * removeItem[N_INTERLEAVE_ACTION] =
526 { startItem[OuterActn], startItem[InnerActn] };
527 for ( InterleaveAction flip = OuterActn
528 ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
529 bobs_prog_removing_end = removeProgress[0] + 1,
530 removeProgress[0] + removeProgress[1] < NumNodes - 1 )
531 ;
532 ) {
533//printf("--- flip=%d removeProgress[0]=%zd removeProgress[1]=%zd removeItem[flip]->self_ord=%zd\n", flip, removeProgress[0], removeProgress[1], removeItem[flip]->self_ord);
534 TRACE('-')
535 BOP_REMOVE( lst, removeItem[flip]->selfListed );
536 TRACE('+')
537
538 InterleaveAction nextFlip = removeItem[flip]->later_flip;
539 removeProgress[flip] += 1;
540 removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
541 flip = nextFlip;
542 }
543
544// for ( InterleaveAction flip = OuterActn;
545// (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
546// bobs_prog_removing_end = removeProgress[0] + 1,
547// removeProgress[0] < numNodesItlv[0] && removeProgress[1] < numNodesItlv[1] );
548// ) {
549// TRACE('-')
550// BOP_REMOVE( lst, removeItem[flip]->selfListed );
551// TRACE('+')
552
553// InterleaveAction nextFlip = removeItem[flip]->later_flip;
554// removeProgress[flip] += 1;
555// removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
556// flip = nextFlip;
557// }
558// TRACE('X') // remove imbalanced
559// // most work done under general; it stops when either flip-side's work finishes
560// // now drain any any stragglers so both flip-sides' work finishes
561// for ( InterleaveAction flip = 0; flip < N_INTERLEAVE_ACTION; flip ++ ) {
562// for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
563// bobs_prog_removing_end = removeProgress[0] + 1,
564// removeProgress[flip] < numNodesItlv[flip] )
565// ;
566// ) {
567// //printf("--- flip=%d removeProgress[flip]=%zd numNodesItlv[flip]=%zd removeItem[flip]->self_ord=%zd\n", flip, removeProgress[flip], numNodesItlv[flip], removeItem[flip]->self_ord);
568// TRACE('-')
569// BOP_REMOVE( lst, removeItem[flip]->selfListed );
570// TRACE('+')
571
572// removeProgress[flip] += 1;
573// removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
574// }
575// }
576 #endif // DISABLE_INTERLEAVING
577 TRACE('D') // remove special last
578 BOP_TEARDOWN(lst);
579 TRACE('d')
580
581 privateOpsCompleted += NumNodes;
582
583 bobs_prog_rollover_flag = 1;
584 TRACE('e')
585 bobs_prog_inserting = 0;
586 bobs_prog_removing = 0;
587 bobs_prog_removing_end = 0;
588 bobs_ops_completed = privateOpsCompleted;
589 TRACE('f')
590 bobs_prog_rollover_flag = 0;
591 TRACE('g')
592 }
593 #ifndef DISABLE_CLOCK_RECHECK
594 clock_t end = clock();
595 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
596 #endif
597 }
598 #ifdef DISABLE_CLOCK_RECHECK
599 {
600 clock_t end = clock();
601 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
602 }
603 #endif
604
605 double mean_op_dur_ns = elapsed_sec / ((double)bobs_ops_completed) * 1000 * 1000 * 1000;
606 printf("%s,%zd,%f,%f\n", argv[0], bobs_ops_completed, elapsed_sec, mean_op_dur_ns);
607
608 free(ui);
609}
Note: See TracBrowser for help on using the repository browser.