Order of constructors in Data.Map.Internal

[Carter Schonwald]

I would like to also emphasize that doing robust measurement for these
things is super subtle.  There’s all sorts of cpu micro architecture things
you possibly need to account for , plus sometimes tools like perf and
dtrace apparently have “skids” where there’s hard to avoid
attribution/measurement errors in an instruction stream. Or I’m totally out
of date and wrong. Or both

On Sun, Feb 3, 2019 at 7:39 PM chessai . <chessai1996 at gmail.com> wrote:

> Awesome, thanks.
>
> On Sun, Feb 3, 2019, 7:35 PM Carter Schonwald <carter.schonwald at gmail.com
> wrote:
>
>> This is about first run  branch prediction on cpus and how constructor
>> order can influence code gen of case expressions.
>>
>> This is more Andreask’S wheelhouse rather than David’s.  In fact Andreas
>> has some work to make things like this easier to do in progress.
>>
>> Johan did some super detailed benchmarking when he did this and other
>> work.  Perhaps he can share with you more about how he did it. I ccd him on
>> this email.
>>
>> On Mon, Jan 28, 2019 at 4:44 PM chessai . <chessai1996 at gmail.com> wrote:
>>
>>> When looking through the source of Data.Map.Internal, there's a note:
>>>
>>> -- [Note: Order of constructors]
>>> -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>> -- The order of constructors of Map matters when considering performance.
>>> -- Currently in GHC 7.0, when type has 2 constructors, a forward
>>> conditional
>>> -- jump is made when successfully matching second constructor.
>>> Successful match
>>> -- of first constructor results in the forward jump not taken.
>>> -- On GHC 7.0, reordering constructors from Tip | Bin to Bin | Tip
>>> -- improves the benchmark by up to 10% on x86.
>>>
>>> I've been curious about this for a while now. GHC 7.0 was released
>>> quite a long time ago, so I wonder if this is still the case? David
>>> might know.
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190203/a4ed3bef/attachment.html>