构造函数/案例/警卫/ if-then-else的顺序对性能有影响吗？

Question

我在Containers/Data/Set/Base.hs中看到了这条评论

-- [Note: Order of constructors]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- The order of constructors of Set 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.

订单还有哪些地方对业绩产生微小的可衡量影响？特别是我想知道有很多选项的案例陈述.

Answer 1

这取决于.不幸的是,构造函数的顺序确实有所作为.这意味着该类型的模式顺序不会.不管你是不是写

foo (Bin x y) = ...
foo Tip = ...

要么

foo Tip = ...
foo (Bin x y) = ...

没有区别,因为它们将在"desugaring"过程中立即由构造函数顺序重新排序.多个模式的匹配顺序在语义上始终是从左到右,因此如果您一起使用多个模式,参数顺序可能很重要(您可以随时解决这个问题case).但是,GHC可以非常自由地重新组织代码,有时是好的,有时是为了生病.例如,如果你写

foo :: Int -> Bool
foo x = x == 5 || x == 0 || x == 7 || x == 4

GHC将其粉碎(基本上)

foo = \x -> case x of
              0 -> True
              4 -> True
              5 -> True
              7 -> True
              _ -> False

然后对这些可能性进行二元搜索.在许多情况下,这可能不是最佳选择,如果你碰巧知道这种x==5情况特别可能,那就特别烦人了.但这就是现在的情况,如果没有人做很多工作,改变它会使事情在某些情况下表现不佳.