- Timestamp:
- Nov 7, 2024, 12:29:33 PM (6 weeks ago)
- Branches:
- master
- Children:
- 83a581a
- Parents:
- e1107ec
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/mike_brooks_MMath/array.tex
re1107ec r04c6340 1096 1096 both are containers wrapping subordinate objects. 1097 1097 Any 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. 1098 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. 1100 1099 Modern programming languages implicitly perform these operations via a type's constructor and destructor. 1101 Therefore, \CFA must assure th ese 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).1100 Therefore, \CFA must assure that an array's subordinate objects' lifetime operations are called. 1101 1102 Preexisting \CFA mechanisms achieve this requirement, but with poor performance. 1104 1103 Furthermore, 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 implementationof 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).1104 Hence, arrays introduce subleties in supporting an element's lifecycle. 1105 1106 The preexisting \CFA support for contained-element lifecycle is based on recursive occurrences of the object-type (@otype@) pseudo-trait. 1107 A type is an @otype@, if it provides a default (parameterless) constructor, copy constructor, assignment operator, and destructor (like \CC). 1109 1108 When declaring a structure with @otype@ members, the compiler implicitly generates implementations of the four @otype@ functions for the outer structure. 1110 1109 Then 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.1110 For a member that is a C array, these calls occur in a loop for each array element, which even works for VLAs. 1112 1111 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)@). 1113 1112 The \CFA array has the simplified form (similar to one seen before): … … 1126 1125 array5( array5( array5( float ) ) ) 1127 1126 \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. 1127 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}. 1128 All the work needed for the full @float@-cube would have 256 leaves. 1133 1129 1134 1130 %array5(T) offers … … 1254 1250 \end{cfa} 1255 1251 \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} 1257 1256 \end{figure} 1258 1257 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. 1258 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. 1261 1259 Anecdotal experience with this solution found the resulting compile times annoyingly slow at three dimensions, and unusable at four. 1262 1260 … … 1264 1262 Consider how @array5(float)@'s default constructor is getting all four lifecycle assertions about the element type, @float@. 1265 1263 It 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. 1264 the full set of operations is never used. 1265 Current work by the \CFA team aims to improve this situation. 1269 1266 Therefore, a workaround is needed for now. 1270 1267 … … 1305 1302 \end{tabular} 1306 1303 \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. 1304 Moreover, the assignment operator is skipped, to avoid hitting a lingering growth case. 1305 Skipping assignment is tolerable because array assignment is not a common operation. 1306 With this solution, the critical lifecycle functions are available, with no growth in thunk creation. 1307 1308 Finally, the intuition that a programmer using an array always wants the elements' default constructor called \emph{automatically} is simplistic. 1311 1309 Arrays exist to store different values at each position. 1312 1310 So, array initialization needs to let the programmer provide different constructor arguments to each element. … … 1315 1313 void ?{}( worker & ) = void; // remove default constructor 1316 1314 void ?{}( 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} 1315 array( worker, 5 ) ws = @{}@; // rejected; but desire is for no initialization yet 1316 for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread, giving id 1317 \end{cfa} 1318 Note the use of the \CFA explicit constructor call, analogous to \CC's placement-@new@. 1319 This call is where initialization is desired, and not at the declaration of @ws@. 1320 The attempt to initialize from nothing (equivalent to dropping @= {}@ altogether) is invalid because the @worker@ type removes the default constructor. 1321 The @worker@ type is designed this way to work with the threading system. 1322 A thread type forks a thread at the end of each constructor and joins with it at the start of each destructor. 1323 But a @worker@ cannot begin its forked-thead work without knowing its @id@. 1324 Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions. 1325 1326 Another \CFA feature may, at first, seem viable for initializing the array @ws@, though on closer inspection, it is not. 1327 C initialization, \lstinline|array(worker, 5) ws @= {};|, ignores all \CFA lifecycle management and uses C empty initialization. 1328 This option does achieve the desired semantics on the construction side. 1329 But on destruction side, the desired semantics is for implicit destructor calls to continue, to keep the join operation tied to lexical scope. 1330 C initialization disables \emph{all} implicit lifecycle management, but the goal is to disable only the implicit construction. 1334 1331 1335 1332 To fix this problem, I enhanced the \CFA standard library to provide the missing semantics, available in either form: … … 1341 1338 Two forms are available, to parallel the development of this feature in \uCpp. 1342 1339 Originally \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.1340 More recently, \uCpp was extended with the declaration macro, @uArray@, with usage similar to the @ws2@ case. 1344 1341 Based on experience piloting @uArray@ as a replacement of @uNoCtor@, it might be possible to remove the first option. 1345 1342
Note: See TracChangeset
for help on using the changeset viewer.