Changeset 7722242


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/fangren_yu_COOP_F20/Report.tex

    r4b1c8da r7722242  
    8888\end{abstract}
    8989
     90\clearpage
    9091\section*{Acknowledgements}
    91 Thanks Mum.
     92I 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.
    9293
    9394\clearpage
    9495\tableofcontents
    9596
     97\clearpage
    9698\section{Introduction}
    9799
     
    398400L & ?=?( L &, L & ); // assignment
    399401\end{cfa}
    400 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.
    401 
    402 \begin{table}[h]
     402
     403\begin{table}[htb]
    403404\centering
    404405\caption{Compilation results of nested cons test}
     
    419420\end{table}
    420421
     422Now 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.
    421423
    422424\section{Analysis of type system correctness}
     
    467469with 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.
    468470
    469 \begin{table}
     471Additionally, 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@).
     472\VRef[Table]{t:SelectedFileByCompilerBuild} shows the selected tests:
     473\begin{itemize}
     474\item
     475@lib/fstream@ (112 KB)
     476\item
     477@lib/mutex@ (166 KB): implementation of concurrency primitive
     478\item
     479@lib/vector@ (43 KB): container example, similar to \CC vector
     480\item
     481@lib/stdlib@ (64 KB): type-safe wrapper to @void *@-based C standard library functions
     482\item
     483@test/io2@ (55 KB): application of I/O library
     484\item
     485@test/thread@ (188 KB): application of threading library
     486\end{itemize}
     487versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally:
     488\begin{itemize}
     489\item
     490old resolver
     491\item
     492\#0 is the first working build of the new AST data structure
     493\item
     494\#1 implements special symbol table and argument-dependent lookup
     495\item
     496\#2 implements late assertion-satisfaction
     497\item
     498\#3 implements revised function-type representation
     499\item
     500\#4 skips pruning on expressions for function types (most recent build)
     501\end{itemize}
     502Reading left to right for a test shows the benefit of each optimization on the cost of compilation.
     503
     504\begin{table}[htb]
    470505\centering
    471506\caption{Compile time of selected files by compiler build, in seconds}
     
    493528\end{table}
    494529
    495 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@).
    496 \VRef[Table]{t:SelectedFileByCompilerBuild} shows the selected tests:
    497 \begin{itemize}
    498 \item
    499 @lib/fstream@ (112 KB)
    500 \item
    501 @lib/mutex@ (166 KB): implementation of concurrency primitive
    502 \item
    503 @lib/vector@ (43 KB): container example, similar to \CC vector
    504 \item
    505 @lib/stdlib@ (64 KB): type-safe wrapper to @void *@-based C standard library functions
    506 \item
    507 @test/ISO2@ (55 KB): application of I/O library
    508 \item
    509 @test/thread@ (188 KB): application of threading library
    510 \end{itemize}
    511 versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally:
    512 \begin{itemize}
    513 \item
    514 old resolver
    515 \item
    516 \#0 is the first working build of the new AST data structure
    517 \item
    518 \#1 implements special symbol table and argument-dependent lookup
    519 \item
    520 \#2 implements late assertion-satisfaction
    521 \item
    522 \#3 implements revised function-type representation
    523 \item
    524 \#4 skips pruning on expressions for function types (most recent build)
    525 \end{itemize}
    526 Reading left to right for a test shows the benefit of each optimization on the cost of compilation.
    527 
    528530\section{Conclusion}
    529531
Note: See TracChangeset for help on using the changeset viewer.