source: doc/theses/mike_brooks_MMath/benchmarks/list/driver.c@ 5ba1356

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef DISABLE_OBSERVATION
#include "proglang.h"
#define bobs_init(...)
#else
#include "observation.h"
#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
#endif

typedef struct B_UserItem 
    BFX_EXTRUSION_DECL(B_UserItem)
{
    BFX_INTRUSION(B_UserItem)
//    BFX_LISTED_ELEM_T(B_UserItem) selfListed;
    UDATA_T userdata[ UDATA_LEN ];
}
B_UserItem;

BFX_EXTRUSION_FOLLOWUP(B_UserItem)

#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
    // = "";
    // = "+ea";
        = "*";
    #define TRACE(tp) \
        if (strcmp("*", tp_filter) == 0 || strchr(tp_filter, tp)) { \
            printf("%c", tp); \
            bobs_report(); \
        }
#endif

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;

#ifdef DISABLE_OBSERVATION
MAYBE_EXTERN_C (
    void bobs_seek(unsigned int i) {}
    void bobs_moveNext() {}
    void bobs_movePrev() {}
    int bobs_hasCurrent() { return 0; }
    void * bobs_getCurrentLoc() { return NULL; }
    int 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 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) {
        observedItem = listedItems[i];
    }

    void bobs_moveNext() {
        observedItem = BFX_GET_AFTER(B_UserItem, lst, observedItem);
    }

    void bobs_movePrev() {
        observedItem = BFX_GET_BEFORE(B_UserItem, lst, observedItem);
    }

    int bobs_hasCurrent() {
        return BFX_IS_VALID_POS(B_UserItem, lst, observedItem);
    }

    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[ UDATA_USE_POS ];
    }

    enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT;
    enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY;
)
#endif


#ifndef DISABLE_OBSERVATION

// 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;
)

#endif // ndef DISABLE_OBSERVATION

unsigned int uDefaultPreemption() {
        return 0;
}

#ifdef DISABLE_ITERS_AR
// 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

int main(int argc, const char *argv[]) {

  #ifdef DISABLE_OBSERVATION
    // 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;
  #endif

    const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]";
    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;

    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: NumNodes = atoi(argv[3]);
      case 2: CheckDonePeriod = atoi(argv[2]);
      case 1: ExperimentDurSec = atoi(argv[1]);
    }

    // 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);
        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

    // 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) {
        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));

  #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
        (*curUI){};
      #endif
        curUI->userdata[ UDATA_USE_POS ] = i;
    }

    BFX_INIT(B_UserItem, lst);

    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, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
    #endif
    #ifndef BOP_TEARDOWN
    #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
    #endif

    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 ) {
            TRACE('a')              // insert special first
            ITERS_SAVE( 0,
                BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]) );
            TRACE('b')              // insert general
            for ( int privateCurInsert = 1;
                  (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
                  privateCurInsert += 1
                ) {
                TRACE('-')
                ITERS_SAVE( privateCurInsert,
                    BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] ) );
                TRACE('+')
            }
          #ifdef DISABLE_INTERLEAVING
            // interleaving off, simple removes
            // (remove logic of 2b01f8eb0956)
            TRACE('c')
            for ( int privateCurRemove = 1;
                  (bobs_prog_removing = privateCurRemove, privateCurRemove < NumNodes);
                  privateCurRemove += 1
                ) {
                TRACE('-')
                BOP_REMOVE( lst, listedItems, privateCurRemove-1 );
                TRACE('+')
            }
          #else
            // interleaving on, complex removes
            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, removeBase[flip]+removeProgress[flip] );
                TRACE('+')
            }
            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('+')
                }
            }
          #endif // DISABLE_INTERLEAVING
            TRACE('D')              // remove special last
            BOP_TEARDOWN(lst, listedItems, NumNodes-1);
            TRACE('d')

            privateOpsCompleted += NumNodes;

            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')
        }
      #ifndef DISABLE_CLOCK_RECHECK
        clock_t end = clock();
        elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
      #endif
    }
    #ifdef DISABLE_CLOCK_RECHECK
    {
        clock_t end = clock();
        elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
    }
    #endif

    double mean_op_dur_ns = elapsed_sec / ((double)bobs_ops_completed) * 1000 * 1000 * 1000;
    printf("%s,%zd,%f,%f\n", argv[0], bobs_ops_completed, elapsed_sec, mean_op_dur_ns);

    free(ui);
    free(listedItems);
  #ifndef DISABLE_SHUFFLING_INDIRECTION
    free(insertOrdShuf);
  #endif
}