UROP Proceedings 2021-22

School of Engineering Department of Computer Science and Engineering 121 Compilation, Optimization, and Metaprogramming Supervisor: PARREAUX Lionel / CSE Student: QIU Jiangkun / ISDN Course: UROP1100, Spring As developers, we seek the triangular balance of writing fast, reading fast, and running fast. Abstraction is an excellent way to achieve this, as we abstract and encapsulate well-written algorithms and optimizations into functions, classes, and libraries. However, many abstractions come with a penalty. Many languages state that they have zero-cost abstraction, but are they really zero-cost? Compilers fail to perform some optimizations behind abstractions and pay a runtime performance cost. Even as simple as invoking a function without inlining has some runtime cost and may influence CPU cache and branch predictions; generics in GoLang have runtime performance penalty; Java relies on virtual tables to invoke methods once failed to infer the specific method. This leaves space for our Programmable Zero-Cost Abstractions, which heavily utilized macro, comp-time interpretation, and specialization. We can avoid many abstraction costs at runtime by leaving more work to comp-time. Compilation, Optimization, and Metaprogramming Supervisor: PARREAUX Lionel / CSE Student: YUAN Keyu / COMP Course: UROP1000, Summer Specialization is a useful technique for program optimization, and on top of that, in PZCA(Programmable Zero-cost Abstractions), program monomorphization is implemented to produce better optimization results. In this UROP we implemented a regular expression matcher as the front end of PZCA, which demonstrated the power of this program optimizer. The matcher takes in a static regex as a class hierarchy and a dynamic string, and applies a naive matching function to determine whether the string matches the regex. The original matching function was slow, but after adequately specialized, the algorithm become as fast as compiling regex.