Skip to content


Subversion checkout URL

You can clone with
Download ZIP


Improve performance by reordering constructors #17

tibbe opened this Issue · 4 comments

2 participants


Milan Straka reports the following improvements from reordering constructors in the containers package:

The order of constructors of IntSet and IntMap matters when considering
performance. Currently in GHC 7.0, when type has 3 constructors, they
are matched from the first to the last -- the best performance is
achieved when the constructors are ordered by frequency.

On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil
improves the containers_benchmark

  • by 9.5% on x86 and by 8% on x86_64 for IntMap
  • by 11% on x86 and by 9% on x86_64 for IntSet The performance should never decrease for any architecture.

is this ticket a todo for possibly improving performance?


It is. I did make a quick attempt of reordering the constructors, without seeing any gain (if I recall correctly.) I left the issue here to remind myself to look into it in depth in the future. It could be that GHC changed how it lays out branches in the code generator such that it no longer uses the data definition order, but the ordering of the case statement branches.


Cool. I may have a go at looking at this too sometime in the near term. I assume that the relative freq in the note means #(bin)> #(tip) > #(nil)


Yes that's right.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.