<p dir="ltr">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.</p>
<p dir="ltr">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.</p>
<p dir="ltr">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.</p>
<p dir="ltr">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.</p>
<div class="gmail_extra"><br><div class="gmail_quote">On Aug 14, 2016 6:52 AM, "Anthony Clayden" <<a href="mailto:anthony_clayden@clear.net.nz">anthony_clayden@clear.net.nz</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div style="text-align:left"><div>Firstly, to correct myself:</div><div><br></div><div><span style="background-color:rgba(255,255,255,0)">> Contrast that with Data.Set [*],
you could stream the contents to a list and filter.</span></div><div><span style="background-color:rgba(255,255,255,0)">> (Which would be horribly inefficient for my purposes.) </span></div><div><span style="background-color:rgba(255,255,255,0)"><br></span></div><div><span style="background-color:rgba(255,255,255,0)">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.)</span></div><div><span style="background-color:rgba(255,255,255,0)"><br></span></div><div><span style="background-color:rgba(255,255,255,0)">> [*] Data.Set seems to have been swallowed into the new
collections library,</span></div><div><span style="background-color:rgba(255,255,255,0)">> which is not currently maintained </span><br></div><div><span style="background-color:rgba(255,255,255,0)"><br></span></div><div><span style="background-color:rgba(255,255,255,0)">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.</span></div><div><br></div><div>But I have some q's about the optimisations:</div><div>The hedge-union algorithm seems to have been taken out, as inefficient.</div><div>(per treeowl on github). But the code on hackage still uses hedge??</div><div>So the docos are out of date. (And quite a bit of commentary on StackOverflow.) </div><div>Was it really not more efficient?</div><div><br></div><div>The Set data type's constructors got reordered (Bin is now first, Tip is second).</div><div>On grounds it "improves the benchmark by up to 10%".</div><div>Are you sure it makes that much difference?</div><div>Are you sure it makes any difference at all?</div><div></div>The culprit seems to be pattern matching. It makes me feel there's something seriously wrong with GHC's code generator.<div>(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.)<br><br>Set is a purely functional data structure, no in-situ updating of nodes, no pointer semantics<div>unlike imperative/low-level implementations of balanced binary trees.</div><div>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?</div><div><br></div><div>Contrast that in an imperative/low-level model they'd be null pointers, nothing allocated.</div><div>Note the number of Tips is equal the number of values in the tree, + 1.<br>Would it save construction/destruction/<wbr>access overhead to have three extra constructors?</div><div>| both sub-trees are empty </div><div>| left (only) is empty</div><div>| right (only) is empty</div><div><br></div><div>If it's true per above that each constructor adds a performance penalty just doing the pattern matching, I guess the answer is 'no' :-(</div><div><br></div><div>Thanks</div><div>AntC</div><div><div><blockquote style="border-left:1px solid #fc2c38;margin:10px 10px 10px 5px;padding:0 0 0 10px"><div><div><div><br>
</div>
</div>
</div>
</blockquote></div></div></div></div></div>
</blockquote></div></div>