Required Optimization

Beelsebob and I were talking at lunch, and we had an interesting idea. Haskell is experimenting with optimizations that C programmers would never dream of. But I say experimenting with emphasis since the optimizations are unpredictable. The Haskell optimizer can lower (and also raise) the space complexity of your program, not changing it from a program that runs slowly to one that runs quickly, but from one that doesn’t run to one that does (eg. allocating 20GB and dying vs. not allocating).

And thus the code becomes very brittle. Adding a trace, accidentally creating a thunk that references something early in a stream, or even doing a semantically nil refactor that happens to confuse the optimizer can cause your program to suddenly become a lot less efficient for no apparent reason. It’s not uncommon for a Haskell programmer to experience this in a real project.

So how can we remedy this? The idea was: annotate which optimizations you expect, and get a compiler error/warning when they don’t happen and some indication why. As a simple example perhaps:

{-# OPTIMIZE ListStream addOne #-}
addOne = map (+1)

Which would annotate that addOne is a good candidate for list fusion; i.e. if composed with another good candidate, they will—not might, but will—be fused. This pragma could be used as a way to guide the compiler, but I’m thinking of it more as a simple check: verify that this is what is happening anyway.

I don’t know enough about the optimization process to know whether ListStream would actually be a valid thing to check, what kinds of such identifiers there could be, which ones would be useful. But I always worry that the compiler will not do enough inlining to see the structure of my program and optimize intermeidate structures away. In fact I fixed a performance issue in Yampa recently that had exactly this problem: integral was not being inlined, which caused allocations instead of simple hardware loops, which caused a 90% performance hit. I’m simply exploring a way to ensure that the optimizations you expect are actually happening, and if you break them, you get yelled at.

</jot>

About these ads

3 thoughts on “Required Optimization

  1. This is an excellent idea! It’d be useful in other languages as well, not just Haskell, but in Haskell it’s definitely needed. It’d also be nice if there was a compiler option to add notices to your code when it uses an optimization so that if it doesn’t use that optimization anymore you’d be notified.

  2. This exposes a problem with Haskell, it’s not close enough to the actual system and too academic.

    Haskell is cool, but not for optimized programs.

  3. People have talked about this idea a lot, but I’m not sure the way you present it would work. Suppose I write “{-# OPTIMIZE ListStream addOne #-}”. What if there’s more than one site in addOne where the ListStream optimization could be applied? Maybe there is one site that the compiler finds “easy” but that is an infrequently invoked bit of code, and I really care about applying ListStream in the common case, which is for some reason more difficult for the compiler to do. For this to be effective, I have to specify *where* in my function I want the optimization to be applied. But at this point, I might as well just write the optimized code myself — since I would have to know exactly what it’s supposed to look like — right?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s