Re: Order of constructors in Data.Map.Internal

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 . wrote:

Awesome, thanks.

On Sun, Feb 3, 2019, 7:35 PM Carter Schonwald

...

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 . 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries