Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision 174a11a642d13a8e4b4d13b64fca611c622ce2f5) +++ doc/theses/mike_brooks_MMath/array.tex (revision e1107ecfb2798a4e827de7583da6ca99b974d239) @@ -1091,28 +1091,27 @@ - \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)@). +An array is an aggregate, like a structure; +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. +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). +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). +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. +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): \begin{cfa} -forall( T* ) // non-otype element, no lifecycle functions +forall( T * ) // non-otype element, no lifecycle functions // forall( T ) // otype element, lifecycle functions asserted struct array5 { @@ -1120,114 +1119,156 @@ }; \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: +Being a structure 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. +For example, in a cube of @float@: \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 - +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. + +%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 + +\begin{figure} +\centering +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}lll@{}} +\begin{cfa}[deletekeywords={default}] float offers -1 parameterless ctor +1 default ctor 2 copy ctor 3 asgt 4 dtor -array5(T) offers -1 parameterless ctor, which asks for T to have - 1 parameterless ctor + + + + + + + + + + + + + + + + + + + + + + + +\end{cfa} +& +\begin{cfa}[deletekeywords={default}] +array5(float) has +1 default ctor, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor -2 copy ctor, which asks for T to have - 1 parameterless ctor +2 copy ctor, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor -3 asgt, which asks for T to have - 1 parameterless ctor +3 asgt, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor -4 dtor, which asks for T to have - 1 parameterless ctor +4 dtor, using float's + 1 default 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 - + + + + + + + +\end{cfa} +& +\begin{cfa}[deletekeywords={default}] array5(array5(float)) has -1 parameterless ctor, which gets array5(float)'s - 1 parameterless ctor, which gets float's - 1 parameterless ctor +1 default ctor, using array5(float)'s + 1 default ctor, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor - 2 copy ctor, which gets float's - 1 parameterless ctor + 2 copy ctor, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor - 3 asgt, which gets float's - 1 parameterless ctor + 3 asgt, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor - 4 dtor, which gets float's - 1 parameterless ctor + 4 dtor, using float's + 1 default ctor 2 copy ctor 3 asgt 4 dtor -2 copy ctor, which gets array5(float)'s +2 copy ctor, using array5(float)'s ... 4 children, 16 leaves -3 asgt, which gets array5(float)'s +3 asgt, using array5(float)'s ... 4 children, 16 leaves -4 dtor, which gets array5(float)'s +4 dtor, using array5(float)'s ... 4 children, 16 leaves (64 leaves) - -array5(array5(array5(float))) has -...(256 leaves) -\end{cfa} +\end{cfa} +\end{tabular} +\caption{write a caption} +\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. -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 +So the @otype@-recursion pattern generates a quantity of thunks that is 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. + +The issue is that the otype-recursion pattern uses more assertions than needed. +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. +Therefore, a workaround is needed for now. + +The workaround is to provide a default constructor, copy constructor and destructor, defined with lean, bespoke assertions: +\begin{cquote} \begin{tabular}{@{}l@{\hspace{0.5in}}l@{}} \begin{cfa} @@ -1263,41 +1304,43 @@ \end{cfa} \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 constructors called \emph{automatically} is simplistic. +Finally, the intuition that a programmer using an array always wants element's default constructor 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} +So, array initialization needs to let the programmer provide different constructor arguments to each element. +\begin{cfa} +thread worker { int id; }; +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 / 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). + 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 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. + 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} -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@ }; +To fix this problem, 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. +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. +Based on experience piloting @uArray@ as a replacement of @uNoCtor@, it might be possible to remove the first option. % note to Mike, I have more fragments on some details available in push24\fragments\uNoCtor.txt