[Haskell-cafe] Data.Set optimisations [was: library for set of heterogeneous values?]

[David Feuer]

I don't really think we need to bring *two* mailing lists into this. I'm
treeowl. The hedge algorithms were usually slower on benchmarks and never
much faster. Their theoretical performance has never been understood well.
Divide and conquer is fast, and its theoretical performance bound is now
understood to be good. The new code is not on Hackage because I haven't
made a release yet. containers doesn't usually release a major version more
than once a year. This year it may get two, but there's no need to rush.

The Tip constructor is not allocated over and over. Nullary constructors of
any given type are shared. So there's just one Tip somewhere. GHC's pointer
tagging means that the pointers to Tip are almost never followed. Pattern
matching on a Tip value ends up just inspecting the two (32-bit) or three
(64-bit) tag bits on the pointer to it.

Yes, constructor order makes a difference, weird as that seems. When GHC
desugars a pattern match, it always reorders the case branches into
constructor order. Sometimes this is obviously good; certain large case
expressions are turned into jump tables. Sometimes this is not so good. One
of my predecessors (probably Milan Straka, but I'm not sure) ran a lot of
benchmarks and picked the constructor order that was usually best.

Milan Straka wrote a paper that, among other things, recommended adding an
additional singleton constructor. I don't actually know why he didn't do
that; I can try to ask him. It's possible that it made some things better
and others worse.

On Aug 14, 2016 6:52 AM, "Anthony Clayden" <anthony_clayden at clear.net.nz>
wrote:

> Firstly, to correct myself:
>
> > Contrast that with Data.Set [*], you could stream the contents to a list
> and filter.
> > (Which would be horribly inefficient for my purposes.)
>
> Thank you Libraries team. Data.Set seems to have been seriously revamped
> since I last looked, and now includes a 'proper' filter function. (It used
> to stream the Set to a List; filter the List; build a new Set.)
>
> > [*] Data.Set seems to have been swallowed into the new collections
> library,
> > which is not currently maintained
>
> Uhh. That was a dead link (of ~10 years ago, but Google still took me to
> it). Data.Set is in the **containers** library supported on hackage.
>
> But I have some q's about the optimisations:
> The hedge-union algorithm seems to have been taken out, as inefficient.
> (per treeowl on github). But the code on hackage still uses hedge??
> So the docos are out of date. (And quite a bit of commentary on
> StackOverflow.)
> Was it really not more efficient?
>
> The Set data type's constructors got reordered (Bin is now first, Tip is
> second).
> On grounds it "improves the benchmark by up to 10%".
> Are you sure it makes that much difference?
> Are you sure it makes any difference at all?
> The culprit seems to be pattern matching. It makes me feel there's
> something seriously wrong with GHC's code generator.
> (And the semantics of ADTs is that the first constructor is ordered first
> if you go `deriving (Ord)`. So there's usually a design reason driving the
> ordering of constructors -- eg Nothing ordered before Just; [] ordered
> before (:), which makes String ordering do the right thing.)
>
> Set is a purely functional data structure, no in-situ updating of nodes,
> no pointer semantics
> unlike imperative/low-level implementations of balanced binary trees.
> That means Tips (empty end-points) genuinely get allocated/built and
> accessed and garbaged on insert -- or does all that strictness
> annotation/INLINing alter that?
>
> Contrast that in an imperative/low-level model they'd be null pointers,
> nothing allocated.
> Note the number of Tips is equal the number of values in the tree, + 1.
> Would it save construction/destruction/access overhead to have three
> extra constructors?
> | both sub-trees are empty
> | left (only) is empty
> | right (only) is empty
>
> If it's true per above that each constructor adds a performance penalty
> just doing the pattern matching, I guess the answer is 'no' :-(
>
> Thanks
> AntC
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160814/e332f3f2/attachment.html>