F＃编译器是否优化了对纯函数的多次调用？ [英] Does F# compiler optimize multiple calls to pure functions?

问题描述

我注意到当我使用相同的参数多次调用一个函数时，它们都是不可变的，在同一范围内，编译器不会保存第一个调用的结果，而这个调用将被用作其他调用的结果。该功能既不改变也不依赖于任何外部状态。上下文是完全纯粹和不可变的，至少与F＃一样多，我知道它允许杂质和几乎所有可以用.Net完成的事情。我创建了这个简单的代码示例来演示我的意思：

 让  rec  pureFib n： int64  = 
  if  n =  0  然后 
 1L 
 elif n =  1    
 1L 
  else  pureFib（n  -   2 ）+ pureFib（n  -   1 ）
 
 让 shouldBeCalledOnce n = 
 让 r1 = pureFib n 
 
 让 r2 = pureFib n 
  //  让r2 = r1 //取消注释这一行并评论前一行，你将得到几乎2倍的速度b oost  
 
 r1 + r2 

在我的电脑上调用shouldBeCalledOnce with n> 42最后足以注意到差异，你也可以使用这个入口点在控制台应用程序中测试它。

 [< EntryPoint>] 
 让 main argv = 
 让 crono = System.Diagnostics。 Stopwatch.StartNew（）
 让 v = shouldBeCalledOnce  43  
 printfn  ％A crono.ElapsedMilliseconds 
 int v 

这个问题（如果有的话）很容易获得，因此，我认为不需要复杂的基准测试。我使用optimize +编译代码，没有调试信息，只有pdb。

如果函数式编程的一个关键特性是函数在使用相同的参数调用时总是返回相同的值，那就是编译器应该使用避免多次无意义的调用以节省时间，并在某些情况下提高可读性和对代码的理解。

简而言之，我的问题如下：

1. F＃编译器是否有一种优化对纯函数的多次调用的方法？

2.对于第一个问题是真的，这意味着编译器能够知道函数何时是纯的什么时候不是。是吗？

解决方案

请确认我理解你的问题;看看我对这个问题的评论。



这是我的想法：在编译器级别，进行这种优化真的很难。在某些情况下，编译器没有足够的信息。考虑有一种方法可以发现函数是纯粹的。它不仅应该以递归方式检查某些函数的主体，还应检查所有被调用的函数。但并非所有此类函数都附带源代码。这个优化器会做什么？如果所有被调用的代码都是.NET代码，则可以对所有代码进行反向工程。但面对它：最终，一些代码将始终执行非托管调用（除非操作系统类似于奇点，纯托管操作系统）。你看，CLI标准没有元数据中的插槽，它带有关于函数纯度的信息，即使它是.NET BCL的一部分。



所以，这是我的论点，解释了为什么我认为这种优化没有意义（再次，请验证我理解你的想法是正确的;看看我对这个问题的评论）。但现在，在所有情况下，您都可以轻松地弄清楚实际情况。优化编译，获取程序集（IL代码）并对其进行反向工程。如果您使用.NET Reflector或开源ILSpy，这很容易做到质量非常好：

http://en.wikipedia.org/wiki/.NET_Reflector [ ^ ]，

http://ilspy.net [ ^ ]。







请参阅我对这个问题的评论，由于存在不同的函数参数，我在这里对这个优化的实际价值提出质疑。



对于极少有实际意义的情况（函数计算非常慢，使用相同参数或无参数计算很可能），您可以在应用程序级别轻松引入此类优化：创建函数字典基于输入函数参数的复合键找到的结果/>


因为你仍然没有多次重新计算函数结果并不重要，你可以为每个函数设置一个字典（你几乎不能拥有很多这样的函数），而不必把所有信息都放在函数参数上。如果可能只是基于参数值的哈希值。比如说，

 使用 System.Collections.Generic; 
 
  //   ...  
 
 type FunctionType =  //   ...  
 FunctionType MyFunction（ params   object  []参数）{ / *   ... * / }  //  可以是任何类型 
 
  //   ...  
 
 Dictionary< int，函数类型> myFunctionOptimizationDictionary = 
  new  Dictionary< int，FunctionType>（）; 
 
 
 FunctionType MyFunctionWrapper（ params   object  [] parameters）{ 
  int  key =  0 ; 
  foreach （ object  @object  参数）
 key ^ = @ object.GetHashCode（）;  //  例如 
 FunctionType结果; 
  if （！myFunctionOptimizationDictionary.TryGetValue（key， out  result）{
 result = MyFunction（参数）;  //  在其他情况下，没有电话 
 myFunctionOptimizationDictionary .Add（键，结​​果）; 
}  //   if  
  return 结果; 
} 

