performance - 根据匹配顺序的OCaml性能

Question

在 OCaml 中，模式匹配中的顺序与性能之间是否存在任何关系？

例如，如果我声明一个类型：

type t = A | B | C

然后执行一些模式匹配，如下所示：

match t1 with
  | A -> ...
  | _ -> ...

从性能的角度来看，它是否等同于

match t1 with
  | B -> ...
  | _ -> ...

假设在第一种情况下，在第二种情况下 A 的数量与 B 的数量一样多？

换句话说，在考虑性能时，我是否应该担心类型中构造函数的声明顺序？

score 5 · Accepted Answer

有一篇论文解释了如何在 OCaml 中编译模式匹配：“Optimizing Pattern Matching”，L. Maranget 和 F. Le Fessant，ICFP'01

它基本上说语义是“按顺序”的，但它通常以最佳方式编译，与行的顺序无关。构造函数的值也不重要，重要的是构造函数的数量，即它是由比较树还是由跳转表编译的。

最优性 + 穷举性测试使得 OCaml 中的模式匹配可能是该语言最精彩的特性，并且比手动编写级联的“if”效率更高。

score 2 · Accepted Answer

这是一个不可能仔细回答的问题。然而，在实践中，如果你有一个类型，它的构造函数都是空的（即，相当于小整数），而且它们的数量非常少，但少于一大堆，代码生成器几乎肯定会使用硬件跳转表，它对每个可能的值具有基本相同的性能。

一般来说，在您确定代码的慢速部分之前，我根本不会担心这样的事情。但是几乎没有机会通过重新排序一组空构造函数来加快速度。

2 回答 2