<div dir="auto">That answer (which I did indeed write once upon a time) is somewhat incomplete. Case matches on Ints actually work in about three different ways:<div dir="auto"><br></div><div dir="auto">1. Linear search</div><div dir="auto">2. Binary search</div><div dir="auto">3. Jump table</div><div dir="auto"><br></div><div dir="auto">There's some amount of mix and match available for gappy things. I don't know all the details. As for tag matching, I know none of the mechanics. I just know that I've always been told to make the first constructor hot.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Feb 23, 2022, 12:08 AM Clinton Mead <<a href="mailto:clintonmead@gmail.com">clintonmead@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">David,<div><br></div><div>A random google search has revealed this <a href="https://stackoverflow.com/a/27324088/525980" target="_blank" rel="noreferrer">StackOverflow answer</a>, presumably by yourself or your evil twin, which mentions a binary search being performed. However the particular case you mention is a case match on "Ints", which are far from a dense set, whereas presumably you could do something nicer on the tag bits of constructors, which are a dense set?</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Feb 23, 2022 at 1:59 PM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">You can ask, but someone else will have to answer. Sorry.<br>
<br>
On Tue, Feb 22, 2022 at 9:52 PM Clinton Mead <<a href="mailto:clintonmead@gmail.com" target="_blank" rel="noreferrer">clintonmead@gmail.com</a>> wrote:<br>
><br>
> Thanks David. Can I ask why? Is it because the first constructor is treated specially? (perhaps because it has zeroed tag bits)? Or is it just because there's always an if/else chain in order of the constructor definition regardless of the order of the case statement so the higher up the list the better?<br>
><br>
> On Wed, Feb 23, 2022 at 1:34 PM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>> wrote:<br>
>><br>
>> I can answer one of your questions for sure: the order of your case branches doesn't matter at all. However, the order of the data constructors in the type declaration does matter. Put your most likely one first.<br>
>><br>
>> On Tue, Feb 22, 2022, 9:09 PM Clinton Mead <<a href="mailto:clintonmead@gmail.com" target="_blank" rel="noreferrer">clintonmead@gmail.com</a>> wrote:<br>
>>><br>
>>> Hi All<br>
>>><br>
>>> I'm developing an unbounded integer type, which I won't go into the details here but in some circumstances has better performance than the standard "Integer".<br>
>>><br>
>>> Anyway, whilst there are complex cases, the most common case is a standard machine int multiplication.<br>
>>><br>
>>> Hence I want the type to be optimised for that case.<br>
>>><br>
>>> I'm going to have a few constructors, anyway, so I first considered something like this:<br>
>>><br>
>>> `data MyInt = BasicZero | BasicPos Word | BasicNeg Word | ComplexPosA ... | ComplexNegA ... | ComplexPosB ... | ComplexNegB ...`<br>
>>><br>
>>> I'd naturally make the "Word"s in "BasicPos" and "BasicNeg" strict/unpack, hopefully eliminating the indirection, or perhaps just making them primitive directly.<br>
>>><br>
>>> This has 7 constructors, which quite nicely I believe fits into the three spare bits in a 64 bit pointer which GHC optimises I believe.<br>
>>><br>
>>> However, this approach I thought of because I assumed that GHC would do a switch style statement on the constructors, so once I have more than one I might as well have as many as I want (well, up to 7, until I lose the optimisation).<br>
>>><br>
>>> But if GHC compiles this to a "if ... else if..." chain, a better representation is the following:<br>
>>><br>
>>> `data MyInt = BasicInt Int | ComplexPosA ... | ComplexNegA ... | ComplexPosB ... | ComplexNegB ...`<br>
>>><br>
>>> That way I can match against BasicInt first, and knock that out of the way as my "hot" case. However, using "Int" instead of "Word" does make the logic a bit more complex, but it may be worth it if I'm reducing the number of patterns I have to check against for all arguments.<br>
>>><br>
>>> I was just wondering if anyone could share some insight on what GHC does in these circumstances? For example, does the order I list my cases in a case statement matter if they're non-overlapping? Will GHC match them in the order I list, or will it just make them into a switch statement so it doesn't matter if I reorder them?<br>
>>><br>
>>> I guess I could benchmark all this (and probably will) but some insights and general guidance would be good.<br>
>>><br>
>>> Thanks,<br>
>>> Clinton<br>
>>> _______________________________________________<br>
>>> Glasgow-haskell-users mailing list<br>
>>> <a href="mailto:Glasgow-haskell-users@haskell.org" target="_blank" rel="noreferrer">Glasgow-haskell-users@haskell.org</a><br>
>>> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users</a><br>
</blockquote></div>
</blockquote></div>