Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision e1107ecfb2798a4e827de7583da6ca99b974d239) +++ doc/theses/mike_brooks_MMath/array.tex (revision 04c63401a743dfe8e00dff6cfac46ecbc46c6647) @@ -1096,18 +1096,17 @@ both are containers wrapping subordinate objects. Any arbitrary object type, like @string@, can be an array element or structure member. -A consequence is that the lifetime of the container must match with its subordinate objects. -For example, all elements and members must be initialized/uninitialized implicitly as part of the container's allocation/deallocation. +A consequence is that the lifetime of the container must match with its subordinate objects: all elements and members must be initialized/uninitialized implicitly as part of the container's allocation/deallocation. Modern programming languages implicitly perform these operations via a type's constructor and destructor. -Therefore, \CFA must assure these lifetime operations are called, regardless of the lexical nesting depth of containers and their components. - -Preexisting \CFA mechanisms achieve this requirement, but with poor performance (discussed shortly). +Therefore, \CFA must assure that an array's subordinate objects' lifetime operations are called. + +Preexisting \CFA mechanisms achieve this requirement, but with poor performance. Furthermore, advanced array users need an exception to the basic mechanism, which does not occur with other aggregates. -Hence, there are subtleties in supporting an element's lifecycle with arrays. - -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 (default) constructor, copy constructor, assignment operator, and destructor (like \CC). +Hence, arrays introduce subleties in supporting an element's lifecycle. + +The preexisting \CFA support for contained-element lifecycle is based on recursive occurrences of the object-type (@otype@) pseudo-trait. +A type is an @otype@, if it provides a default (parameterless) constructor, copy constructor, assignment operator, and destructor (like \CC). When declaring a structure with @otype@ members, the compiler implicitly generates implementations of the four @otype@ functions for the outer structure. Then the generated default constructor for the outer structure calls the default constructor for each member, and the other @otype@ functions work similarly. -For a member that is a C array, these calls occur in a loop for each array element, which even for VLAs. +For a member that is a C array, these calls occur in a loop for each array element, which even works for VLAs. 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 asserted to be an @otype@ (which is implicit in the syntax, @forall(T)@). The \CFA array has the simplified form (similar to one seen before): @@ -1126,9 +1125,6 @@ array5( array5( array5( float ) ) ) \end{cfa} -its lifecycle functions, under the @otype@-recursion pattern, is shown in \VRef[Figure]{}, where -\begin{cfa} -array5(array5(array5(float))) -\end{cfa} -has 256 leaves. +the first few steps of the compiler's work to find the lifecycle functions, under the @otype@-recursion pattern, are shown in \VRef[Figure]{f:OtypeRecursionBlowup}. +All the work needed for the full @float@-cube would have 256 leaves. %array5(T) offers @@ -1254,9 +1250,11 @@ \end{cfa} \end{tabular} -\caption{write a caption} +\caption{Exponential thunk generation under the otype-recursion pattern. + Each time that one type's function (\eg ctor) uses another type's function, the \CFA compiler generates a thunk, to capture the used function's dependencies, presented according to the using function's need. + So, each non-leaf line represents a generated thunk and every line represents a search request for the resolver to find a satisfying function.} +\label{f:OtypeRecursionBlowup} \end{figure} -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. +So the @otype@-recursion pattern seeks a quantity of helper functions, and generates a quantity of thunks, that are exponential in the number of dimensions. Anecdotal experience with this solution found the resulting compile times annoyingly slow at three dimensions, and unusable at four. @@ -1264,7 +1262,6 @@ Consider how @array5(float)@'s default constructor is getting all four lifecycle assertions about the element type, @float@. It only needs @float@'s default constructor; -all the operations are never used. -%For the assignment operator, it turns out that today's RAII pattern has it using a copy constructor, assignment operator and destructor. -Current by the \CFA team aims to improve this situation. +the full set of operations is never used. +Current work by the \CFA team aims to improve this situation. Therefore, a workaround is needed for now. @@ -1305,8 +1302,9 @@ \end{tabular} \end{cquote} -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's default constructor called \emph{automatically} is simplistic. +Moreover, the assignment operator is skipped, to avoid hitting a lingering growth case. +Skipping assignment is tolerable because array assignment is not a common operation. +With this solution, the critical lifecycle functions are available, with no growth in thunk creation. + +Finally, the intuition that a programmer using an array always wants the elements' default constructor called \emph{automatically} is simplistic. Arrays exist to store different values at each position. So, array initialization needs to let the programmer provide different constructor arguments to each element. @@ -1315,21 +1313,20 @@ void ?{}( worker & ) = void; // remove default constructor void ?{}( worker &, int id ); -array( worker, 5 ) ws = {}; // no initialization -for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread's id -\end{cfa} -Note the ability to explicitly call a constructor in \CFA, unlike in \CC. - -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 / elided default constructor. - The problem is that a thread type needs to fork a thread at the \emph{end} of each constructor and join with a thread at the \emph{start} of each destructor. - Therefore, there is a conflict between the implicit actions by a builtin @thread@ type and a user's desire to remove actions with respect to allocation/deallocation. -\item - C initialization: \lstinline|array(worker, 5) ws @= {};|, which ignores all \CFA initialization and uses C empty initialization. - This option does achieve the desired semantics on the construction side. - But on destruction side, the desired semantics is for implicit destructor calls to continue for the join operation. - C initialization disables \emph{all} implicit lifecycle management; whereas, the goal is to disable only the implicit construction. -\end{itemize} +array( worker, 5 ) ws = @{}@; // rejected; but desire is for no initialization yet +for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread, giving id +\end{cfa} +Note the use of the \CFA explicit constructor call, analogous to \CC's placement-@new@. +This call is where initialization is desired, and not at the declaration of @ws@. +The attempt to initialize from nothing (equivalent to dropping @= {}@ altogether) is invalid because the @worker@ type removes the default constructor. +The @worker@ type is designed this way to work with the threading system. +A thread type forks a thread at the end of each constructor and joins with it at the start of each destructor. +But a @worker@ cannot begin its forked-thead work without knowing its @id@. +Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions. + +Another \CFA feature may, at first, seem viable for initializing the array @ws@, though on closer inspection, it is not. +C initialization, \lstinline|array(worker, 5) ws @= {};|, ignores all \CFA lifecycle management and uses C empty initialization. +This option does achieve the desired semantics on the construction side. +But on destruction side, the desired semantics is for implicit destructor calls to continue, to keep the join operation tied to lexical scope. +C initialization disables \emph{all} implicit lifecycle management, but the goal is to disable only the implicit construction. To fix this problem, I enhanced the \CFA standard library to provide the missing semantics, available in either form: @@ -1341,5 +1338,5 @@ Two forms are available, to parallel the development of this feature in \uCpp. Originally \uCpp offered only the @ws1@ form, using the class-template @uNoCtor@ equivalent to \CFA's @uninit@. -More recently, \uCpp was extended with declaration macro, @uArray@, with usage similar to the @ws2@ case. +More recently, \uCpp was extended with the declaration macro, @uArray@, with usage similar to the @ws2@ case. Based on experience piloting @uArray@ as a replacement of @uNoCtor@, it might be possible to remove the first option.