Changeset 7722242 for doc/theses/fangren_yu_COOP_F20

Timestamp:

Jan 19, 2021, 1:31:06 PM (4 years ago)

Author:

Fangren Yu <f37yu@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

2f47ea4

Parents:

4b1c8da

Message:

add acknowledgement section, fix a few format issues

File:

• doc/theses/fangren_yu_COOP_F20/Report.tex (modified) (5 diffs)

doc/theses/fangren_yu_COOP_F20/Report.tex

@@ -88 +88 @@
 \end{abstract}
 
+\clearpage
 \section*{Acknowledgements}
-Thanks Mum.
+I would like to thank everyone in the \CFA team for their contribution towards this project. Programming language design and development is a tough subject and requires a lot of teamwork. Without the collaborative efforts from the team, this project could not have been a success. Specifically, I would like to thank Andrew Beach for introducing me to the \CFA codebase, Thierry Delisle for maintaining the test and build automation framework, Michael Brooks for providing example programs of various experimental language and type system features, and most importantly, Professor Martin Karsten for recommending me to the \CFA team, and my supervisor, Professor Peter Buhr for encouraging me to explore deeply into intricate compiler algorithms. Finally, I gratefully acknowledge the help from Aaron Moss, former graduate from the team and the author of the precedent thesis work, to participate in the \CFA team's virtual conferences and email correspondence, and provide many critical arguments and suggestions. 2020 had been an unusually challenging year for everyone and we managed to keep a steady pace.
 
 \clearpage
 \tableofcontents
 
+\clearpage
 \section{Introduction}
 
@@ -398 +400 @@
 L & ?=?( L &, L & ); // assignment
 \end{cfa}
-Now since the right hand side of outermost cons is again a cons, recursive assertions are required. \VRef[Table]{t:NestedConsTest} shows when the compiler does not cache and reuse already resolved assertions, it becomes a problem, as each of these 4 pending assertions again asks for 4 more assertions one level below. Without caching, the number of resolved assertions grows exponentially, which is unnecessary since there are only $n+1$ different types involved. Even worse, this problem causes exponentially many wrapper functions to be generated at the backend, resulting in a huge binary. As the local functions are implemented by emitting executable code on the stack~\cite{gcc-nested-func}, it means that compiled code also has exponential run time. This problem has practical implications, as nested collection types are frequently used in real production code.
-
-\begin{table}[h]
+
+\begin{table}[htb]
 \centering
 \caption{Compilation results of nested cons test}
@@ -419 +420 @@
 \end{table}
 
+Now since the right hand side of outermost cons is again a cons, recursive assertions are required. \VRef[Table]{t:NestedConsTest} shows when the compiler does not cache and reuse already resolved assertions, it becomes a problem, as each of these 4 pending assertions again asks for 4 more assertions one level below. Without caching, the number of resolved assertions grows exponentially, which is unnecessary since there are only $n+1$ different types involved. Even worse, this problem causes exponentially many wrapper functions to be generated at the backend, resulting in a huge binary. As the local functions are implemented by emitting executable code on the stack~\cite{gcc-nested-func}, it means that compiled code also has exponential run time. This problem has practical implications, as nested collection types are frequently used in real production code.
 
 \section{Analysis of type system correctness}
@@ -467 +469 @@
 with the slowest file taking 23 seconds. In contrast, the library build with the old compiler takes 85 minutes total, 5 minutes for the slowest file. The full test-suite takes too long with old compiler build and is therefore not run, but the slowest test cases take approximately 5 minutes. Overall, the most recent build compared to an old build is consistently faster by a factor of 20.
 
-\begin{table}
+Additionally, 6 selected \CFA source files with distinct features from the library and test suite are used to illustrate the compiler performance change after each of the implemented optimizations. Test files are from the most recent build and run through the C preprocessor to expand header file, perform macro expansions, but no line number information (@gcc -E -P@).
+\VRef[Table]{t:SelectedFileByCompilerBuild} shows the selected tests:
+\begin{itemize}
+\item
+@lib/fstream@ (112 KB)
+\item
+@lib/mutex@ (166 KB): implementation of concurrency primitive
+\item
+@lib/vector@ (43 KB): container example, similar to \CC vector
+\item
+@lib/stdlib@ (64 KB): type-safe wrapper to @void *@-based C standard library functions
+\item
+@test/io2@ (55 KB): application of I/O library
+\item
+@test/thread@ (188 KB): application of threading library
+\end{itemize}
+versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally:
+\begin{itemize}
+\item
+old resolver
+\item
+\#0 is the first working build of the new AST data structure
+\item
+\#1 implements special symbol table and argument-dependent lookup
+\item
+\#2 implements late assertion-satisfaction
+\item
+\#3 implements revised function-type representation
+\item
+\#4 skips pruning on expressions for function types (most recent build)
+\end{itemize}
+Reading left to right for a test shows the benefit of each optimization on the cost of compilation.
+
+\begin{table}[htb]
 \centering
 \caption{Compile time of selected files by compiler build, in seconds}
@@ -493 +528 @@
 \end{table}
 
-Additionally, 6 selected \CFA source files with distinct features from the library and test suite are used to illustrate the compiler performance change after each of the implemented optimizations. Test files are from the most recent build and run through the C preprocessor to expand header file, perform macro expansions, but no line number information (@gcc -E -P@).
-\VRef[Table]{t:SelectedFileByCompilerBuild} shows the selected tests:
-\begin{itemize}
-\item
-@lib/fstream@ (112 KB)
-\item
-@lib/mutex@ (166 KB): implementation of concurrency primitive
-\item
-@lib/vector@ (43 KB): container example, similar to \CC vector
-\item
-@lib/stdlib@ (64 KB): type-safe wrapper to @void *@-based C standard library functions
-\item
-@test/ISO2@ (55 KB): application of I/O library
-\item
-@test/thread@ (188 KB): application of threading library
-\end{itemize}
-versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally:
-\begin{itemize}
-\item
-old resolver
-\item
-\#0 is the first working build of the new AST data structure
-\item
-\#1 implements special symbol table and argument-dependent lookup
-\item
-\#2 implements late assertion-satisfaction
-\item
-\#3 implements revised function-type representation
-\item
-\#4 skips pruning on expressions for function types (most recent build)
-\end{itemize}
-Reading left to right for a test shows the benefit of each optimization on the cost of compilation.
-
 \section{Conclusion}