[Haskell-cafe] computational overhead of the "data" declarations
wren ng thornton
wren at freegeek.org
Tue Oct 28 21:01:22 EDT 2008
Brent Yorgey wrote:
> Daryoush Mehrtash wrote:
> > What is (or where do you see) the computational overhead of the "data"
> > declrations?
> So, to answer your question, the only computational overhead with a
> data declaration is the extra memory and time to store and process the
> constructor tags. It usually isn't noticeable, but sometimes the
> difference can be important.
Another important part of this that wasn't mentioned is pattern
matching. For datatypes with only one constructor there's only one
branch to choose among for (one-ply deep) patterns, and so the matching
can be skipped entirely. This saves a conditional/vector jump, which can
dramatically affect cache behavior. Not needing to pattern match also
allows unpacking of the arguments to the constructor into arguments to
the function, thus saving on allocation and garbage collection. More
importantly, if the arguments are primitive types and strict then they
can be unboxed into registers as well.
In principle many of these optimizations can be and are applied to
single-constructor 'data' types, but using 'newtype' tells the compiler
to be sure to optimize them thusly.
More information about the Haskell-Cafe