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