Index: doc/theses/mike_brooks_MMath/benchmarks/list/.gitignore =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/.gitignore (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/.gitignore (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,4 @@ +perfexp--* +*.d +results--*.csv +results-latest.csv Index: doc/theses/mike_brooks_MMath/benchmarks/list/Makefile =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/Makefile (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/Makefile (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,141 @@ + +CFA = cfa +CXX = g++-11 +UXX = ~/u++/u++-7.0.0/bin/u++ + +MODE = performance +RUNARGS= + +ifeq "$(MODE)" "performance" +PERFFLAGS_CFA = -nodebug -O3 +PERFFLAGS_CC = -DNDEBUG -O3 +else ifeq "$(MODE)" "correctness" +PERFFLAGS_CFA = -debug -O0 -g +PERFFLAGS_CC = -O0 -g +else +$(error Bad MODE ($(MODE)); should be performance or correctness) +endif + +PERFFLAGS_CXX = $(PERFFLAGS_CC) +PERFFLAGS_UXX = $(PERFFLAGS_CC) + +SHELL = /usr/bin/bash + +# function: project an element from a filename that contains a delimited tuple +# (call proj,-,a-b-c.hfa,3) +# is +# c +define proj +$(word $(3),$(subst $(1), ,$(basename $(2)))) +endef + +# functions: cross two lists, adding given delimiter between +# (call cross,-,a b c,1 2) +# is +# a-1 a-2 b-1 b-2 c-1 c-2 +define cross +$(foreach x,$(2),$(foreach xs,$(3),$(x)$(1)$(xs))) +endef +define cross3 +$(call cross,$(1),$(2),$(call cross,$(1),$(3),$(4))) +endef +define cross4 +$(call cross,$(1),$(2),$(call cross3,$(1),$(3),$(4),$(5))) +endef +define cross5 +$(call cross,$(1),$(2),$(call cross4,$(1),$(3),$(4),$(5),$(6))) +endef + +OP_MOVEMENTS=stack queue +OP_POLARITIES=insfirst inslast +OP_ACCESSORS=allhead inselem remelem +FX_SOLUTIONS=lq-tailq lq-list cfa-cfa upp-upp cpp-stlref + +OPS=$(call cross3,-,$(OP_MOVEMENTS),$(OP_POLARITIES),$(OP_ACCESSORS)) +FXS=$(FX_SOLUTIONS) + +all : perfprogs results-latest.csv + +# Want to add functional dependency: +# if current FX_SOLUTION is lq-list then +# current OP_MOVEMENT must be stack and +# current OP_POLARITY must be insfirst +LQ_LIST_INCOMPAT_OP_MOVEMENTS=$(filter-out stack,$(OP_MOVEMENTS)) +LQ_LIST_INCOMPAT_OP_POLARITIES=$(filter-out insfirst,$(OP_POLARITIES)) +LQ_LIST_INCOMPAT_OPS=$(call cross3,-,$(LQ_LIST_INCOMPAT_OP_MOVEMENTS),$(OP_POLARITIES),$(OP_ACCESSORS)) \ + $(call cross3,-,$(OP_MOVEMENTS),$(LQ_LIST_INCOMPAT_OP_POLARITIES),$(OP_ACCESSORS)) +INCOMPAT=$(call cross,--,lq-list,$(LQ_LIST_INCOMPAT_OPS)) +define filterFds +$(filter-out $(INCOMPAT),$(1)) +endef + + +CORES_FULL=$(call cross,--,$(FXS),$(OPS)) # lq-tailq--stack-inslast-allhead +CORES=$(call filterFds,$(CORES_FULL)) # lq-tailq--stack-inslast-allhead + + +PERFPROGS=$(call cross,--,perfexp,$(CORES)) + +perfprogs : $(PERFPROGS) + +perfexp--% driver--%.o result--%.1csv : FX=$(call proj,--,$@,2) +perfexp--% driver--%.o result--%.1csv : FX_COARSE=$(call proj,-,$(FX),1) +perfexp--% driver--%.o result--%.1csv : OP=$(call proj,--,$@,3) +perfexp--% driver--%.o result--%.1csv : OP_MOVEMENT=$(call proj,-,$(OP),1) +perfexp--% driver--%.o result--%.1csv : OP_POLARITY=$(call proj,-,$(OP),2) +perfexp--% driver--%.o result--%.1csv : OP_ACCESSOR=$(call proj,-,$(OP),3) +perfexp--% driver--%.o result--%.1csv : OP_DEFINES=-DOP_MOVEMENT=$(OP_MOVEMENT) -DOP_POLARITY=$(OP_POLARITY) -DOP_ACCESSOR=$(OP_ACCESSOR) + +perfexp--cfa-% driver--cfa-%.o : COMPILER=$(CFA) $(PERFFLAGS_CFA) +perfexp--lq-% driver--lq-%.o : COMPILER=$(CC) $(PERFFLAGS_CC) +perfexp--cpp-% driver--cpp-%.o : COMPILER=$(CXX) $(PERFFLAGS_CXX) +perfexp--upp-% driver--upp-%.o : COMPILER=$(UXX) $(PERFFLAGS_UXX) +perfexp--% driver--%.o : COMPILER=NO-COMPILER-FOR-$(FX_COARSE) + +perfexp--% : driver--%.o observation.o + $(COMPILER) $^ -o $@ + +driver--%.o : driver.c + $(COMPILER) -c $< $(OP_DEFINES) -include op-$(OP).h -include fx-$(FX).h -o $@ -MMD + + + + +RUN_NUM_REPS=3 +RUN_REP_IDS=$(shell echo {1..$(RUN_NUM_REPS)}) # 1 2 3 +RUN_REP_EXTS=$(call cross3,,run,$(RUN_REP_IDS),.1csv) # run1.1csv run2.1cav run3.1csv + +RESULT1S=$(call cross,.,$(CORES),$(RUN_REP_EXTS)) # lq-tailq--stack-inslast-allhead.run2.1csv + +RESULT1S_SHUFD=$(shell shuf -e $(RESULT1S)) + +%.1csv : CORE=$(basename $(basename $@)) +%.1csv : REP_ID=$(subst .run,,$(suffix $(basename $@))) +%.1csv : REP_TIME=$(shell date '+%F %H:%M:%S') +%.1csv : perfprogs FORCE + ./perfexp--$(CORE) $(RUNARGS) | xargs -n 1 printf '%s,%s,%s\n' "$(REP_TIME)" "$(REP_ID)" | tee $@ + +BATCHTIME=$(shell date '+%F--%H-%M-%S') + +results--$(BATCHTIME).csv : $(RESULT1S_SHUFD) + cat $^ | tee $@ + rm $^ + +results-latest.csv : results--$(BATCHTIME).csv + rm -f $@ + ln -s $< $@ + + + +clean : + rm -f *.o *.d perfexp--* + +# The FORCE business means any target that mentions it is also phony +# https://www.gnu.org/software/make/manual/html_node/Phony-Targets.html says: To always rebuild a pattern rule consider using a “force target” (see [https://www.gnu.org/software/make/manual/html_node/Force-Targets.html]). +.PHONY: all perfprogs results-latest.csv clean +FORCE: + +.PRECIOUS: result--%.1csv driver--%.o perfexp--% %.o + + +-include *.d Index: doc/theses/mike_brooks_MMath/benchmarks/list/_classic.c =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/_classic.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/_classic.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,252 @@ +/* + +$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 +#include + +#if defined IMPL_LQ + + #include + struct S { + volatile int f[64]; + TAILQ_ENTRY(S) x; + }; + TAILQ_HEAD(SL, S); + + +#elif defined IMPL_STL + + #include + struct S { + volatile int f[64]; + }; + +#elif defined IMPL_UPP + + #include + #include + struct S : public uSeqable { + volatile int f[64]; + }; + +#elif defined IMPL_CFA + + #include + 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 + 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 + + +#define Repeat( op ) for ( volatile unsigned int i = 0; 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 ( volatile unsigned int 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 lst; + start = clock(); + for ( volatile unsigned int 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 lst; + start = clock(); + for ( volatile unsigned int 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 ( volatile unsigned int 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 ( volatile unsigned int 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 +} Index: doc/theses/mike_brooks_MMath/benchmarks/list/driver.c =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/driver.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/driver.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,171 @@ +#include +#include +#include +#include + +#include "observation.h" + +typedef struct B_UserItem + BFX_EXTRUSION_DECL(B_UserItem) +{ + BFX_INTRUSION(B_UserItem) + int userdata[64]; +} +B_UserItem; + +BFX_EXTRUSION_FOLLOWUP(B_UserItem) + +#if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__)) + enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckClockFreq = 1000, DefaultExperimentDurOpCount = -1 }; + #define TRACE(tp) +#else + enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckClockFreq = 2, DefaultExperimentDurOpCount = 20 }; + 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; + + +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_rollover_flag = 0; + + 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); + } + + int bobs_getCurrent() { + B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem); + return curUI->userdata[17]; + } + + enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT; + enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY; +) + +int main(int argc, const char *argv[]) { + + + const char * usage_args = "[ExperimentDurSec [CheckClockFreq [NumNodes [ExperimentDurOpCount]]]]"; + const int static_arg_posns = 4; + + unsigned int ExperimentDurSec = DefaultExperimentDurSec; + unsigned int CheckClockFreq = DefaultCheckClockFreq; + unsigned int NumNodes = DefaultNumNodes; + size_t ExperimentDurOpCount = DefaultExperimentDurOpCount; + + switch ((argc < static_arg_posns) ? argc : static_arg_posns) { + case 5: ExperimentDurOpCount = atoi(argv[4]); + case 4: NumNodes = atoi(argv[3]); + case 3: CheckClockFreq = atoi(argv[2]); + case 2: ExperimentDurSec = atoi(argv[1]); + } + + if (ExperimentDurSec == 0 || CheckClockFreq == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 ) { + printf("usage: %s %s\n", argv[0], usage_args); + return -1; + } + + 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))); + + for (int i = 0; i < NumNodes; i++) { + B_UserItem * curUI = & ui[i]; + curUI->userdata[17] = i; + } + + BFX_INIT(B_UserItem, lst); + + 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]. + // 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. + + // 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) + #endif + #ifndef BOP_TEARDOWN + #define BOP_TEARDOWN(lst, ui, iters, i) BOP_REMOVE(lst, ui, iters, i) + #endif + + double elapsed_sec = 0; + clock_t start = clock(); + + while (elapsed_sec <= (double) ExperimentDurSec && bobs_ops_completed < ExperimentDurOpCount) { + for ( int t = 0; t < CheckClockFreq; t += 1 ) { + TRACE('a') + listedItems[0] = + BOP_INIT(lst, ui, listedItems, 0); + TRACE('b') + for ( bobs_prog_inserting = 1; bobs_prog_inserting < NumNodes; bobs_prog_inserting += 1 ) { + TRACE('-') + listedItems[bobs_prog_inserting] = + BOP_INSERT( lst, ui, listedItems, bobs_prog_inserting ); + TRACE('+') + } + TRACE('c') + for ( bobs_prog_removing = 1; bobs_prog_removing < NumNodes; bobs_prog_removing += 1 ) { + TRACE('-') + BOP_REMOVE( lst, ui, listedItems, bobs_prog_removing-1 ); + TRACE('+') + } + TRACE('D') + BOP_TEARDOWN(lst, ui, listedItems, NumNodes-1); + TRACE('d') + + bobs_prog_rollover_flag = 1; + TRACE('e') + bobs_prog_inserting = 0; + bobs_prog_removing = 0; + bobs_ops_completed += NumNodes; + TRACE('f') + bobs_prog_rollover_flag = 0; + TRACE('g') + } + clock_t end = clock(); + elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC); + } + + 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); +} Index: doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-insfirst.txt =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-insfirst.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-insfirst.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,89 @@ +a 0 + 0/2 + 0/2 (list is empty) +b 0 + 0/2 + 0/2 (list is empty) +- 0 + 1/2 + 0/2 | <0> | ... | <0> | ++ 0 + 1/2 + 0/2 | 1 <0> | ... | 1 <0> | +- 0 + 2/2 + 0/2 | <1> 0 | ... | 1 <0> | ++ 0 + 2/2 + 0/2 | 2 <1> 0 | ... 2 1 <0> | +- 0 + 3/2 + 0/2 | <2> 1 0 ... 2 1 <0> | ++ 0 + 3/2 + 0/2 | 3 <2> 1 0 ... 2 1 <0> | +- 0 + 4/2 + 0/2 | <3> 2 1 ... 2 1 <0> | ++ 0 + 4/2 + 0/2 | 4 <3> 2 1 ... 2 1 <0> | +- 0 + 5/2 + 0/2 | <4> 3 2 ... 2 1 <0> | ++ 0 + 5/2 + 0/2 | 5 <4> 3 2 ... 2 1 <0> | +- 0 + 6/2 + 0/2 | <5> 4 3 ... 2 1 <0> | ++ 0 + 6/2 + 0/2 | 6 <5> 4 3 ... 2 1 <0> | +- 0 + 7/2 + 0/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 7/2 + 0/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 8/2 + 0/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 8/2 + 0/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 9/2 + 0/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 0 + 9/2 + 0/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +c 0 + 10/2 + 0/2 | <9> 8 7 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 0 + 10/2 + 1/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 3 2 <1> 0 | ++ 0 + 10/2 + 1/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 3 2 <1> | +- 0 + 10/2 + 2/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 4 3 <2> 1 | ++ 0 + 10/2 + 2/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 4 3 <2> | +- 0 + 10/2 + 3/2 | <9> 8 7 ... 8 7 <6> 5 4 ... 5 4 <3> 2 | ++ 0 + 10/2 + 3/2 | <9> 8 7 ... 8 7 <6> 5 4 ... 5 4 <3> | +- 0 + 10/2 + 4/2 | <9> 8 7 ... 6 5 <4> 3 | ++ 0 + 10/2 + 4/2 | <9> 8 7 ... 6 5 <4> | +- 0 + 10/2 + 5/2 | <9> 8 7 ... 7 6 <5> 4 | ++ 0 + 10/2 + 5/2 | <9> 8 7 ... 7 6 <5> | +- 0 + 10/2 + 6/2 | <9> 8 7 ... 8 7 <6> 5 | ++ 0 + 10/2 + 6/2 | <9> 8 7 ... 8 7 <6> | +- 0 + 10/2 + 7/2 | <9> 8 7 ... 9 8 <7> 6 | ++ 0 + 10/2 + 7/2 | <9> 8 7 ... 9 8 <7> | +- 0 + 10/2 + 8/2 | <9> 8 7 ... | 9 <8> 7 | ++ 0 + 10/2 + 8/2 | <9> 8 | ... | 9 <8> | +- 0 + 10/2 + 9/2 | <9> 8 | ... | <9> 8 | ++ 0 + 10/2 + 9/2 | <9> | ... | <9> | +D 0 + 10/2 + 10/2 (list is empty) +d 0 + 10/2 + 10/2 (list is empty) +e 0 + ? (rolling over) +f 10 + ? (rolling over) +g 10 + 0/2 + 0/2 (list is empty) +a 10 + 0/2 + 0/2 (list is empty) +b 10 + 0/2 + 0/2 (list is empty) +- 10 + 1/2 + 0/2 | <0> | ... | <0> | ++ 10 + 1/2 + 0/2 | 1 <0> | ... | 1 <0> | +- 10 + 2/2 + 0/2 | <1> 0 | ... | 1 <0> | ++ 10 + 2/2 + 0/2 | 2 <1> 0 | ... 2 1 <0> | +- 10 + 3/2 + 0/2 | <2> 1 0 ... 2 1 <0> | ++ 10 + 3/2 + 0/2 | 3 <2> 1 0 ... 2 1 <0> | +- 10 + 4/2 + 0/2 | <3> 2 1 ... 2 1 <0> | ++ 10 + 4/2 + 0/2 | 4 <3> 2 1 ... 2 1 <0> | +- 10 + 5/2 + 0/2 | <4> 3 2 ... 2 1 <0> | ++ 10 + 5/2 + 0/2 | 5 <4> 3 2 ... 2 1 <0> | +- 10 + 6/2 + 0/2 | <5> 4 3 ... 2 1 <0> | ++ 10 + 6/2 + 0/2 | 6 <5> 4 3 ... 2 1 <0> | +- 10 + 7/2 + 0/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 7/2 + 0/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 8/2 + 0/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 8/2 + 0/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 9/2 + 0/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 10 + 9/2 + 0/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +c 10 + 10/2 + 0/2 | <9> 8 7 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 10 + 10/2 + 1/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 3 2 <1> 0 | ++ 10 + 10/2 + 1/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 3 2 <1> | +- 10 + 10/2 + 2/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 4 3 <2> 1 | ++ 10 + 10/2 + 2/2 | <9> 8 7 ... 7 6 <5> 4 3 ... 4 3 <2> | +- 10 + 10/2 + 3/2 | <9> 8 7 ... 8 7 <6> 5 4 ... 5 4 <3> 2 | ++ 10 + 10/2 + 3/2 | <9> 8 7 ... 8 7 <6> 5 4 ... 5 4 <3> | +- 10 + 10/2 + 4/2 | <9> 8 7 ... 6 5 <4> 3 | ++ 10 + 10/2 + 4/2 | <9> 8 7 ... 6 5 <4> | +- 10 + 10/2 + 5/2 | <9> 8 7 ... 7 6 <5> 4 | ++ 10 + 10/2 + 5/2 | <9> 8 7 ... 7 6 <5> | +- 10 + 10/2 + 6/2 | <9> 8 7 ... 8 7 <6> 5 | ++ 10 + 10/2 + 6/2 | <9> 8 7 ... 8 7 <6> | +- 10 + 10/2 + 7/2 | <9> 8 7 ... 9 8 <7> 6 | ++ 10 + 10/2 + 7/2 | <9> 8 7 ... 9 8 <7> | +- 10 + 10/2 + 8/2 | <9> 8 7 ... | 9 <8> 7 | ++ 10 + 10/2 + 8/2 | <9> 8 | ... | 9 <8> | +- 10 + 10/2 + 9/2 | <9> 8 | ... | <9> 8 | ++ 10 + 10/2 + 9/2 | <9> | ... | <9> | +D 10 + 10/2 + 10/2 (list is empty) +d 10 + 10/2 + 10/2 (list is empty) +e 10 + ? (rolling over) +f 20 + ? (rolling over) +g 20 + 0/2 + 0/2 (list is empty) + Index: doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-inslast.txt =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-inslast.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/expect.queue-inslast.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,89 @@ +a 0 + 0/2 + 0/2 (list is empty) +b 0 + 0/2 + 0/2 (list is empty) +- 0 + 1/2 + 0/2 | <0> | ... | <0> | ++ 0 + 1/2 + 0/2 | <0> 1 | ... | <0> 1 | +- 0 + 2/2 + 0/2 | <0> 1 | ... | 0 <1> | ++ 0 + 2/2 + 0/2 | <0> 1 2 ... | 0 <1> 2 | +- 0 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> | ++ 0 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> 3 | +- 0 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> | ++ 0 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 | +- 0 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> | ++ 0 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 | +- 0 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> | ++ 0 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> 6 | +- 0 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | ++ 0 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | +- 0 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | ++ 0 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | +- 0 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | ++ 0 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | +c 0 + 10/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 7 8 <9> | +- 0 + 10/2 + 1/2 | 0 <1> 2 3 ... 3 4 <5> 6 7 ... 7 8 <9> | ++ 0 + 10/2 + 1/2 | <1> 2 3 ... 3 4 <5> 6 7 ... 7 8 <9> | +- 0 + 10/2 + 2/2 | 1 <2> 3 4 ... 3 4 <5> 6 7 ... 7 8 <9> | ++ 0 + 10/2 + 2/2 | <2> 3 4 ... 3 4 <5> 6 7 ... 7 8 <9> | +- 0 + 10/2 + 3/2 | 2 <3> 4 5 ... 4 5 <6> 7 8 ... 7 8 <9> | ++ 0 + 10/2 + 3/2 | <3> 4 5 ... 4 5 <6> 7 8 ... 7 8 <9> | +- 0 + 10/2 + 4/2 | 3 <4> 5 6 ... 7 8 <9> | ++ 0 + 10/2 + 4/2 | <4> 5 6 ... 7 8 <9> | +- 0 + 10/2 + 5/2 | 4 <5> 6 7 ... 7 8 <9> | ++ 0 + 10/2 + 5/2 | <5> 6 7 ... 7 8 <9> | +- 0 + 10/2 + 6/2 | 5 <6> 7 8 ... 7 8 <9> | ++ 0 + 10/2 + 6/2 | <6> 7 8 ... 7 8 <9> | +- 0 + 10/2 + 7/2 | 6 <7> 8 9 ... 7 8 <9> | ++ 0 + 10/2 + 7/2 | <7> 8 9 ... 7 8 <9> | +- 0 + 10/2 + 8/2 | 7 <8> 9 | ... 7 8 <9> | ++ 0 + 10/2 + 8/2 | <8> 9 | ... | 8 <9> | +- 0 + 10/2 + 9/2 | 8 <9> | ... | 8 <9> | ++ 0 + 10/2 + 9/2 | <9> | ... | <9> | +D 0 + 10/2 + 10/2 (list is empty) +d 0 + 10/2 + 10/2 (list is empty) +e 0 + ? (rolling over) +f 10 + ? (rolling over) +g 10 + 0/2 + 0/2 (list is empty) +a 10 + 0/2 + 0/2 (list is empty) +b 10 + 0/2 + 0/2 (list is empty) +- 10 + 1/2 + 0/2 | <0> | ... | <0> | ++ 10 + 1/2 + 0/2 | <0> 1 | ... | <0> 1 | +- 10 + 2/2 + 0/2 | <0> 1 | ... | 0 <1> | ++ 10 + 2/2 + 0/2 | <0> 1 2 ... | 0 <1> 2 | +- 10 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> | ++ 10 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> 3 | +- 10 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> | ++ 10 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 | +- 10 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> | ++ 10 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 | +- 10 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> | ++ 10 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> 6 | +- 10 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | ++ 10 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | +- 10 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | ++ 10 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | +- 10 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | ++ 10 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | +c 10 + 10/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 7 8 <9> | +- 10 + 10/2 + 1/2 | 0 <1> 2 3 ... 3 4 <5> 6 7 ... 7 8 <9> | ++ 10 + 10/2 + 1/2 | <1> 2 3 ... 3 4 <5> 6 7 ... 7 8 <9> | +- 10 + 10/2 + 2/2 | 1 <2> 3 4 ... 3 4 <5> 6 7 ... 7 8 <9> | ++ 10 + 10/2 + 2/2 | <2> 3 4 ... 3 4 <5> 6 7 ... 7 8 <9> | +- 10 + 10/2 + 3/2 | 2 <3> 4 5 ... 4 5 <6> 7 8 ... 7 8 <9> | ++ 10 + 10/2 + 3/2 | <3> 4 5 ... 4 5 <6> 7 8 ... 7 8 <9> | +- 10 + 10/2 + 4/2 | 3 <4> 5 6 ... 7 8 <9> | ++ 10 + 10/2 + 4/2 | <4> 5 6 ... 7 8 <9> | +- 10 + 10/2 + 5/2 | 4 <5> 6 7 ... 7 8 <9> | ++ 10 + 10/2 + 5/2 | <5> 6 7 ... 7 8 <9> | +- 10 + 10/2 + 6/2 | 5 <6> 7 8 ... 7 8 <9> | ++ 10 + 10/2 + 6/2 | <6> 7 8 ... 7 8 <9> | +- 10 + 10/2 + 7/2 | 6 <7> 8 9 ... 7 8 <9> | ++ 10 + 10/2 + 7/2 | <7> 8 9 ... 7 8 <9> | +- 10 + 10/2 + 8/2 | 7 <8> 9 | ... 7 8 <9> | ++ 10 + 10/2 + 8/2 | <8> 9 | ... | 8 <9> | +- 10 + 10/2 + 9/2 | 8 <9> | ... | 8 <9> | ++ 10 + 10/2 + 9/2 | <9> | ... | <9> | +D 10 + 10/2 + 10/2 (list is empty) +d 10 + 10/2 + 10/2 (list is empty) +e 10 + ? (rolling over) +f 20 + ? (rolling over) +g 20 + 0/2 + 0/2 (list is empty) + Index: doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-insfirst.txt =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-insfirst.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-insfirst.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,89 @@ +a 0 + 0/2 + 0/2 (list is empty) +b 0 + 0/2 + 0/2 (list is empty) +- 0 + 1/2 + 0/2 | <0> | ... | <0> | ++ 0 + 1/2 + 0/2 | 1 <0> | ... | 1 <0> | +- 0 + 2/2 + 0/2 | <1> 0 | ... | 1 <0> | ++ 0 + 2/2 + 0/2 | 2 <1> 0 | ... 2 1 <0> | +- 0 + 3/2 + 0/2 | <2> 1 0 ... 2 1 <0> | ++ 0 + 3/2 + 0/2 | 3 <2> 1 0 ... 2 1 <0> | +- 0 + 4/2 + 0/2 | <3> 2 1 ... 2 1 <0> | ++ 0 + 4/2 + 0/2 | 4 <3> 2 1 ... 2 1 <0> | +- 0 + 5/2 + 0/2 | <4> 3 2 ... 2 1 <0> | ++ 0 + 5/2 + 0/2 | 5 <4> 3 2 ... 2 1 <0> | +- 0 + 6/2 + 0/2 | <5> 4 3 ... 2 1 <0> | ++ 0 + 6/2 + 0/2 | 6 <5> 4 3 ... 2 1 <0> | +- 0 + 7/2 + 0/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 7/2 + 0/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 8/2 + 0/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 8/2 + 0/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 9/2 + 0/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 0 + 9/2 + 0/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +c 0 + 10/2 + 0/2 | <9> 8 7 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 0 + 10/2 + 1/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 0 + 10/2 + 1/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 0 + 10/2 + 2/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 10/2 + 2/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 10/2 + 3/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 10/2 + 3/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 0 + 10/2 + 4/2 | 6 <5> 4 3 ... 2 1 <0> | ++ 0 + 10/2 + 4/2 | <5> 4 3 ... 2 1 <0> | +- 0 + 10/2 + 5/2 | 5 <4> 3 2 ... 2 1 <0> | ++ 0 + 10/2 + 5/2 | <4> 3 2 ... 2 1 <0> | +- 0 + 10/2 + 6/2 | 4 <3> 2 1 ... 2 1 <0> | ++ 0 + 10/2 + 6/2 | <3> 2 1 ... 2 1 <0> | +- 0 + 10/2 + 7/2 | 3 <2> 1 0 ... 2 1 <0> | ++ 0 + 10/2 + 7/2 | <2> 1 0 ... 2 1 <0> | +- 0 + 10/2 + 8/2 | 2 <1> 0 | ... 2 1 <0> | ++ 0 + 10/2 + 8/2 | <1> 0 | ... | 1 <0> | +- 0 + 10/2 + 9/2 | 1 <0> | ... | 1 <0> | ++ 0 + 10/2 + 9/2 | <0> | ... | <0> | +D 0 + 10/2 + 10/2 (list is empty) +d 0 + 10/2 + 10/2 (list is empty) +e 0 + ? (rolling over) +f 10 + ? (rolling over) +g 10 + 0/2 + 0/2 (list is empty) +a 10 + 0/2 + 0/2 (list is empty) +b 10 + 0/2 + 0/2 (list is empty) +- 10 + 1/2 + 0/2 | <0> | ... | <0> | ++ 10 + 1/2 + 0/2 | 1 <0> | ... | 1 <0> | +- 10 + 2/2 + 0/2 | <1> 0 | ... | 1 <0> | ++ 10 + 2/2 + 0/2 | 2 <1> 0 | ... 2 1 <0> | +- 10 + 3/2 + 0/2 | <2> 1 0 ... 2 1 <0> | ++ 10 + 3/2 + 0/2 | 3 <2> 1 0 ... 2 1 <0> | +- 10 + 4/2 + 0/2 | <3> 2 1 ... 2 1 <0> | ++ 10 + 4/2 + 0/2 | 4 <3> 2 1 ... 2 1 <0> | +- 10 + 5/2 + 0/2 | <4> 3 2 ... 2 1 <0> | ++ 10 + 5/2 + 0/2 | 5 <4> 3 2 ... 2 1 <0> | +- 10 + 6/2 + 0/2 | <5> 4 3 ... 2 1 <0> | ++ 10 + 6/2 + 0/2 | 6 <5> 4 3 ... 2 1 <0> | +- 10 + 7/2 + 0/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 7/2 + 0/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 8/2 + 0/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 8/2 + 0/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 9/2 + 0/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 10 + 9/2 + 0/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +c 10 + 10/2 + 0/2 | <9> 8 7 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 10 + 10/2 + 1/2 | 9 <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | ++ 10 + 10/2 + 1/2 | <8> 7 6 ... 6 5 <4> 3 2 ... 2 1 <0> | +- 10 + 10/2 + 2/2 | 8 <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 10/2 + 2/2 | <7> 6 5 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 10/2 + 3/2 | 7 <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 10/2 + 3/2 | <6> 5 4 ... 5 4 <3> 2 1 ... 2 1 <0> | +- 10 + 10/2 + 4/2 | 6 <5> 4 3 ... 2 1 <0> | ++ 10 + 10/2 + 4/2 | <5> 4 3 ... 2 1 <0> | +- 10 + 10/2 + 5/2 | 5 <4> 3 2 ... 2 1 <0> | ++ 10 + 10/2 + 5/2 | <4> 3 2 ... 2 1 <0> | +- 10 + 10/2 + 6/2 | 4 <3> 2 1 ... 2 1 <0> | ++ 10 + 10/2 + 6/2 | <3> 2 1 ... 2 1 <0> | +- 10 + 10/2 + 7/2 | 3 <2> 1 0 ... 2 1 <0> | ++ 10 + 10/2 + 7/2 | <2> 1 0 ... 2 1 <0> | +- 10 + 10/2 + 8/2 | 2 <1> 0 | ... 2 1 <0> | ++ 10 + 10/2 + 8/2 | <1> 0 | ... | 1 <0> | +- 10 + 10/2 + 9/2 | 1 <0> | ... | 1 <0> | ++ 10 + 10/2 + 9/2 | <0> | ... | <0> | +D 10 + 10/2 + 10/2 (list is empty) +d 10 + 10/2 + 10/2 (list is empty) +e 10 + ? (rolling over) +f 20 + ? (rolling over) +g 20 + 0/2 + 0/2 (list is empty) + Index: doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-inslast.txt =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-inslast.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/expect.stack-inslast.txt (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,89 @@ +a 0 + 0/2 + 0/2 (list is empty) +b 0 + 0/2 + 0/2 (list is empty) +- 0 + 1/2 + 0/2 | <0> | ... | <0> | ++ 0 + 1/2 + 0/2 | <0> 1 | ... | <0> 1 | +- 0 + 2/2 + 0/2 | <0> 1 | ... | 0 <1> | ++ 0 + 2/2 + 0/2 | <0> 1 2 ... | 0 <1> 2 | +- 0 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> | ++ 0 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> 3 | +- 0 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> | ++ 0 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 | +- 0 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> | ++ 0 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 | +- 0 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> | ++ 0 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> 6 | +- 0 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | ++ 0 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | +- 0 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | ++ 0 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | +- 0 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | ++ 0 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | +c 0 + 10/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 7 8 <9> | +- 0 + 10/2 + 1/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | ++ 0 + 10/2 + 1/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | +- 0 + 10/2 + 2/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | ++ 0 + 10/2 + 2/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | +- 0 + 10/2 + 3/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | ++ 0 + 10/2 + 3/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | +- 0 + 10/2 + 4/2 | <0> 1 2 ... 3 4 <5> 6 | ++ 0 + 10/2 + 4/2 | <0> 1 2 ... 3 4 <5> | +- 0 + 10/2 + 5/2 | <0> 1 2 ... 2 3 <4> 5 | ++ 0 + 10/2 + 5/2 | <0> 1 2 ... 2 3 <4> | +- 0 + 10/2 + 6/2 | <0> 1 2 ... 1 2 <3> 4 | ++ 0 + 10/2 + 6/2 | <0> 1 2 ... 1 2 <3> | +- 0 + 10/2 + 7/2 | <0> 1 2 ... 0 1 <2> 3 | ++ 0 + 10/2 + 7/2 | <0> 1 2 ... 0 1 <2> | +- 0 + 10/2 + 8/2 | <0> 1 2 ... | 0 <1> 2 | ++ 0 + 10/2 + 8/2 | <0> 1 | ... | 0 <1> | +- 0 + 10/2 + 9/2 | <0> 1 | ... | <0> 1 | ++ 0 + 10/2 + 9/2 | <0> | ... | <0> | +D 0 + 10/2 + 10/2 (list is empty) +d 0 + 10/2 + 10/2 (list is empty) +e 0 + ? (rolling over) +f 10 + ? (rolling over) +g 10 + 0/2 + 0/2 (list is empty) +a 10 + 0/2 + 0/2 (list is empty) +b 10 + 0/2 + 0/2 (list is empty) +- 10 + 1/2 + 0/2 | <0> | ... | <0> | ++ 10 + 1/2 + 0/2 | <0> 1 | ... | <0> 1 | +- 10 + 2/2 + 0/2 | <0> 1 | ... | 0 <1> | ++ 10 + 2/2 + 0/2 | <0> 1 2 ... | 0 <1> 2 | +- 10 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> | ++ 10 + 3/2 + 0/2 | <0> 1 2 ... 0 1 <2> 3 | +- 10 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> | ++ 10 + 4/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 | +- 10 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> | ++ 10 + 5/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 | +- 10 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> | ++ 10 + 6/2 + 0/2 | <0> 1 2 ... 3 4 <5> 6 | +- 10 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | ++ 10 + 7/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | +- 10 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | ++ 10 + 8/2 + 0/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | +- 10 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | ++ 10 + 9/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | +c 10 + 10/2 + 0/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 7 8 <9> | +- 10 + 10/2 + 1/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> 9 | ++ 10 + 10/2 + 1/2 | <0> 1 2 ... 2 3 <4> 5 6 ... 6 7 <8> | +- 10 + 10/2 + 2/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> 8 | ++ 10 + 10/2 + 2/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 5 6 <7> | +- 10 + 10/2 + 3/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> 7 | ++ 10 + 10/2 + 3/2 | <0> 1 2 ... 1 2 <3> 4 5 ... 4 5 <6> | +- 10 + 10/2 + 4/2 | <0> 1 2 ... 3 4 <5> 6 | ++ 10 + 10/2 + 4/2 | <0> 1 2 ... 3 4 <5> | +- 10 + 10/2 + 5/2 | <0> 1 2 ... 2 3 <4> 5 | ++ 10 + 10/2 + 5/2 | <0> 1 2 ... 2 3 <4> | +- 10 + 10/2 + 6/2 | <0> 1 2 ... 1 2 <3> 4 | ++ 10 + 10/2 + 6/2 | <0> 1 2 ... 1 2 <3> | +- 10 + 10/2 + 7/2 | <0> 1 2 ... 0 1 <2> 3 | ++ 10 + 10/2 + 7/2 | <0> 1 2 ... 0 1 <2> | +- 10 + 10/2 + 8/2 | <0> 1 2 ... | 0 <1> 2 | ++ 10 + 10/2 + 8/2 | <0> 1 | ... | 0 <1> | +- 10 + 10/2 + 9/2 | <0> 1 | ... | <0> 1 | ++ 10 + 10/2 + 9/2 | <0> | ... | <0> | +D 10 + 10/2 + 10/2 (list is empty) +d 10 + 10/2 + 10/2 (list is empty) +e 10 + ? (rolling over) +f 20 + ? (rolling over) +g 20 + 0/2 + 0/2 (list is empty) + Index: doc/theses/mike_brooks_MMath/benchmarks/list/fx-cfa-cfa.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/fx-cfa-cfa.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/fx-cfa-cfa.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,21 @@ +#include + +#define BFX_INTRUSION(S) inline dlink(S); +#define BFX_EXTRUSION_DECL(S) +#define BFX_EXTRUSION_FOLLOWUP(S) P9_EMBEDDED( S, dlink(S) ) +#define BFX_LIST_HEAD_T(S) dlist(S) +#define BFX_LISTED_ELEM_T(S) S* + +#define BFX_INSERT_FIRST(S, lst, item) (insert_first (lst, item), (S*)&(item)) +#define BFX_INSERT_LAST(S, lst, item) (insert_last (lst, item), (S*)&(item)) +#define BFX_INSERT_BEFORE(S, lst, item, refIter) (insert_before(*refIter, item), (S*)&(item)) +#define BFX_INSERT_AFTER(S, lst, item, refIter) (insert_after (*refIter, item), (S*)&(item)) +#define BFX_REMOVE_FIRST(S, lst) remove(lst`first) +#define BFX_REMOVE_LAST(S, lst) remove(lst`last) +#define BFX_REMOVE_HERE(S, lst, refIter) remove(*refIter) +#define BFX_INIT(S, lst) + +#define BFX_GET_AFTER(S, lst, iter) (&(*iter)`next) +#define BFX_GET_BEFORE(S, lst, iter) (&(*iter)`prev) +#define BFX_IS_VALID_POS(S, lst, iter) ((iter)!=NULL) +#define BFX_DEREF_POS(S, lst, iter) (iter) Index: doc/theses/mike_brooks_MMath/benchmarks/list/fx-cpp-stlref.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/fx-cpp-stlref.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/fx-cpp-stlref.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,22 @@ +#include +using namespace std; + +#define BFX_INTRUSION(S) +#define BFX_EXTRUSION_DECL(S) +#define BFX_EXTRUSION_FOLLOWUP(S) +#define BFX_LIST_HEAD_T(S) list +#define BFX_LISTED_ELEM_T(S) list::iterator + +#define BFX_INSERT_FIRST(S, lst, item) (lst.push_front(&item), lst.begin()) +#define BFX_INSERT_LAST(S, lst, item) (lst.push_back(&item), BFX_GET_BEFORE(S, lst, lst.end())) +#define BFX_REMOVE_FIRST(S, lst) lst.pop_front() +#define BFX_REMOVE_LAST(S, lst) lst.pop_back() +#define BFX_INSERT_BEFORE(S, lst, item, refIter) lst.insert(refIter, &item) +#define BFX_INSERT_AFTER(S, lst, item, refIter) lst.insert(BFX_GET_AFTER(S, lst, refIter), &item) +#define BFX_REMOVE_HERE(S, lst, refIter) lst.erase(refIter) +#define BFX_INIT(S, lst) + +#define BFX_GET_AFTER(S, lst, iter) ({ list::iterator answer = (iter); answer++; answer;}) +#define BFX_GET_BEFORE(S, lst, iter) ({ list::iterator answer = (iter); if ((answer) == lst.begin()) { answer = lst.end(); } else { answer--; } answer; }) +#define BFX_IS_VALID_POS(S, lst, iter) ((iter)!=lst.end()) +#define BFX_DEREF_POS(S, lst, iter) (*iter) Index: doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-list.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-list.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-list.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,44 @@ +#include +#include +#include + +#define HEADNAME_(S) S ## Head + +#define BFX_INTRUSION(S) LIST_ENTRY(S) xx; +#define BFX_EXTRUSION_DECL(S) +#define BFX_EXTRUSION_FOLLOWUP(S) LIST_HEAD(HEADNAME_(S), S); +#define BFX_LIST_HEAD_T(S) struct HEADNAME_(S) +#define BFX_LISTED_ELEM_T(S) S* + +#define BFX_INSERT_FIRST(S, lst, item) ({LIST_INSERT_HEAD(&lst, &item, xx); &item;}) +#define BFX_INSERT_LAST(S, lst, item) assert(false&&"unimplemented INSERT_LAST on lq-list") +#define BFX_INSERT_BEFORE(S, lst, item, refIter) ({LIST_INSERT_BEFORE(refIter, &item, xx); &item;}) +#define BFX_INSERT_AFTER(S, lst, item, refIter) ({LIST_INSERT_AFTER(refIter, &item, xx); &item;}) +#define BFX_REMOVE_FIRST(S, lst) LIST_REMOVE( LIST_FIRST( &lst ), xx ) +#define BFX_REMOVE_LAST(S, lst) assert(false&&"unimplemented REMOVE_LAST on lq-list") +#define BFX_REMOVE_HERE(S, lst, refIter) LIST_REMOVE( refIter, xx ) +#define BFX_INIT(S, lst) LIST_INIT(&lst); + +#define BFX_GET_AFTER(S, lst, iter) LIST_NEXT(iter, xx) +#define BFX_GET_BEFORE(S, lst, iter) HACK_UNSUPPORTED_PREV(S, lst, iter, xx) +#define BFX_IS_VALID_POS(S, lst, iter) ((iter)!=NULL) +#define BFX_DEREF_POS(S, lst, iter) (iter) + +#define HACK_UNSUPPORTED_PREV(S, lst, iter, NAME) ({ \ + S * answer = NULL; \ + S ** linkAtMe = (iter)->NAME.le_prev; \ + if ( &(lst) != (BFX_LIST_HEAD_T(S)*)linkAtMe ) { \ + answer = (S*)( (char*)linkAtMe - offsetof(S, NAME) ); \ + } \ + answer; \ +}) + +#if 0 +void bobs_moveNext() { observedItem = ((observedItem)->xx.le_next); } +struct { struct B_UserItem *le_next; struct B_UserItem **le_prev; } xx; +struct { struct B_UserItem *tqe_next; struct B_UserItem * *tqe_prev; } xx; + +void bobs_movePrev() { + observedItem = (*(((struct B_UserItemHead *)((observedItem)->xx.tqe_prev))->tqh_last)); } + +#endif Index: doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-tailq.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-tailq.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/fx-lq-tailq.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,23 @@ +#include + +#define HEADNAME_(S) S ## Head + +#define BFX_INTRUSION(S) TAILQ_ENTRY(S) xx; +#define BFX_EXTRUSION_DECL(S) +#define BFX_EXTRUSION_FOLLOWUP(S) TAILQ_HEAD(HEADNAME_(S), S); +#define BFX_LIST_HEAD_T(S) struct HEADNAME_(S) +#define BFX_LISTED_ELEM_T(S) S* + +#define BFX_INSERT_FIRST(S, lst, item) ({TAILQ_INSERT_HEAD(&lst, &item, xx); &item;}) +#define BFX_INSERT_LAST(S, lst, item) ({TAILQ_INSERT_TAIL(&lst, &item, xx); &item;}) +#define BFX_INSERT_BEFORE(S, lst, item, refIter) ({TAILQ_INSERT_BEFORE(refIter, &item, xx); &item;}) +#define BFX_INSERT_AFTER(S, lst, item, refIter) ({TAILQ_INSERT_AFTER(&lst, refIter, &item, xx); &item;}) +#define BFX_REMOVE_FIRST(S, lst) ({ S * first=TAILQ_FIRST( &lst ); TAILQ_REMOVE( &lst, first, xx ); }) // about two steps: see tailq-bug.c +#define BFX_REMOVE_LAST(S, lst) ({ S * last =TAILQ_LAST ( &lst, HEADNAME_(S) ); TAILQ_REMOVE( &lst, last , xx ); }) +#define BFX_REMOVE_HERE(S, lst, refIter) TAILQ_REMOVE( &lst, refIter, xx ) +#define BFX_INIT(S, lst) TAILQ_INIT(&lst); + +#define BFX_GET_AFTER(S, lst, iter) TAILQ_NEXT(iter, xx) +#define BFX_GET_BEFORE(S, lst, iter) TAILQ_PREV(iter, HEADNAME_(S), xx) +#define BFX_IS_VALID_POS(S, lst, iter) ((iter)!=NULL) +#define BFX_DEREF_POS(S, lst, iter) (iter) Index: doc/theses/mike_brooks_MMath/benchmarks/list/fx-upp-upp.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/fx-upp-upp.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/fx-upp-upp.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,22 @@ +#include +#include + +#define BFX_INTRUSION(S) +#define BFX_EXTRUSION_DECL(S) : public uSeqable +#define BFX_EXTRUSION_FOLLOWUP(S) +#define BFX_LIST_HEAD_T(S) uSequence +#define BFX_LISTED_ELEM_T(S) S* + +#define BFX_INSERT_FIRST(S, lst, item) lst.addHead(&item) +#define BFX_INSERT_LAST(S, lst, item) lst.addTail(&item) +#define BFX_REMOVE_FIRST(S, lst) lst.dropHead() +#define BFX_REMOVE_LAST(S, lst) lst.dropTail() +#define BFX_INSERT_BEFORE(S, lst, item, refIter) lst.insertBef(&item, refIter) +#define BFX_INSERT_AFTER(S, lst, item, refIter) lst.insertAft(refIter, &item) +#define BFX_REMOVE_HERE(S, lst, refIter) lst.remove(refIter) +#define BFX_INIT(S, lst) + +#define BFX_GET_AFTER(S, lst, iter) lst.succ(iter) +#define BFX_GET_BEFORE(S, lst, iter) lst.pred(iter) +#define BFX_IS_VALID_POS(S, lst, iter) ((iter)!=NULL) +#define BFX_DEREF_POS(S, lst, iter) (iter) Index: doc/theses/mike_brooks_MMath/benchmarks/list/observation.c =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/observation.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/observation.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,124 @@ +#include + +#ifdef __needExternC +#error Only compile observation.c (once) in plain C +#endif + +#include +#include + +#include "observation.h" + +static int NumNodes; + +void bobs_init(int NumNodes_) { + // printf("at bobs_init; bobs_ops_completed = %zd\n", bobs_ops_completed); + + // todo: register a signal handler that prints progress info + // note function bobs_XXX in driver.c are untested until that's working + // to be driven as: + // ./a.out & # then, very quickly + // kill -s USR2 $! + + NumNodes = NumNodes_; +} + + +static void printPreds(unsigned int leash) { + if (leash==0) + return; + if (!bobs_hasCurrent()) { + printf(" |"); + return; + } + int userValue = bobs_getCurrent(); + bobs_movePrev(); + printPreds(leash - 1); + printf(" %d", userValue); +} +static void printSuccs(unsigned int leash) { + if (leash==0) + return; + if (!bobs_hasCurrent()) { + printf(" |"); + return; + } + int userValue = bobs_getCurrent(); + printf(" %d", userValue); + bobs_moveNext(); + printSuccs(leash - 1); +} +static void explore(int here) { + bobs_seek(here); + if (!bobs_hasCurrent()) { + printf(" "); + return; + } + bobs_movePrev(); + printPreds(2); + + bobs_seek(here); + int userValue = bobs_getCurrent(); + printf(" <%d>", userValue); + + bobs_moveNext(); + printSuccs(2); +} +static void exploreRange(int validFrom, int validTo) { + int gapsize = validTo - validFrom; + int midpoint = (validTo + validFrom) / 2; + + int listFirstmost, listLastmost; + switch(bobs_op_polarity) { + case insfirst: + listFirstmost = validTo; + listLastmost = validFrom; + break; + case inslast: + listFirstmost = validFrom; + listLastmost = validTo; + break; + default: + assert(0 && "unsupported bobs_op_movement value"); + } + + explore(listFirstmost); + printf(" ..."); + if (gapsize > 5) { + explore(midpoint); + printf(" ..."); + } + explore(listLastmost); +} + +void bobs_report(void) { + if (bobs_prog_rollover_flag) { + printf("%8zd + ? (rolling over)\n", bobs_ops_completed); + } else { + printf("%8zd + %6d/2 + %6d/2", bobs_ops_completed, bobs_prog_inserting, bobs_prog_removing); + + int validFrom, validTo; + switch(bobs_op_movement) { + case stack: + validFrom = 0; + validTo = MIN((signed)bobs_prog_inserting-1, (signed)NumNodes - (signed)bobs_prog_removing - 1); + break; + case queue: + validFrom = (signed)bobs_prog_removing; + validTo = (signed)bobs_prog_inserting-1; + break; + default: + assert(0 && "unsupported bobs_op_movement value"); + } + + printf(" "); + + if (validTo < validFrom) { + printf(" (list is empty)"); + } else { + exploreRange(validFrom, validTo); + } + + printf("\n"); + } +} Index: doc/theses/mike_brooks_MMath/benchmarks/list/observation.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/observation.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/observation.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,25 @@ +#include "proglang.h" + +MAYBE_EXTERN_C ( + + // driver.c defines + + extern enum bobs_op_movement_t { stack, queue } bobs_op_movement; + extern enum bobs_op_polarity_t { insfirst, inslast } bobs_op_polarity; + + void bobs_seek(unsigned int); + void bobs_moveNext(); + void bobs_movePrev(); + int bobs_hasCurrent(); + int bobs_getCurrent(); + + extern volatile size_t bobs_ops_completed; + extern volatile unsigned int bobs_prog_inserting; + extern volatile unsigned int bobs_prog_removing; + extern volatile unsigned int bobs_prog_rollover_flag; + + // observation.c defines + + void bobs_init(int NumNodes); + void bobs_report(void); +) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-allhead.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,6 @@ +// queue: inserts and removes happen at opposite ends +// insfirst: elements flow from "first," "head" or "front", to "last", "tail" or "back" +// allhead: inserts and removes happen via the api-provided "last"/"tail"/"back"/"first"/"tail"/"front" + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-inselem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// queue: inserts and removes happen at opposite ends +// insfirst: elements flow from "first," "head" or "front", to "last", "tail" or "back" +// inselem: inserts happen via an element-level operation and removes happen via the api-provided "last"/"tail"/"back" + +#define BOP_INIT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_BEFORE(B_UserItem, lst, ui[i], iters[i-1]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-remelem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-insfirst-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// queue: inserts and removes happen at opposite ends +// insfirst: elements flow from "first," "head" or "front", to "last", "tail" or "back" +// remelem: removes happen via an element-level operation and inserts happen via the api-provided "first"/"head"/"front" + +#define BOP_TEARDOWN(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_HERE(B_UserItem, lst, iters[i]) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-allhead.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,6 @@ +// queue: inserts and removes happen at opposite ends +// inslast: elements flow from "last", "tail" or "back", to "first," "head" or "front" +// allhead: inserts and removes happen via the api-provided "last"/"tail"/"back"/"first"/"tail"/"front" + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-inselem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// queue: inserts and removes happen at opposite ends +// inslast: elements flow from "last", "tail" or "back", to "first," "head" or "front" +// inselem: inserts happen via an element-level operation and removes happen via the api-provided "first"/"tail"/"front" + +#define BOP_INIT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_AFTER(B_UserItem, lst, ui[i], iters[i-1]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-remelem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-queue-inslast-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// queue: inserts and removes happen at opposite ends +// inslast: elements flow from "last", "tail" or "back", to "first," "head" or "front" +// remelem: removes happen via an element-level operation and inserts happen via the api-provided "last"/"tail"/"back" + +#define BOP_TEARDOWN(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_HERE(B_UserItem, lst, iters[i]) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-allhead.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,6 @@ +// stack: inserts and removes happen at the same end +// insfirst: stack's action happens at the end called "first", "head" or "front" +// allhead: inserts and removes happen via the api-provided "first"/"head"/"front" + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-inselem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// stack: inserts and removes happen at the same end +// insfirst: stack's action happens at the end called "first", "head" or "front" +// inselem: inserts happen via an element-level operation and removes happen via the api-provided "first"/"head"/"front" + +#define BOP_INIT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_BEFORE(B_UserItem, lst, ui[i], iters[i-1]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-remelem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-insfirst-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// stack: inserts and removes happen at the same end +// insfirst: stack's action happens at the end called "first", "head" or "front" +// remelem: removes happen via an element-level operation and inserts happen via the api-provided "first"/"head"/"front" + +#define BOP_TEARDOWN(lst, ui, iters, i) BFX_REMOVE_FIRST(B_UserItem, lst) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_FIRST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_HERE(B_UserItem, lst, iters[NumNodes-(i)-1]) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-allhead.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-allhead.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,6 @@ +// stack: inserts and removes happen at the same end +// inslast: stack's action happens at the end called "last", "tail" or "back" +// allhead: inserts and removes happen via the api-provided "last"/"tail"/"back" + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-inselem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-inselem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// stack: inserts and removes happen at the same end +// inslast: stack's action happens at the end called "last", "tail" or "back" +// inselem: inserts happen via an element-level operation and removes happen via the api-provided "last"/"tail"/"back" + +#define BOP_INIT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_AFTER(B_UserItem, lst, ui[i], iters[i-1]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) Index: doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-remelem.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/op-stack-inslast-remelem.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,8 @@ +// stack: inserts and removes happen at the same end +// inslast: stack's action happens at the end called "last", "tail" or "back" +// remelem: removes happen via an element-level operation and inserts happen via the api-provided "last"/"tail"/"back" + +#define BOP_TEARDOWN(lst, ui, iters, i) BFX_REMOVE_LAST(B_UserItem, lst) + +#define BOP_INSERT(lst, ui, iters, i) BFX_INSERT_LAST(B_UserItem, lst, ui[i]) +#define BOP_REMOVE(lst, ui, iters, i) BFX_REMOVE_HERE(B_UserItem, lst, iters[NumNodes-(i)-1]) Index: doc/theses/mike_brooks_MMath/benchmarks/list/proglang.h =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/proglang.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/proglang.h (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,13 @@ +#ifdef __cforall +#define __needExternC +#endif + +#ifdef __cplusplus +#define __needExternC +#endif + +#ifdef __needExternC +#define MAYBE_EXTERN_C(...) extern "C" { __VA_ARGS__ } +#else +#define MAYBE_EXTERN_C(...) __VA_ARGS__ +#endif Index: doc/theses/mike_brooks_MMath/benchmarks/list/results-baseline.csv =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/results-baseline.csv (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/results-baseline.csv (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,51 @@ +2023-03-31 18:23:19,1,./perfexp--cfa-cfa--stack-inslast-allhead,48000000,1.013766,21.120125 +2023-03-31 18:23:20,1,./perfexp--cpp-stlref--stack-inslast-remelem,17000000,1.026633,60.390176 +2023-03-31 18:23:21,1,./perfexp--cfa-cfa--queue-insfirst-inselem,40000000,1.016458,25.411450 +2023-03-31 18:23:22,1,./perfexp--cpp-stlref--queue-inslast-allhead,19000000,1.024882,53.941158 +2023-03-31 18:23:23,1,./perfexp--lq-tailq--queue-inslast-inselem,39000000,1.020426,26.164769 +2023-03-31 18:23:24,1,./perfexp--upp-upp--stack-inslast-remelem,48000000,1.006786,20.974708 +2023-03-31 18:23:25,1,./perfexp--lq-list--stack-insfirst-allhead,41000000,1.018723,24.846902 +2023-03-31 18:23:26,1,./perfexp--cfa-cfa--queue-inslast-remelem,54000000,1.006503,18.638944 +2023-03-31 18:23:27,1,./perfexp--cpp-stlref--queue-inslast-remelem,18000000,1.025963,56.997944 +2023-03-31 18:23:28,1,./perfexp--lq-tailq--stack-insfirst-allhead,36000000,1.017789,28.271917 +2023-03-31 18:23:29,1,./perfexp--lq-list--stack-insfirst-remelem,38000000,1.026793,27.020868 +2023-03-31 18:23:30,1,./perfexp--upp-upp--stack-inslast-inselem,39000000,1.012432,25.959795 +2023-03-31 18:23:32,1,./perfexp--cfa-cfa--queue-inslast-inselem,41000000,1.019139,24.857049 +2023-03-31 18:23:33,1,./perfexp--lq-list--stack-insfirst-inselem,36000000,1.023135,28.420417 +2023-03-31 18:23:34,1,./perfexp--cpp-stlref--stack-insfirst-inselem,18000000,1.037970,57.665000 +2023-03-31 18:23:35,1,./perfexp--cpp-stlref--queue-insfirst-allhead,18000000,1.034939,57.496611 +2023-03-31 18:23:36,1,./perfexp--upp-upp--stack-insfirst-inselem,42000000,1.015293,24.173643 +2023-03-31 18:23:37,1,./perfexp--lq-tailq--queue-insfirst-allhead,39000000,1.009513,25.884949 +2023-03-31 18:23:38,1,./perfexp--lq-tailq--queue-inslast-allhead,34000000,1.007878,29.643471 +2023-03-31 18:23:39,1,./perfexp--cfa-cfa--queue-insfirst-allhead,47000000,1.013482,21.563447 +2023-03-31 18:23:40,1,./perfexp--upp-upp--stack-insfirst-allhead,41000000,1.002117,24.441878 +2023-03-31 18:23:41,1,./perfexp--cfa-cfa--queue-insfirst-remelem,57000000,1.016380,17.831228 +2023-03-31 18:23:42,1,./perfexp--cfa-cfa--stack-insfirst-inselem,42000000,1.015385,24.175833 +2023-03-31 18:23:43,1,./perfexp--cpp-stlref--queue-inslast-inselem,19000000,1.009252,53.118526 +2023-03-31 18:23:44,1,./perfexp--cpp-stlref--stack-insfirst-remelem,17000000,1.000099,58.829353 +2023-03-31 18:23:45,1,./perfexp--upp-upp--queue-insfirst-allhead,38000000,1.008441,26.537921 +2023-03-31 18:23:46,1,./perfexp--cfa-cfa--stack-inslast-remelem,56000000,1.005325,17.952232 +2023-03-31 18:23:47,1,./perfexp--lq-tailq--stack-inslast-allhead,37000000,1.008959,27.269162 +2023-03-31 18:23:48,1,./perfexp--cpp-stlref--queue-insfirst-inselem,20000000,1.033535,51.676750 +2023-03-31 18:23:49,1,./perfexp--cpp-stlref--stack-insfirst-allhead,19000000,1.050044,55.265474 +2023-03-31 18:23:50,1,./perfexp--lq-tailq--queue-insfirst-inselem,37000000,1.004851,27.158135 +2023-03-31 18:23:51,1,./perfexp--lq-tailq--stack-insfirst-inselem,42000000,1.018301,24.245262 +2023-03-31 18:23:52,1,./perfexp--upp-upp--queue-inslast-remelem,37000000,1.020093,27.570081 +2023-03-31 18:23:53,1,./perfexp--upp-upp--queue-inslast-inselem,38000000,1.015943,26.735342 +2023-03-31 18:23:54,1,./perfexp--cpp-stlref--queue-insfirst-remelem,18000000,1.008713,56.039611 +2023-03-31 18:23:55,1,./perfexp--cpp-stlref--stack-inslast-inselem,18000000,1.009262,56.070111 +2023-03-31 18:23:56,1,./perfexp--cfa-cfa--queue-inslast-allhead,47000000,1.009578,21.480383 +2023-03-31 18:23:57,1,./perfexp--cfa-cfa--stack-inslast-inselem,41000000,1.016502,24.792732 +2023-03-31 18:23:58,1,./perfexp--lq-tailq--queue-insfirst-remelem,40000000,1.021677,25.541925 +2023-03-31 18:23:59,1,./perfexp--cfa-cfa--stack-insfirst-remelem,56000000,1.014010,18.107321 +2023-03-31 18:24:00,1,./perfexp--lq-tailq--stack-inslast-inselem,42000000,1.006019,23.952833 +2023-03-31 18:24:01,1,./perfexp--upp-upp--stack-inslast-allhead,47000000,1.019206,21.685234 +2023-03-31 18:24:02,1,./perfexp--lq-tailq--stack-inslast-remelem,40000000,1.014028,25.350700 +2023-03-31 18:24:04,1,./perfexp--lq-tailq--queue-inslast-remelem,34000000,1.006046,29.589588 +2023-03-31 18:24:05,1,./perfexp--lq-tailq--stack-insfirst-remelem,40000000,1.014269,25.356725 +2023-03-31 18:24:06,1,./perfexp--cfa-cfa--stack-insfirst-allhead,47000000,1.008706,21.461830 +2023-03-31 18:24:07,1,./perfexp--upp-upp--queue-insfirst-inselem,33000000,1.012105,30.669848 +2023-03-31 18:24:08,1,./perfexp--upp-upp--stack-insfirst-remelem,38000000,1.007728,26.519158 +2023-03-31 18:24:09,1,./perfexp--cpp-stlref--stack-inslast-allhead,18000000,1.010964,56.164667 +2023-03-31 18:24:10,1,./perfexp--upp-upp--queue-inslast-allhead,52000000,1.011266,19.447423 +2023-03-31 18:24:11,1,./perfexp--upp-upp--queue-insfirst-remelem,41000000,1.006773,24.555439 Index: doc/theses/mike_brooks_MMath/benchmarks/list/tailq-bug.c =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/tailq-bug.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/tailq-bug.c (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,118 @@ +/* + +There is a right way and a wrong way to remove the last element of a tailq. +The right way does it in two steps. +This fact is undocumented anywhere and never asked on SO. + +When the TAILQ_REMOVE is in an intermediate state of removal, it proceeds with a subsequent step starting from its "remove this guy" argument. +So "remove this guy" must be fully evaluated to a concrete node (call by value). +If you try to do it with nested expressions, this subsequent call of "from which guy again?" performs an evaluation of TAILQ_LAST in the intermediate state (call by name), which gives the wrong value. +Everything then gets trashed. + +The actual/expected annotations are for the symptom that led me to the test. + actual means without -DFIXIT + expected obtains with -DFIXIT +Other outputs are unannotated, but we can easily see things getting trashed in them too. + +*/ + + +#include +#include + +#ifdef FIXIT +#define MY_TAILQ_REMOVE_LAST(headp, TYPE, HEADNAME, NAME) ({\ + struct TYPE * last = TAILQ_LAST(headp, HEADNAME); \ + TAILQ_REMOVE(headp, last, NAME); \ +}) +#else +#define MY_TAILQ_REMOVE_LAST(headp, TYPE, HEADNAME, NAME) \ + TAILQ_REMOVE(headp, TAILQ_LAST(headp, HEADNAME), NAME) +#endif + +int main () { + +struct req { + int pri, rqr; + TAILQ_ENTRY(req) x; +}; + +TAILQ_HEAD(reql, req); + +struct reql reqs = TAILQ_HEAD_INITIALIZER(reqs); +TAILQ_INIT(&reqs); + +struct req + r1 = {1, 42}, + r2 = {2, 42}; + +struct req *cur; +/* + (Irrelevant to the bug, not a problem:) + You can't navigate next/prev for unlisted elements (it crashes). + So I only show them for listed ones. +*/ + +printf("r1@%p, r2@%p\n", &r1, &r2); + +printf("reqs.first = %p\n", TAILQ_FIRST(&reqs)); +printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql)); +printf("reqs ="); +TAILQ_FOREACH(cur, &reqs, x) + printf(" %p", cur); +printf("\n"); + + +TAILQ_INSERT_TAIL(&reqs, &r1, x); + +printf("-\n"); +printf("r1.next=%p\n", TAILQ_NEXT(&r1, x)); // a&e: (nil) is last +printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x)); // a&e: (nil) is first + +printf("reqs.first = %p\n", TAILQ_FIRST(&reqs)); +printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql)); +printf("reqs ="); +TAILQ_FOREACH(cur, &reqs, x) + printf(" %p", cur); +printf("\n"); + +TAILQ_INSERT_TAIL(&reqs, &r2, x); + +printf("-\n"); +printf("r1.next=%p\n", TAILQ_NEXT(&r1, x)); // a&e: @r2 has succ +printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x)); // a&e: (nil) is first +printf("r2.next=%p\n", TAILQ_NEXT(&r2, x)); // a&e: (nil) is last +printf("r2.prev=%p\n", TAILQ_PREV(&r2, reql, x)); // a&e: @r1 has pred + +printf("reqs.first = %p\n", TAILQ_FIRST(&reqs)); +printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql)); +printf("reqs ="); +TAILQ_FOREACH(cur, &reqs, x) + printf(" %p", cur); +printf("\n"); + +MY_TAILQ_REMOVE_LAST(&reqs, req, reql, x); + +printf("-\n"); +printf("r1.next=%p\n", TAILQ_NEXT(&r1, x)); // e: (nil) is last; a: @r2 +printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x)); // e: (nil) is first; a: @r2 + +printf("reqs.first = %p\n", TAILQ_FIRST(&reqs)); +printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql)); +printf("reqs ="); +TAILQ_FOREACH(cur, &reqs, x) + printf(" %p", cur); +printf("\n"); + +MY_TAILQ_REMOVE_LAST(&reqs, req, reql, x); + +printf("-\n"); + +printf("reqs.first = %p\n", TAILQ_FIRST(&reqs)); +printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql)); +printf("reqs ="); // e: (none); a: @ +TAILQ_FOREACH(cur, &reqs, x) + printf(" %p", cur); +printf("\n"); + +} Index: doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness-regenerate-expected.sh =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness-regenerate-expected.sh (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness-regenerate-expected.sh (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,24 @@ +echo Should you make? Clean? + +# example uses: +# ./test-correctness-regenerate-expected +# ./test-correctness-regenerate-expected -overwrite +# ./test-correctness-regenerate-expected cfa-cfa allhead +# ./test-correctness-regenerate-expected -overwrite cfa-cfa allhead + +if [[ "$1" == "-overwrite" ]] +then + suffix='' + oracle_fx=${2:-cfa-cfa} + oracle_accessor=${3:-allhead} +else + suffix='.proposed' + oracle_fx=${1:-cfa-cfa} + oracle_accessor=${2:-allhead} +fi + +for casegroup in stack-insfirst stack-inslast queue-insfirst queue-inslast +do + program=perfexp--$oracle_fx--$casegroup-$oracle_accessor + ./$program | sed 's|^\./perfexp--.*||g' > expect.$casegroup$suffix.txt +done Index: doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness.sh =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness.sh (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) +++ doc/theses/mike_brooks_MMath/benchmarks/list/test-correctness.sh (revision 0b66ef942dcd38c37734175ce587f2abf585bbe0) @@ -0,0 +1,20 @@ +echo Should you make clean? + +# Accept by eyeball when all you see is +# - (irrelevant) performance numbers being reported and +# - any u++ "allocated but not freed" warnings that you can live with. +# Reject when you see lines of trace messages, like what's in the "expect" files. + +function test1 { + echo + diff "<($1)" $2 + diff <($1) $2 +} +export -f test1 + +make perfprogs -j 8 CFA=$cfa MODE=correctness + +for casegroup in stack-insfirst stack-inslast queue-insfirst queue-inslast +do + export casegroup + ls perfexp--*$casegroup* | xargs -n 1 -I {} bash -c 'test1 "./$@" expect.$casegroup.txt' _ {} +done