Changeset 2b01f8e for doc/theses/mike_brooks_MMath/benchmarks/list/driver.c

Timestamp:

Apr 10, 2023, 12:03:17 PM (20 months ago)

Author:

Mike Brooks <mlbrooks@…>

Branches:

ADT, ast-experimental, master

Children:

a085470

Parents:

e9ed2a1

Message:

Adjust LL perf to use a random layout of nodes in memory

File:

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

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

@@ -17 +17 @@
 
 #if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__))
-    enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1 };
+    enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 };
     #define TRACE(tp)
 #else 
-    enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20 };
+    enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 };
     static const char * tp_filter
     // = "";
@@ -63 +63 @@
     }
 
-    int bobs_getCurrent() {
+    void * bobs_getCurrentLoc() {
+        return BFX_DEREF_POS(B_UserItem, lst, observedItem);
+    }
+    int bobs_getCurrentVal() {
         B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem);
         return curUI->userdata[17];
@@ -78 +81 @@
 int main(int argc, const char *argv[]) {
 
-
-    const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount]]]]";
-    const int static_arg_posns = 4;
+    const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed]]]]]";
+    const int static_arg_posns = 5;
 
     unsigned int ExperimentDurSec     = DefaultExperimentDurSec;
@@ -86 +88 @@
     unsigned int NumNodes             = DefaultNumNodes;
     size_t       ExperimentDurOpCount = DefaultExperimentDurOpCount;
+    unsigned int Seed                 = DefaultSeed;
 
     switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) {
+      case 5: Seed = atoi(argv[5]);
       case 4: ExperimentDurOpCount = atol(argv[4]);
       case 3: NumNodes = atoi(argv[3]);
@@ -94 +98 @@
     }
 
-    if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 ) {
+    if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) {
         printf("usage: %s %s\n", argv[0], usage_args);
         return -1;
@@ -106 +110 @@
   #endif
 
-    ui = (B_UserItem*) malloc( NumNodes * sizeof(B_UserItem) );
-    memset(ui, 0, NumNodes * sizeof(B_UserItem));
-
-    listedItems = (BFX_LISTED_ELEM_T(B_UserItem)*)malloc( NumNodes * sizeof(BFX_LISTED_ELEM_T(B_UserItem)) );
-    memset(listedItems, 0, NumNodes * sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
-
+  #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++) {
-        B_UserItem * curUI = & ui[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
+
+    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));
+
+    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)));
+
+    // Fill with demo data
+    for (unsigned int i = 0; i < NumNodes; i++) {
+        B_UserItem * curUI = & ui[INSERTPOS(i)];
         curUI->userdata[17] = i;
     }
@@ -121 +162 @@
     bobs_init(NumNodes);
 
-    // BOP Convention:
-    // Action-number arguments are for the BOP cartridge to interpret.
-    // I.e. the driver assumes no relationship between BOP_INSERT(_,_,xx) and ui[xx].
+    // 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  counter of the ADD calls (logical insert number)
+    //   remNo  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, ui, iters, i) BOP_INSERT(lst, ui, iters, i)
+    #define BOP_INIT(lst, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
     #endif
     #ifndef BOP_TEARDOWN
-    #define BOP_TEARDOWN(lst, ui, iters, i) BOP_REMOVE(lst, ui, iters, i)
+    #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
     #endif
 
@@ -146 +193 @@
             TRACE('a')
             listedItems[0] =
-                BOP_INIT(lst, ui, listedItems, 0);
+                BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]);
             TRACE('b')
             for ( int privateCurInsert = 1;
@@ -154 +201 @@
                 TRACE('-')
                 listedItems[privateCurInsert] =
-                    BOP_INSERT( lst, ui, listedItems, privateCurInsert );
+                    BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] );
                 TRACE('+')
             }
@@ -163 +210 @@
                 ) {
                 TRACE('-')
-                BOP_REMOVE( lst, ui, listedItems, privateCurRemove-1 );
+                BOP_REMOVE( lst, listedItems, privateCurRemove-1 );
                 TRACE('+')
             }
             TRACE('D')
-            BOP_TEARDOWN(lst, ui, listedItems, NumNodes-1);
+            BOP_TEARDOWN(lst, listedItems, NumNodes-1);
             TRACE('d')
 
@@ -198 +245 @@
     free(ui);
     free(listedItems);
+    free(insertOrdShuf);
 }