Index: doc/theses/mike_brooks_MMath/.gitignore =================================================================== --- doc/theses/mike_brooks_MMath/.gitignore (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/.gitignore (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,3 @@ +!Makefile +build +thesis.pdf Index: doc/theses/mike_brooks_MMath/Makefile =================================================================== --- doc/theses/mike_brooks_MMath/Makefile (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/Makefile (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,72 @@ +## Define the configuration variables. + +MODULES = \ + string + +Build ?= build +Macros ?= ../../LaTeXmacros +PLBib ?= ../../bibliography + +MODULE_PHONIES = ${addsuffix .module,$(MODULES)} +MODULE_BUILDDIRS = ${addprefix $(Build)/,$(MODULES)} + +TeXLIB = .:${Macros}:${Build}:${MODULE_BUILDDIRS}:${PLBib}: +LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} +pdfLaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && pdflatex -halt-on-error -output-directory=${Build} +BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex + +MAKEFLAGS = --no-print-directory # --silent + + + +## Define the documents that need to be made. +all: thesis.pdf +thesis.pdf: ${MODULE_PHONIES} thesis.tex glossary.tex $(Macros)/common.tex $(Macros)/common.sty # local.bib + +DOCUMENT = thesis.pdf +BASE = ${basename ${DOCUMENT}} + +# Directives # + +.NOTPARALLEL: # cannot make in parallel + +.PHONY : all clean %.module # not file names + +all : ${DOCUMENT} + +clean : + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} + +# File Dependencies # + +# %.pdf : build/%.ps | ${Build} +# ps2pdf $< + +# build/%.ps : build/%.dvi | ${Build} +# dvips $< -o $@ + +# build/%.dvi : %.tex Makefile | ${Build} +# # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. +# if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi +# # Must have *.aux file containing citations for bibtex +# if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} $< ; fi +# -${BibTeX} ${basename $@} +# # Some citations reference others so run again to resolve these citations +# ${LaTeX} $< +# -${BibTeX} ${basename $@} +# # Make index from *.aux entries and input index at end of document +# -makeglossaries -q -s ${basename $@}.ist ${basename $@} +# # Make index from *.aux entries and input index at end of document +# -makeindex ${basename $@}.idx +# # Run again to finish citations +# ${LaTeX} $< + +%.pdf : %.tex | ${Build} + ${pdfLaTeX} $< + cp ${Build}/$@ $@ + +${Build}: + mkdir -p ${Build} + +%.module: content/% + $(MAKE) -C $< BuildBase=../../$(Build) Index: doc/theses/mike_brooks_MMath/content/array/features/array.hfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/features/array.hfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/features/array.hfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,127 @@ + + +// a type whose size is n +#define Z(n) char[n] + +// the inverse of Z(-) +#define z(Zn) sizeof(Zn) + +// if you're expecting a Z(n), say so, by asking for a ztype, instead of dtype or otype +#define ztype(Zn) Zn & | sized(Zn) + +forall( T & ) struct tag {}; +#define ttag(T) ((tag(T)){}) +#define ztag(n) ttag(Z(n)) + + +// +// Single-dim array sruct (with explicit packing and atom) +// + +forall( ztype(Zn), ztype(S), Timmed &, Tbase & ) { + struct arpk { + S strides[z(Zn)]; + }; + + Timmed & ?[?]( arpk(Zn, S, Timmed, Tbase) & a, ptrdiff_t i ) { + return (Timmed &) a.strides[i]; + } + + // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa) + void ?{}( arpk(Zn, S, Timmed, Tbase) & this ) { + void ?{}( S (&inner)[z(Zn)] ) {} + ?{}(this.strides); + } + void ^?{}( arpk(Zn, S, Timmed, Tbase) & this ) { + void ^?{}( S (&inner)[z(Zn)] ) {} + ^?{}(this.strides); + } +} + +// +// Sugar for declaring array structure instances +// + +forall( Te ) +Te mkar_( tag(Te) ) {} + +forall( ztype(Zn), ZTags ... , Trslt &, Tatom & | { Trslt mkar_( tag(Tatom), ZTags ); } ) +arpk(Zn, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(Zn), ZTags ) {} + +// stolen from https://stackoverflow.com/questions/1872220/is-it-possible-to-iterate-over-arguments-in-variadic-macros + + // Make a FOREACH macro + #define FE_0(WHAT) + #define FE_1(WHAT, X) WHAT(X) + #define FE_2(WHAT, X, ...) WHAT(X)FE_1(WHAT, __VA_ARGS__) + #define FE_3(WHAT, X, ...) WHAT(X)FE_2(WHAT, __VA_ARGS__) + #define FE_4(WHAT, X, ...) WHAT(X)FE_3(WHAT, __VA_ARGS__) + #define FE_5(WHAT, X, ...) WHAT(X)FE_4(WHAT, __VA_ARGS__) + //... repeat as needed + + #define GET_MACRO(_0,_1,_2,_3,_4,_5,NAME,...) NAME + #define FOR_EACH(action,...) \ + GET_MACRO(_0,__VA_ARGS__,FE_5,FE_4,FE_3,FE_2,FE_1,FE_0)(action,__VA_ARGS__) + +#define COMMA_ttag(X) , ttag(X) +#define array( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ttag, __VA_ARGS__ ) ) ) + +#define COMMA_ztag(X) , ztag(X) +#define zarray( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ztag, __VA_ARGS__ ) ) ) + +// +// Sugar for multidimensional indexing +// + +// Core -[[-,-,-]] operator + +// Desired form, one definition with recursion on IxBC (worked until Jan 2021, see trac #__TODO__) +// forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) +// TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { +// return this[ab][bc]; +// } + +// Workaround form. Listing all possibilities up to 4 dims. +forall( TA &, TB &, IxAB | { TB & ?[?]( TA &, IxAB ); } + , TC &, IxBC | { TC & ?[?]( TB &, IxBC ); } ) +TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { + return this[ab][bc]; +} +// forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) +// TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { +// return this[ab][bc]; +// } + +// Adapters for "indexed by ptrdiff_t" implies "indexed by [this other integral type]" +// Work around restriction that assertions underlying -[[-,-,-]] must match excatly +forall( C &, E & | { E & ?[?]( C &, ptrdiff_t ); } ) { + + // Targeted to support: for( i; z(N) ) ... a[[ ..., i, ... ]] + E & ?[?]( C & this, size_t i ) { + return this[ (ptrdiff_t) i ]; + } + + // Targeted to support: for( i; 5 ) ... a[[ ..., i, ... ]] + E & ?[?]( C & this, int i ) { + return this[ (ptrdiff_t) i ]; + } +} + +// +// Rotation +// + +// Base +forall( ztype(Zq), ztype(Sq), Tbase & ) +tag(arpk(Zq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(Tbase) ) {} + +// Rec +forall( ztype(Zq), ztype(Sq), ztype(Z), ztype(S), recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(recq) ); } ) +tag(arpk(Z, S, recr, Tbase)) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(arpk(Z, S, recq, Tbase)) ) {} + +// Wrapper +struct all_t {} all; +forall( ztype(Z), ztype(S), Te &, result &, Tbase & | { tag(result) enq_( tag(Tbase), tag(Z), tag(S), tag(Te) ); } ) +result & ?[?]( arpk(Z, S, Te, Tbase) & this, all_t ) { + return (result&) this; +} Index: doc/theses/mike_brooks_MMath/content/array/features/hello-accordion.cfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/features/hello-accordion.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/features/hello-accordion.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,120 @@ +#include "stdlib.hfa" +#include "array.hfa" + + + + + + + + + + + + + + + + + +forall( ztype(Nclients), ztype(Ncosts) ) +struct request { + unsigned int requestor_id; + array( unsigned int, Nclients ) impacted_client_ids; + array( float, Ncosts ) cost_contribs; + float total_cost; +}; + + +// TODO: understand (fix?) why these are needed (autogen seems to be failing ... is typeof as struct member nayok?) + +forall( ztype(Nclients), ztype(Ncosts) ) +void ?{}( request(Nclients, Ncosts) & this ) {} + +forall( ztype(Nclients), ztype(Ncosts) ) +void ^?{}( request(Nclients, Ncosts) & this ) {} + + + + + + + + + + + + + + +forall( ztype(Nclients), ztype(Ncosts) ) +void summarize( request(Nclients, Ncosts) & r ) { + r.total_cost = 0; + for( i; z(Ncosts) ) + r.total_cost += r.cost_contribs[i]; + // say the cost is per-client, to make output vary + r.total_cost *= z(Nclients); +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +int main( int argc, char ** argv ) { + + + +const int ncl = atoi(argv[1]); +const int nco = 2; + +request( Z(ncl), Z(nco) ) r; +r.cost_contribs[0] = 100; +r.cost_contribs[1] = 0.1; + +summarize(r); +printf("Total cost: %.1f\n", r.total_cost); + +/* +./a.out 5 +Total cost: 500.5 +./a.out 6 +Total cost: 600.6 +*/ + + + + +} Index: doc/theses/mike_brooks_MMath/content/array/features/hello-array.cfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/features/hello-array.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/features/hello-array.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,204 @@ + +#include +#include + +extern "C" { + int atoi(const char *str); +} + + +#include "stdlib.hfa" +#include "array.hfa" // learned has to come afer stdlib, which uses the word tag + + + + + + + + + + + + + + + + +// Usage: +// ./a.out 5 +// example does an unchecked reference to argv[1] + + + + + + + + + + + + + + + + + + + +forall( ztype( N ) ) +array(bool, N) & f( array(float, N) & a, array(float, N) & b ) { + array(bool, N) & ret = *alloc(); + for( i; z(N) ) { + float fracdiff = 2 * abs( a[i] - b[i] ) + / ( abs( a[i] ) + abs( b[i] ) ); + ret[i] = fracdiff < 0.005; + } + return ret; +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +// TODO: standardize argv + +int main( int argc, char ** argv ) { + int n = atoi(argv[1]); + array(float, Z(n)) a, b; + for (i; n) { + a[i] = 3.14 / (i+1); + b[i] = a[i] + 0.005 ; + } + array(bool, Z(n)) & answer = f( a, b ); + printf("answer:"); + for (i; n) + printf(" %d", answer[i]); + printf("\n"); + free( & answer ); +} +/* +$ ./a.out 5 +answer: 1 1 1 0 0 +$ ./a.out 7 +answer: 1 1 1 0 0 0 0 +*/ + + + + + + + + + + + + + + + + +forall( ztype(M), ztype(N) ) +void not_so_bad(array(float, M) &a, array(float, N) &b ) { + f( a, a ); + f( b, b ); +} + + + + + + + +#ifdef SHOWERR1 + +forall( ztype(M), ztype(N) ) +void bad( array(float, M) &a, array(float, N) &b ) { + f( a, a ); // ok + f( b, b ); // ok + f( a, b ); // error +} + +#endif + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +forall( ztype(M), ztype(N) ) +void bad_fixed( array(float, M) &a, array(float, N) &b ) { + + + if ( z(M) == z(N) ) { + f( a, ( array(float, M) & ) b ); // fixed + } + +} Index: doc/theses/mike_brooks_MMath/content/array/features/sec.tex =================================================================== --- doc/theses/mike_brooks_MMath/content/array/features/sec.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/features/sec.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,58 @@ + + +The present work adds a type @array@ to the \CFA standard library. + +This array's length is statically governed and dynamically valued. This static governance achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference). In present state, this work is a runtime libray accessed through a system of macros, while section [TODO: discuss C conexistence] discusses a path for the new array type to be accessed directly by \CFA's array syntax, replacing the lifted C array that this syntax currently exposes. + +This section presents motivating examples of the new array type's usage, and follows up with definitions of the notations that appear. + +The core of the new array governance is tracking all array lengths in the type system. Dynamically valued lengths are represented using type variables. The stratification of type variables preceding object declarations makes a length referenceable everywhere that it is needed. For example, a declaration can share one length, @N@, among a pair of parameters and the return. +\lstinputlisting[language=C, firstline=50, lastline=59]{hello-array.cfa} +Here, the function @f@ does a pointwise comparison, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated bool array. + +The array type uses the parameterized length information in its @sizeof(-)@ determination, illustrated in the example's call to @alloc@. That call requests an allocation of type @array(bool, N)@, which the type system deduces from the left-hand side of the initialization, into the return type of the @alloc@ call. Preexesting \CFA behaviour is leveraged here, both in the return-type-only polymorphism, and the @sized(T)@-aware standard-library @alloc@ routine. The new @array@ type plugs into this behaviour by implementing the @sized@/@sizeof(-)@ assertion to have the intuitive meaning. As a result, this design avoids an opportunity for programmer error by making the size/length communication to a called routine implicit, compared with C's @calloc@ (or the low-level \CFA analog @aalloc@) which take an explicit length parameter not managed by the type system. + +A harness for this @f@ function shows how dynamic values are fed into the system. +\lstinputlisting[language=C, firstline=100, lastline=119]{hello-array.cfa} +Here, the @a@ sequence is loaded with decreasing values, and the @b@ sequence with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later. The driver program is run with two different inputs of sequence length. + +The loops in the driver follow the more familiar pattern of using the ordinary variable @n@ to convey the length. The type system implicitly captures this value at the call site (@main@ calling @f@) and makes it available within the callee (@f@'s loop bound). + +The two parts of the example show @Z(n)@ adapting a variable into a type-system governed length (at @main@'s declarations of @a@, @b@, and @result@), @z(N)@ adapting in the opposite direction (at @f@'s loop bound), and a passthru use of a governed length (at @f@'s declaration of @ret@.) It is hoped that future language integration will allow the macros @Z@ and @z@ to be omitted entirely from the user's notation, creating the appearance of seamlessly interchanging numeric values with appropriate generic parameters. + +The macro-assisted notation, @forall...ztype@, participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function body. So future language integration only sweetens this form and does not seek to elimimate the declaration. The present form is chosen to parallel, as closely as a macro allows, the existing forall forms: +\begin{lstlisting} + forall( dtype T ) ... + forall( otype T ) ... + forall( ztype(N) ) ... +\end{lstlisting} + +The notation @array(thing, N)@ is also macro-assisted, though only in service of enabling multidimensional uses discussed further in section \ref{toc:mdimpl}. In a single-dimensional case, the marco expansion gives a generic type instance, exactly like the original form suggests. + + + +In summary: + +\begin{tabular}{p{15em}p{20em}} + @ztype( N )@ & within a forall, declares the type variable @N@ to be a governed length \\[0.25em] + @Z( @ $e$ @ )@ & a type representing the value of $e$ as a governed length, where $e$ is a @size_t@-typed expression \\[0.25em] + @z( N )@ & an expression of type @size_t@, whose value is the governed length @N@ \\[0.25em] + @array( thing, N0, N1, ... )@ + & a type wrapping $\prod_i N_i$ adjacent occurrences of @thing@ objects +\end{tabular} + +Unsigned integers have a special status in this type system. Unlike how C++ allows @template< size_t N, char * msg, typename T >...@ declarations, this system does not accommodate values of any user-provided type. TODO: discuss connection with dependent types. + + +An example of a type error demonstrates argument safety. The running example has @f@ expecting two arrays of the same length. A compile-time error occurs when attempting to call @f@ with arrays whose lengths may differ. +\lstinputlisting[language=C, firstline=150, lastline=155]{hello-array.cfa} +As is common practice in C, the programmer is free to cast, to assert knownledge not shared with the type system. +\lstinputlisting[language=C, firstline=200, lastline=202]{hello-array.cfa} + +Argument safety, and the associated implicit communication of length, work with \CFA's generic types too. As a structure can be defined over a parameterized element type, so can it be defined over a parameterized length. Doing so gives a refinement of C's ``flexible array member'' pattern, that allows nesting structures with array members anywhere within other structures. +\lstinputlisting[language=C, firstline=20, lastline=26]{hello-accordion.cfa} +This structure's layout has the starting offest of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic paramters. For a function that operates on a @request@ structure, the type system handles this variation transparently. +\lstinputlisting[language=C, firstline=50, lastline=57]{hello-accordion.cfa} +In the example runs of a driver program, different offset values are navigated in the two cases. +\lstinputlisting[language=C, firstline=100, lastline=115]{hello-accordion.cfa} +The output values show that @summarize@ and its caller agree on both the offsets (where the callee starts reading @cost_contribs@ and where the callee writes @total_cost@). Yet the call site still says just, ``pass the request.'' Index: doc/theses/mike_brooks_MMath/content/array/mdim/array.hfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/mdim/array.hfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/mdim/array.hfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,127 @@ + + +// a type whose size is n +#define Z(n) char[n] + +// the inverse of Z(-) +#define z(Zn) sizeof(Zn) + +// if you're expecting a Z(n), say so, by asking for a ztype, instead of dtype or otype +#define ztype(Zn) Zn & | sized(Zn) + +forall( T & ) struct tag {}; +#define ttag(T) ((tag(T)){}) +#define ztag(n) ttag(Z(n)) + + +// +// Single-dim array sruct (with explicit packing and atom) +// + +forall( ztype(Zn), ztype(S), Timmed &, Tbase & ) { + struct arpk { + S strides[z(Zn)]; + }; + + Timmed & ?[?]( arpk(Zn, S, Timmed, Tbase) & a, ptrdiff_t i ) { + return (Timmed &) a.strides[i]; + } + + // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa) + void ?{}( arpk(Zn, S, Timmed, Tbase) & this ) { + void ?{}( S (&inner)[z(Zn)] ) {} + ?{}(this.strides); + } + void ^?{}( arpk(Zn, S, Timmed, Tbase) & this ) { + void ^?{}( S (&inner)[z(Zn)] ) {} + ^?{}(this.strides); + } +} + +// +// Sugar for declaring array structure instances +// + +forall( Te ) +Te mkar_( tag(Te) ) {} + +forall( ztype(Zn), ZTags ... , Trslt &, Tatom & | { Trslt mkar_( tag(Tatom), ZTags ); } ) +arpk(Zn, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(Zn), ZTags ) {} + +// stolen from https://stackoverflow.com/questions/1872220/is-it-possible-to-iterate-over-arguments-in-variadic-macros + + // Make a FOREACH macro + #define FE_0(WHAT) + #define FE_1(WHAT, X) WHAT(X) + #define FE_2(WHAT, X, ...) WHAT(X)FE_1(WHAT, __VA_ARGS__) + #define FE_3(WHAT, X, ...) WHAT(X)FE_2(WHAT, __VA_ARGS__) + #define FE_4(WHAT, X, ...) WHAT(X)FE_3(WHAT, __VA_ARGS__) + #define FE_5(WHAT, X, ...) WHAT(X)FE_4(WHAT, __VA_ARGS__) + //... repeat as needed + + #define GET_MACRO(_0,_1,_2,_3,_4,_5,NAME,...) NAME + #define FOR_EACH(action,...) \ + GET_MACRO(_0,__VA_ARGS__,FE_5,FE_4,FE_3,FE_2,FE_1,FE_0)(action,__VA_ARGS__) + +#define COMMA_ttag(X) , ttag(X) +#define array( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ttag, __VA_ARGS__ ) ) ) + +#define COMMA_ztag(X) , ztag(X) +#define zarray( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ztag, __VA_ARGS__ ) ) ) + +// +// Sugar for multidimensional indexing +// + +// Core -[[-,-,-]] operator + +// Desired form, one definition with recursion on IxBC (worked until Jan 2021, see trac #__TODO__) +// forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) +// TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { +// return this[ab][bc]; +// } + +// Workaround form. Listing all possibilities up to 4 dims. +forall( TA &, TB &, IxAB | { TB & ?[?]( TA &, IxAB ); } + , TC &, IxBC | { TC & ?[?]( TB &, IxBC ); } ) +TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { + return this[ab][bc]; +} +// forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) +// TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { +// return this[ab][bc]; +// } + +// Adapters for "indexed by ptrdiff_t" implies "indexed by [this other integral type]" +// Work around restriction that assertions underlying -[[-,-,-]] must match excatly +forall( C &, E & | { E & ?[?]( C &, ptrdiff_t ); } ) { + + // Targeted to support: for( i; z(N) ) ... a[[ ..., i, ... ]] + E & ?[?]( C & this, size_t i ) { + return this[ (ptrdiff_t) i ]; + } + + // Targeted to support: for( i; 5 ) ... a[[ ..., i, ... ]] + E & ?[?]( C & this, int i ) { + return this[ (ptrdiff_t) i ]; + } +} + +// +// Rotation +// + +// Base +forall( ztype(Zq), ztype(Sq), Tbase & ) +tag(arpk(Zq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(Tbase) ) {} + +// Rec +forall( ztype(Zq), ztype(Sq), ztype(Z), ztype(S), recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(recq) ); } ) +tag(arpk(Z, S, recr, Tbase)) enq_( tag(Tbase), tag(Zq), tag(Sq), tag(arpk(Z, S, recq, Tbase)) ) {} + +// Wrapper +struct all_t {} all; +forall( ztype(Z), ztype(S), Te &, result &, Tbase & | { tag(result) enq_( tag(Tbase), tag(Z), tag(S), tag(Te) ); } ) +result & ?[?]( arpk(Z, S, Te, Tbase) & this, all_t ) { + return (result&) this; +} Index: doc/theses/mike_brooks_MMath/content/array/mdim/hello-md.cfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/mdim/hello-md.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/mdim/hello-md.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,172 @@ +#include "array.hfa" + + +trait ix( C &, E &, ztype(N) ) { + E & ?[?]( C &, ptrdiff_t ); + void __taglen( tag(C), tag(N) ); +}; + +forall( ztype(Zn), ztype(S), Timmed &, Tbase & ) +void __taglen( tag(arpk(Zn, S, Timmed, Tbase)), tag(Zn) ) {} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +forall( ztype( N ) ) +void print1d_cstyle( array(float, N) & c ); + +forall( C &, ztype( N ) | ix( C, float, N ) ) +void print1d( C & c ); + + + + + + + + + + + + + + + +forall( ztype( N ) ) +void print1d_cstyle( array(float, N) & c ) { + for( i; z(N) ) { + printf("%.1f ", c[i]); + } + printf("\n"); +} + + + + + + + + + + + + + +forall( C &, ztype( N ) | ix( C, float, N ) ) +void print1d( C & c ) { + for( i; z(N) ) { + printf("%.1f ", c[i]); + } + printf("\n"); +} + + + + + + + + + + + + + + +void fill( array(float, Z(5), Z(7)) & a ) { + for ( i; (ptrdiff_t) 5 ) { + for ( j; 7 ) { + a[[i,j]] = 1.0 * i + 0.1 * j; + printf("%.1f ", a[[i,j]]); + } + printf("\n"); + } + printf("\n"); +} + +int main() { + + + + + + + +array( float, Z(5), Z(7) ) a; +fill(a); +/* +0.0 0.1 0.2 0.3 0.4 0.5 0.6 +1.0 1.1 1.2 1.3 1.4 1.5 1.6 +2.0 2.1 2.2 2.3 2.4 2.5 2.6 +3.0 3.1 3.2 3.3 3.4 3.5 3.6 +4.0 4.1 4.2 4.3 4.4 4.5 4.6 +*/ + + + + + + + + + + + +print1d_cstyle( a[ 2 ] ); // 2.0 2.1 2.2 2.3 2.4 2.5 2.6 + + + + +print1d( a[ 2 ] ); // 2.0 2.1 2.2 2.3 2.4 2.5 2.6 + + + + +print1d( a[[ 2, all ]] ); // 2.0 2.1 2.2 2.3 2.4 2.5 2.6 +print1d( a[[ all, 3 ]] ); // 0.3 1.3 2.3 3.3 4.3 + + + +print1d_cstyle( a[[ 2, all ]] ); + + + + + + + +#ifdef SHOWERR1 + +print1d_cstyle( a[[ all, 2 ]] ); // bad + +#endif + +} + + + Index: doc/theses/mike_brooks_MMath/content/array/mdim/matmul.cfa =================================================================== --- doc/theses/mike_brooks_MMath/content/array/mdim/matmul.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/mdim/matmul.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,22 @@ +#include "array.hfa" + + +// TODO: can I mini-sweeten the type overloads of -[[-,-,-]] beyond ptrdiff_t +// so that it works with for(i; z(-)) + +// PARK: refining the feature idea of equationally-defined operators, to include +// declaration: foo a = b * c; +// meaning construct a to be b times c + +forall( ztype(R), ztype(C), ztype(Mid) ) +void mul( array( float, R, Mid) & srcL, + array( float, Mid, C) & srcR, + array( float, R, C ) & dst ) { + for (ptrdiff_t r = 0; r < z(R); r++) for (ptrdiff_t c = 0; c < z(C); c++) { + dst[[r,c]] = 0; + for (ptrdiff_t i = 0; i < z(Mid); i++) + dst[[r,c]] += srcL[[r,i]] * srcR[[i,c]]; + } +} + + Index: doc/theses/mike_brooks_MMath/content/array/mdim/sec.tex =================================================================== --- doc/theses/mike_brooks_MMath/content/array/mdim/sec.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/array/mdim/sec.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,93 @@ + +TODO: introduce multidimensional array feature and approaches + +The new \CFA standard library @array@ datatype supports multidimensional uses more richly than the C array. The new array's multimentsional interface and implementation, follows an array-of-arrays setup, meaning, like C's @float[n][m]@ type, one contiguous object, with coarsely-strided dimensions directly wrapping finely-strided dimensions. This setup is in contrast with the pattern of array of pointers to other allocations representing a sub-array. Beyond what C's type offers, the new array brings direct support for working with a noncontiguous array slice, allowing a program to work with dimension subscripts given in a non-physical order. C and C++ require a programmer with such a need to manage pointer/offset arithmetic manually. + +Examples are shown using a $5 \times 7$ float array, @a@, loaded with increments of $0.1$ when stepping across the length-7 finely-strided dimension shown on columns, and with increments of $1.0$ when stepping across the length-5 corsely-strided dimension shown on rows. +\lstinputlisting[language=C, firstline=120, lastline=128]{hello-md.cfa} +The memory layout of @a@ has strictly increasing numbers along its 35 contiguous positions. + +A trivial form of slicing extracts a contiguous inner array, within an array-of-arrays. Like with the C array, a lesser-dimensional array reference can be bound to the result of subscripting a greater-dimensional array, by a prefix of its dimensions. This action first subscripts away the most coaresly strided dimensions, leaving a result that expects to be be subscripted by the more finely strided dimensions. +\lstinputlisting[language=C, firstline=60, lastline=66]{hello-md.cfa} +\lstinputlisting[language=C, firstline=140, lastline=140]{hello-md.cfa} + +This function declaration is asserting too much knowledge about its parameter @c@, for it to be usable for printing either a row slice or a column slice. Specifically, declaring the parameter @c@ with type @array@ means that @c@ is contiguous. However, the function does not use this fact. For the function to do its job, @c@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@), with governed length @N@. The new-array library provides the trait @ix@, so-defined. With it, the original declaration can be generalized, while still implemented with the same body, to the latter declaration: +\lstinputlisting[language=C, firstline=40, lastline=44]{hello-md.cfa} +\lstinputlisting[language=C, firstline=145, lastline=145]{hello-md.cfa} + +Nontrivial slicing, in this example, means passing a noncontiguous slice to @print1d@. The new-array library provides a ``subscript by all'' operation for this purpose. In a multi-dimensional subscript operation, any dimension given as @all@ is left ``not yet subscripted by a value,'' implementing the @ix@ trait, waiting for such a value. +\lstinputlisting[language=C, firstline=150, lastline=151]{hello-md.cfa} + +The example has shown that @a[2]@ and @a[[2, all]]@ both refer to the same, ``2.*'' slice. Indeed, the various @print1d@ calls under discussion access the entry with value 2.3 as @a[2][3]@, @a[[2,all]][3]@, and @a[[all,3]][2]@. This design preserves (and extends) C array semantics by defining @a[[i,j]]@ to be @a[i][j]@ for numeric subscripts, but also for ``subscripting by all''. That is: + +\begin{tabular}{cccccl} + @a[[2,all]][3]@ & $=$ & @a[2][all][3]@ & $=$ & @a[2][3]@ & (here, @all@ is redundant) \\ + @a[[all,3]][2]@ & $=$ & @a[all][3][2]@ & $=$ & @a[2][3]@ & (here, @all@ is effective) +\end{tabular} + +Narrating progress through each of the @-[-][-][-]@ expressions gives, firstly, a definition of @-[all]@, and secondly, a generalization of C's @-[i]@. + +\noindent Where @all@ is redundant: + +\begin{tabular}{ll} + @a@ & 2-dimensional, want subscripts for coarse then fine \\ + @a[2]@ & 1-dimensional, want subscript for fine; lock coarse = 2 \\ + @a[2][all]@ & 1-dimensional, want subscript for fine \\ + @a[2][all][3]@ & 0-dimensional; lock fine = 3 +\end{tabular} + +\noindent Where @all@ is effective: + +\begin{tabular}{ll} + @a@ & 2-dimensional, want subscripts for coarse then fine \\ + @a[all]@ & 2-dimensional, want subscripts for fine then coarse \\ + @a[all][3]@ & 1-dimensional, want subscript for coarse; lock fine = 3 \\ + @a[all][3][2]@ & 0-dimensional; lock coarse = 2 +\end{tabular} + +The semantics of @-[all]@ is to dequeue from the front of the ``want subscripts'' list and re-enqueue at its back. The semantics of @-[i]@ is to dequeue from the front of the ``want subscripts'' list and lock its value to be @i@. + +Contiguous arrays, and slices of them, are all realized by the same underlying parameterized type. It includes stride information in its metatdata. The @-[all]@ operation is a conversion from a reference to one instantiation, to a reference to another instantiation. The running example's @all@-effective step, stated more concretely, is: + +\begin{tabular}{ll} + @a@ & : 5 of ( 7 of float each spaced 1 float apart ) each spaced 7 floats apart \\ + @a[all]@ & : 7 of ( 5 of float each spaced 7 floats apart ) each spaced 1 float apart +\end{tabular} + +\begin{figure} + \includegraphics{measuring-like-layout} + \caption{Visualization of subscripting by value and by \lstinline[language=C,basicstyle=\ttfamily]{all}, for \lstinline[language=C,basicstyle=\ttfamily]{a} of type \lstinline[language=C,basicstyle=\ttfamily]{array( float, Z(5), Z(7) )}. The horizontal dimension represents memory addresses while vertical layout is conceptual.} + \label{fig:subscr-all} +\end{figure} + +\noindent While the latter description implies overlapping elements, Figure \ref{fig:subscr-all} shows that the overlaps only occur with unused spaces between elements. Its depictions of @a[all][...]@ show the navigation of a memory layout with nontrivial strides, that is, with ``spaced \_ floats apart'' values that are greater or smaller than the true count of valid indeces times the size of a logically indexed element. Reading from the bottom up, the expression @a[all][3][2]@ shows a float, that is masquerading as a @float[7]@, for the purpose of being arranged among its peers; five such occurrences form @a[all][3]@. The tail of flatter boxes extending to the right of a poper element represents this stretching. At the next level of containment, the structure @a[all][3]@ masquerades as a @float[1]@, for the purpose of being arranged among its peers; seven such occurrences form @a[all]@. The verical staircase arrangement represents this compression, and resulting overlapping. + +The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping. The private @arpk@ structure (array with explicit packing) is generic over these two types (and more): the contained element, what it is masquerading as. This structure's public interface is the @array(...)@ construction macro and the two subscript operators. Construction by @array@ initializes the masquerading-as type information to be equal to the contained-element information. Subscrpting by @all@ rearranges the order of masquerading-as types to achieve, in genernal, nontrivial striding. Subscripting by a number consumes the masquerading-as size of the contained element type, does normal array stepping according to that size, and returns there element found there, in unmasked form. + +The @arpk@ structure and its @-[i]@ operator are thus defined as: +\begin{lstlisting} +forall( ztype(N), // length of current dimension + dtype(S) | sized(S), // masquerading-as + dtype E_im, // immediate element, often another array + dtype E_base // base element, e.g. float, never array + ) { + struct arpk { + S strides[z(N)]; // so that sizeof(this) is N of S + }; + + // expose E_im, stride by S + E_im & ?[?]( arpk(N, S, E_im, E_base) & a, ptrdiff_t i ) { + return (E_im &) a.strides[i]; + } +} +\end{lstlisting} + +An instantion of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ exapnsion, which is @arpk( N0, Rec, Rec, E_base )@, where @Rec@ is @array(E_base, N1, ...)@. In the base case, @array(E_base)@ is just @E_base@. Because this construction uses the same value for the generic parameters @S@ and @E_im@, the resulting layout has trivial strides. + +Subscripting by @all@, to operate on nontrivial strides, is a dequeue-enqueue operation on the @E_im@ chain, which carries @S@ instatiations, intact, to new positions. Expressed as an operation on types, this rotation is: +\begin{eqnarray*} +suball( arpk(N, S, E_i, E_b) ) & = & enq( N, S, E_i, E_b ) \\ +enq( N, S, E_b, E_b ) & = & arpk( N, S, E_b, E_b ) \\ +enq( N, S, arpk(N', S', E_i', E_b), E_b ) & = & arpk( N', S', enq(N, S, E_i', E_b), E_b ) +\end{eqnarray*} + Index: doc/theses/mike_brooks_MMath/content/string/Makefile =================================================================== --- doc/theses/mike_brooks_MMath/content/string/Makefile (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/Makefile (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,64 @@ +SHELL := /bin/bash + +# The targets made here are individual code-level demos. +# Some produce LaTeX fragments. All are being checked for the code being valid. +# None are being built from *.tex toward *.pdf. Use the top-level makefile for that. + + +BuildBase = ../../build +Build = ${BuildBase}/string + +# (plg2 has gem) +# gem install --user-install liquid +# gem install --user-install liquid-cli +Liquid = ~/.gem/ruby/2.7.0/bin/liquid + +CFA = ../../../../../../build/driver/cfa + +DEMOS = ${addsuffix -demo, \ + sharing \ +} + +EZDEMOS = ${addsuffix -ezdemo, \ + sharectx \ +} + + +all: $(DEMOS) $(EZDEMOS) + +# removing the echo rule body means the rule doesn't fire +%-demo: $(Build)/%-demo.tex %-demo-runok | $(Build) + @echo target $@ made + +%-ezdemo: %-ezdemo-runok | $(Build) + @echo target $@ made + +%-demo-runok: $(Build)/%-demo | $(Build) + $< + +%-ezdemo-runok: $(Build)/%-ezdemo | $(Build) + $< + +$(Build)/%-demo.tex: %-demo.json %-demo.tex.liquid | $(Build) + $(Liquid) "$$(< $<)" < $(word 2,$^) > $@ +# echo will run $(Liquid) +# echo will get JSON from $< +# echo will get template from $(word 2,$^) + +$(Build)/%-demo: $(Build)/%-demo.cfa + $(CFA) $< -o $@ + +$(Build)/%-demo.cfa: %-demo.json %-demo.cfa.liquid | $(Build) + $(Liquid) "$$(< $<)" < $(word 2,$^) > $@ + +$(Build)/%-ezdemo: %-demo.cfa + $(CFA) $< -o $@ + + + + +${Build}: + mkdir -p $@ + +.PHONY : all %-demo %-demo %-runok +.PRECIOUS : $(Build)/%-demo.tex $(Build)/%-demo.cfa $(Build)/%-demo Index: doc/theses/mike_brooks_MMath/content/string/sharectx-demo.cfa =================================================================== --- doc/theses/mike_brooks_MMath/content/string/sharectx-demo.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/sharectx-demo.cfa (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,35 @@ +#include +#include + +void a() {} +void b() {} +void c() {} +void d() {} +void e() {} + + + + + + + + + + + +void helper2() { + c(); + string_sharectx c = {NEW_SHARING}; + d(); +} +void helper1() { + a(); + string_sharectx c = {NO_SHARING}; + b(); + helper2(); + e(); +} +int main() { + helper1(); +} + Index: doc/theses/mike_brooks_MMath/content/string/sharing-demo.cfa.liquid =================================================================== --- doc/theses/mike_brooks_MMath/content/string/sharing-demo.cfa.liquid (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/sharing-demo.cfa.liquid (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,53 @@ +#include +#include + +void demo1() { + + +{% for item in demo1 %} + {% if item.type == "text" %} + /* {{ item.value }} */ + {% elsif item.type == "demo" %} + {% for step in item.steps %} + {% for line in step.code %}{{ line }} + {% endfor %} + {% for endval in step.endvals %} + assert( {{endval[0]}} == "{{endval[1]}}" ); + {% endfor %} + {% endfor %} + {% else %} + BAD ITEM + {% endif %} +{% endfor %} + +} + + +void demo2() { + + +{% for item in demo2 %} + {% if item.type == "text" %} + /* {{ item.value }} */ + {% elsif item.type == "demo" %} + {% for step in item.steps %} + {% for line in step.code %}{{ line }} + {% endfor %} + {% for endval in step.endvals %} + assert( {{endval[0]}} == "{{endval[1]}}" ); + {% endfor %} + {% endfor %} + {% else %} + BAD ITEM + {% endif %} +{% endfor %} + +} + + +int main(int argc, char ** argv) { + + demo1(); + demo2(); + printf("%s done running\n", argv[0]); +} Index: doc/theses/mike_brooks_MMath/content/string/sharing-demo.json =================================================================== --- doc/theses/mike_brooks_MMath/content/string/sharing-demo.json (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/sharing-demo.json (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,403 @@ +{ + "demo1":[ + { "type":"text", + "value":"Consider two strings s1 and s1a that are in an aliasing relationship, and a third, s2, made by a simple copy from s1." + }, + { "type":"demo", + "vars":["s1", "s1a", "s2"], + "steps":[ + { "code":["string s1 = \"abc\";", + "string s1a = s1`shareEdits;", + "string s2 = s1;"], + "endvals":{ + "s1":"abc", + "s1a":"abc", + "s2":"abc" + } + } + ] + }, + { "type":"text", + "value":"Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not." + }, + { "type":"demo", + "vars":["s1", "s1a", "s2"], + "steps":[ + { "endvals":{ + "s1":"abc", + "s1a":"abc", + "s2":"abc" + } + }, + { "code":["s1 [1] = '+';"], + "endvals":{ + "s1":"a+c", + "s1a":"a+c", + "s2":"abc" + } + }, + { "code":["s1a[1] = '-';"], + "endvals":{ + "s1":"a-c", + "s1a":"a-c", + "s2":"abc" + } + }, + { "code":["s2 [1] = '|';"], + "endvals":{ + "s1":"a-c", + "s1a":"a-c", + "s2":"a|c" + } + } + ] + }, + { "type":"text", + "value":"Assignment of a value is just a modificiation. The aliasing relationship is established at construction and is unaffected by assignment of a value." + }, + { "type":"demo", + "vars":["s1", "s1a", "s2"], + "steps":[ + { "endvals":{ + "s1":"a-c", + "s1a":"a-c", + "s2":"a|c" + } + }, + { "code":["s1 = \"qrs\";"], + "endvals":{ + "s1":"qrs", + "s1a":"qrs", + "s2":"a|c" + } + }, + { "code":["s1a = \"tuv\";"], + "endvals":{ + "s1":"tuv", + "s1a":"tuv", + "s2":"a|c" + } + }, + { "code":["s2 = \"wxy\";"], + "endvals":{ + "s1":"tuv", + "s1a":"tuv", + "s2":"wxy" + } + } + ] + }, + { "type":"text", + "value":"Assignment from a string is just assignment of a value. RHS participaing in aliasing (or not) is irrelevant. Aliasing of LHS is unaffected." + }, + { "type":"demo", + "vars":["s1", "s1a", "s2"], + "steps":[ + { "endvals":{ + "s1":"tuv", + "s1a":"tuv", + "s2":"wxy" + } + }, + { "code":["s1 = s2;"], + "endvals":{ + "s1":"wxy", + "s1a":"wxy", + "s2":"wxy" + } + }, + { "code":["s1 = \"aaa\";"], + "endvals":{ + "s1":"aaa", + "s1a":"aaa", + "s2":"wxy" + } + }, + { "code":["s2 = s1;"], + "endvals":{ + "s1":"aaa", + "s1a":"aaa", + "s2":"aaa" + } + }, + { "code":["s2 = \"bbb\";"], + "endvals":{ + "s1":"aaa", + "s1a":"aaa", + "s2":"bbb" + } + }, + { "code":["s2 = s1a;"], + "endvals":{ + "s1":"aaa", + "s1a":"aaa", + "s2":"aaa" + } + }, + { "code":["s2 = \"ccc\";"], + "endvals":{ + "s1":"aaa", + "s1a":"aaa", + "s2":"ccc" + } + }, + { "code":["s1 = \"xxx\";"], + "endvals":{ + "s1":"xxx", + "s1a":"xxx", + "s2":"ccc" + } + } + ] + } + ], + "demo2":[ + { "type":"text", + "value":"Consider new strings @s1_mid@ being an alias for a run in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@." + }, + { "type":"demo", + "vars":["s1", "s1_mid", "s2"], + "steps":[ + { "code":["string s1 = \"abcd\";", + "string s1_mid = s1(1,3)`shareEdits;", + "string s2 = s1(1,3);"], + "endvals":{ + "s1":"abcd", + "s1_mid":"bc", + "s2":"bc" + } + } + ] + }, + { "type":"text", + "value":"Again, @`shareEdits@ passes changes in both directions; copy does not. Note the difference in index values, with the \\emph{b} position being 1 in the longer string and 0 in the shorter strings. In the case of s1 aliasing with @s1_mid@, the very same character is being accessed by different postitions." + }, + { "type":"demo", + "vars":["s1", "s1_mid", "s2"], + "steps":[ + { "endvals":{ + "s1":"abcd", + "s1_mid":"bc", + "s2":"bc" + } + }, + { "code":["s1 [1] = '+';"], + "endvals":{ + "s1":"a+cd", + "s1_mid":"+c", + "s2":"bc" + } + }, + { "code":["s1_mid[0] = '-';"], + "endvals":{ + "s1":"a-cd", + "s1_mid":"-c", + "s2":"bc" + } + }, + { "code":["s2 [0] = '|';"], + "endvals":{ + "s1":"a-cd", + "s1_mid":"-c", + "s2":"|c" + } + } + ] + }, + { "type":"text", + "value":"Once again, assignment of a value is a modificiation that flows through the aliasing relationship, without affecting its structure." + }, + { "type":"demo", + "vars":["s1", "s1_mid", "s2"], + "steps":[ + { "endvals":{ + "s1":"a-cd", + "s1_mid":"-c", + "s2":"|c" + } + }, + { "code":["s1_mid = \"ff\";"], + "endvals":{ + "s1":"affd", + "s1_mid":"ff", + "s2":"|c" + } + }, + { "code":["s2 = \"gg\";"], + "endvals":{ + "s1":"affd", + "s1_mid":"ff", + "s2":"gg" + } + } + ] + }, + { "type":"text", + "value":"In the \\emph{ff} step, which is a positive example of flow across an aliasing relationship, the result is straightforward to accept because the flow direction is from contained (small) to containing (large). The following rules for edits through aliasing substrings will guide how to flow in the opposite direction.\n\n" + }, + { "type":"text", + "value":"Growth and shrinkage are natural extensions. An empty substring is a real thing, at a well-defined location, whose meaning is extrapolated from the examples so far. The intended metaphor is to operating a GUI text editor. Having an aliasing substring is like using the mouse to select a few words. Assigning onto an aliasign substring is like typing from having a few words selected: depending how much you type, the file being edited can get shorter or longer." + }, + { "type":"demo", + "vars":["s1", "s1_mid"], + "steps":[ + { "endvals":{ + "s1":"affd", + "s1_mid":"fc" + } + }, + { "code":["s1_mid = \"hhhh\";"], + "endvals":{ + "s1":"ahhhhd", + "s1_mid":"hhhh" + } + }, + { "code":["s1_mid = \"i\";"], + "endvals":{ + "s1":"aid", + "s1_mid":"i" + } + }, + { "code":["s1_mid = \"\";"], + "endvals":{ + "s1":"ad" + } + }, + { "code":["s1_mid = \"jj\";"], + "endvals":{ + "s1":"ajjd", + "s1_mid":"jj" + } + } + ] + }, + { "type":"text", + "value":"Multiple portions can be aliased. When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor. I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else." + }, + { "type":"demo", + "vars":["s1", "s1_bgn", "s1_mid", "s1_end"], + "steps":[ + { "code":["string s1_bgn = s1(0, 1)`shareEdits;", + "string s1_end = s1(3, 4)`shareEdits;"], + "endvals":{ + "s1":"ajjd", + "s1_bgn":"a", + "s1_mid":"jj", + "s1_end":"d" + } + }, + { "code":["s1_bgn = \"zzzz\";"], + "endvals":{ + "s1":"zzzzjjd", + "s1_bgn":"zzzz", + "s1_mid":"jj", + "s1_end":"d" + } + } + ] + }, + { "type":"text", + "value":"When an edit happens on an aliasing substring that overlaps another, an effect is unavoidable. Here, the passive party sees its selection shortened, to exclude the characters that were not part of the original selection." + }, + { "type":"demo", + "vars":["s1", "s1_bgn", "s1_crs", "s1_mid", "s1_end"], + "steps":[ + { "code":["string s1_crs = s1(3, 5)`shareEdits;"], + "endvals":{ + "s1":"zzzzjjd", + "s1_bgn":"zzzz", + "s1_crs":"zj", + "s1_mid":"jj", + "s1_end":"d" + } + }, + { "code":["s1_crs = \"+++\";"], + "endvals":{ + "s1":"zzz+++jd", + "s1_bgn":"zzz", + "s1_crs":"+++", + "s1_mid":"j", + "s1_end":"d" + } + } + ] + }, + { "type":"text", + "value":"This shortening behaviour means that a modification has to occur entirely inside a substring, to show up in that substring. Sharing changes through the intersection of partially overlapping aliases is still possible, so long as the receiver's boundary is not inside the edit." + }, + { "type":"demo", + "vars":["word", "consonants", "miniscules"], + "steps":[ + { "code":["string word = \"Phi\";", + "string consonants = word(0,2)`shareEdits;", + "string miniscules = word(1,3)`shareEdits;"], + "endvals":{ + "word":"Phi", + "consonants":"Ph", + "miniscules":"hi" + } + }, + { "code":["consonants[1] = 's';"], + "endvals":{ + "word":"Psi", + "consonants":"Ps", + "miniscules":"si" + } + } + ] + }, + { "type":"text", + "value":"The extreme form of this shortening happens when a bystander alias is a proper substring of an edit. The bystander becomes an empty substring." + }, + { "type":"demo", + "vars":["all", "greet", "greet_bgn", "greet_end"], + "steps":[ + { "code":["string all = \"They said hello again\";", + "string greet = all(10,15)`shareEdits;", + "string greet_bgn = all(10,11)`shareEdits;", + "string greet_end = all(14,15)`shareEdits;"], + "endvals":{ + "all":"They said hello again", + "greet":"hello", + "greet_bgn":"h", + "greet_end":"o" + } + }, + { "code":["greet = \"sup\";"], + "endvals":{ + "all":"They said sup again", + "greet":"sup" + } + } + ] + }, + { "type":"text", + "value":"As in the earlier step where \\emph{aj} becomes \\emph{ajjd}, such empty substrings maintain their places in the total string, and can be used for filling it. Because @greet_bgn@ was orginally at the start of the edit, in the outcome, the empty @greet_bgn@ sits just before the written value. Similarly @greed_end@ goes after. Though not shown, an overwritten substring at neither side goes arbitrarily to the before side." + }, + { "type":"demo", + "vars":["all", "greet", "greet_bgn", "greet_end"], + "steps":[ + { "code":["greet_bgn = \"what\"; "], + "endvals":{ + "all":"They said whatsup again", + "greet":"sup", + "greet_bgn":"what" + } + }, + { "code":["greet_end = \"...\"; "], + "endvals":{ + "all":"They said whatsup... again", + "greet":"sup", + "greet_bgn":"what", + "greet_end":"..." + } + } + ] + }, + { "type":"text", + "value":"Though these empty substrings hold their places in the total string, an empty string only belongs to bigger strings when it occurs completely inside them. There is no such state as including an empty substring at an edge. For this reason, @word@ gains the characters added by assigning to @greet_bgn@ and @greet_end@, but the string @greet@ does not." + } + + + ] +} Index: doc/theses/mike_brooks_MMath/content/string/sharing-demo.tex.liquid =================================================================== --- doc/theses/mike_brooks_MMath/content/string/sharing-demo.tex.liquid (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/sharing-demo.tex.liquid (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,45 @@ +{% for item in demo1 -%} + {% if item.type == "text" %}{{ + item.value + }}{% elsif item.type == "demo" %} \\ + \begin{tabular}{l{%for var in item.vars %}c{% endfor %}} + {%for var in item.vars %} & @{{var}}@ {% endfor %} \\ +{% for step in item.steps -%} +{%-if step.code -%} +\begin{lstlisting} +{% for line in step.code %}{{ line }} +{% endfor -%} +\end{lstlisting} +{%- endif -%} + {% for var in item.vars -%} + & {{ step.endvals[var] }} + {%- endfor %} \\ + {% endfor -%} + \end{tabular} \vspace{6pt} \\ + {% else %} + BAD ITEM + {% endif %} +{%- endfor -%} + +{% for item in demo2 -%} + {% if item.type == "text" %}{{ + item.value + }}{% elsif item.type == "demo" %} \\ + \begin{tabular}{l{%for var in item.vars %}c{% endfor %}} + {%for var in item.vars %} & @{{var}}@ {% endfor %} \\ +{% for step in item.steps -%} +{%-if step.code -%} +\begin{lstlisting} +{% for line in step.code %}{{ line }} +{% endfor -%} +\end{lstlisting} +{%- endif -%} + {% for var in item.vars -%} + & {{ step.endvals[var] }} + {%- endfor %} \\ + {% endfor -%} + \end{tabular} \vspace{6pt} \\ + {% else %} + BAD ITEM + {% endif %} +{%- endfor -%} Index: doc/theses/mike_brooks_MMath/content/string/string-master.tex =================================================================== --- doc/theses/mike_brooks_MMath/content/string/string-master.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/content/string/string-master.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,224 @@ +\section{String} + +\subsection{Logical Overlap} + +\include{sharing-demo} + +\subsection{RAII limitations} + +Earlier work on \CFA [to cite Schluntz] implemented the feature of constructors and destructors. A constructor is a user-defined function that runs implicitly, when control passes an object's declaration, while a destructor runs at the exit of the declaration's lexical scope. The feature allows programmers to assume that, whenever a runtime object of a certain type is accessible, the system called one of the programmer's constuctor functions on that object, and a matching destructor call will happen in the future. The feature helps programmers know that their programs' invariants obtain. + +The purposes of such invariants go beyond ensuring authentic values for the bits inside the object. These invariants can track occurrences of the managed objects in other data structures. Reference counting is a typical application of the latter invariant type. With a reference-counting smart pointer, the consturctor and destructor \emph{of the pointer type} track the lifecycles of occurrences of these pointers, by incrementing and decrementing a counter (ususally) on the referent object, that is, they maintain a that is state separate from the objects to whose lifecycles they are attached. Both the C++ and \CFA RAII systems ares powerful enough to achive such reference counting. + +The C++ RAII system supports a more advanced application. A lifecycle function has access to the object under managamanet, by location; constructors and destuctors receive a @this@ parameter providing its memory address. A lifecycle-function implementation can then add its objects to a collection upon creation, and remove them at destruction. A modulue that provides such objects, by using and encapsulating such a collection, can traverse the collection at relevant times, to keep the objects ``good.'' Then, if you are the user of such an module, declaring an object of its type means not only receiving an authentically ``good'' value at initialization, but receiving a subscription to a service that will keep the value ``good'' until you are done with it. + +In many cases, the relationship between memory location and lifecycle is simple. But with stack-allocated objects being used as parameters and returns, there is a sender version in one stack frame and a receiver version in another. C++ is able to treat those versions as distinct objects and guarantee a copy-constructor call for communicating the value from one to the other. This ability has implications on the language's calling convention. Consider an ordinary function @void f( Vehicle x )@, which receives an aggregate by value. If the type @Vehicle@ has custom lifecycle functions, then a call to a user-provided copy constructor occurs, after the caller evaluates its argument expression, after the callee's stack frame exists, with room for its variable @x@ (which is the location that the copy-constructor must target), but before the user-provided body of @f@ begins executing. C++ achieves this ordering by changing the function signature, in the compiled form, to pass-by-reference and having the callee invoke the copy constructor in its preamble. On the other hand, if @Vehicle@ is a simple structure then the C calling convention is applied as the code originally appeared, that is, the callsite implementation code performs a bitwise copy from the caller's expression result, into the callee's x. + +TODO: learn correction to fix inconcsistency: this discussion says the callee invokes the copy constructor, but only the caller knows which copy constructor to use! + +TODO: discuss the return-value piece of this pattern + +The \CFA RAII system has limited support for using lifecycle functions to provide a ``stay good'' service. It works in restricted settings, including on dynamically allocated objects. It does not work for communicating arguments and returns by value because the system does not produce a constructor call that tracks the implied move from a sender frame to a reciver frame. This limitation does not prevent a typical reference-counting design from using call-with-value/return-of-value, because the constructor--destructor calls are correctly balanced. But it impedes a ``stay-good'' service from supporting call-with-value/return-of-value, because the lifecycles presented to the constructor/destor calls do not keep stable locations. A ``stay-good'' service is acheivable so long as call-with-value/return-of-value do not occur. The original presentation [to cite Schluntz section] acknoweledges this limitiation; the present discussion makes its consequences more apparent. + +The \CFA team sees this limitation as part of a tactical interem state that should some day be improved. The \CFA compiler is currently a source-to-source translator that targets relativly portable C. Several details of its features are provisionally awkward or under-performant until finer control of its code generation is feasible. In the present state, all calls that appear in \CFA source code as call-with-value/return-of-value are emitted this way to the underlying C calling convention. SO WHAT? + +The present string-API contribution has both the ``stay good'' promise and call-with-value/return-of-value being essential. The main string API uses a work-around to acheive the full feature set, at a runtime performance penalty. An alternative API sacrifices call-with-value/return-of-value functionality to recover full runtime performance. These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL). They present the same features, up to lifecycle management, with call-with-value/return-of-value being disabled in LL and implemented with the workaround in HL. The intention is for most future code to target HL. In a more distant future state, where \CFA has an RAII system that can handle the problematic quadrant, the HL layer can be abolished, the LL can be renamed to match today's HL, and LL can have its call-with-value/return-of-value permission reenabled. Then, programs written originally against HL will simply run faster. In the meantime, two use cases of LL exist. Performance-critical sections of applications have LL as an option. Within [Xref perf experiments], though HL-v-LL penalties are measured, typcial comparisons of the contributed string libary vs similar systems are made using LL. This measurement gives a fair estimate of the goal state for \CFA while it is an evloving work in progress. + + + +\subsection{Memory Management} + +A centrepriece of the string module is its memory manager. The managment scheme defines a large shared buffer for strings' text. Allocation in this buffer is always bump-pointer; the buffer is compacted and/or relocated with growth when it fills. A string is a smart pointer into this buffer. + +This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC). A few differences are noteworthy. First, in a general purpose manager, the objects of allocation contain pointers to other such objects, making the transitive reachability of these objects be a critical property. Here, the allocations are of buffers of text, never pointers, so one allocation never keeps another one alive. Second, in a general purpose manager, where the handle that keeps an allocation alive is the same as the program's general-purpose inter-object reference, an extremely lean representation of this reference is required. Here, a fatter representation is acceptable because [why??]. + + +Figure [memmgr-basix.vsdx] shows the representation. A heap header, with its text buffer, defines a sharing context. Often, one global sharing context is appropriate for an entire program; exceptions are discussed in [xref TBD]. Strings are handles into the buffer. They are members of a linked list whose order matches the order of their buffer fragments (exactly, where there is no overlapping, and approximately, where there is). The header maintains a next-allocation pointer (alloc, in the figure) after the last live allocation of the buffer. No external references into the buffer are allowed and the management procedure relocates the text allocations as needed. The string handles contain explicit length fields, null termination characters are not used and all string text is kept in contiguous storage. When strings (the inter-linked hanldes) are allocated on the program's call stack, a sustained period with no use of the program's dynamic memory allocator can ensue, during which the program nonetheless creates strings, destroys them, and runs length-increasing modifications on existing ones. + +Compaction happens when the heap fills. It is the first of two uses of the linked list. The list allows discovering all live string handles, and from them, the ranges of the character buffer that are in use. With these ranges known, their total character count gives the amount of space in use. When that amount is small, compared with the current buffer size, an in-place compaction occurs, which enatils copying the in-use ranges, to be adjacent, at the font of the buffer. When the in-use amount is large, a larger buffer is allocated (using the program's general-purpose dynamic allcator), the in-use strings are copied to be adjacent at the front of it, and the original buffer is freed back to the program's general allocator. Either way, navigating the links between the handles provides the pointers into the buffer, first read, to find the source fragment, then written with the location of the resultant fragment. This linkage across the structure is unaffected during a compaction; only the pointers from the handles to the buffer are modified. This modification, along with the grooming/provisioning of the text storage resouce that it represents, is an example, in the language of [xref RAII limitations] of the string module providing a ``stay good'' service. + +Object lifecycle events are the subscription-management triggers in such a service. There are two fundamental string-creation routines: importing from external text like a C-string, and initialization from an existing \CFA string. When importing, a fresh allocation at the free end fo the buffer occurs, into which the text is copied. The resultant handle is therefore inserted into the list at the position after the incumbent last handle, a position given by the heap manager's ``last handle'' pointer. When initializing from text already on the \CFA heap, the resultant handle is a second reference onto the original run of characters. In this case, the resultant handle's linked-list position is beside the original handle. Both string initialization styles preserve the string module's internal invriant that the linked-list order match the buffer order. For string destruction, the list being doubly linked provides for easy removal of the disappearing handle. + +While a string handle is live, it accepts modification operations, some of which make it reference a different portion of the underlying buffer, and accordingly, move the handle to a different position in the inter-handle list. While special cases have more optimal handling, the general case requires a fresh buffer run. In this case, the new run is allocated at the bump-pointer end and filled with the required value. Then, handles that originally referenced the old location and need to see the new value are pointed at the new buffer location, unlinked from their original positions in the handles' list, and linked in at the end of the list. An optimal case, when the target is not a substring of something larger, and the source is text from elsewhere in the managed buffer, allows the target to be re-pointed at the source characters, and accordingly, move list position to be beside the source. Cases where in-place editing happens, addressed further in [xref: TBD], leave affected handles in their original list positions. In analogy to the two cases of string initialization, the two cases of realizing assignment by moving either to a fresh buffer run, or to overlap references with the source, maintain the invariant of linked list order matching buffer order. + + +To explain: GCing allocator doing bump-pointer with compaction + + + +At the level of the memory manager, these modifications can aways be explained as assignments; for example, an append is an assignemnt into the empty substring at the end. + +While favourable conditions allow for in-place editing, the general case requires a fresh buffer run. For example, if the new value does not fit in the old place, or if other handles are still using the old value, then the new value will use a fresh buffer run. + +where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location should see the new value, + + +always boiled down to assignment and appendment. Assignment has special cases that happen in-place, but in the general case, it is implemented as a sequence of appends onto a fresh allocation at the end of the buffer. (The sequence has multiple steps when the assignment target is a substring: old before, new middle, old after.) Similarly, an append request can be serviced in-place when there is room, or as a pair of appends + + + +\subsection{Sharing implementation} + +The \CFA string module has two manners in which serveral string handles can share an unerlying run of characters. + +The first type of sharing is user-requested, following the [xref Logical Overlap]. Here, the user requests, explicitly, that both handles be views of the same logical, modifiable string. This state is typically prodecd by the substring operation. In a typical substring call, the source string-handle is referencing an entire string, and the resluting, newly made, string handle is referencing a portion of the orignal. In this state, a subsequent modification made by either is visible in both. + +The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization. This state is typically produced by constructing a new string, using an original string as its intialization source. In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different runs within the buffer, holding distinct values. + +A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing. A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one being constructed from the other, with the ``share edits'' opt-in given. It is represented by a second linked list among the handles. A string that shares edits with no other is in a SES by itself. Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap. Conversely, no logical value change can flow outside of a SES. Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they don't overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text. + + +\subsection{Avoiding Implicit Sharing} + +There are tradeoffs associated with the copy-on-write mechanism. Several quatitative matters are detailed in the [xref: Performance Assessment] section and the qualitiative issue of multi-threaded support is introduced here. The \CFA sting library provides a switch to disable the sharing mechanism for situtations where it is inappropriate. + +Because of the inter-linked string handles, any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.'' This data structure is intended for sequential access. A negative consequence of this decision is that multiple threads using strings need to be set up so that they avoid attempting to modify (concurrently) an instance of this structure. A positive consequence is that a single-threaded program, or a program with several independent threads, can use the sharing context without an overhead from locking. + +The \CFA sting library provides the @string_sharectx@ type to control an ambient sharing context for the current thread. It allows two adjustments: to opt out of sharing entirely, or to begin sharing within a private context. Either way, the chosen mode applies to the current thread, for the duration of the lifetime of the created @string_sharectx@ object, up to being suspended by child liftimes of different contexts. The indended use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that don't create their own contexts. +\lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx-demo.cfa} +In this example, the single-letter functions are called in alphabetic order. The functions @a@ and @d@ share string character ranges within themselves, but not with each other. The functions @b@, @c@ and @e@ never share anything. + +[ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ] + +When the string library is running with sharing disabled, it runs without implicit thread-safety challenges (which same as the STL) and with performance goals similar to the STL's. This thread-safety quality means concurrent users of one string object must still bring their own mutual exlusion, but the string libary will not add any cross thread uses that were not apparent in the user's code. + +Running with sharing disabled can be thought of as STL-emulation mode. + + + +\subsection{Future Work} + +To discuss: Unicode + +To discuss: Small-string optimization + + +\subsection{Performance Assessment} + +I assessed the CFA string library's speed and memory usage. I present these results ineven quivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality. They also show the benefits and tradeoffs, as >100\% effects, of switching to CFA, with the tradeoff points quantified. The final test shows the overall win of the CFA text-sharing mechanism. It exercises several operations together, showing CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve. + +To discuss: general goal of ... while STL makes you think about memory management, all the time, and if you do your performance can be great ... CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory mamangement. [Does this position cover all of it?] + +To discuss: revisit HL v LL APIs + +To discuss: revisit nosharing as STL emulation modes + +These tests use randomly generated text fragments of varying lengths. A collection of such fragments is a \emph{corpus}. The mean length of a fragment from corpus is a typical explanatory variable. Such a length is used in one of three modes: +\begin{description} + \item [Fixed-size] means all string fragments are of the stated size + \item [Varying from 1] means string lengths are drawn from a geometric distribution with the stated mean, and all lengths occur + \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and obove occur; thus, the stated mean will be above 16. +\end{description} +The geometric distribution implies that lengths much longer than the mean occur frequently. The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [todo: write and cross-ref future-work SSO]), currently not implmented in \CFA. When success notwithstanding SSO is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side. In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins. + +To discuss: vocabulary for reused case variables + +To discuss: common approach to iteration and quoted rates + +To discuss: hardware and such + +To discuss: memory allocator + + +\subsubsection{Test: Append} + +This test measures the speed of appending fragments of text onto a growing string. Its subcases include both CFA being similar to STL, and their designs offering a tradeoff. + +One experimental variable is the user's operation being @a = a + b@ vs. @a += b@. While experienced programmers expect the latter to be ``what you obviously should do,'' controling the penatly of the former both helps the API be accessible to beginners and also helps offer confidence that when a user tries to compose operations, the forms that are most natural to the user's composition are viable. + +Another experimental variable is whether the user's logical allocation is fresh vs reused. Here, \emph{reusing a logical allocation}, means that the prgram variable, into which the user is concatenating, previously held a long string:\\ +\begin{tabular}{ll} + Logical allocation fresh & Logical allocation reused \\ + & @ string x; @ \\ + @ for( ... ) { @ & @ for( ... ) { @ \\ + @ string x; @ & @ x = ""; @ \\ + @ for( ... ) @ & @ for( ... ) @ \\ + @ x += ... @ & @ x += ... @ \\ + @ } @ & @ } @ +\end{tabular}\\ +These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.'' It is sensible to doubt that a user should have to care about this difference, yet the STL performs differently in these cases. Concretly, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length. For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while CFA-sharing hides such a cost entirely. The reuse-vs-fresh distinction is only relevant in the currrent \emph{append} tests. + +The \emph{append} tests use the varying-from-1 corpus construction; that is they do not assume away the STL's advantage from small-string opitimization. + +To discuss: any other case variables intruduced in the performance intro + +\begin{figure} + \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png} + \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA with STL implementations (given \CFA running in STL emulation mode), and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \label{fig:string-graph-peq-cppemu} +\end{figure} + +Figure \ref{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode. \CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case. This penatly characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state. The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings. + +\begin{figure} + \includegraphics[width=\textwidth]{string-graph-peq-sharing.png} + \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA (having implicit sharing activated) with STL, and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \label{fig:string-graph-peq-sharing} +\end{figure} + +In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in Figure \ref{fig:string-graph-peq-sharing}. At append lengths 5 and above, CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode. + +\begin{figure} + \includegraphics[width=\textwidth]{string-graph-pta-sharing.png} + \caption{Average time per iteration with one \lstinline{x = x + y} invocation (new, purple bands), comparing \CFA (having implicit sharing activated) with STL. For context, the results from Figure \ref{fig:string-graph-peq-sharing} are repeated as the bottom bands. While not a design goal, and not graphed out, \CFA in STL-emulation mode outperformed STL in this case; user-managed allocation reuse did not affect any of the implementations in this case.} + \label{fig:string-graph-pta-sharing} +\end{figure} + +When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in Figure \ref{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while CFA's (with sharing) is under $2 \times$, averaged across the cases shown here. Moreover, the STL's gap increases with string size, while \CFA's converges. + +\subsubsection{Test: Pass argument} + +To have introduced: STL string library forces users to think about memory management when communicating values across a function call + +STL charges a prohibitive penalty for passing a string by value. With implicit sharing active, \CFA treats this operation as normal and supported. This test illustrates a main adjantage of the \CFA sharing algorithm. It also has a case in which STL's small-string optimization provides a successful mitigation. + +\begin{figure} + \includegraphics[width=\textwidth]{string-graph-pbv.png} + \caption{Average time per iteration with one call to a function that takes a by-value string argument, comparing \CFA (having implicit sharing activated) with STL. (a) With \emph{Varying-from-1} corpus construction, in which the STL-only benefit of small-string optimization occurs, in varying degrees, at all string sizes. (b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16. [TODO: show version (b)]} + \label{fig:string-graph-pbv} +\end{figure} + +Figure \ref{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value. STL's performance worsens as string length increases, while \CFA has the same performance at all sizes. + +The \CFA cost to pass is nontrivial. The contributor is adding and removing the callee's string handle from the global list. This cost is $1.5 \times$ to $2 \times$ over STL's when small-string optimization applies, though this cost should be avoidable in the same case, given a \CFA realization of this optimization. At the larger sizes, when STL has to manage storage for the string, STL runs more than $3 \times$ slower, mainly due to time spent in the general-purpose memory allocator. + + +\subsubsection{Test: Allocate} + +This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string. It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free. The test shows that \CFA enables faster speed at a cost in memory usage. + +A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an ammortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects. (In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light. A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure. + +A garbage collector keeps allocations around for longer than the using program can reach them. By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable. Therefore, the same harness will use more memory while running under garbage collection. A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often. Tuned in this way, it spends a lot of time collecting, easily so much as to overwhelm its speed advantage from bump-pointer allocation. If it is tuned to collect rarely, then it leaves a lot of garbage allocated (waiting to be collected) but gains the advantage of little time spent doing collection. + +[TODO: find citations for the above knowledge] + +The speed for memory tradeoff is, therefore, standard for comparisons like \CFA--STL string allocations. The test verifies that it is so and quantifies the returns available. + +These tests manipulate a tuning knob that controls how much extra space to use. Specific values of this knob are not user-visible and are not presented in the results here. Instead, its two effects (amount of space used and time per operation) are shown. The independent variable is the liveness target, which is the fraction of the text buffer that is in use at the end of a collection. The allocator will expand its text buffer during a collection if the actual fraction live exceeds this target. + +This experiment's driver allocates strings by constructing a string handle as a local variable then looping over recursive calls. The time measurement is of nanoseconds per such allocating call. The arrangement of recursive calls and their fan-out (iterations per recursion level) makes some of the strings long-lived and some of them short-lived. String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls. The run presented in this section used a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one. This sizing was chosen to keep the amounts of consumed memory within the machine's last-level cache. + +\begin{figure} + \includegraphics[width=\textwidth]{string-graph-allocn.png} + \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (emph{Fixed-size} corpus construction. [MISSING] The identified clusters are for the default fraction-live target, which is 30\%. MISSING: STL results, typically just below the 0.5--0.9 CFA segment. All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.} + \label{fig:string-graph-allocn} +\end{figure} + +Figure \ref{fig:string-graph-allocn} shows the results of this experiemnt. At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL. At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint. + + + +\subsubsection{Test: Normalize} + +This test is more applied than the earlier ones. It combines the effects of several operations. It also demonstrates a case of the CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity. + +To motivate: edits being rare + +The program is doing a specialized find-replace operation on a large body of text. In the program under test, the replacement is just to erase a magic character. But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings. The challenge is to apply this packaged function across chunks taken from the large body. Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context. Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context. + +\begin{lstlisting} +void processItem( string & item ) { + // find issues in item and fix them +} +\end{lstlisting} Index: doc/theses/mike_brooks_MMath/glossary.tex =================================================================== --- doc/theses/mike_brooks_MMath/glossary.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/glossary.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,33 @@ +% Define Glossary terms (This is properly done here, in the preamble. Could be \input{} from a file...) +% Main glossary entries -- definitions of relevant terminology +\newglossaryentry{computer} +{ +name=computer, +description={A programmable machine that receives input data, + stores and manipulates the data, and provides + formatted output} +} + +% Nomenclature glossary entries -- New definitions, or unusual terminology +\newglossary*{nomenclature}{Nomenclature} +\newglossaryentry{dingledorf} +{ +type=nomenclature, +name=dingledorf, +description={A person of supposed average intelligence who makes incredibly brainless misjudgments} +} + +% List of Abbreviations (abbreviations type is built in to the glossaries-extra package) +\newabbreviation{aaaaz}{AAAAZ}{American Association of Amature Astronomers and Zoologists} + +% List of Symbols +\newglossary*{symbols}{List of Symbols} +\newglossaryentry{rvec} +{ +name={$\mathbf{v}$}, +sort={label}, +type=symbols, +description={Random vector: a location in n-dimensional Cartesian space, where each dimensional component is determined by a random process} +} + +\makeglossaries Index: doc/theses/mike_brooks_MMath/style/master.tex =================================================================== --- doc/theses/mike_brooks_MMath/style/master.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/style/master.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,10 @@ +\input{style/uw-top} + +\input{common} % CForall team's common + +\CFAStyle % CFA code-style for all languages +\lstset{language=CFA,basicstyle=\linespread{0.9}\tt} % CFA default language + +\usepackage[T1]{fontenc} % means a | character should be that, not an em dash + +\input{style/uw-bot} Index: doc/theses/mike_brooks_MMath/style/uw-bot.tex =================================================================== --- doc/theses/mike_brooks_MMath/style/uw-bot.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/style/uw-bot.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,81 @@ +% \usepackage[pdftex,pagebackref=false]{hyperref} % with basic options + +\usepackage[pagebackref=false]{hyperref} % with basic options + % N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing. +\hypersetup{ + plainpages=false, % needed if Roman numbers in frontpages + unicode=false, % non-Latin characters in Acrobat’s bookmarks + pdftoolbar=true, % show Acrobat’s toolbar? + pdfmenubar=true, % show Acrobat’s menu? + pdffitwindow=false, % window fit to page when opened + pdfstartview={FitH}, % fits the width of the page to the window + pdftitle={uWaterloo\ LaTeX\ Thesis\ Template}, % title: CHANGE THIS TEXT! +% pdfauthor={Author}, % author: CHANGE THIS TEXT! and uncomment this line +% pdfsubject={Subject}, % subject: CHANGE THIS TEXT! and uncomment this line +% pdfkeywords={keyword1} {key2} {key3}, % list of keywords, and uncomment this line if desired + pdfnewwindow=true, % links in new window + colorlinks=true, % false: boxed links; true: colored links + linkcolor=blue, % color of internal links + citecolor=green, % color of links to bibliography + filecolor=magenta, % color of file links + urlcolor=cyan % color of external links +} +\ifthenelse{\boolean{PrintVersion}}{ % for improved print quality, change some hyperref options +\hypersetup{ % override some previously defined hyperref options +% colorlinks,% + citecolor=black,% + filecolor=black,% + linkcolor=black,% + urlcolor=black} +}{} % end of ifthenelse (no else) + +% from uw template +% Exception to the rule of hyperref being the last add-on package +\usepackage[automake,toc,abbreviations]{glossaries-extra} + +% Setting up the page margins... +% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the +% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter +% margin (on binding side). While this is not an issue for electronic +% viewing, a PDF may be printed, and so we have the same page layout for +% both printed and electronic versions, we leave the gutter margin in. +% Set margins to minimum permitted by uWaterloo thesis regulations: +\setlength{\marginparwidth}{0pt} % width of margin notes +% N.B. If margin notes are used, you must adjust \textwidth, \marginparwidth +% and \marginparsep so that the space left between the margin notes and page +% edge is less than 15 mm (0.6 in.) +\setlength{\marginparsep}{0pt} % width of space between body text and margin notes +\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all +% even-numbered pages when the "twoside" printing option is selected +\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages +% when "oneside" printing is selected, and to the left of all odd-numbered +% pages when "twoside" printing is selected +\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and +% side margins as above +\raggedbottom + +% The following statement specifies the amount of space between +% paragraphs. Other reasonable specifications are \bigskipamount and \smallskipamount. +\setlength{\parskip}{\medskipamount} + +% Peter's fix. UW being broken. +\setlength{\textheight}{9in} +\setlength{\topmargin}{-0.45in} +\setlength{\headsep}{0.25in} + +% The following statement controls the line spacing. The default +% spacing corresponds to good typographic conventions and only slight +% changes (e.g., perhaps "1.2"), if any, should be made. +\renewcommand{\baselinestretch}{1} % this is the default line space setting + +% By default, each chapter will start on a recto (right-hand side) +% page. We also force each section of the front pages to start on +% a recto page by inserting \cleardoublepage commands. +% In many cases, this will require that the verso page be +% blank and, while it should be counted, a page number should not be +% printed. The following statements ensure a page number is not +% printed on an otherwise blank verso page. +\let\origdoublepage\cleardoublepage +\newcommand{\clearemptydoublepage}{% + \clearpage{\pagestyle{empty}\origdoublepage}} +\let\cleardoublepage\clearemptydoublepage Index: doc/theses/mike_brooks_MMath/style/uw-top.tex =================================================================== --- doc/theses/mike_brooks_MMath/style/uw-top.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/style/uw-top.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,11 @@ +\newcommand{\package}[1]{\textbf{#1}} % package names in bold text +\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font +\newcommand{\href}[1]{#1} % does nothing, but defines the command so the + +\usepackage{ifthen} +\newboolean{PrintVersion} +\setboolean{PrintVersion}{false} + +%\usepackage{nomencl} % For a nomenclature (optional; available from ctan.org) +\usepackage{amsmath,amssymb,amstext} +%\usepackage[pdftex]{graphicx} Index: doc/theses/mike_brooks_MMath/thesis-frontpgs.tex =================================================================== --- doc/theses/mike_brooks_MMath/thesis-frontpgs.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/thesis-frontpgs.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,128 @@ +% T I T L E P A G E +% ------------------- +% Last updated June 14, 2017, by Stephen Carr, IST-Client Services +% The title page is counted as page `i' but we need to suppress the +% page number. Also, we don't want any headers or footers. +\pagestyle{empty} +\pagenumbering{roman} + +% The contents of the title page are specified in the "titlepage" +% environment. +\begin{titlepage} + \begin{center} + \vspace*{1.0cm} + % TODO: punch up the title, thinking getting interest in the department-wide posting of my presentation + % Modern collections for C + \Huge + {\bf \CFA Container Library } + + \vspace*{1.0cm} + + \normalsize + by \\ + + \vspace*{1.0cm} + + \Large + Michael Leslie Brooks \\ + + \vspace*{3.0cm} + + \normalsize + A thesis \\ + presented to the University of Waterloo \\ + in fulfillment of the \\ + thesis requirement for the degree of \\ + Master of Mathematics \\ + in \\ + Computer Science \\ + + \vspace*{2.0cm} + + Waterloo, Ontario, Canada, 2022 \\ + + \vspace*{1.0cm} + + \copyright\ Michael Leslie Brooks 2022 \\ + \end{center} +\end{titlepage} + +% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii' +\pagestyle{plain} +\setcounter{page}{2} + +\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed. +% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary. + + + + +% D E C L A R A T I O N P A G E +% ------------------------------- + % The following is a sample Delaration Page as provided by the GSO + % December 13th, 2006. It is designed for an electronic thesis. + \noindent +I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. + + \bigskip + + \noindent +I understand that my thesis may be made electronically available to the public. + +\cleardoublepage + +% A B S T R A C T +% --------------- + +\begin{center}\textbf{Abstract}\end{center} + +TODO + +\cleardoublepage + +% A C K N O W L E D G E M E N T S +% ------------------------------- + +\begin{center}\textbf{Acknowledgements}\end{center} + +TODO. +\cleardoublepage + +% D E D I C A T I O N +% ------------------- + +\begin{center}\textbf{Dedication}\end{center} + +TODO. +\cleardoublepage + +% T A B L E O F C O N T E N T S +% --------------------------------- +\renewcommand\contentsname{Table of Contents} +\tableofcontents +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% L I S T O F T A B L E S +% --------------------------- +\addcontentsline{toc}{chapter}{List of Tables} +\listoftables +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% L I S T O F F I G U R E S +% ----------------------------- +\addcontentsline{toc}{chapter}{List of Figures} +\listoffigures +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) +% ----------------------------- +\printglossaries +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% Change page numbering back to Arabic numerals +\pagenumbering{arabic} + Index: doc/theses/mike_brooks_MMath/thesis.tex =================================================================== --- doc/theses/mike_brooks_MMath/thesis.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) +++ doc/theses/mike_brooks_MMath/thesis.tex (revision 8e819a94d8115bf4605e13dfbb79f504db752d6e) @@ -0,0 +1,107 @@ +% based on: +% uWaterloo Thesis Template for LaTeX +% Last Updated June 14, 2017 by Stephen Carr, IST Client Services +% FOR ASSISTANCE, please send mail to rt-IST-CSmathsci@ist.uwaterloo.ca + +\documentclass[letterpaper,12pt,titlepage,oneside,final]{book} + +\input{style/master} +\input{glossary} + +\usepackage{subfiles} + +\begin{document} + +\input{thesis-frontpgs} + + + +% %====================================================================== +% \chapter{Introduction} +% %====================================================================== + +% Tation exerci delenit ullamcorper at feugiat ullamcorper, ullamcorper elit vulputate iusto esse luptatum duis autem esse nulla qui. Volutpat praesent et at nisl ut in consequat blandit vel augue ut dolor illum facilisis zzril ipsum, augue odio, accumsan ea augue molestie lobortis zzril laoreet. Ex duis, te velit illum odio, nisl qui consequat aliquip qui blandit hendrerit. Ea dolor nonummy ullamcorper nulla lorem tation laoreet in ea, ullamcorper vel consequat zzril delenit quis dignissim, vulputate tincidunt ut." + +%====================================================================== +\chapter{Array} +%====================================================================== + +\section{Features Added} \subfile{content/array/features/sec.tex} +\section{Multidimensional implementation} \label{toc:mdimpl} \subfile{content/array/mdim/sec.tex} + + +%====================================================================== +\chapter{String} +%====================================================================== + +\subfile{content/string/string-master.tex} + + + +% %---------------------------------------------------------------------- +% % END MATERIAL +% %---------------------------------------------------------------------- + +% % B I B L I O G R A P H Y +% % ----------------------- + +% % The following statement selects the style to use for references. It controls the sort order of the entries in the bibliography and also the formatting for the in-text labels. +% \bibliographystyle{plain} +% % This specifies the location of the file containing the bibliographic information. +% % It assumes you're using BibTeX (if not, why not?). +% \cleardoublepage % This is needed if the book class is used, to place the anchor in the correct page, +% % because the bibliography will start on its own page. +% % Use \clearpage instead if the document class uses the "oneside" argument +% \phantomsection % With hyperref package, enables hyperlinking from the table of contents to bibliography +% % The following statement causes the title "References" to be used for the bibliography section: +% \renewcommand*{\bibname}{References} + +% % Add the References to the Table of Contents +% \addcontentsline{toc}{chapter}{\textbf{References}} + + + +% \bibliography{thesis} +% % Tip 5: You can create multiple .bib files to organize your references. +% % Just list them all in the \bibliogaphy command, separated by commas (no spaces). + +% % The following statement causes the specified references to be added to the bibliography% even if they were not +% % cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional). +% \nocite{*} + + + +% % The \appendix statement indicates the beginning of the appendices. +% \appendix +% % Add a title page before the appendices and a line in the Table of Contents +% \chapter*{APPENDICES} +% \addcontentsline{toc}{chapter}{APPENDICES} +% %====================================================================== +% \chapter[PDF Plots From Matlab]{Matlab Code for Making a PDF Plot} +% \label{AppendixA} +% % Tip 4: Example of how to get a shorter chapter title for the Table of Contents +% %====================================================================== +% \section{Using the GUI} +% Properties of Matab plots can be adjusted from the plot window via a graphical interface. Under the Desktop menu in the Figure window, select the Property Editor. You may also want to check the Plot Browser and Figure Palette for more tools. To adjust properties of the axes, look under the Edit menu and select Axes Properties. + +% To set the figure size and to save as PDF or other file formats, click the Export Setup button in the figure Property Editor. + +% \section{From the Command Line} +% All figure properties can also be manipulated from the command line. Here's an example: +% \begin{verbatim} +% x=[0:0.1:pi]; +% hold on % Plot multiple traces on one figure +% plot(x,sin(x)) +% plot(x,cos(x),'--r') +% plot(x,tan(x),'.-g') +% title('Some Trig Functions Over 0 to \pi') % Note LaTeX markup! +% legend('{\it sin}(x)','{\it cos}(x)','{\it tan}(x)') +% hold off +% set(gca,'Ylim',[-3 3]) % Adjust Y limits of "current axes" +% set(gcf,'Units','inches') % Set figure size units of "current figure" +% set(gcf,'Position',[0,0,6,4]) % Set figure width (6 in.) and height (4 in.) +% cd n:\thesis\plots % Select where to save +% print -dpdf plot.pdf % Save as PDF +% \end{verbatim} + +\end{document}