Changeset f728971 for doc/theses
 Timestamp:
 Feb 20, 2019, 2:00:37 PM (4 years ago)
 Branches:
 aaronthesis, armeh, cleanupdtors, enum, forallpointerdecay, jacob/cs343translation, jenkinssandbox, master, newast, newastuniqueexpr, pthreademulation, qualifiedEnum
 Children:
 a2971cc
 Parents:
 95c0ebe (diff), 7e9fa47 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent.  Location:
 doc/theses/aaron_moss_PhD/phd
 Files:

 27 added
 6 edited
Legend:
 Unmodified
 Added
 Removed

doc/theses/aaron_moss_PhD/phd/Makefile
r95c0ebe rf728971 39 39 generictiming \ 40 40 testscompleted \ 41 perprobhisto \ 42 perprobdepth \ 43 cfatime \ 41 44 } 42 45 … … 69 72 gnuplot e BUILD="'${BUILD}/'" ${EVALDIR}/algosummary.gp 70 73 74 perprobhisto.tex : perprob.gp perprob.tsv ${BUILD} 75 gnuplot e BUILD="'${BUILD}/'" ${EVALDIR}/perprob.gp 76 77 perprobdepth.tex : perprobscatter.gp ${BUILD} 78 gnuplot e BUILD="'${BUILD}/'" ${EVALDIR}/perprobscatter.gp 79 80 cfatime.tex : cfaplots.gp cfatime.tsv cfamem.tsv ${BUILD} 81 gnuplot e BUILD="'${BUILD}/'" ${EVALDIR}/cfaplots.gp 82 71 83 ${BUILD}: 72 84 mkdir p ${BUILD} 
doc/theses/aaron_moss_PhD/phd/experiments.tex
r95c0ebe rf728971 68 68 \TODO{test performance; shouldn't be too hard to change \texttt{resolveAssertions} to use unification} 69 69 70 \section{Prototype Experiments} 70 \section{Prototype Experiments} \label{protoexpsec} 71 71 72 72 The primary performance experiments for this thesis were conducted using the resolver prototype on problem instances generated from actual \CFA{} code using the method described in Section~\ref{rpfeaturessec}. … … 98 98 Terminal output was suppressed for all tests to avoid confounding factors in the timing results, and all tests were run three times in series, with the median result reported in all cases. 99 99 The medians are representative data points; considering test cases that took at least 0.2~s to run, the average run was within 2\% of the reported median runtime, and no run diverged by more than 20\% of median runtime or 5.5~s. 100 The memory results are even more consistent, with no run exceeding 2\% difference from median in peak resident set size, and 93\% of tests not recording any difference within the 1~KB granularity of the measurement software. 100 The memory results are even more consistent, with no run exceeding 2\% difference from median in peak resident set size, and 93\% of tests not recording any difference within the 1~KB granularity of the measurement software. 101 All tests were run on a machine with 128~GB of RAM and 64 cores running at 2.2~GHz. 101 102 102 103 As a matter of experimental practicality, test runs which exceeded 8~GB of peak resident memory usage were excluded from the data set. … … 156 157 \section{Instance Difficulty} 157 158 158 \section{\CFA{} Results} 159 To characterize the difficulty of expression resolution problem instances, the test suites must be explored at a finer granuarity. 160 As discussed in Section~\ref{resnanalysissec}, a single toplevel expression is the fundamental problem instance for resolution, yet the test inputs discussed above are composed of thousands of toplevel expressions, like the actual source code they are derived from. 161 To pull out the effects of these individual problems, I instrumented the resolver prototype to time resolution for each expression, and also report some relevant properties of the expression. 162 This instrumented resolver was then run on a set of difficult test instances; to limit the data collection task, these runs were limited to the bestperforming \textsc{budcaper} algorithm and test inputs which that algorithm took more than 1~s to complete. 163 164 The 13 test inputs thus selected contain 20632 toplevel expressions between them, which are separated into orderofmagnitude bins by runtime in Figure~\ref{perprobhistofig}. 165 As can be seen from this figure, overall runtime is dominated by a few particularly difficult problem instances  the 60\% of expressions which resolve in under 0.1~ms collectively take less time to resolve than any of the 0.2\% of expressions which take at least 100~ms to resolve. 166 On the other hand, the 46 expressions in that 0.2\% take 38\% of the overall time in this difficult test suite, while the 201 expressions that take between 10 and 100~ms to resolve consume another 30\%. 167 168 \begin{figure} 169 \centering 170 \input{perprobhisto} 171 \caption[Histogram of toplevel expressions]{Histogram of toplevel expression resolution runtime, binned by orderofmagnitude. The left series counts the expressions in each bin according to the left axis, while the right series reports the summed runtime of resolution for all expressions in that bin. Note that both yaxes are logscaled.} \label{perprobhistofig} 172 \end{figure} 173 174 Since the top centile of expression resolution instances requires approximately twothirds of the resolver's time, optimizing the resolver for specific hard problem instances has proven to be an effective technique for reducing overall runtime. 175 The data below indicates that number of assertions necessary to resolve has the greatest effect on runtime, as seen in 176 Figure~\ref{perprobassnsfig}. 177 However, since the number of assertions required is only known once resolution is finished, the mostpromising preresolution metric of difficulty is the nesting depth of the expression; as seen in Figure~\ref{perprobdepthfig}, expressions of depth $> 10$ in this dataset are uniformly difficult. 178 Figure~\ref{perprobsubsfig} presents a similar pattern for number of subexpressions, though given that the expensive tail of problem instances occurs at approximately twice the depth values, it is reasonable to believe that the difficult expressions in question are deeplynested invocations of binary functions rather than wider but shallowlynested expressions. 179 180 % TODO statistics to tease out difficulty? Is ANOVA the right keyword? 181 % TODO maybe metrics to sum number of polyoverloads invoked 182 183 \begin{figure} 184 \centering 185 \input{perprobassns} 186 \caption[Toplevel expression resolution time by number of assertions resolved.]{Toplevel expression resolution time by number of assertions resolved. Note log scales on both axes.} \label{perprobassnsfig} 187 \end{figure} 188 189 \begin{figure} 190 \centering 191 \input{perprobdepth} 192 \caption[Toplevel expression resolution time by maximum nesting depth of expression.]{Toplevel expression resolution time by maximum nesting depth of expression. Note log scales on both axes.} \label{perprobdepthfig} 193 \end{figure} 194 195 \begin{figure} 196 \centering 197 \input{perprobsubs} 198 \caption[Toplevel expression resolution time by number of subexpressions.]{Toplevel expression resolution time by number of subexpressions. Note log scales on both axes.} \label{perprobsubsfig} 199 \end{figure} 200 201 202 \section{\CFA{} Results} \label{cfaresultssec} 203 204 I have integrated most of the algorithmic techniques discussed in this chapter into \CFACC{}. 205 This integration took place over a period of months while \CFACC{} was under active development on a number of other fronts, so it is not possible to completely isolate the effects of the algorithmic changes, but I have generated some data. 206 To generate this data, representative commits from the \texttt{git} history of the project were checked out and compiled, then run on the same machine used for the resolver prototype experiments discussed in Section~\ref{protoexpsec}. 207 To negate the effects of changes to the \CFA{} standard library on the timing results, 55 test files from the test suite of the oldest \CFA{} variant were compiled with the \texttt{E} flag to inline their library dependencies, and these inlined files were used to test the remaining \CFACC{} versions. 208 209 I performed two rounds of modification to \CFACC{}; the first round moved from Bilson's original combinedbottomup algorithm to an uncombined bottomup algorithm, denoted \textsc{cfaco} and \textsc{cfabu}, respectively. 210 A topdown algorithm was not attempted in \CFACC{} due to its poor performance in the prototype. 211 The second round of modifications addressed assertion satisfaction, taking Bilson's original \textsc{cfaimm} algorithm, and iteratively modifying it, first to use the deferred approach \textsc{cfadef}, then caching those results in the \text{cfadca} algorithm. 212 The new environment data structures discussed in Section~\ref{protoexpsec} have not been successfully merged into \CFACC{} due to their dependencies on the garbagecollection framework in the prototype; I spent several months modifiying \CFACC{} to use similar garbage collection, but due to \CFACC{} not being designed to use such memory management the performance of the modified compiler was nonviable. 213 It is possible that the persistent unionfind environment could be modified to use a referencecounted pointer internally without changing the entire memorymanagement framework of \CFACC{}, but such an attempt is left to future work. 214 215 As can be seen in Figures~\ref{cfatimefig} and~\ref{cfamemfig}, which show the time and peak memory results for these five versions of \CFACC{} on the same test suite, assertion resolution dominates total resolution cost, with the \textsc{cfadef} and \textsc{cfadca} variants running consistently faster than the others on more expensive test cases. 216 The results from \CFACC{} do not exactly mirror those from the prototype; I conjecture this is mostly due to the different memorymanagement schemes and sorts of data required to run type unification and assertion satisfaction calculations, as \CFACC{} performance has proven to be particularly sensitive to the amount of heap allocation performed. 217 This data also shows a noticable regression in compiler performance in the eleven months between \textsc{cfabu} and \textsc{cfaimm}; this regression is not due to expression resolution, as no integration work happened in this time, but I am unable to ascertain its actual cause. 218 It should also be noted with regard to the peak memory results in Figure~\ref{cfamemfig} that the peak memory usage does not always occur during the resolution phase of the compiler. 219 220 \begin{figure} 221 \centering 222 \input{cfatime} 223 \caption[\CFACC{} runtime against \textsc{cfaco} baseline.]{\CFACC{} runtime against \textsc{cfaco} baseline. Note log scales on both axes.} \label{cfatimefig} 224 \end{figure} 225 226 \begin{figure} 227 \centering 228 \input{cfamem} 229 \caption[\CFACC{} peak memory usage against \textsc{cfaco} baseline runtime.]{\CFACC{} peak memory usage against \textsc{cfaco} baseline runtime. Note log scales on both axes.} \label{cfamemfig} 230 \end{figure} 159 231 160 232 % use Jenkins daily build logs to rebuild speedup graph with more data … … 167 239 168 240 % look back at Resolution Algorithms section for threads to tie up "does the algorithm look like this?" 241 242 \section{Conclusion} 243 244 As can be seen from the prototype results, perexpression benchmarks, and \CFACC{}, the dominant factor in the cost of \CFA{} expression resolution is assertion satisfaction. 245 Reducing the number of total number of assertion satisfaction problems solved, as in the deferred satisfaction algorithm, is consistently effective at reducing runtime, and caching results of these satisfaction problems has shown promise in the prototype system. 246 The results presented here also demonstrate that a bottomup approach to expression resolution is superior to topdown, settling an open question from Baker~\cite{Baker82}. 247 The persistent unionfind type environment introduced in Chapter~\ref{envchap} has also been demonstrated to be a modest performance improvement on the na\"{\i}ve approach. 248 249 Given the consistently strong performance of the \textsc{budcaimm} and \textsc{budcaper} variants of the resolver prototype, the results in this chapter demonstrate that it is possible to develop a \CFA{} compiler with acceptable runtime performance for widespread use, an important and previously unaddressed consideration for the practical viability of the language. 250 However, the lessmarked improvement in Section~\ref{cfaresultssec} from retrofitting these algorithmic changes onto the existing compiler leave the actual development of a performant \CFA{} compiler to future work. 251 Characterization and elimination of the performance deficits in the existing \CFACC{} has proven difficult, though runtime is generally dominated by the expression resolution phase; as such, building a new \CFA{} compiler based on the resolver prototype contributed by this work may prove to be an effective strategy. 
doc/theses/aaron_moss_PhD/phd/resolutionheuristics.tex
r95c0ebe rf728971 28 28 \begin{itemize} 29 29 \item If either operand is a floatingpoint type, the common type is the size of the largest floatingpoint type. If either operand is !_Complex!, the common type is also !_Complex!. 30 \item If both operands are of integral type, the common type has the same size\footnote{Technically, the C standard defines a notion of \emph{rank} , a distinct value for each \lstinline{signed} and \lstinline{unsigned} pair; integral types of the same size thus may have distinct ranks. For instance, if \lstinline{int} and \lstinline{long} are the same size, \lstinline{long} will have greater rank. The standarddefined types are declared to have greater rank than any types of the same size added as compiler extensions.} as the larger type.30 \item If both operands are of integral type, the common type has the same size\footnote{Technically, the C standard defines a notion of \emph{rank} in \cite[\S{}6.3.1.1]{C11}, a distinct value for each \lstinline{signed} and \lstinline{unsigned} pair; integral types of the same size thus may have distinct ranks. For instance, if \lstinline{int} and \lstinline{long} are the same size, \lstinline{long} will have greater rank. The standarddefined types are declared to have greater rank than any types of the same size added as compiler extensions.} as the larger type. 31 31 \item If the operands have opposite signedness, the common type is !signed! if the !signed! operand is strictly larger, or !unsigned! otherwise. If the operands have the same signedness, the common type shares it. 32 32 \end{itemize} 33 33 34 Beginning with the work of Bilson\cite{Bilson03}, \CFA{} has defineda \emph{conversion cost} for each function call in a way that generalizes C's conversion rules.34 Beginning with the work of Bilson\cite{Bilson03}, \CFA{} defines a \emph{conversion cost} for each function call in a way that generalizes C's conversion rules. 35 35 Loosely defined, the conversion cost counts the implicit conversions utilized by an interpretation. 36 36 With more specificity, the cost is a lexicographicallyordered tuple, where each element corresponds to a particular kind of conversion. 37 In Bilson's \CFA{}design, conversion cost is a 3tuple, $(unsafe, poly, safe)$, where $unsafe$ is the count of unsafe (narrowing) conversions, $poly$ is the count of polymorphic type bindings, and $safe$ is the sum of the degree of safe (widening) conversions.38 Degree of safe conversion is calculated as path weight in a weighted directed graph of safe conversions between types; the current version of this graph isin Figure~\ref{safeconvgraphfig}.39 The safe conversion graph designed such that the common type $c$ of two types $u$ and $v$ is compatible with the C standard definitions from \cite[\S{}6.3.1.8]{C11} and can be calculated as the unique type minimizing the sum of the path weights of $\overrightarrow{uc}$ and $\overrightarrow{vc}$.37 In Bilson's design, conversion cost is a 3tuple, $(unsafe, poly, safe)$, where $unsafe$ is the count of unsafe (narrowing) conversions, $poly$ is the count of polymorphic type bindings, and $safe$ is the sum of the degree of safe (widening) conversions. 38 Degree of safe conversion is calculated as path weight in a directed graph of safe conversions between types; both Bilson's version and the current version of this graph are in Figure~\ref{safeconvgraphfig}. 39 The safe conversion graph is designed such that the common type $c$ of two types $u$ and $v$ is compatible with the C standard definitions from \cite[\S{}6.3.1.8]{C11} and can be calculated as the unique type minimizing the sum of the path weights of $\overrightarrow{uc}$ and $\overrightarrow{vc}$. 40 40 The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters: 41 41 42 42 \begin{cfa} 43 43 void f(char, long); $\C{// (1,0,1)}$ 44 void f(short, long); $\C{// (1,0,1)}$ 44 45 forall(otype T) void f(T, long); $\C{// (0,1,1)}$ 45 46 void f(long, long); $\C{// (0,0,2)}$ … … 48 49 \end{cfa} 49 50 50 Note that safe and unsafe conversions are handled differently; \CFA{} counts distance of safe conversions (\eg{} !int! to !long! is cheaper than !int! to !unsigned long!), while only counting the number of unsafe conversions (\eg{} !int! to !char! and !int! to !short! both have unsafe cost 1). 51 Note that safe and unsafe conversions are handled differently; \CFA{} counts distance of safe conversions (\eg{} !int! to !long! is cheaper than !int! to !unsigned long!), while only counting the number of unsafe conversions (\eg{} !int! to !char! and !int! to !short! both have unsafe cost 1, as in the first fwo declarations above). 52 These costs are summed over the paramters in a call; in the example above, the cost of the two !int! to !long! conversions for the fourth declaration sum equal to the one !int! to !unsigned long! conversion in the fifth. 51 53 52 54 As part of adding reference types to \CFA{} (see Section~\ref{typefeaturessec}), Schluntz added a new $reference$ element to the cost tuple, which counts the number of implicit referencetorvalue conversions performed so that candidate interpretations can be distinguished by how closely they match the nesting of reference types; since references are meant to act almost indistinguishably from lvalues, this $reference$ element is the least significant in the lexicographic comparison of cost tuples. 53 55 54 56 I have also refined the \CFA{} cost model as part of this thesis work. 55 Bilson's \CFA{} cost model includes the cost of polymorphic type bindings from a function's type assertions in the $poly$ element of the cost tuple; this has the effect of making moreconstrained functions more expensive than lessconstrained functions. 57 Bilson's \CFA{} cost model includes the cost of polymorphic type bindings from a function's type assertions in the $poly$ element of the cost tuple; this has the effect of making moreconstrained functions more expensive than lessconstrained functions, as in the following example: 58 59 \begin{cfa} 60 forall(dtype T  { T& ++?(T&); }) T& advance(T&, int); 61 forall(dtype T  { T& ++?(T&); T& ?+=?(T&, int)}) T& advance(T&, int); 62 \end{cfa} 63 64 In resolving a call to !advance!, the binding to the !T&! parameter in the assertions is added to the $poly$ cost in Bilson's model. 56 65 However, type assertions actually make a function \emph{less} polymorphic, and as such functions with more type assertions should be preferred in type resolution. 57 As an example, some iteratorbased algorithms can work on a forward iterator that only provides an increment operator, but are more efficient on a randomaccess iterator that can be incremented by an arbitrary number of steps in a single operation. 58 The randomaccess iterator has more type constraints, but should be chosen whenever those constraints can be satisfied. 59 As such, I have added a $specialization$ element to the \CFA{} cost tuple, the values of which are always negative. 60 Each type assertion subtracts 1 from $specialization$, so that moreconstrained functions will cost less and thus be chosen over lessconstrained functions, all else being equal. 66 In the example above, the moreconstrained second function can be implemented more efficiently, and as such should be chosen whenever its added constraint can be satisfied. 67 As such, a $specialization$ element is now included in the \CFA{} cost tuple, the values of which are always negative. 68 Each type assertion subtracts 1 from $specialization$, so that moreconstrained functions cost less, and thus are chosen over lessconstrained functions, all else being equal. 61 69 A more sophisticated design would define a partial order over sets of type assertions by set inclusion (\ie{} one function would only cost less than another if it had a strict superset of assertions, rather than just more total assertions), but I did not judge the added complexity of computing and testing this order to be worth the gain in specificity. 62 70 63 I havealso incorporated an unimplemented aspect of Ditchfield's earlier cost model.71 I also incorporated an unimplemented aspect of Ditchfield's earlier cost model. 64 72 In the example below, adapted from \cite[p.89]{Ditchfield92}, Bilson's cost model only distinguished between the first two cases by accounting extra cost for the extra set of !otype! parameters, which, as discussed above, is not a desirable solution: 65 73 … … 71 79 \end{cfa} 72 80 73 I accountfor the fact that functions with more polymorphic variables are less constrained by introducing a $var$ cost element that counts the number of type variables on a candidate function.81 The new cost model accounts for the fact that functions with more polymorphic variables are less constrained by introducing a $var$ cost element that counts the number of type variables on a candidate function. 74 82 In the example above, the first !f! has $var = 2$, while the remainder have $var = 1$. 75 My new \CFA{}cost model also accounts for a nuance unhandled by Ditchfield or Bilson, in that it makes the more specific fourth function above cheaper than the more generic third function.83 The new cost model also accounts for a nuance unhandled by Ditchfield or Bilson, in that it makes the more specific fourth function above cheaper than the more generic third function. 76 84 The fourth function is presumably somewhat optimized for handling pointers, but the prior \CFA{} cost model could not account for the more specific binding, as it simply counted the number of polymorphic unifications. 77 85 78 In my modified model, each level of constraint on a polymorphic type in the parameter list results in a decrement of the $specialization$ cost element.79 Thus, all else equal, if both a binding to !T! and a binding to !T*! are available, \CFA{} will pick the more specific !T*! binding.80 This process is recursive, such that !T**! produces a 2 specialization cost, as opposed to the 1 cost for !T*!.81 This works similarly for generic types, \eg{} !box(T)! also has specialization cost 1.86 In the modified model, each level of constraint on a polymorphic type in the parameter list results in a decrement of the $specialization$ cost element, which is shared with the count of assertions due to their common nature as constraints on polymorphic type bindings. 87 Thus, all else equal, if both a binding to !T! and a binding to !T*! are available, the model chooses the more specific !T*! binding with $specialization = 1$. 88 This process is recursive, such that !T**! has $specialization = 2$. 89 This calculation works similarly for generic types, \eg{} !box(T)! also has specialization cost 1. 82 90 For multiargument generic types, the leastspecialized polymorphic parameter sets the specialization cost, \eg{} the specialization cost of !pair(T, S*)! is 1 (from !T!) rather than 2 (from !S!). 83 Since the user programmer provides parameters, but cannot provide guidance on return type, specialization cost is not counted for the return type list. 91 Specialization cost is not counted on the return type list; since $specialization$ is a property of the function declaration, a lower specialization cost prioritizes one declaration over another. 92 User programmers can choose between functions with varying parameter lists by adjusting the arguments, but the same is not true of varying return types, so the return types are omitted from the $specialization$ element. 84 93 Since both $vars$ and $specialization$ are properties of the declaration rather than any particular interpretation, they are prioritized less than the interpretationspecific conversion costs from Bilson's original 3tuple. 85 94 86 A final refinement I have made to the \CFA{} cost model is with regard to choosing betweenarithmetic conversions.87 The C standard states that the common type of !int! and !unsigned int! is !unsigned int! and that the common type of !int! and !long! is !long!, but does not provide guidance for making a choice between those twoconversions.88 Bilson's \CFACC{} use d conversion costs based off a graph similar to that in Figure~\ref{safeconvgraphfig}, but with arcs selectively removed to disambiguate the costs of such conversions.89 However, the arc removal in Bilson's design resultedin inconsistent and somewhat surprising costs, with conversion to the nextlarger samesign type generally (but not always) double the cost of conversion to the !unsigned! type of the same size.90 In my redesign, for consistency with the approach of the usual arithmetic conversions,which select a common type primarily based on size, but secondarily on sign, the costs of arcs in the new graph are defined to be $1$ to go to a larger size, but $1 + \varepsilon$ to change the sign.95 A final refinement I have made to the \CFA{} cost model is with regard to choosing among arithmetic conversions. 96 The C standard \cite[\S{}6.3.1.8]{C11} states that the common type of !int! and !unsigned int! is !unsigned int! and that the common type of !int! and !long! is !long!, but does not provide guidance for making a choice among conversions. 97 Bilson's \CFACC{} uses conversion costs based off the left graph in Figure~\ref{safeconvgraphfig}. 98 However, Bilson's design results in inconsistent and somewhat surprising costs, with conversion to the nextlarger samesign type generally (but not always) double the cost of conversion to the !unsigned! type of the same size. 99 In the redesign, for consistency with the approach of the usual arithmetic conversions, which select a common type primarily based on size, but secondarily on sign, arcs in the new graph are annotated with whether they represent a sign change, and such sign changes are summed in a new $sign$ cost element that lexicographically succeeds than $safe$. 91 100 This means that sign conversions are approximately the same cost as widening conversions, but slightly more expensive (as opposed to less expensive in Bilson's graph). 92 The $\varepsilon$ portion of the arc cost is implemented by adding a new $sign$ cost lexicographically after $safe$ which counts sign conversions.93 101 94 102 \begin{figure} 95 103 \centering 96 104 \includegraphics{figures/safeconvgraph} 97 \caption[Safe conversion graph .]{Safe conversion graph; plain arcs have cost $1$ while dashed signconversion arcs have cost $1+ \varepsilon$. The arc from \lstinline{unsigned long} to \lstinline{long long} is deliberately omitted, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}105 \caption[Safe conversion graphs.]{Safe conversion graphs; Bilson's on the left, the extended graph on the right. In both graphs, plain arcs have cost $safe = 1, sign = 0$ while dashed signconversion arcs have cost $safe = 1, sign = 1$. As per \cite[\S{}6.3.1.8]{C11}, types promote to types of the same signedness with greater rank, from \lstinline{signed} to \lstinline{unsigned} with the same rank, and from \lstinline{unsigned} to \lstinline{signed} with greater size. The arc from \lstinline{unsigned long} to \lstinline{long long} is deliberately omitted in the modified graph, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.} 98 106 \label{safeconvgraphfig} 99 107 \end{figure} … … 105 113 \end{equation*} 106 114 107 \subsection{Expression Cost} 115 \subsection{Expression Cost} \label{exprcostsec} 108 116 109 117 The mapping from \CFA{} expressions to cost tuples is described by Bilson in \cite{Bilson03}, and remains effectively unchanged modulo the refinements to the cost tuple described above. … … 189 197 190 198 To resolve the outermost !wrap!, the resolver must check that !pair(pair(int))! unifies with itself, but at three levels of nesting, !pair(pair(int))! is more complex than either !pair(T)! or !T!, the types in the declaration of !wrap!. 191 Accordingly, the cost of a single argumentparameter unification is $O(d)$, where !d!is the depth of the expression tree, and the cost of argumentparameter unification for a single candidate for a given function call expression is $O(pd)$, where $p$ is the number of parameters.199 Accordingly, the cost of a single argumentparameter unification is $O(d)$, where $d$ is the depth of the expression tree, and the cost of argumentparameter unification for a single candidate for a given function call expression is $O(pd)$, where $p$ is the number of parameters. 192 200 193 201 Implicit conversions are also checked in argumentparameter matching, but the cost of checking for the existence of an implicit conversion is again proportional to the complexity of the type, $O(d)$. … … 364 372 365 373 % Mention relevance of work to C++20 concepts 374 375 % Mention more compact representations of the (growing) cost tuple
Note: See TracChangeset
for help on using the changeset viewer.