CodeBoost is a tool for source-to-source transformation and
optimisation of C++ programs. It is intended to be used as a testbed
for various high-level optimisations; the traditional textbook
optimisations are assumed to be handled by the C++ compiler. The
CodeBoost optimiser will attempt to bridge the gap between a
human-friendly coding style and current compiler/optimiser
implementations. The C++ framework forms the basis for the optimiser,
but may also be useful for more general C++ transformation--it has
already been used in an experimental instrumentation/profiling tool.
CodeBoost is part of the Sophus[1] project, which explores the use of
high-level abstractions for numerical applications. This has great
advantages in terms of easier programming and maintenance, but poor
performance has hindered the adoption of these techniques in HPC.
Current compilers have proven unable to optimise sufficiently, partly
due to low demand for such optimisations, and partly because some of
the most effective optimisations are in conflict with the C++
standard. For
CodeBoost, three optimisations are on the way, and more
are planned for the future.
The first optimisation is motivated by the use of operator overloading
in C++, which greatly improve the readability of complex expressions
involving user defined types. For instance, we can write A = A + B *
c, instead of something like mul(B, c, t); add(A, t, A); (possibly
with the function bodies hand-inlined). Unfortunately, this
programmer-friendly style is bad for performance; the result must be
copied, and each operator call involves the creation of a new
temporary. This might be fine with only a few bytes of data, but
unacceptable when working with many megabytes. If the optimiser knows
that A += B means the same as A = A + B, it can rewrite the expression
to use only one temporary, and eliminate copying of the result. This
is what the C++ compiler does for built-in types, but it can't do it
for user-defined types, because the standard forbids assuming any
relation between + and +=. If we demand that this relation holds, or
allow the user to specify it for each case, we can perform the
optimisation.
But even if we do this optimisation, we are left with another
performance problem; the operators are typically defined in terms of
loops, thus the computation is done in several passes over the data.
This causes unnecessary cache misses and index computations. A smart
optimiser can inline the operators, and use loop fusion to fold
consecutive loops into a single loop. Your compiler might actually do
loop fusion in some cases, but most likely it won't look for this
case, and miss the opportunity.
Inlining a function eliminates the function-call overhead, and allows
for further optimisations--such as loop fusion. C++ provides the
inline keyword as a hint to the compiler that a function can be
inlined, but this is merely a hint; the compiler is free to ignore it.
Depending on the compiler, seemingly easy-to-inline code may run a lot
slower than hand-inlined code. With proper inlining, we can use
functions actively, and get better readability, maintainability and
flexibility.
The
CodeBoost framework is limited to processing a simplified version
of the C++ language. Many irrelevant features, such as namespaces,
pointers to functions, and inheritance, have been ignored to keep the
implementation concise and managable. New features are added as the
need arises. The restrictions are motivated not only by implementation
concerns, but also by good coding practice and assumptions made by the
CodeBoost optimiser.
The implementation is based on standard compiler design, with clearly
seprarate parts for each step in the process. A modified version of
Open C++[2] is used for parsing, everything else is written in Stratego.
Stratego is a language for specifying program transformations; the
transformations are described by a combination of concise rewrite
rules, and strategies allowing precise application of the rules based
on context.
Intermediate output from
CodeBoost is in the ATerm format, and is
primarily useful for Stratego programs, but is also accessible from C,
C++ and Java, and is easily parsable. The final output is readable C++
code.
See also