Changeset 7806f91 for doc/theses/mike_brooks_MMath/benchmarks/list/driver.c

Timestamp:

Jul 25, 2025, 3:29:48 PM (2 months ago)

Author:

Mike Brooks <mlbrooks@…>

Branches:

master

Children:

1eea589f, 29c6a7d

Parents:

7640ff5

Message:

Add code for reproducing performance numbers in thesis draft of 16a843

File:

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

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

@@ -6 +6 @@
 #include "observation.h"
 
+#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
+#endif
+
 typedef struct B_UserItem 
     BFX_EXTRUSION_DECL(B_UserItem)
 {
     BFX_INTRUSION(B_UserItem)
-    int userdata[64];
+    UDATA_T userdata[ UDATA_LEN ];
 }
 B_UserItem;
@@ -18 +28 @@
 #if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__))
     enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 };
+    const double DefaultInterleaveFrac = 0.0;
     #define TRACE(tp)
 #else 
     enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 };
+    const double DefaultInterleaveFrac = 0.5;
     static const char * tp_filter
     // = "";
@@ -39 +51 @@
 static BFX_LIST_HEAD_T(B_UserItem) lst;
 
-
 MAYBE_EXTERN_C (
 
@@ -45 +56 @@
     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;
+    //                    bobs_prog_rem_pos         (defined after BOP_REMPROGEND_IS_REMNO_BASED)
 
     void bobs_seek(unsigned int i) {
@@ -68 +81 @@
     int bobs_getCurrentVal() {
         B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem);
-        return curUI->userdata[17];
+        return curUI->userdata[ UDATA_USE_POS ];
     }
 
@@ -75 +88 @@
 )
 
+
+// Remove progress end (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 unsigned int const * bobs_prog_rem_pos
+        = BOP_REMPROGEND_IS_REMNO_BASED ? & bobs_prog_removing_end : & bobs_prog_removing;
+)
+
 unsigned int uDefaultPreemption() {
         return 0;
@@ -81 +107 @@
 int main(int argc, const char *argv[]) {
 
-    const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed]]]]]";
-    const int static_arg_posns = 5;
+    const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]";
+    const int static_arg_posns = 6;
 
     unsigned int ExperimentDurSec     = DefaultExperimentDurSec;
@@ -89 +115 @@
     size_t       ExperimentDurOpCount = DefaultExperimentDurOpCount;
     unsigned int 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]);
@@ -98 +126 @@
     }
 
+    // printf("ExperimentDurSec=%d, CheckDonePeriod=%d, NumNodes=%d, ExperimentDurOpCount=%zd, Seed=%d,\n",
+    //     ExperimentDurSec, CheckDonePeriod, NumNodes, ExperimentDurOpCount, Seed );
+
     if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) {
         printf("usage: %s %s\n", argv[0], usage_args);
@@ -110 +141 @@
   #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
@@ -138 +171 @@
   #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
+    printf("interleave key %x\n", 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) {
@@ -152 +235 @@
     memset(listedItems, 0, (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
 
-    // Fill with demo data
+    // Construct and fill with demo data
     for (unsigned int i = 0; i < NumNodes; i++) {
         B_UserItem * curUI = & ui[INSERTPOS(i)];
-        curUI->userdata[17] = i;
+      #ifdef __cforall
+        (*curUI){};
+      #endif
+        curUI->userdata[ UDATA_USE_POS ] = i;
     }
 
@@ -166 +252 @@
     //   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  counter of the ADD calls (logical insert number)
-    //   remNo  counter of the REM calls (logical remove number)
+    //   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.
@@ -186 +272 @@
     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;
@@ -191 +285 @@
     while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
         for ( int t = 0; t < CheckDonePeriod; t += 1 ) {
-            TRACE('a')
+            TRACE('a')              // insert special first
             listedItems[0] =
                 BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]);
-            TRACE('b')
+            TRACE('b')              // insert general
             for ( int privateCurInsert = 1;
                   (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
@@ -204 +298 @@
                 TRACE('+')
             }
-            TRACE('c')
-            for ( int privateCurRemove = 1;
-                  (bobs_prog_removing = privateCurRemove, privateCurRemove < NumNodes);
-                  privateCurRemove += 1
+            TRACE('c')              // remove general
+            int removeProgress[] = { 0, 0 };
+            for ( int flip = 0;
+                  (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
                 ) {
                 TRACE('-')
-                BOP_REMOVE( lst, listedItems, privateCurRemove-1 );
+                BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
                 TRACE('+')
             }
-            TRACE('D')
+            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('+')
+                }
+            }
+            TRACE('D')              // remove special last
             BOP_TEARDOWN(lst, listedItems, NumNodes-1);
             TRACE('d')
@@ -222 +334 @@
             TRACE('e')
             bobs_prog_inserting = 0;
-            bobs_prog_removing = 0;            
+            bobs_prog_removing = 0;
+            bobs_prog_removing_end = 0;
             bobs_ops_completed = privateOpsCompleted;
             TRACE('f')
@@ -245 +358 @@
     free(ui);
     free(listedItems);
+  #ifndef DISABLE_SHUFFLING_INDIRECTION
     free(insertOrdShuf);
+  #endif
 }