source: doc/theses/mike_brooks_MMath/benchmarks/list/_classic.c

/*

$cfa is the result of building this configuration:
../cfa-cc/configure --with-target-hosts=host:nodebug


Make it fixed duration and report mean time/op.

I want the field of competitors to include
        STL-reference
        STL-value
        u++ intrusive
        LQ intrusive
        Something from Boost?

Insert-remove tests
-------------------

These are the fundamental list operations.

The basic end-managed shapes:
        First-First stack
        Last-Last stack
        First-to-last queue
        Last-to-first queue
        Rando Deque

Do the basic shapes, using the head for both operations.
Repeat the basic shapes, using the head for one operation and an element accessor for the other.

Fix a baseline basic shape 
  - probably first-first stack
  - intent: the best and simplest
Varying the fun operation across insert, remove
Do the fun operation as item-oriented random middle.
Do the boring operation (probably) using head-provided accessors

All the above on a subsequent list direction

Probably want to vary
 - am linking nodes in memory order
 - random access



Traversal tests
---------------

Set up a large bunch of inter-linked nodes.  Walk the list.

Cases
 - am walking in memory order
 - am walking doing random access



Measures of overhead
--------------------

Example motivations
- some scenarios need running an RNG each iteration
  - don't assume I'm getting the same RNG on each platform
  - don't report time in RNG as a slowdown of the scenario that needs it
- slowdowns due to random accesses (inevitable cache misses) are the user's fault
- slowdowns due to memory allocation are the SUT's fault
- slowdowns due to cache churn because SUT uses more memory than necessary are SUT's fault
  - these are also unlikely
  - I haven't designed experiments to catch it

Actual RNG uses
- for the rando-deque scenario: coin toss to work at head or tail
- for the insert/remove-at-middle operations: index of item (in master array) to work on next
    - can be a precomputed master array
> It almost all generalizes into a precomputed master array
  - Except: choice of head-oriented at-front/at-back implies different control flow (branch prediction, FP indirection)
    - While an element-oriented operation is always the same control flow
    - [control flow within the harness; point is to reveal penalties due to control-flow in SUT]

=====================

Attic of early attempts to give the taxonomy above


I want times for the basic operations, as applicable, in their various cases.
  - head-end-provided insert/remove
      exercising one end    (stack)
      exercising both ends  (queue; rando-deque)
  - item-relative insert/remove
      in middle/random
      at a head-managed end
      at a head-unmanaged end
  - mashup head-provided insert with item-relative remove, and vice-versa
  - iterating through


Insert          Remove
Head:First      Head:Same
Head:First      Head:Opposite

[Insert]
Head:First
Head:Last
Head:Randomly-Either
Item:First
Item:Last
Item:Randomly-Middle

[Remove]
Head:Same / Head:First
  ^^ If Insertion does Head:x then Removal does Head:x; else Removal does Head:First
Head:Opposite / Head:Last
  ^^ Ditto; not applicable for Randomly-Either


*/


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

#if defined IMPL_LQ

        #include <sys/queue.h>
        struct S {
                volatile int f[64];
                TAILQ_ENTRY(S) x;
        };
        TAILQ_HEAD(SL, S);


#elif defined IMPL_STL

        #include <list>
        struct S {
                volatile int f[64];
        };

#elif defined IMPL_UPP

        #include <uC++.h>
        #include <uSequence.h>
        struct S : public uSeqable {
                volatile int f[64];
        };

#elif defined IMPL_CFA

        #include <containers/list.hfa>
        struct S {
                int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
                inline dlink(S);
        };
        P9_EMBEDDED( S, dlink(S) )

#elif defined IMPL_CFA_UPP_PORT

        #include <bits/sequence.hfa>
        struct S {
                inline Seqable;
                int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
        };
        static inline S *& Back( S * n ) {
                return (S *)Back( (Seqable *)n );
        }
        static inline S *& Next( S * n ) {
                return (S *)Next( (Colable *)n );
        }

#else
        #error bad impl
#endif

volatile unsigned int t = 0;
volatile unsigned int i_official = 0;

#define Repeat( op ) for ( unsigned int i = 0; (i_official = i, i < NoOfNodes); i += 1 ) { op; }

int main() {
        enum { NoOfNodes = 1000, Times = 100000 }; // Times supposed to be 100000
        struct S s[NoOfNodes];
        clock_t start, end;
        const char * impl = 0;

    #define STATS
    #define REPORT do { \
        double elapsed = ((double) (end - start)) / CLOCKS_PER_SEC; \
        printf("%s %f sec\n", impl, elapsed); \
        STATS \
    } while(0);

    #if defined IMPL_LQ
    do {
        struct SL lst;
        TAILQ_INIT(&lst);
        start = clock();
        for ( t = 0; t < Times; t += 1 ) {
                Repeat( TAILQ_INSERT_TAIL( &lst, &s[i], x ) );
                Repeat( TAILQ_REMOVE( &lst, TAILQ_FIRST( &lst ), x ) );
        }
        end = clock();
        impl = "LQ, TAILQ";
        REPORT
    } while (0);
    #elif defined IMPL_STL
    do {
        std::list<S *> lst;
        start = clock();
        for ( t = 0; t < Times; t += 1 ) {
                Repeat( lst.push_back( &s[i] ) );
                Repeat( lst.pop_front() );
        }
        end = clock();
        impl = "STL list, pointer";
        REPORT
    } while (0);
    #elif defined IMPL_UPP
    do {
        uSequence<S> lst;
        start = clock();
        for ( t = 0; t < Times; t += 1 ) {
                Repeat( lst.addTail( &s[i] ) );
                Repeat( lst.dropHead() );
        }
        end = clock();
        impl = "u++ intrusive list";
        REPORT
    } while (0);
    #elif defined IMPL_CFA
    do {
        dlist(S) lst;
        start = clock();
        for ( t = 0; t < Times; t += 1 ) {
                Repeat( insert_last( lst, s[i] ) );
                Repeat( remove( lst`first ) );
        }
        end = clock();
        impl = "cfa mike-new intrusive list";
        REPORT
    } while (0);
    #elif defined IMPL_CFA_UPP_PORT
    do {
        Sequence(S) lst;
        start = clock();
        for ( t = 0; t < Times; t += 1 ) {
                Repeat( addHead( lst, s[i] ) );
                Repeat( dropTail( lst ) );
        }
        end = clock();
        impl = "cfa colby intrusive list";
        REPORT
    } while (0);

    #endif
}