Haskell is a lazy functional language with a strong static type system and
excellent support for parallel programming. The language features of Haskell
make it easier to write correct and maintainable programs, but execution speed
often suffers from the high levels of abstraction. While much past research
focuses on high-level optimizations that take advantage of the functional
properties of Haskell, relatively little attention has been paid to the
optimization opportunities in the low-level imperative code generated during
translation to machine code. One problem with current low-level optimizations
is that their effectiveness is limited by the obscured control flow caused by
Haskell's high-level abstractions. My thesis is that trace-based optimization
techniques can be used to improve the effectiveness of low-level optimizations
for Haskell programs. I claim three unique contributions in this work.
The first contribution is to expose some properties of low-level Haskell codes
by looking at the mix of operations performed by the selected benchmark codes
and comparing them to the low-level codes coming from traditional programming
languages. The low-level measurements reveal that the control flow is obscured
by indirect jumps caused by the implementation of lazy evaluation,
higher-order functions, and the separately managed stacks used by Haskell
programs.
My second contribution is a study on the effectiveness of a dynamic binary
trace-based optimizer running on Haskell programs. My results show that while
viable program traces frequently occur in Haskell programs the overhead
associated with maintaing the traces in a dynamic optimization system outweigh
the benefits we get from running the traces. To reduce the runtime overheads,
I explore a way to find traces in a separate profiling step.
My final contribution is to build and evaluate a static trace-based optimizer
for Haskell programs. The static optimizer uses profiling data to find traces
in a Haskell program and then restructures the code around the traces to
increase the scope available to the low-level optimizer. My results show that
we can successfully build traces in Haskell programs, and the optimized code
yields a speedup over existing low-level optimizers of up to 86%
with an average speedup of 5% across 32 benchmarks.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/64648 |
| Date | 06 September 2012 |
| Creators | Peixotto, David |
| Contributors | Cooper, Keith D. |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | thesis, text |
| Format | application/pdf |
Page generated in 0.0019 seconds