Changeset 04c6340 for doc


Ignore:
Timestamp:
Nov 7, 2024, 12:29:33 PM (6 weeks ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
master
Children:
83a581a
Parents:
e1107ec
Message:

Array, lifecycle: more proofreading

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/mike_brooks_MMath/array.tex

    re1107ec r04c6340  
    10961096both are containers wrapping subordinate objects.
    10971097Any arbitrary object type, like @string@, can be an array element or structure member.
    1098 A consequence is that the lifetime of the container must match with its subordinate objects.
    1099 For example, all elements and members must be initialized/uninitialized implicitly as part of the container's allocation/deallocation.
     1098A 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.
    11001099Modern programming languages implicitly perform these operations via a type's constructor and destructor.
    1101 Therefore, \CFA must assure these lifetime operations are called, regardless of the lexical nesting depth of containers and their components.
    1102 
    1103 Preexisting \CFA mechanisms achieve this requirement, but with poor performance (discussed shortly).
     1100Therefore, \CFA must assure that an array's subordinate objects' lifetime operations are called.
     1101
     1102Preexisting \CFA mechanisms achieve this requirement, but with poor performance.
    11041103Furthermore, advanced array users need an exception to the basic mechanism, which does not occur with other aggregates.
    1105 Hence, there are subtleties in supporting an element's lifecycle with arrays.
    1106 
    1107 The preexisting \CFA support for contained-element lifecycle is based on a recursive implementation of the object-type (@otype@) pseudo-trait.
    1108 A type is an @otype@, if it provides a parameterless (default) constructor, copy constructor, assignment operator, and destructor (like \CC).
     1104Hence, arrays introduce subleties in supporting an element's lifecycle.
     1105
     1106The preexisting \CFA support for contained-element lifecycle is based on recursive occurrences of the object-type (@otype@) pseudo-trait.
     1107A type is an @otype@, if it provides a default (parameterless) constructor, copy constructor, assignment operator, and destructor (like \CC).
    11091108When declaring a structure with @otype@ members, the compiler implicitly generates implementations of the four @otype@ functions for the outer structure.
    11101109Then the generated default constructor for the outer structure calls the default constructor for each member, and the other @otype@ functions work similarly.
    1111 For a member that is a C array, these calls occur in a loop for each array element, which even for VLAs.
     1110For a member that is a C array, these calls occur in a loop for each array element, which even works for VLAs.
    11121111This 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)@).
    11131112The \CFA array has the simplified form (similar to one seen before):
     
    11261125array5( array5( array5( float ) ) )
    11271126\end{cfa}
    1128 its lifecycle functions, under the @otype@-recursion pattern, is shown in \VRef[Figure]{}, where
    1129 \begin{cfa}
    1130 array5(array5(array5(float)))
    1131 \end{cfa}
    1132 has 256 leaves.
     1127the 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}.
     1128All the work needed for the full @float@-cube would have 256 leaves.
    11331129
    11341130%array5(T) offers
     
    12541250\end{cfa}
    12551251\end{tabular}
    1256 \caption{write a caption}
     1252\caption{Exponential thunk generation under the otype-recursion pattern.
     1253        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.
     1254        So, each non-leaf line represents a generated thunk and every line represents a search request for the resolver to find a satisfying function.}
     1255\label{f:OtypeRecursionBlowup}
    12571256\end{figure}
    12581257
    1259 Each xxx corresponds to a generated thunk.
    1260 So the @otype@-recursion pattern generates a quantity of thunks that is exponential in the number of dimensions.
     1258So the @otype@-recursion pattern seeks a quantity of helper functions, and generates a quantity of thunks, that are exponential in the number of dimensions.
    12611259Anecdotal experience with this solution found the resulting compile times annoyingly slow at three dimensions, and unusable at four.
    12621260
     
    12641262Consider how @array5(float)@'s default constructor is getting all four lifecycle assertions about the element type, @float@.
    12651263It only needs @float@'s default constructor;
    1266 all the operations are never used.
    1267 %For the assignment operator, it turns out that today's RAII pattern has it using a copy constructor, assignment operator and destructor.
    1268 Current by the \CFA team aims to improve this situation.
     1264the full set of operations is never used.
     1265Current work by the \CFA team aims to improve this situation.
    12691266Therefore, a workaround is needed for now.
    12701267
     
    13051302\end{tabular}
    13061303\end{cquote}
    1307 Moreover, the assignment operator is skipped, because array assignment is not a common operation.
    1308 This way, the critical lifecycle functions are available, with no growth in thunk creation.
    1309 
    1310 Finally, the intuition that a programmer using an array always wants element's default constructor called \emph{automatically} is simplistic.
     1304Moreover, the assignment operator is skipped, to avoid hitting a lingering growth case.
     1305Skipping assignment is tolerable because array assignment is not a common operation.
     1306With this solution, the critical lifecycle functions are available, with no growth in thunk creation.
     1307
     1308Finally, the intuition that a programmer using an array always wants the elements' default constructor called \emph{automatically} is simplistic.
    13111309Arrays exist to store different values at each position.
    13121310So, array initialization needs to let the programmer provide different constructor arguments to each element.
     
    13151313void ?{}( worker & ) = void; // remove default constructor
    13161314void ?{}( worker &, int id );
    1317 array( worker, 5 ) ws = {}; // no initialization
    1318 for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread's id
    1319 \end{cfa}
    1320 Note the ability to explicitly call a constructor in \CFA, unlike in \CC.
    1321 
    1322 Two \CFA features may, at first, seem viable for initializing the array @ws@, but on closer inspection, they are not.
    1323 \begin{itemize}
    1324 \item
    1325         Empty initializer / elided default constructor.
    1326         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.
    1327         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.
    1328 \item
    1329         C initialization: \lstinline|array(worker, 5) ws @= {};|, which ignores all \CFA initialization and uses C empty initialization.
    1330         This option does achieve the desired semantics on the construction side.
    1331         But on destruction side, the desired semantics is for implicit destructor calls to continue for the join operation.
    1332         C initialization disables \emph{all} implicit lifecycle management; whereas, the goal is to disable only the implicit construction.
    1333 \end{itemize}
     1315array( worker, 5 ) ws = @{}@; // rejected; but desire is for no initialization yet
     1316for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread, giving id
     1317\end{cfa}
     1318Note the use of the \CFA explicit constructor call, analogous to \CC's placement-@new@.
     1319This call is where initialization is desired, and not at the declaration of @ws@.
     1320The attempt to initialize from nothing (equivalent to dropping @= {}@ altogether) is invalid because the @worker@ type removes the default constructor.
     1321The @worker@ type is designed this way to work with the threading system.
     1322A thread type forks a thread at the end of each constructor and joins with it at the start of each destructor.
     1323But a @worker@ cannot begin its forked-thead work without knowing its @id@.
     1324Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions.
     1325
     1326Another \CFA feature may, at first, seem viable for initializing the array @ws@, though on closer inspection, it is not.
     1327C initialization, \lstinline|array(worker, 5) ws @= {};|, ignores all \CFA lifecycle management and uses C empty initialization.
     1328This option does achieve the desired semantics on the construction side.
     1329But on destruction side, the desired semantics is for implicit destructor calls to continue, to keep the join operation tied to lexical scope.
     1330C initialization disables \emph{all} implicit lifecycle management, but the goal is to disable only the implicit construction.
    13341331
    13351332To fix this problem, I enhanced the \CFA standard library to provide the missing semantics, available in either form:
     
    13411338Two forms are available, to parallel the development of this feature in \uCpp.
    13421339Originally \uCpp offered only the @ws1@ form, using the class-template @uNoCtor@ equivalent to \CFA's @uninit@.
    1343 More recently, \uCpp was extended with declaration macro, @uArray@, with usage similar to the @ws2@ case.
     1340More recently, \uCpp was extended with the declaration macro, @uArray@, with usage similar to the @ws2@ case.
    13441341Based on experience piloting @uArray@ as a replacement of @uNoCtor@, it might be possible to remove the first option.
    13451342
Note: See TracChangeset for help on using the changeset viewer.