- Timestamp:
- Feb 8, 2021, 10:30:51 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- f4eb705
- Parents:
- 7584279
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/fangren_yu_COOP_F20/Report.tex
r7584279 r735b627 102 102 \CFA language, developed by the Programming Language Group at the University of Waterloo, has a long history, with the initial language design in 1992 by Glen Ditchfield~\cite{Ditchfield92} and the first proof-of-concept compiler built in 2003 by Richard Bilson~\cite{Bilson03}. Many new features have been added to the language over time, but the core of \CFA's type-system --- parametric functions introduced by the @forall@ clause (hence the name of the language) providing parametric overloading --- remains mostly unchanged. 103 103 104 The current \CFA reference compiler, @cfa-cc@, is designed using the visitor pattern~\cite{vistorpattern} over an abstract syntax tree (AST), where multiple passes over the AST modify it for subsequent passes. @cfa-cc@ still includes many parts taken directly from the original Bilson implementation, which served as the starting point for this enhancement work to the type system. Unfortunately, the prior implementation did not provide the efficiency required for the language to be practical: a \CFA source file of approximately 1000 lines of code can take amultiple minutes to compile. The cause of the problem is that the old compiler used inefficient data structures and algorithms for expression resolution, which involved significant copying and redundant work.104 The current \CFA reference compiler, @cfa-cc@, is designed using the visitor pattern~\cite{vistorpattern} over an abstract syntax tree (AST), where multiple passes over the AST modify it for subsequent passes. @cfa-cc@ still includes many parts taken directly from the original Bilson implementation, which served as the starting point for this enhancement work to the type system. Unfortunately, the prior implementation did not provide the efficiency required for the language to be practical: a \CFA source file of approximately 1000 lines of code can take multiple minutes to compile. The cause of the problem is that the old compiler used inefficient data structures and algorithms for expression resolution, which involved significant copying and redundant work. 105 105 106 106 This report presents a series of optimizations to the performance-critical parts of the resolver, with a major rework of the compiler data-structures using a functional-programming approach to reduce memory complexity. The improvements were suggested by running the compiler builds with a performance profiler against the \CFA standard-library source-code and a test suite to find the most underperforming components in the compiler algorithm. … … 122 122 \end{itemize} 123 123 124 The resolver algorithm, designed for overload resolution, uses a significant amount ofreused, and hence copying, for the intermediate representations, especially in the following two places:124 The resolver algorithm, designed for overload resolution, allows a significant amount of code reused, and hence copying, for the intermediate representations, especially in the following two places: 125 125 \begin{itemize} 126 126 \item … … 301 301 forall( dtype T | sized( T ) ) 302 302 T * malloc( void ) { return (T *)malloc( sizeof(T) ); } // call C malloc 303 int * i = malloc(); // type deduced from left-hand size $\ Rightarrow$ no size argument or return cast303 int * i = malloc(); // type deduced from left-hand size $\(\Rightarrow\)$ no size argument or return cast 304 304 \end{cfa} 305 305 An unbound return-type is problematic in resolver complexity because a single match of a function call with an unbound return type may create multiple candidates. In the worst case, consider a function declared that returns any @otype@ (defined \VPageref{otype}): … … 432 432 \begin{cfa} 433 433 void f( int ); 434 double g$ _1$( int );435 int g$ _2$( long );434 double g$\(_1\)$( int ); 435 int g$\(_2\)$( long ); 436 436 f( g( 42 ) ); 437 437 \end{cfa}
Note: See TracChangeset
for help on using the changeset viewer.