haskell - 构造函数/cases/guards/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.

还有什么地方订单对性能有微小的可衡量影响？我特别想知道带有多种选项的 case 语句。

Answer 1

这要看情况。不幸的是，构造函数的顺序确实会产生影响。这意味着该类型的模式顺序不。不管你写

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

或

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

没有什么区别，因为它们将在“脱糖”过程中立即按构造函数顺序重新排序。多个模式的匹配顺序在语义上始终是从左到右，因此如果同时使用多个模式，参数顺序可能很重要(您始终可以使用 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 特别有可能，这会特别烦人。但目前情况就是这样，改变它会让事情在某些情况下表现得很糟糕，而无需有人做很多工作。