简单，不是吗。你可以轻松地使这个算法通用。



然而，这种优化的副作用可能是过度使用用于存储优化键和值的内存。总是权衡。这个事实也是一个告诉我们的一点在CLR级别实际使用优化会非常值得怀疑。



我希望我们现在可以解决这个问题。你会说什么？

-SA

I have noticed that when I call a function multiple times with the same arguments, all of them immutable, in the same scope, the compiler does not save the result of the first call to be used as the result of the other calls. The function neither change nor depend on any outside state. The context is completely "pure and immutable", at least as much as F# is, I’m aware that it allows impurity and almost everything that can be done with .Net. I created this simple code example to demonstrate what I mean:

let rec pureFib n : int64 =
    if n = 0 then
        1L
    elif n = 1 then
        1L
    else pureFib(n - 2) + pureFib(n - 1)
 
let shouldBeCalledOnce n =
    let r1 = pureFib n

    let r2 = pureFib n
    //let r2 = r1  //uncomment this line and comment the previuous one and you will get almost a 2x speed boost

    r1 + r2

On my computer calling shouldBeCalledOnce with n > 42 last enough to notice the difference, you can also use this entry point to test it in a console application.

[<EntryPoint>]
let main argv = 
    let crono = System.Diagnostics.Stopwatch.StartNew()
    let v = shouldBeCalledOnce 43
    printfn "%A" crono.ElapsedMilliseconds
    int v

The issue (if there is really one) is easy to get, so, I suppose there is no need for complex benchmarks. I compiled the code with optimize+ and without debug information, only pdb.
If one of the key features of functional programming is that a function will always return the same value when called with the same arguments, that’s something the compiler should use to avoid multiple meaningless calls to save time, and in some cases improve readability and the understanding of code.
In short, my questions are the following:
1. Does F# compiler have a way of optimizing multiple calls to pure functions?
2. For that first question to be true, it would imply that the compiler was able to know when a function is pure and when it is not. Does it?

解决方案

Please confirm that I understand your question correctly; look at my comment to the question.

Here is my idea: at the level of the compiler, it's really hard to do this optimization. In some cases, the compiler does not have enough information. Consider there is a way to figure out that the function is "pure". It should check up not only the body of some functions, but also all called functions, recursively. But not all such functions come with the source code. What would this optimizer do? If all the called code is the .NET code, it's possible to reverse-engineer all code. But face it: ultimately, some code will always do unmanaged calls (unless the OS is something like Singularity, pure managed OS). You see, the CLI standard does not have a slot in metadata which carry information on the "purity" of the function, even if it is a part of .NET BCL.

So, that was my arguments explaining why I don't think that such optimization makes sense (again, please validate that I understood your idea correctly; look at my comment to the question). But now, in all cases, you can easily figure out what is going on in reality. Optimize your compilation, obtain the assembly (IL code) and reverse-engineer it. This is easy to do with very good quality if you use .NET Reflector or open-source ILSpy:
http://en.wikipedia.org/wiki/.NET_Reflector[^],
http://ilspy.net[^].

[EDIT]

Please see also my comment to the question, where I question the practical value of this optimization, due to presence of different function arguments.

For those rare cases when it makes a lot of practical sense (function calculation is really slow, calculations with the same parameters or no parameters is quite likely), you can easily introduce such optimization on an application level: create a dictionary of functions results found by the compound key based on input function arguments.

As it's not critical that you still recalculate the function result few extra times, you could have one dictionary per function (you hardly can have many of such functions), not having to put all the information on the function parameters. If could be just a hash value based on parameters value. Say,

using System.Collections.Generic;

//...

type FunctionType = //...
FunctionType MyFunction(params object[] parameters) { /* ... */ }  // could be any types

//...

Dictionary<int, FunctionType> myFunctionOptimizationDictionary =
   new Dictionary<int, FunctionType>();


FunctionType MyFunctionWrapper(params object[] parameters) {
    int key = 0;
    foreach(object @object in parameters)
        key ^= @object.GetHashCode(); // for example
    FunctionType result;
    if (!myFunctionOptimizationDictionary.TryGetValue(key, out result) {
        result = MyFunction(parameters); // in other cases, there is no a call
        myFunctionOptimizationDictionary.Add(key, result);
    } //if       
    return result;
}

Simple, isn't it. You can easily make this algorithm generic.

However, the side effect of such optimization can be the overuse of the memory spent for storing the "optimized" keys and values. Always a trade off. This fact, too, is a point telling us that the practical use of the optimization at the CLR level would be quite questionable.

I hope we can close this issue now. What will you say?

—SA

这篇关于F＃编译器是否优化了对纯函数的多次调用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！