Changeset f2c5726
- Timestamp:
- Jan 22, 2019, 4:49:23 PM (6 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 104a13e
- Parents:
- 9a38436c
- Location:
- doc
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/bibliography/pl.bib
r9a38436c rf2c5726 4175 4175 } 4176 4176 4177 @misc{Haberman16, 4178 keywords = {C++ template expansion}, 4179 contributer = {a3moss@uwaterloo.ca}, 4180 author = {Josh Haberman}, 4181 title = {Making arbitrarily-large binaries from fixed-size {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} code}, 4182 year = 2016, 4183 howpublished= {\href{http://blog.reverberate.org/2016/01/making-arbitrarily-large-binaries-from.html} 4184 { 4185 {http://blog.reverberate.org/\-2016/\-01/\-making-arbitrarily-large-binaries-from.html} 4186 }}, 4187 optnote = {Accessed: 2016-09}, 4188 } 4189 4177 4190 @article{c++libs, 4178 4191 keywords = {directory structure}, -
doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex
r9a38436c rf2c5726 1 1 \chapter{Resolution Heuristics} 2 2 \label{resolution-chap} 3 4 % consider using "satisfaction" throughout when talking about assertions 3 5 4 6 The main task of the \CFACC{} type-checker is \emph{expression resolution}, determining which declarations the identifiers in each expression correspond to. … … 138 140 \section{Resolution Algorithms} 139 141 142 \CFA{} expression resolution is not, in general, polynomial in the size of the input expression, as shown in Section~\ref{resn-analysis-sec}. 143 While this theoretical result is daunting, its implications can be mitigated in practice. 144 \CFACC{} does not solve one instance of expression resolution in the course of compiling a program, but rather thousands; therefore, if the worst case of expression resolution is sufficiently rare, worst-case instances can be amortized by more-common easy instances for an acceptable overall runtime. 145 Secondly, while a programmer \emph{can} deliberately generate a program designed for inefficient compilation\footnote{see for instance \cite{Haberman16}, which generates arbitrarily large \CC{} template expansions from a fixed-size source file.}, source code tends to follow common patterns. 146 Programmers generally do not want to run the full compiler algorithm in their heads, and as such keep mental shortcuts in the form of language idioms. 147 If the compiler can be tuned to handle idiomatic code more efficiently, then the reduction in runtime for idiomatic (but otherwise difficult) resolution instances can make a significant difference in total compiler runtime. 148 149 \subsection{Analysis} \label{resn-analysis-sec} 150 151 Expression resolution has a number of components which contribute to its runtime, including argument-parameter type unification, recursive traversal of the expression tree, and satisfaction of type assertions. 152 153 If the bound type for a type variable can be looked up or mutated in constant time (as asserted in Table~\ref{env-bounds-table}), then the runtime of the unification algorithm to match an argument to a parameter is proportional to the complexity of the types being unified. 154 In C, complexity of type representation is bounded by the most-complex type explicitly written in a declaration; in \CFA{}, however, polymorphism can generate more-complex types: 155 156 \begin{cfa} 157 forall(otype T) pair(T) wrap(T x, T y); 158 159 wrap(wrap(wrap(1, 2), wrap(3, 4)), wrap(wrap(5, 6), wrap(7, 8))); 160 \end{cfa} 161 162 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!. 163 According to this argument, then, the cost of a single argument-parameter unification is !O(d)!, where !d! is the depth of the expression tree, and the cost of argument-parameter unification for a single candidate for a given function call expression is !O(pd)!, where !p! is the number of parameters. 164 165 % continue from here 166 140 167 \subsection{Related Work} 141 168 … … 147 174 I have modified \CFACC{} to first sort assertion satisfaction candidates by conversion cost, and only resolve recursive assertions until a unique minimal-cost candidate or an ambiguity is detected. 148 175 176 \section{Experimental Results} 177 178 % use Jenkins daily build logs to rebuild speedup graph with more data 179 180 % look back at Resolution Algorithms section for threads to tie up "does the algorithm look like this?" 181 182 \section{Conclusion \& Future Work} 183 149 184 I have experimented with using expression resolution rather than type unification to choose assertion resolutions; this path should be investigated further in future work. 150 185 This approach is more flexible than type unification, allowing for conversions to be applied to functions to satisfy assertions. … … 153 188 The main challenge to implement this approach in \CFACC{} would be applying the implicit conversions generated by the resolution process in the code-generation for the thunk functions that \CFACC{} uses to pass type assertions with the proper signatures. 154 189 190 % Discuss possibility of parallel subexpression resolution 191 155 192 % Mention relevance of work to C++20 concepts
Note: See TracChangeset
for help on using the changeset viewer.