F#Array.reduce的性能

Question

我在做一些F#实验时注意到,如果为Array编写我自己的reduce函数,它的执行效果要比内置的reduce更好.例如:

type Array with
    static member inline fastReduce f (values : 'T[]) =
        let mutable result = Unchecked.defaultof<'T>
        for i in 0 .. values.Length-1 do
            result  <- f result values.[i]
        result

这似乎与内置的行为完全相同,Array.reduce但简单快了约2倍f

内置的一个更灵活吗？

Answer 1

通过查看生成的IL代码,可以更容易地了解正在发生的事情.

使用内置Array.reduce:

let reducer (vs : int []) : int = Array.reduce (+) vs

给出以下等效的C#(使用IL代码进行反向工程ILSpy)

public static int reducer(int[] vs)
{
  return ArrayModule.Reduce<int>(new Program.BuiltIn.reducer@31(), vs);
}

Array.reduce 看起来像这样:

public static T Reduce<T>(FSharpFunc<T, FSharpFunc<T, T>> reduction, T[] array)
{
  if (array == null)
  {
    throw new ArgumentNullException("array");
  }
  int num = array.Length;
  if (num == 0)
  {
    throw new ArgumentException(LanguagePrimitives.ErrorStrings.InputArrayEmptyString, "array");
  }
  OptimizedClosures.FSharpFunc<T, T, T> fSharpFunc = OptimizedClosures.FSharpFunc<T, T, T>.Adapt(reduction);
  T t = array[0];
  int num2 = 1;
  int num3 = num - 1;
  if (num3 >= num2)
  {
    do
    {
      t = fSharpFunc.Invoke(t, array[num2]);
      num2++;
    }
    while (num2 != num3 + 1);
  }
  return t;
}

请注意,它调用reducer函数f是一个虚拟调用,通常JIT:er难以内联.

与您的fastReduce功能相比:

let reducer (vs : int []) : int = Array.fastReduce (+) vs

反向工程C#代码:

public static int reducer(int[] vs)
{
  int num = 0;
  for (int i = 0; i < vs.Length; i++)
  {
    num += vs[i];
  }
  return num;
}

虚拟呼叫现在消失了,效率更高.似乎在这种情况下,F#既代码fastReduce也代表(+).

F#中存在某种截止,因为更复杂的reducer函数不会被内联.我不确定具体细节.

希望这可以帮助

旁注; Unchecked.defaultOf返回null.NET中类类型的值,例如string.我更喜欢LanguagePrimitives.GenericZero.

PS.真正的性能饥饿的一个常见技巧是循环0.在F#中for-expressions由于生成方式中的轻微性能错误而无效for-expressions.在这种情况下,您可以尝试使用尾递归来实现循环.