Changeset 6c58850 for doc/theses/mike_brooks_MMath/benchmarks/list/driver.c

Timestamp:

Aug 12, 2025, 12:44:35 AM (2 months ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

7f995d70

Parents:

81e1984b

Message:

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.

File:

• doc/theses/mike_brooks_MMath/benchmarks/list/driver.c (modified) (17 diffs)

doc/theses/mike_brooks_MMath/benchmarks/list/driver.c

@@ -3 +3 @@
 #include <stdlib.h>
 #include <string.h>
+#include <stdint.h>
+#include <assert.h>
 
 #ifdef DISABLE_OBSERVATION
@@ -11 +13 @@
 #endif
 
-#ifdef TINY_USER_ITEMS
-  #define UDATA_T char
-  #define UDATA_LEN 1
-  #define UDATA_USE_POS 0
-#else
-  #define UDATA_T int
-  #define UDATA_LEN 64
-  #define UDATA_USE_POS 17
+#ifdef HUGE_USER_ITEMS
+  #define UDATA_T float
+  #define UDATA_LEN 17
 #endif
 
-typedef struct B_UserItem 
+// 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)
-//    BFX_LISTED_ELEM_T(B_UserItem) selfListed;
-    UDATA_T userdata[ UDATA_LEN ];
+  #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;
@@ -52 +74 @@
 static B_UserItem *ui = NULL;
 
-static BFX_LISTED_ELEM_T(B_UserItem) *listedItems = NULL;
 static BFX_LISTED_ELEM_T(B_UserItem) observedItem;
 
 static BFX_LIST_HEAD_T(B_UserItem) lst;
+
+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(unsigned int i) {}
+    void bobs_seek(size_t i) {}
     void bobs_moveNext() {}
     void bobs_movePrev() {}
-    int bobs_hasCurrent() { return 0; }
+    bool bobs_hasCurrent() { return 0; }
     void * bobs_getCurrentLoc() { return NULL; }
-    int bobs_getCurrentVal() { return 0; }
+    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;
@@ -74 +105 @@
 
     volatile size_t       bobs_ops_completed      = 0;
-    volatile unsigned int bobs_prog_inserting     = 0;
-    volatile unsigned int bobs_prog_removing      = 0;
-    volatile unsigned int bobs_prog_removing_end  = 0;
-    volatile unsigned int bobs_prog_rollover_flag = 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         (defined after BOP_REMPROGEND_IS_REMNO_BASED)
 
-    void bobs_seek(unsigned int i) {
-        observedItem = listedItems[i];
+    void bobs_seek(size_t i) {
+      #ifndef DISABLE_ITERS
+        observedItem = seekUi(i)->selfListed;
+      #endif
     }
 
@@ -92 +125 @@
     }
 
-    int bobs_hasCurrent() {
+    bool bobs_hasCurrent() {
         return BFX_IS_VALID_POS(B_UserItem, lst, observedItem);
     }
@@ -99 +132 @@
         return BFX_DEREF_POS(B_UserItem, lst, observedItem);
     }
-    int bobs_getCurrentVal() {
+    size_t bobs_getCurrentVal() {
         B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem);
-        return curUI->userdata[ UDATA_USE_POS ];
+        return curUI->self_ord;
     }
 
@@ -112 +145 @@
 #ifndef DISABLE_OBSERVATION
 
-// Remove progress end (number) is based (upon) remove-number
+// 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
@@ -120 +153 @@
 #endif
 MAYBE_EXTERN_C (
-    volatile unsigned int const * bobs_prog_rem_pos =
+    volatile size_t const * bobs_prog_rem_pos =
       #ifdef DISABLE_INTERLEAVING
         & bobs_prog_removing
@@ -131 +164 @@
 #endif // ndef DISABLE_OBSERVATION
 
-unsigned int uDefaultPreemption() {
-        return 0;
-}
-
-#ifdef DISABLE_ITERS_AR
+// 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
@@ -144 +177 @@
 #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
+
 int main(int argc, const char *argv[]) {
 
@@ -149 +197 @@
     // define the outbound dependencies as locals, for compiling into nops
     size_t       bobs_ops_completed      = 0;
-    unsigned int bobs_prog_inserting     = 0;
-    unsigned int bobs_prog_removing      = 0;
-    unsigned int bobs_prog_removing_end  = 0;
-    unsigned int bobs_prog_rollover_flag = 0;
+    size_t bobs_prog_inserting     = 0;
+    size_t bobs_prog_removing      = 0;
+    size_t bobs_prog_removing_end  = 0;
+    size_t bobs_prog_rollover_flag = 0;
   #endif
 
@@ -158 +206 @@
     const int static_arg_posns = 6;
 
-    unsigned int ExperimentDurSec     = DefaultExperimentDurSec;
-    unsigned int CheckDonePeriod      = DefaultCheckDonePeriod;
-    unsigned int NumNodes             = DefaultNumNodes;
-    size_t       ExperimentDurOpCount = DefaultExperimentDurOpCount;
-    unsigned int Seed                 = DefaultSeed;
-    double       InterleaveFrac       = DefaultInterleaveFrac;
+    size_t ExperimentDurSec     = DefaultExperimentDurSec;
+    size_t CheckDonePeriod      = DefaultCheckDonePeriod;
+    size_t NumNodes             = DefaultNumNodes;
+    size_t ExperimentDurOpCount = DefaultExperimentDurOpCount;
+    size_t Seed                 = DefaultSeed;
+    double InterleaveFrac       = DefaultInterleaveFrac;
 
     switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) {
@@ -189 +237 @@
   #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
-    #define INSERTPOS(insertNum) insertNum
-  #else
-    // To ensure random memory order of nodes being inserted, do so according to a shuffled ordering of them.
-    unsigned int * insertOrdShuf = (unsigned int *) malloc( (size_t)NumNodes * sizeof(unsigned int) );
-    if (!insertOrdShuf) {
-        printf("malloc request for %zd bytes for insertOrdShuf refused\n", (size_t)NumNodes * (size_t)sizeof(unsigned int));
-        return 1;
-    }
-    // Fill with the ordinals (iota)
-    for (int i = 0; i < NumNodes; i++) {
-        insertOrdShuf[i] = i;
-    }
-    // Dummy "Seed" of -1 means skip the shuffle: measure overhead of insertOrdShuf indirection
-    if (Seed != -1) {
-        // Shuffle
-        srand(Seed);
-        for (unsigned int i = 0; i < NumNodes; i++) {
-            unsigned int nodesRemaining = NumNodes - i;
-            unsigned int swapWith = i + rand() % nodesRemaining;
-            unsigned int tempValue = insertOrdShuf[swapWith];
-            insertOrdShuf[swapWith] = insertOrdShuf[i];
-            insertOrdShuf[i] = tempValue;
-        }
-    }
-    #define INSERTPOS(insertNum) insertOrdShuf[insertNum]
-  #endif
-
-    // Interleaving affects the list position where an element-oriented operation occurs: at an end vs. in the middle.
-    // 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 [mid end mid end mid end solo], for a perfect-alternation interleave; except that the
-    // end/mid interleave is atually selected randomly.
-  #ifdef DISABLE_INTERLEAVING
-    #define nextInterleave 0
-  #else
-    const unsigned int INTRL_KEYLEN = 64;
-    unsigned char interleaveKey[INTRL_KEYLEN];
-    unsigned char nextInterleavePos = 0;
-    {
-        unsigned int numOnes = INTRL_KEYLEN * InterleaveFrac;
-        unsigned int numZeros = INTRL_KEYLEN - numOnes;
-        // generate randomly drawn 0/1
-        memset( interleaveKey         , 0, numZeros );  // zeros then ones
-        memset( interleaveKey+numZeros, 1, numOnes );
-        for (unsigned int i = 0; i < 64; i++) { // shuffle it
-            unsigned int nodesRemaining = 64 - i;
-            unsigned int swapWith = i + rand() % nodesRemaining;
-            unsigned char tempValue = interleaveKey[swapWith];
-            interleaveKey[swapWith] = interleaveKey[i];
-            interleaveKey[i] = tempValue;
-        }
-        #define nextInterleave (interleaveKey[nextInterleavePos = (nextInterleavePos + 1) % 64])
-    }
-    {
-        unsigned int z = 0, o = 0;
-        for ( int i = 0; i < INTRL_KEYLEN; i++ ) {
-            if (interleaveKey[i]) o++;
-            else z++;
-        }
-        // printf("Interleaving with %u in middle and %u at end\n", o, z);
-    }
-    // printf("interleave key begins %016llx\n", *(unsigned long long*)interleaveKey);
-    // printf("interleave key begins %016llx\n", *(unsigned long long*)(interleaveKey+8));
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-    // printf("sample interleave value %d\n", nextInterleave);
-  #endif
-
     ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) );
     if (!ui) {
@@ -274 +243 @@
     }
     memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem));
