StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow do you write data structures that are as efficient as possible in GHC?
text
Body
copied!<p>So sometimes I need to write a data structure I can't find on Hackage, or what I find isn't tested or quality enough for me to trust, or it's just something I don't want to be a dependency. I am reading Okasaki's book right now, and it's quite good at explaining how to design asymptotically fast data structures.</p> <p>However, I am working specifically with GHC. Constant factors are a big deal for my applications. Memory usage is also a big deal for me. So I have questions specifically about GHC.</p> <p>In particular</p> <ul> <li>How to maximize sharing of nodes</li> <li>How to reduce memory footprint</li> <li>How to avoid space leaks due to improper strictness/laziness</li> <li>How to get GHC to produce tight inner loops for important sections of code</li> </ul> <p>I've looked around various places on the web, and I have a <em>vague</em> idea of how to work with GHC, for example, looking at core output, using <code>UNPACK</code> pragmas, and the like. But I'm not sure I get it.</p> <p>So I popped open my favorite data structures library, containers, and looked at the Data.Sequence module. I can't say I understand a lot of what they're doing to make Seq fast.</p> <p>The first thing that catches my eye is the definition of <code>FingerTree a</code>. I assume that's just me being unfamiliar with finger trees though. The second thing that catches my eye is all the <code>SPECIALIZE</code> pragmas. I have no idea what's going on here, and I'm very curious, as these are littered all over the code.</p> <p>Many functions also have an <code>INLINE</code> pragma associated with them. I can guess what that means, but how do I make a judgement call on when to <code>INLINE</code> functions?</p> <p>Things get really interesting around line ~475, a section headered as 'Applicative Construction'. They define a newtype wrapper to represent the Identity monad, they write their own copy of the strict state monad, and they have a function defined called <code>applicativeTree</code> which, apparently is specialized to the Identity monad and this increases sharing of the output of the function. I have no idea what's going on here. What sorcery is being used to increase sharing?</p> <p>Anyway, I'm not sure there's much to learn from Data.Sequence. Are there other 'model programs' I can read to gain wisdom? I'd really like to know how to soup up my data structures when I really need them to go faster. One thing in particular is writing data structures that make fusion easy, and how to go about writing good fusion rules.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload