Re: [Haskell-cafe] Re: Implementing "unionAll"

On Thu, Feb 18, 2010 at 5:22 PM, Leon Smith wrote:

On Thu, Feb 18, 2010 at 3:07 AM, Evan Laforge wrote:

...

BTW, I notice that your merges, like mine, are left-biased.  This is a useful property (my callers require it), and doesn't seem to cost anything to implement, so maybe you could commit to it in the documentation?

Ohh, I see it now, I just wasn't looking at the module doc.

Also, I did briefly consider giving up left bias.  GHC has an optimization strategy that seeks to reduce pattern matching,  and due to interactions with this I could have saved a few kilobytes of -O2 object code size by giving up left-bias.

Interesting... but left bias is so useful I think it's worth a few extra k.

If you are curious why,  I suggest taking a look at GHC's core output for each of these two variants.   The hackage package "ghc-core" makes this a little bit more pleasant,  as it can pretty-print it for you.

I can see there's one extra case in the first one, and I can tell the last case is the 'loop' case including the case on Ordering, but I admit I don't understand what the previous cases are doing. Core is really hard for me to read.

It's amazing to think that this library,  at 55k (Optimized -O2 for x64),  would take up most of the memory of my very first computer,  a Commodore 64.   Of course,  I'm sure there are many others on this list who's first computers had a small fraction of 64k of memory to play with.  :-)

It's not even that much assembly. I intended to write a small quick program... then I did it in haskell, and then I linked in the GHC API (fatal blow). Now the stripped optimized binary is 22MB (optimization doesn't seem to have an effect on size). The non-haskell UI part is 367k...