12

作为这个问题的后续行动，F# 的内置不变性相对于 C# 有哪些优势？——我是否正确假设 F# 编译器可以进行某些优化，因为它知道它正在处理大部分不可变的代码？我的意思是，即使开发人员编写了“函数式 C#”，编译器也不知道开发人员试图编写的所有不变性，因此无法进行相同的优化，对吧？

一般来说，函数式语言的编译器是否能够进行命令式语言无法实现的优化——即使是用尽可能多的不变性编写的语言？

4

6 回答 6

20

我是否正确假设 F# 编译器可以进行某些优化，因为它知道它正在处理大部分不可变的代码？

不幸的是没有。对于编译器作者来说，“基本上不可变”和“不可变”之间存在巨大差异。即使保证不变性对优化器来说也不是那么重要。它给你带来的主要好处是你可以编写一个非常激进的内联。

一般来说，函数式语言的编译器是否能够进行命令式语言无法实现的优化——即使是用尽可能多的不变性编写的语言？

是的，但这主要是一个能够在更多地方更轻松地应用经典优化的问题。例如，不变性使得应用公共子表达式消除变得更加容易，因为不变性可以保证某些内存单元的内容不会改变。

另一方面，如果您的函数式语言不仅是不可变的而且是纯粹的（没有像 I/O 这样的副作用），那么您可以启用一类新的优化，包括将源级表达式重写为更有效的表达式。最重要和更有趣的内容之一是捷径砍伐森林，这是一种避免为中间结果分配内存空间的方法。一个很好的例子是流融合。

如果您正在编译静态类型的函数式语言以获得高性能，这里有一些重点：

  • 有效地使用内存。如果可以，请使用“未装箱”值，避免分配和对堆的额外间接级别。特别是河流融合和其他森林砍伐技术都非常有效，因为它们消除了分配。

  • 拥有一个超快速的分配器，并在多个分配上摊销堆耗尽检查。

  • 内联函数有效。特别是跨模块边界的内联小函数。

  • 有效地表示一等函数，通常通过闭包转换。有效地处理部分应用的功能。

  • 不要忽视经典的标量和循环优化。它们对 TIL 和 Objective Caml 等编译器产生了巨大的影响。

如果您有像 Haskell 或 Clean 这样的惰性函数式语言，那么还有很多专门的事情与 thunk 相关。

脚注：

  • 具有完全不变性的一个有趣的选择是更有能力执行非常细粒度的并行性。这个故事的结局还没有说完。

  • 为 F# 编写一个好的编译器比编写一个典型的编译器（如果有这样的事情）更难，因为 F# 受到如此严格的限制：它必须做好功能性的事情，但它也必须在 .NET 框架内有效地工作，这是设计时没有考虑到函数式语言。我们应该感谢 Don Syme 和他的团队在一个严重受限的问题上做了如此出色的工作。

于 2010-02-06T02:53:59.953 回答
7

不。

F# 编译器不会尝试分析方法或 lambda 的引用透明度。.NET BCL 根本不是为此而设计的。

F# 语言规范确实保留了关键字“pure”，因此可以在 vNext 中手动将方法标记为纯，从而允许更积极地减少 lambda 表达式的图形。

但是，如果您使用记录或代数类型，F# 将创建默认的比较和相等运算符，并提供复制语义。在许多其他好处（模式匹配、封闭世界假设）中，这减轻了巨大的负担！

于 2010-02-06T01:14:35.633 回答
5

是的，如果您不考虑 F#，但可以考虑 Haskell。没有副作用的事实确实为优化开辟了很多可能性。

例如考虑使用类似 C 的语言：

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

如果相应的方法是用 Haskell 编写的，那么当您调用 factorialuser 时，将不会再调用 factorial。在 C# 中可能可以做到这一点，但我怀疑当前的编译器会这样做，即使是这样一个简单的例子。随着事情变得越来越复杂，C# 编译器将很难优化到 Haskell 可以做到的水平。

请注意，目前 F# 并不是真正的“纯”函数式语言。所以，我引入了 Haskell（这很棒！）。

于 2010-02-06T00:57:34.593 回答
3

不幸的是，因为 F# 大部分只是纯粹的，所以没有太多机会进行积极优化。事实上，与 C# 相比，F# 在某些地方“悲观”了代码（例如，制作结构的防御性副本以防止可观察到的突变）。从好的方面来说，尽管如此，编译器总体上做得很好，在大多数地方提供了与 C# 相当的性能，同时使程序更容易推理。

于 2010-02-06T01:26:32.730 回答
2

我会说“不”。

您从不变性或引用透明性中获得的主要“优化”优势是当您看到类似...f(x)...f(x).... 但是如果没有非常精确的信息，这种分析很难做到，而且由于 F# 在 .Net 运行时上运行，而 .Net 无法将方法标记为纯（无效果），它需要大量内置信息和分析才能甚至尝试做任何这些。

另一方面，在像 Haskell 之类的语言中（主要是指“Haskell”，因为很少有人听说过或使用过“像 Haskell”这样的语言:)），它是惰性和纯粹的，分析更简单（一切都是纯，发疯）。

也就是说，这种“优化”通常会与系统的其他有用方面（性能可预测性、调试......）产生不良交互。

经常有“一个足够聪明的编译器可以做 X”的故事，但我认为“足够聪明的编译器”是一个神话，而且永远都是一个神话。如果你想要快速的代码，那就写快速的代码；编译器不会拯救你。如果您想要消除公共子表达式，请创建一个局部变量（自己做）。

这主要是我的意见，欢迎您投反对票或不同意（事实上，我听说“多核”被认为是潜在的“优化可能再次变得性感”的一个上升原因，这在表面上听起来似乎是合理的）。但是，如果您对任何编译器进行任何重要的优化（源代码中的注释不支持）抱有希望，那么请准备好等待很长很长时间才能实现您的希望。

不要误会我的意思 - 不变性很好，并且可能会帮助您在许多情况下编写“快速”代码。但不是因为编译器对其进行了优化——而是因为代码易于编写、调试、正确、并行化、分析和决定哪些是最重要的瓶颈，需要花费时间（可能会可变地重写它们）。如果您想要高效的代码，请使用可让您快速开发、测试和分析的开发流程。

于 2010-02-06T01:40:42.330 回答
2

函数式语言的额外优化有时是可能的，但不一定是因为不变性。在内部，许多编译器会将代码转换为 SSA（单一静态分配）形式，其中函数内的每个局部变量只能分配一次。对于命令式和函数式语言都可以做到这一点。例如：

x := x + 1
y := x + 4

可以变成

x_1 := x_0 + 1
y := x_1 + 4

其中x_0和x_1是不同的变量名。这极大地简化了许多转换，因为您可以移动代码位，而不必担心它们在程序中的特定点有什么价值。但是，这不适用于存储在内存中的值（即全局变量、堆值、数组等）。同样，这适用于函数式和命令式语言。

大多数函数式语言提供的一个好处是强大的类型系统。这允许编译器做出假设，否则它将无法做到。例如，如果您有两个不同类型的引用，编译器知道它们不能别名（指向同一事物）。这不是 C 编译器可以做出的假设。

于 2010-02-06T01:29:49.470 回答