-
-  #ifndef DISABLE_ITERS_AR
-    listedItems = (BFX_LISTED_ELEM_T(B_UserItem)*)malloc( (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)) );
-    if (!listedItems) {
-        printf("malloc request for %zd bytes for listedItems refused\n", (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
-        return 1;
-    }
-    memset(listedItems, 0, (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
-    #define ITERS_SAVE(i, insertElemExpr) listedItems[i] = (insertElemExpr)
-  #endif
-
-    // Construct and fill with demo data
-    for (unsigned int i = 0; i < NumNodes; i++) {
-        B_UserItem * curUI = & ui[INSERTPOS(i)];
-      #ifdef __cforall
+    // Construct
+    #ifdef __cforall
+    for (size_t i = 0; i < NumNodes; i++) {
+        B_UserItem * curUI = & ui[i];
         (*curUI){};
-      #endif
-        curUI->userdata[ UDATA_USE_POS ] = i;
-    }
+    }
+    #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;
+        }
+        // Fill with the ordinals (iota)
+        for (size_t i = 0; i < NumNodes; i++) {
+            insertOrdShuf[i] = i;
+        }
+        // Dummy "Seed" of -1 means skip the shuffle: measure overhead of shuffling indirection
+        if (Seed != -1) {
+            // 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( ( 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) (lastInsertedElemPtr)->selfListed = lastInsertedIter
+  #endif
 
     BFX_INIT(B_UserItem, lst);
@@ -314 +452 @@
     // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
     #ifndef BOP_INIT
-    #define BOP_INIT(lst, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
+    #define BOP_INIT(lst, item) BOP_INSERT(lst, ERROR_REQD_ITER_NOT_PROVIDED, item)
     #endif
     #ifndef BOP_TEARDOWN
-    #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
+    #define BOP_TEARDOWN(lst) BOP_REMOVE(lst, ERROR_REQD_ITER_NOT_PROVIDED)
     #endif
+
+
+    size_t privateOpsCompleted = 0;
 
     double elapsed_sec = 0;
     clock_t start = clock();
- 
-    const unsigned int numMiddleNodes = (NumNodes-1) * InterleaveFrac;
-    const unsigned int numEndNodes = NumNodes - numMiddleNodes - 1;
-
-    // printf("Running with %u in the middle and %u at end\n", numMiddleNodes, numEndNodes);
-
-    const unsigned int removeBase[] = {0, numEndNodes};
-    const unsigned int removeLimit[] = {numEndNodes, numMiddleNodes};
-
-    size_t privateOpsCompleted = 0;
 
     while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
-        for ( int t = 0; t < CheckDonePeriod; t += 1 ) {
+        for ( size_t t = 0; t < CheckDonePeriod; t += 1 ) {
             TRACE('a')              // insert special first
-            ITERS_SAVE( 0,
-                BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]) );
+            ITERS_SAVE( &ui[0],
+                BOP_INIT(lst, ui[0]) );
             TRACE('b')              // insert general
-            for ( int privateCurInsert = 1;
+            // Keep lastInserted even on DISABLE_ITERS because it's communication to the remove phase
+            BFX_LISTED_ELEM_T(B_UserItem) lastInserted = BFX_GET_FIRST(B_UserItem, lst);
+            B_UserItem * insertNow = seekUi(1);
+            for ( size_t privateCurInsert = 1;
                   (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
                   privateCurInsert += 1
                 ) {
+                assert( insertNow->self_ord == privateCurInsert );
                 TRACE('-')
-                ITERS_SAVE( privateCurInsert,
-                    BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] ) );
+                lastInserted =
+                    BOP_INSERT( lst, lastInserted, (*insertNow) );
                 TRACE('+')
+                ITERS_SAVE( insertNow, lastInserted );
+              #ifdef DISABLE_SHUFFLING_INDIRECTION
+                insertNow++;
+              #else
+                insertNow = & ui[ insertNow->succ_pos ];
+              #endif
             }
           #ifdef DISABLE_INTERLEAVING
             // interleaving off, simple removes
             // (remove logic of 2b01f8eb0956)
+          #ifndef DISABLE_ITERS
+            BFX_LISTED_ELEM_T(B_UserItem) nextRemoval = BOP_SWITCH_REMDIR (
+                ui[0].selfListed,  // forward starts from first insert
+                lastInserted       // backward starts from last insert
+            );
+          #endif
             TRACE('c')
-            for ( int privateCurRemove = 1;
+            for ( size_t privateCurRemove = 1;
                   (bobs_prog_removing = privateCurRemove, privateCurRemove < NumNodes);
                   privateCurRemove += 1
                 ) {
+              #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, 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, listedItems, privateCurRemove-1 );
+                BOP_REMOVE( lst, curRemovalI );
                 TRACE('+')
             }
@@ -363 +521 @@
             // interleaving on, complex removes
             TRACE('c')              // remove general
-            int removeProgress[] = { 0, 0 };
-            for ( int flip = 0;
-                  (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
+            size_t removeProgress  [N_INTERLEAVE_ACTION] = { 0, 0 };
+            #define startItem BOP_SWITCH_REMDIR( iactFwdStartItem, iactRevStartItem )
+            B_UserItem * removeItem[N_INTERLEAVE_ACTION] = 
+                { startItem[OuterActn], startItem[InnerActn] };
+            for ( InterleaveAction flip = OuterActn
+                ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
                      bobs_prog_removing_end = removeProgress[0] + 1,
-                     flip = nextInterleave,
-                     removeProgress[0] < removeLimit[0] && removeProgress[1] < removeLimit[1] );
-                  removeProgress[flip] += 1
+                     removeProgress[0] + removeProgress[1] < NumNodes - 1 )
+                ;
                 ) {
+//printf("--- flip=%d removeProgress[0]=%zd removeProgress[1]=%zd removeItem[flip]->self_ord=%zd\n", flip, removeProgress[0], removeProgress[1], removeItem[flip]->self_ord);
                 TRACE('-')
-                BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
+                BOP_REMOVE( lst, removeItem[flip]->selfListed );
                 TRACE('+')
+
+                InterleaveAction nextFlip = removeItem[flip]->later_flip;
+                removeProgress[flip] += 1;
+                removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
+                flip = nextFlip;
             }
-            TRACE('X')              // remove imbalanced
-            // most work done under general; it stops when either flip-side's work finishes
-            // now drain any any stragglers so both flip-sides' work finishes
-            for ( int flip = 0; flip < 2; flip ++ ) {
-                for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
-                         bobs_prog_removing_end = removeProgress[0] + 1,
-                         removeProgress[flip] < removeLimit[flip] )
-                      ;  removeProgress[flip] += 1
-                    ) {
-                    TRACE('-')
-                    BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
-                    TRACE('+')
-                }
-            }
+
+//             for ( InterleaveAction flip = OuterActn;
+//                   (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
+//                      bobs_prog_removing_end = removeProgress[0] + 1,
+//                      removeProgress[0] < numNodesItlv[0] && removeProgress[1] < numNodesItlv[1] );
+//                 ) {
+//                 TRACE('-')
+//                 BOP_REMOVE( lst, removeItem[flip]->selfListed );
+//                 TRACE('+')
+
+//                 InterleaveAction nextFlip = removeItem[flip]->later_flip;
+//                 removeProgress[flip] += 1;
+//                 removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
+//                 flip = nextFlip;
+//             }
+//             TRACE('X')              // remove imbalanced
+//             // most work done under general; it stops when either flip-side's work finishes
+//             // now drain any any stragglers so both flip-sides' work finishes
+//             for ( InterleaveAction flip = 0; flip < N_INTERLEAVE_ACTION; flip ++ ) {
+//                 for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
+//                          bobs_prog_removing_end = removeProgress[0] + 1,
+//                          removeProgress[flip] < numNodesItlv[flip] )
+//                       ;
+//                     ) {
+// //printf("--- flip=%d removeProgress[flip]=%zd numNodesItlv[flip]=%zd removeItem[flip]->self_ord=%zd\n", flip, removeProgress[flip], numNodesItlv[flip], removeItem[flip]->self_ord);
+//                     TRACE('-')
+//                     BOP_REMOVE( lst, removeItem[flip]->selfListed );
+//                     TRACE('+')
+
+//                     removeProgress[flip] += 1;
+//                     removeItem[flip] = & ui[ removeItem[flip]-> BOP_SWITCH_REMDIR(succ_pos, pred_pos) ];
+//                 }
+//             }
           #endif // DISABLE_INTERLEAVING
             TRACE('D')              // remove special last
-            BOP_TEARDOWN(lst, listedItems, NumNodes-1);
+            BOP_TEARDOWN(lst);
             TRACE('d')
 
@@ -422 +607 @@
 
     free(ui);
-    free(listedItems);
-  #ifndef DISABLE_SHUFFLING_INDIRECTION
-    free(insertOrdShuf);
-  #endif
 }