构造函数/模式匹配顺序/守卫/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.

在哪些方面，顺序对性能有微小的可测量影响？特别是我想知道关于带有许多选项的条件语句。

- Michael Fox

---

FYI，GHC 7.0已经发布了4年，所以事情可能已经发生了变化。 - ErikR

@user5402，是的，但他们还没有。我认为这段特定的代码在最近的历史中没有被修改过。 - dfeuer

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特别可能，则尤其令人恼火。但目前就是这样，更改它将使某些情况下的性能变差，而不会有人做大量的工作。

- dfeuer

---

我曾认为对于函数定义，GHC尊重您定义模式的顺序，因为如果它决定重新排列可能重叠的模式，则可能会使您的函数表现不正确。 - bheklilr

简单的构造器模式，如 Bin x y 和 Tip x 显然不会重叠。当然，使用相同构造器的多个模式可以重叠，且不能重新排序。你在考虑哪种模式？ - ErikR

@bheklilr，GHC 尊重模式匹配的语义，但不尊重实际的代码结构，因此性能可能会有所不同。它对文字常量的相等性有特殊的代码处理方式，并且像我展示的那样粉碎 case。还有各种其他事情，比如 case-of-case 转换。 - dfeuer