Почему сокращение быстрее, чем сумма или sumBy?

Моя коллега и я сравнивали скорость функций С# при передаче в лямбдасе работы по сравнению с встроенными функциями в отношении времени, затраченного на выполнение работы. Мы обнаружили, что вы понесли стоимость при прохождении в проекции лямбды на функцию выбора С# (например) и хотели увидеть, были ли у F # одинаковые проблемы или что-то другое.

Независимо от нашего первоначального намерения, мы наткнулись на то, что мы не можем понять. В следующем примере мы суммируем список 3 разных способа

Сокращение
Сумма
SumBy

module fs

open NUnit.Framework
open FsUnit
open System
open System.Diagnostics;

[<Test>]
let sumTest() = 
    let nums = [0..1000]

    let repeat = 100000

    let stopWatch = new Stopwatch()

    stopWatch.Start()

    let sumsReduce = 
        [
            for i in [0..repeat] do
                yield List.reduce (+) nums
        ]

    Console.WriteLine("reduce = {0} - Time = {1}", List.head sumsReduce, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()

    let sumsSum = 
        [
            for i in [0..repeat] do
                yield List.sum nums
        ]

    Console.WriteLine("sum = {0} - Time = {1}", List.head sumsSum, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()


    let sumsSumBy = 
        [
            for i in [0..repeat] do
                yield List.sumBy id nums
        ]

    Console.WriteLine("sumBy = {0} - Time = {1}", List.head sumsSumBy, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()

Вывод на это выглядит так:

reduce = 500500 - Time = 0.2725156
sum = 500500 - Time = 1.1183165
sumBy = 500500 - Time = 1.1126781

Так ясно, что это большой победитель здесь. В декомпиляции я вижу, что сокращение сокращается

[Serializable]
internal class sumsReduce\u004021\u002D1 : OptimizedClosures.FSharpFunc<int, int, int>
{
  internal sumsReduce\u004021\u002D1()
  {
    base.\u002Ector();
  }

  public override int Invoke(int x, int y)
  {
    return x + y;
  }
}

Но мне сложно определить, какую сумму и sumBy делают. Где временное расхождение от?

В текущем ответе было сказано, что сокращение в 5 раз быстрее, потому что изначально я давал возможность уменьшить неконтролируемый оператор. Тем не менее, обновление теста для использования проверяемого оператора (из модуля Checked), и я все равно получаю тот же результат

let sumsReduce = 
        [
            for i in [0..repeat] do
                yield List.reduce (Checked.(+)) nums
        ]

Обратите внимание, что временное несоответствие все еще существует

reduce = 500500 - Time = 0.274697
sum = 500500 - Time = 1.1126796
sumBy = 500500 - Time = 1.1370642

Ответ 1

Сумма и SumBy используют перечислитель:

    while e.MoveNext() do
        acc <- Checked.(+) acc e.Current
    acc

тогда как сокращение использует рекурсивный цикл с оптимизированным замыканием: (сокращение использует сгиб под крышкой - сгиб хвоста головы)

    let fold<'T,'State> f (s:'State) (list: 'T list) = 
        match list with 
        | [] -> s
        | _ -> 
            let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
            let rec loop s xs = 
                match xs with 
                | [] -> s
                | h::t -> loop (f.Invoke(s,h)) t
            loop s list

Использование оптимизированных закрытий часто может привести к повышению производительности.

Ответ 2

sum и sumBy используйте проверочную арифметику, но вы передаете непроверенный оператор + в reduce - не совсем яблоки для яблок.