Changeset 97ac01d3 for doc/theses/mike_brooks_MMath

Timestamp:

Nov 5, 2024, 7:27:44 PM (10 days ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

5ba756c

Parents:

7d95bce9

Message:

Thesis, array: add section on lifecycle

File:

• doc/theses/mike_brooks_MMath/array.tex (modified) (1 diff)

doc/theses/mike_brooks_MMath/array.tex

@@ -1092 +1092 @@
 
 
-
+\section{Array lifecycle}
+
+An array is an aggregate, like a struct.
+Both wrap subordinate objects.
+An arbitrary other type, like @string@, can be used as a struct member or an array element.
+When it is, that type's lifecycle assumptions must be respected.
+In the case of @string@, it would be disasterous to start calling string-management functions on uninitialized storage.
+The @string@ type provides its constructors and destructor;
+\CFA is supposed to provide a reasonable assurance that they will be called, even if the string is wrapped in something else, even if the user-programmer isn't thinking about it.
+
+Preexisting \CFA mechanisms achieve this requirement in correctness, but not with reasonable performance.
+Furthermore, advanced users of arrays need an exception to the bluntly-stated requirement, which does not come up when working with other aggregates.
+So the \CFA array has subtleties in its support for element lifecycle.
+
+The preexisting \CFA support for contained-element lifecycle is based on a recursive implementation of the object-type (otype) pseudo-trait.
+A type is an otype if it provides a parameterless constructor, copy constructor, assignment operator and destructor.
+When declaring a struct whose members are all otypes, the compiler generates implementations of the four otype functions for the outer struct.
+The generated parameterless constructor for the outer struct calls the parameterless constructor for each memeber, and the other otype functions work similarly.
+For a member that is a C array, these calls occur in loops, which work correctly for dynamic bounds.
+This logic works the same, whether the member is a concrete type (that happens to be an otype) or if the member is a polymorphic type variable asserted to be an otype (which is implicit in the default syntax, @forall(T)@).
+The \CFA array has the simplified form (similar to one seen before):
+\begin{cfa}
+forall( T* )   // non-otype element, no lifecycle functions
+// forall( T )  // otype element, lifecycle functions asserted
+struct array5 {
+        T __items[ 5 ];
+};
+\end{cfa}
+Being a struct with a C-array member, using the otype-form declaration for @T@ causes @array5(float)@ to implement otype too.
+
+But this otype-recursion pattern has a performance issue.
+A cube of @float@ is, in the running simplification:
+\begin{cfa}
+array5( array5( array5( float ) ) )
+\end{cfa}
+Its lifecycle functions, under the otype-recursion pattern, would be:
+\begin{cfa}
+TODO: rework this crude exposition into a readable figure
+
+float offers
+1 parameterless ctor
+2 copy ctor
+3 asgt
+4 dtor
+
+array5(T) offers
+1 parameterless ctor, which asks for T to have
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+2 copy ctor, which asks for T to have
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+3 asgt, which asks for T to have
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+4 dtor, which asks for T to have
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+
+array5(float) has
+1 parameterless ctor, which gets float's
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+2 copy ctor, which gets float's
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+3 asgt, which gets float's
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+4 dtor, which gets float's
+        1 parameterless ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+
+array5(array5(float)) has
+1 parameterless ctor, which gets array5(float)'s
+        1 parameterless ctor, which gets float's
+                1 parameterless ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        2 copy ctor, which gets float's
+                1 parameterless ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        3 asgt, which gets float's
+                1 parameterless ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        4 dtor, which gets float's
+                1 parameterless ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+2 copy ctor, which gets array5(float)'s
+        ... 4 children, 16 leaves
+3 asgt, which gets array5(float)'s
+        ... 4 children, 16 leaves
+4 dtor, which gets array5(float)'s
+        ... 4 children, 16 leaves
+(64 leaves)
+
+array5(array5(array5(float))) has
+...(256 leaves)
+\end{cfa}
+
+Each xxx corresponds to a generated thunk.
+So the otype-recursion pattern generates a quantity of thunks that is exponential in the number of dimensions.
+Anecdotal experience with this solutuion found the resulting compile times annoying at three dimensions, and unusable at four.
+
+But the otype-recursion pattern uses more assertions than are really needed.
+Consider how @array5(float)@'s parameterless constructor is getting all four lifecycle assertions about the element type, @float@.
+It only needs @float@'s parameterless constructor; it is getting a destructor (among others) and never using it.
+The same idea applies to the copy constructor and the destructor.
+For the assignment operator, it turns out that today's RAII pattern has it using a copy constructor, assignment operator and destructor.
+Concurrent work on the \CFA team aims to improve this whole situation.
+A workaround is needed for now.
+
+The workaround is to provide parameterless constructor, copy constructor and destructor, defined with lean, bespoke assertions:
+
+\noindent
+\begin{tabular}{@{}l@{\hspace{0.5in}}l@{}}
+\begin{cfa}
+// autogenerated for otype-recursion:
+forall( T )
+void ?{}( array5(T) & this ) {
+        for (i; 5) { ( this[i] ){}; }
+}
+forall( T )
+void ?{}( array5(T) & this, array5(T) & src ) {
+        for (i; 5) { ( this[i] ){ src[i] }; }
+}
+forall( T )
+void ^?{}( array5(T) & this ) {
+        for (i; 5) { ^( this[i] ){}; }
+}
+\end{cfa}
+&
+\begin{cfa}
+// lean, bespoke:
+forall( T* | { void @?{}( T & )@; } )
+void ?{}( array5(T) & this ) {
+        for (i; 5) { ( this[i] ){}; }
+}
+forall( T* | { void @?{}( T &, T )@; } )
+void ?{}( array5(T) & this, array5(T) & src ) {
+        for (i; 5) { ( this[i] ){ src[i] }; }
+}
+forall( T* | { void @?{}( T & )@; } )
+void ^?{}( array5(T) & this ) {
+        for (i; 5) { ^( this[i] ){}; }
+}
+\end{cfa}
+\end{tabular}
+Moreover, the assignment operator is skipped, because array assignment is not a common operation.
+This way, the critical lifecycle functions are available, with no growth in thunk creation.
+
+Finally, the intuition that a programmer using an array always wants element constructors called \emph{automatically} is simplistic.
+Arrays exist to store different values at each position.
+So, an array initialization, in general, needs to let the prorammer provide different constructor arguments to each element.
+\begin{cfa}
+thread worker;
+void ?{}( worker & ) = void;
+void ?{}( worker &, int worker_num );
+array(worker, 5) ws @= ???@;
+for (i; 5) ( ws[i] ){ @i@ };
+\end{cfa}
+
+Two \CFA features may, at first, seem viable for initializing the array @ws@, but on closer inspection, they are not.
+\begin{itemize}
+\item
+        Empty initializer / default constructor: \lstinline{array(worker, 5) ws;}.
+        This option does not work with the semantics of a thread: it has forked as soon as the constructor returns.
+        The type does not provide a parameterless constructor because it is not possible to fork the thread until the @worker_num@ parameter is received.
+\item
+        C initialization: \lstinline{array(worker, 5) ws AT EQUALS OPEN CLOSE;} (TODO: typeset at-equals).
+        This option does achieve the desired semantics on the construction side.
+        But destruction side, the desired semantics is for implicit destructor calls to continue, because with threads, the destructor is a join operation.
+        C initialization disables \emph{all} implicit lifecycle management; here, the goal is to disable only the implicit construction.
+\end{itemize}
+
+So, I enhanced the \CFA standard library to provide the missing semantics, available in either form:
+\begin{cfa}
+array(@uninit@(worker), 5) ws1;
+array(worker, 5) ws2 = { @delay_init@ };
+\end{cfa}
+Both cause the @ws@-construction-time implicit call chain to stop before reaching a @worker@ constructor, while leaving the implicit destruction calls intact.
+Two forms are available, to parallel the development of this feature in \uCpp.
+Originally \uCpp offered only the @ws1@ form, there with the class-tempate @uNoCtor@ replacing \CFA's @uninit@.
+More recently, \uCpp got a declaration-helping macro, @uArray@, whose usage similar to the @ws2@ case.
+Based on results of piloting @uArray@ (as a replacement of @uNoCtor@), future work may choose to remove one of the options.
+
+% note to Mike, I have more fragments on some details available in push24\fragments\uNoCtor.txt
 
 \section{Comparison with other arrays}