- Timestamp:
- Jan 19, 2021, 1:31:06 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:
- 2f47ea4
- Parents:
- 4b1c8da
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/fangren_yu_COOP_F20/Report.tex
r4b1c8da r7722242 88 88 \end{abstract} 89 89 90 \clearpage 90 91 \section*{Acknowledgements} 91 Thanks Mum.92 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. 92 93 93 94 \clearpage 94 95 \tableofcontents 95 96 97 \clearpage 96 98 \section{Introduction} 97 99 … … 398 400 L & ?=?( L &, L & ); // assignment 399 401 \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] 403 404 \centering 404 405 \caption{Compilation results of nested cons test} … … 419 420 \end{table} 420 421 422 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. 421 423 422 424 \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. 468 470 469 \begin{table} 471 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@). 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} 487 versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally: 488 \begin{itemize} 489 \item 490 old 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} 502 Reading left to right for a test shows the benefit of each optimization on the cost of compilation. 503 504 \begin{table}[htb] 470 505 \centering 471 506 \caption{Compile time of selected files by compiler build, in seconds} … … 493 528 \end{table} 494 529 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 \item499 @lib/fstream@ (112 KB)500 \item501 @lib/mutex@ (166 KB): implementation of concurrency primitive502 \item503 @lib/vector@ (43 KB): container example, similar to \CC vector504 \item505 @lib/stdlib@ (64 KB): type-safe wrapper to @void *@-based C standard library functions506 \item507 @test/ISO2@ (55 KB): application of I/O library508 \item509 @test/thread@ (188 KB): application of threading library510 \end{itemize}511 versus \CFA compiler builds picked from the git commit history that implement the optimizations incrementally:512 \begin{itemize}513 \item514 old resolver515 \item516 \#0 is the first working build of the new AST data structure517 \item518 \#1 implements special symbol table and argument-dependent lookup519 \item520 \#2 implements late assertion-satisfaction521 \item522 \#3 implements revised function-type representation523 \item524 \#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 528 530 \section{Conclusion} 529 531
Note: See TracChangeset
for help on using the changeset viewer.