#include #include #include #include #include #include #include // signal #include // alarm #include // MIN #ifdef DISABLE_OBSERVATION #include "proglang.h" #define bobs_init(...) #else #include "observation.h" #endif #ifdef HUGE_USER_ITEMS #define UDATA_T float #define UDATA_LEN 17 #endif #ifndef DISABLE_INTERLEAVING #error You must disable interleaving---no longer maintained #endif // canonical insertion order means the order of traversing B_UserItem.{succ|pred}_pos references // outer v middle action: as at (just after) inserting or (just before) removing the element in question... // - outer-action node: one that is at the front or back of the list // - middle-action node: otherwise // outer action is // - typical/default: middle action happens only when InterleaveFrac > 0, and only on this fraction // - logically first: a prefix of items, in canonical insertion order, gets outer action; a suffix gets middle action // regardless of interleaving, canonical insertion order is the same as linked-list element order in the final built-up state, up to polarity // nontrivial interleaving makes the time oder of insertion/removal _operation_invocations_ different from canonical typedef enum InterleaveAction { OuterActn = 0, InnerActn = 1 } InterleaveAction; enum { N_INTERLEAVE_ACTION = 2 } ; typedef struct __attribute__(( aligned(64) )) B_UserItem BFX_EXTRUSION_DECL(B_UserItem) { BFX_INTRUSION(B_UserItem) #ifndef DISABLE_SHUFFLING_INDIRECTION size_t succ_pos; size_t pred_pos; #endif size_t self_ord; #ifndef DISABLE_INTERLEAVING InterleaveAction later_flip; #endif #ifndef DISABLE_ITERS BFX_LISTED_ELEM_T(struct B_UserItem) selfListed; #endif #ifdef HUGE_USER_ITEMS UDATA_T udata[UDATA_T] __attribute__((unused)); #endif } B_UserItem; BFX_EXTRUSION_FOLLOWUP(B_UserItem) #if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__)) enum { DefaultListLen = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 }; const double DefaultInterleaveFrac = 0.0; #define TRACE(tp) #else enum { DefaultListLen = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 }; const double DefaultInterleaveFrac = 0.0; static const char * tp_filter // = ""; // = "+ea"; = "*"; #define TRACE(tp) \ if (strcmp("*", tp_filter) == 0 || strchr(tp_filter, tp)) { \ printf("%c", tp); \ bobs_report(); \ } #endif // Number of lists used in experiment // General tests use one // Greater values help explain away poor len-1 IPC // Value always compiled in #ifndef WIDTH #define WIDTH 1 #endif static B_UserItem *ui = NULL; static BFX_LISTED_ELEM_T(B_UserItem) observedItem; static BFX_LIST_HEAD_T(B_UserItem) lst[ WIDTH ]; B_UserItem * seekUi( size_t i ) { #ifdef DISABLE_SHUFFLING_INDIRECTION return & ui[i]; #else B_UserItem * cur = & ui[0]; for (; i > 0; i--) cur = & ui[ cur->succ_pos ]; return cur; #endif } #ifdef DISABLE_OBSERVATION MAYBE_EXTERN_C ( void bobs_seek(size_t i) {} void bobs_moveNext() {} void bobs_movePrev() {} bool bobs_hasCurrent() { return 0; } void * bobs_getCurrentLoc() { return NULL; } size_t bobs_getCurrentVal() { return 0; } // enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT; // enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY; ) #else MAYBE_EXTERN_C ( volatile size_t bobs_ops_completed = 0; volatile size_t bobs_prog_inserting = 0; volatile size_t bobs_prog_removing = 0; volatile size_t bobs_prog_removing_end = 0; volatile size_t bobs_prog_rollover_flag = 0; // bobs_prog_rem_pos (declared obs.h; defined after BOP_REMPROGEND_IS_REMNO_BASED) volatile size_t bobs_priv_active_list_no = -1; volatile size_t bobs_priv_list_len = -1; void bobs_seek(size_t i) { #ifndef DISABLE_ITERS observedItem = seekUi(i)->selfListed; #endif } void bobs_moveNext() { observedItem = BFX_GET_AFTER(B_UserItem, lst[bobs_priv_active_list_no], observedItem); } void bobs_movePrev() { observedItem = BFX_GET_BEFORE(B_UserItem, lst[bobs_priv_active_list_no], observedItem); } bool bobs_hasCurrent() { return BFX_IS_VALID_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem); } void * bobs_getCurrentLoc() { return BFX_DEREF_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem); } size_t bobs_getCurrentVal() { B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst[bobs_priv_active_list_no], observedItem); return curUI->self_ord; } enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT; enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY; static inline ssize_t signDiv( ssize_t num, size_t denom ) { if ( num >= 0 ) return num / denom; else return -1 - ( ((-num)-1) / denom ); } // Abstracts progress on all insertions and on queue removals into one treatment. // `nodeProgress` is a count of nodes inserted or removed, stepping (quickly) through [0..NumNodes] // (rather than steppling slowly through [0..Length]). // Returns the position congruent to the active list number (mod WIDTH) // that is maximally less than `nodeProgress`. // A negative return means no such position is yet reached. // Interpreting this result as last listed (last inserted) vs first unlisted (last removed), // and interpreting `nodeProgress` as advancing from 0 (eg inslast-stack remove) vs // receding from NumNodes-1 (eg insfirst-stack remove), are left to the caller. static ssize_t lastActiveNodeReached( size_t nodeProgress ) { assert( signDiv( 20, 5 ) == 4 ); assert( signDiv( 19, 5 ) == 3 ); assert( signDiv( 6, 5 ) == 1 ); assert( signDiv( 5, 5 ) == 1 ); assert( signDiv( 4, 5 ) == 0 ); assert( signDiv( 3, 5 ) == 0 ); assert( signDiv( 2, 5 ) == 0 ); assert( signDiv( 1, 5 ) == 0 ); assert( signDiv( 0, 5 ) == 0 ); assert( signDiv( -1, 5 ) == -1 ); assert( signDiv( -2, 5 ) == -1 ); assert( signDiv( -2, 5 ) == -1 ); assert( signDiv( -3, 5 ) == -1 ); assert( signDiv( -4, 5 ) == -1 ); assert( signDiv( -6, 5 ) == -2 ); assert( signDiv( -7, 5 ) == -2 ); assert( signDiv( -20, 5 ) == -4 ); assert( signDiv( -21, 5 ) == -5 ); ssize_t activeLenProgress = signDiv( (ssize_t)nodeProgress - (ssize_t)bobs_priv_active_list_no, WIDTH ); // IDW ssize_t activeNodeProgress = activeLenProgress * WIDTH + (ssize_t)bobs_priv_active_list_no; // IWA if ( activeNodeProgress == nodeProgress ) return activeNodeProgress - WIDTH; else return activeNodeProgress; } ssize_t bobs_first_valid() { switch(bobs_op_movement) { case stack: return (ssize_t)bobs_priv_active_list_no; case queue: return lastActiveNodeReached( *bobs_prog_rem_pos ) + WIDTH; } assert(0 && "unsupported bobs_op_movement value"); return -1; } ssize_t bobs_last_valid() { switch(bobs_op_movement) { 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; case queue: return lastActiveNodeReached( bobs_prog_inserting ); } assert(0 && "unsupported bobs_op_movement value"); return -1; } ) #endif #ifndef DISABLE_OBSERVATION // Remove progress end (as in, outer) (number) is based (upon) remove-number // True when an OP's REMELEM used remNo to choose which element to remove // False otherwise; notably including when REMELEM just bases upon first/last // Default to false. #ifndef BOP_REMPROGEND_IS_REMNO_BASED #define BOP_REMPROGEND_IS_REMNO_BASED false #endif MAYBE_EXTERN_C ( volatile size_t const * bobs_prog_rem_pos = #ifdef DISABLE_INTERLEAVING & bobs_prog_removing #else BOP_REMPROGEND_IS_REMNO_BASED ? & bobs_prog_removing_end : & bobs_prog_removing #endif ; ) #endif // ndef DISABLE_OBSERVATION // size_t uDefaultPreemption() { // return 0; // } #ifdef DISABLE_ITERS // Saves on memory accesses, makes element-oriented removals and observation impossible (instead, they crash) static inline BFX_LISTED_ELEM_T(B_UserItem) buhrdice_pass( BFX_LISTED_ELEM_T(B_UserItem) v ) { // prevent eliding, cheaper than volatile __asm__ __volatile__ ( "" : "+r"(v) ); return v ; } // pass #define ITERS_SAVE(i, insertElemExpr) buhrdice_pass(insertElemExpr) #endif // begin: copied from https://stackoverflow.com/a/33021408 #define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12)) #define RAND_MAX_WIDTH IMAX_BITS(RAND_MAX) static_assert((RAND_MAX & (RAND_MAX + 1u)) == 0, "RAND_MAX not a Mersenne number"); uint64_t rand64(void) { uint64_t r = 0; for (int i = 0; i < 64; i += RAND_MAX_WIDTH) { r <<= RAND_MAX_WIDTH; r ^= (unsigned) rand(); } return r; } // end: copied from https://stackoverflow.com/a/33021408 #ifdef DISABLE_OBSERVATION #define OBS(...) #else #define OBS(...) __VA_ARGS__ #endif static volatile bool stop = false; static void sigAlarm( int p __attribute__(( unused )) ) { stop = true; } void runtest(const char * argv0, size_t NumNodes, size_t ExperimentDurOpCount ); int main(int argc, const char *argv[]) { const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [ListLen [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]"; const int static_arg_posns = 6; size_t ExperimentDurSec = DefaultExperimentDurSec; size_t CheckDonePeriod = DefaultCheckDonePeriod; size_t ListLen = DefaultListLen; size_t ExperimentDurOpCount = DefaultExperimentDurOpCount; size_t Seed = DefaultSeed; double InterleaveFrac = DefaultInterleaveFrac; switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) { case 6: InterleaveFrac = atof(argv[6]); case 5: Seed = atoi(argv[5]); case 4: ExperimentDurOpCount = atol(argv[4]); case 3: ListLen = atoi(argv[3]); case 2: CheckDonePeriod = atoi(argv[2]); case 1: ExperimentDurSec = atoi(argv[1]); } // printf("ExperimentDurSec=%d, CheckDonePeriod=%d, ListLen=%d, ExperimentDurOpCount=%zd, Seed=%d,\n", // ExperimentDurSec, CheckDonePeriod, ListLen, ExperimentDurOpCount, Seed ); if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || ListLen == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) { printf("usage: %s %s\n", argv[0], usage_args); return -1; } #ifdef DISABLE_CLOCK_RECHECK if (ExperimentDurSec != -1) { 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); return -1; } #endif OBS( bobs_priv_list_len = ListLen ); const size_t NumNodes = ListLen * WIDTH; ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) ); if (!ui) { printf("malloc request for %zd bytes for ui refused\n", (size_t)NumNodes * (size_t)sizeof(B_UserItem)); return 1; } memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem)); // Construct #ifdef __cforall for (size_t i = 0; i < NumNodes; i++) { B_UserItem * curUI = & ui[i]; (*curUI){}; } #endif // Shuffling makes listed items' physical order in memory different from their order within to the list. // Affects insertion: next item to insert picked through insertOrdShuf. #ifdef DISABLE_SHUFFLING_INDIRECTION for ( size_t insertOrdinal = 0; insertOrdinal < NumNodes; insertOrdinal += 1 ) { ui[insertOrdinal].self_ord = insertOrdinal; } #else // To ensure random memory order of nodes being inserted, do so according to a shuffled ordering of them. { // insertOrdShuf is a temporary list of integers; once the order is generated, we'll write its consequence into the elements size_t * insertOrdShuf = (size_t *) malloc( sizeof( size_t ) * NumNodes ); if (!insertOrdShuf) { printf("malloc request for %zd bytes for insertOrdShuf refused\n", (size_t)NumNodes * (size_t)sizeof(size_t)); return 1; } // Dummy "Seed" of -1 means skip the shuffle: measure overhead of shuffling indirection if (Seed == -1) { // Fill with the ordinals, shifted left (iota+1) // The specific single-cyle permutation that visits each item in order for (size_t i = 0; i < NumNodes; i++) { insertOrdShuf[i] = (i+1) % NumNodes; } } else { // Fill with the ordinals (iota) for (size_t i = 0; i < NumNodes; i++) { insertOrdShuf[i] = i; } // Shuffle per https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm // Don't want to draw from all permutations, only single-cycle permutations srand(Seed); for (size_t i = NumNodes - 1; i > 0; --i) { size_t j = rand64() % i; // j in [0, i-1] size_t tmp = insertOrdShuf[i]; insertOrdShuf[i] = insertOrdShuf[j]; insertOrdShuf[j] = tmp; } } // take inserOrdShuf as successor-index; write consequences of this traversal into the elements size_t lastPos = 0; size_t curPos = 0; for ( size_t insertOrdinal = 0; insertOrdinal < NumNodes; insertOrdinal += 1 ) { B_UserItem * curItem = & ui[ curPos ]; curItem->succ_pos = insertOrdShuf[ curPos ]; curItem->pred_pos = lastPos; curItem->self_ord = insertOrdinal; lastPos = curPos; curPos = curItem->succ_pos; } assert( curPos == 0 ); // completed sole cycle ui[0].pred_pos = lastPos; free(insertOrdShuf); } #define INSERTPOS(insertNum) insertOrdShuf[insertNum] #endif /* TO FIX clarify self_ord meaning insertion order or physical-adjacency order */ // Interleaving affects the list position where an element-oriented operation occurs: at an outer vs. inner node. // Perterbs the sequence of logical insert/remove numbers presented to the OP cartridge, e.g. from [0 1 2 3 4 5 6] // 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 // outer/inner interleave is atually selected randomly. #ifndef DISABLE_INTERLEAVING // see InterleaveAction comments near top size_t numNodesItlv[N_INTERLEAVE_ACTION] = {}; // logically const, complex init // // begin: specific to a two-fingered interleave // static_assert( OuterActn == 0 && InnerActn == 1 && N_INTERLEAVE_ACTION == 2 ); const size_t iactSplitPos = NumNodes - NumNodes * InterleaveFrac; // initialize numNodesItlv numNodesItlv[InnerActn] = (NumNodes-1) * InterleaveFrac; // inner, later: usual outer-inner order revd for data dep numNodesItlv[OuterActn] = (NumNodes-1) - numNodesItlv[InnerActn]; // outer, earlier: ditto assert( (numNodesItlv[InnerActn] + numNodesItlv[OuterActn] == NumNodes - 1) && "The two modes are meant to cover all items but one, which is left for bop_setup/bop_teardown" ); B_UserItem * const iactFwdStartItem[N_INTERLEAVE_ACTION] = { seekUi(0), (iactSplitPos == NumNodes) ? NULL : seekUi(iactSplitPos) }; B_UserItem * const iactRevStartItem[N_INTERLEAVE_ACTION] = { seekUi(NumNodes-1), (iactSplitPos == NumNodes) ? NULL : seekUi(NumNodes - iactSplitPos -1) }; { // Not all nodes'interleave invalues are random. Need bookending nodes set to specific values. // Last node seen in outer handling // - must refer to inner mode // - is near the split position (middle of list) // - forward outer processing goes first to middle // - reverse outer processing goes last to middle // Last node seen in inner handling // - must refer to outer mode // - is at a leaf (first or last of list) // - forward inner processing goes middle to last // - reverse inner processing goes middle to first // One of these cross references gets navigated, when its mode is the one that finishes first. // (By then, all references "back" into this mode have been used up, so it's a termination condition for the mode that finishes first.) // When the other mode exhausts its stash, the global ternimation condition (handled all non setup/teardown nodes) overrides its cross reference. // Call out these four nodes as special (equal number, 2, referring to each mode); fill the rest randomly. assert( InterleaveFrac >= 0.0 && InterleaveFrac <= 1.0 ); // no action required on no-interleave if ( InterleaveFrac > 0.0 ) { assert(false && "interleaving was abandoned; always run with InterleaveFrac=0.0"); // assert( ( NumNodes >= 2 * N_INTERLEAVE_ACTION) // && "Don't feel like dealing with interleave edge cases on tiny lists"); if ( NumNodes >= 2 * N_INTERLEAVE_ACTION ) { InterleaveAction * interleaveKey = (InterleaveAction *) malloc( sizeof(InterleaveAction) * NumNodes ); const size_t iactStartPos [N_INTERLEAVE_ACTION] = { 0, iactSplitPos }; const size_t iactFinshPos [N_INTERLEAVE_ACTION] = { iactSplitPos, NumNodes }; // generate randomly drawn ikey values static_assert( 1 && "sorry, not checkable" && "values of InterleaveAction are enumerable" ); for ( unsigned char kk = 0; kk < (unsigned char) N_INTERLEAVE_ACTION; kk++ ) { // fill to the fractions InterleaveAction k = (InterleaveAction) kk; for ( int i = iactStartPos[k]; i < iactFinshPos[k]; i++ ) { interleaveKey[i] = k; } } for (size_t i = 0; i < NumNodes; i++) { // shuffle size_t nodesRemaining = NumNodes - i; size_t swapWith = i + (rand64() % nodesRemaining); InterleaveAction tempValue = interleaveKey[swapWith]; interleaveKey[swapWith] = interleaveKey[i]; interleaveKey[i] = tempValue; } for (size_t i = 0; i < NumNodes; i++) { // record inside items ui[i].later_flip = interleaveKey[i]; } // set bookened positions // FIXME: still incorrect; can't simply overwrite like done here; // need to find an oppositely actioned node to swap with; // as is, // ./perfexp--upp-upp--queue-inslast-remelem 5 100000 37 -1 3 .50 // gets one too many outers; // this extra outer reenables the outer cursor at ordinal 18 // after the inner cursor already remvoed ordinal 18 assert(false && "need to fix bookends"); seekUi( iactStartPos[OuterActn] )->later_flip = OuterActn; seekUi( iactStartPos[InnerActn] )->later_flip = InnerActn; seekUi( iactFinshPos[OuterActn] -1 )->later_flip = InnerActn; seekUi( iactFinshPos[InnerActn] -1 )->later_flip = OuterActn; // // end: specific to a two-fingered interleave // free(interleaveKey); } else { // makefile targets call it, not easy to disable // so just fill as if no interleave for (size_t i = 0; i < NumNodes; i++) { ui[i].later_flip = OuterActn; } } } } #endif #ifndef DISABLE_ITERS #define ITERS_SAVE(lastInsertedElemPtr, lastInsertedIter) \ lastInserted[listno] = (lastInsertedElemPtr)->selfListed = lastInsertedIter #endif for ( size_t listno = 0; listno < WIDTH; listno ++ ) BFX_INIT(B_UserItem, lst[ listno ]); bobs_init(NumNodes); // BOP_ADDFOO(lst, iters, insNo, item) // BOP_REMFOO(lst, iters, remNo) // lst lvalue of the list head being added to / removed from // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo) // insNo interleave-perterbed counter of the ADD calls (logical insert number) // remNo interleave-perterbed counter of the REM calls (logical remove number) // item lvalue of the item being added // Logical insert number 0 and remove number n-1 are given with a distinguished hook. // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks. // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list. // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.) // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.) // Default init/teardown is insert/remove // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones. #ifndef BOP_INIT #define BOP_INIT(lst, item) BOP_INSERT(lst, ERROR_REQD_ITER_NOT_PROVIDED, item) #endif #ifndef BOP_TEARDOWN #define BOP_TEARDOWN(lst) BOP_REMOVE(lst, ERROR_REQD_ITER_NOT_PROVIDED) #endif #ifdef __U_CPLUSPLUS__ // uC++ doesn't implement `alarm`---it crashes with "not implemented" at runtime // so, here is an equivalent timer task _Task timer_t { size_t alarmDurSec; void main() { _Accept( ~timer_t ); or _Timeout( uDuration( alarmDurSec ) ) { sigAlarm(0); } } public: timer_t( size_t alarmDurSec ) : alarmDurSec(alarmDurSec) {} }; timer_t timer ( ExperimentDurSec ); #else signal( SIGALRM, sigAlarm ); // setup signal handler alarm( ExperimentDurSec ); // trigger in N seconds #endif runtest( argv[0], NumNodes, ExperimentDurOpCount ); free(ui); } void runtest(const char * argv0, const size_t NumNodes, size_t ExperimentDurOpCount ) { assert( NumNodes >= WIDTH ); assert( NumNodes % WIDTH == 0 ); size_t privateOpsCompleted = 0; double elapsed_sec = 0; clock_t start = clock(); while ( ! stop && privateOpsCompleted < ExperimentDurOpCount ) { B_UserItem * insertNow = & ui[ 0 ]; #ifdef DISABLE_ITERS #define INSERTION_NEIGHBOUR NOT_SUPPORTED #else BFX_LISTED_ELEM_T(B_UserItem) lastInserted[ WIDTH ]; #define INSERTION_NEIGHBOUR lastInserted[ listno ] #endif #ifdef DISABLE_SHUFFLING_INDIRECTION #define HAS_NEXT ( (void*)insertNow < (void*)&ui[NumNodes] ) #define MOVE_NEXT ( insertNow++ ) #else #define HAS_NEXT ( insertNow->self_ord != 0 ) #define MOVE_NEXT ( insertNow = & ui[ insertNow->succ_pos ] ) #endif // insert special first for ( size_t listno = 0; listno < WIDTH; listno ++ ) { OBS( bobs_priv_active_list_no = bobs_prog_inserting = listno; ) TRACE('a') ITERS_SAVE( insertNow, BOP_INIT( lst[listno], (*insertNow) ) ); MOVE_NEXT; TRACE('b') } // insert general for ( OBS( size_t privateCurInsert = WIDTH ); HAS_NEXT; ) { for ( size_t listno = 0; listno < WIDTH; (listno ++) ) { OBS( bobs_prog_inserting = privateCurInsert; ) OBS( bobs_priv_active_list_no = listno; ) TRACE('-') ITERS_SAVE( insertNow, BOP_INSERT( lst[listno], INSERTION_NEIGHBOUR, (*insertNow) ) ); TRACE('+') OBS( privateCurInsert += 1; ) MOVE_NEXT; } OBS( bobs_prog_inserting = privateCurInsert; ) } #ifndef DISABLE_ITERS BFX_LISTED_ELEM_T(B_UserItem) nextRemoval = BOP_SWITCH_REMDIR ( ui[0].selfListed, // forward starts from first insert lastInserted[ WIDTH - 1 ] // backward starts from last insert ); #endif for ( size_t listno = 0; listno < WIDTH; listno += 1 ) { OBS( bobs_priv_active_list_no = listno; ) TRACE('c') } // remove general size_t privateCurRemove = 1; // count 1/<= to observe from the item not yet being removed while ( privateCurRemove <= NumNodes - WIDTH ) // -WIDTH to stop before special last for ( size_t listno = 0; listno < WIDTH; listno += 1 ) { OBS( bobs_prog_removing = privateCurRemove; ) OBS( bobs_priv_active_list_no = listno; ) #ifdef DISABLE_ITERS #define curRemovalI ERROR_REQD_ITER_NOT_PROVIDED #else BFX_LISTED_ELEM_T(B_UserItem) curRemovalI = nextRemoval; B_UserItem * curRemovalE = BFX_DEREF_POS(B_UserItem, lst[listno], nextRemoval); #ifdef DISABLE_SHUFFLING_INDIRECTION nextRemoval = (BOP_SWITCH_REMDIR( curRemovalE + 1, curRemovalE - 1 ))->selfListed; #else nextRemoval = ui[ curRemovalE->BOP_SWITCH_REMDIR(succ_pos, pred_pos) ].selfListed; #endif #endif TRACE('-') BOP_REMOVE( lst[listno], curRemovalI ); TRACE('+') privateCurRemove += 1; } // remove special last for ( size_t listno = 0; listno < WIDTH; listno += 1 ) { OBS( bobs_prog_removing = privateCurRemove; ) OBS( bobs_priv_active_list_no = listno; ) TRACE('D') BOP_TEARDOWN(lst[listno]); TRACE('d') privateCurRemove += 1; } OBS( bobs_prog_removing = privateCurRemove; ) privateOpsCompleted += NumNodes; OBS( bobs_prog_rollover_flag = 1; TRACE('e') bobs_prog_inserting = 0; bobs_prog_removing = 0; bobs_prog_removing_end = 0; bobs_ops_completed = privateOpsCompleted; TRACE('f') bobs_prog_rollover_flag = 0; TRACE('g') ) } clock_t end = clock(); elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC); double mean_op_dur_ns = elapsed_sec / ((double)privateOpsCompleted) * 1000 * 1000 * 1000; printf("%s,%d,%zd,%f,%f\n", argv0, WIDTH, privateOpsCompleted, elapsed_sec, mean_op_dur_ns); }