Order of constructors in Data.Map.Internal

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Order of constructors in Data.Map.Internal

chessai .
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Order of constructors in Data.Map.Internal

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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Order of constructors in Data.Map.Internal

chessai .
Awesome, thanks.

On Sun, Feb 3, 2019, 7:35 PM Carter Schonwald <[hidden email] 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 . <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: 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 . <[hidden email]> wrote:
Awesome, thanks.

On Sun, Feb 3, 2019, 7:35 PM Carter Schonwald <[hidden email] 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 . <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries