Pourquoi réduire plus vite que sum ou sumBy?

Question

Mon collègue et moi comparions la vitesse des fonctions C# lors du passage en lambdas pour faire du travail par rapport aux fonctions inline en ce qui concerne le temps passé à travailler. Nous avons constaté que vous avez encouru un coût lors de la transmission d'une projection lambda à une fonction de sélection C# (par exemple) et que vous vouliez voir si F # avait les mêmes problèmes, ou s'il faisait quelque chose de différent. Indépendamment de notre intention d'origine, nous avons trébuché sur quelque chose que nous ne pouvons pas comprendre. Dans l'exemple suivant, nous additionnons une liste de 3 façons différentes

1. Réduire
2. Somme
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() 

La sortie à cela ressemble à:

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

Donc clairement réduire est le grand gagnant ici. Dans la décompilation, je peux voir qui permettent de réduire obtient bouilli vers le bas

[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; 
    } 
} 

Mais je vais avoir du mal à comprendre quelle somme et sumBy font. D'où vient l'écart de synchronisation?

---

La réponse actuelle a suggéré que réduire est 5 fois plus rapide parce que je donnais à l'origine réduire un opérateur non contrôlé. Cependant, la mise à jour du test à utiliser un opérateur contrôlé (à partir du module Checked) et je reçois toujours le même résultat

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

Notez la différence de temps existe encore

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

Answer 1

Sum et SumBy utilisent un énumérateur:

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

alors réduire utilise une boucle récursive avec une fermeture optimisée: (réduire les utilisations plient sous le de couverture - pli f tête queue)

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 

L'utilisation de fermetures optimisées peut souvent améliorer les performances.

Answer 2

sum et sumBy utilisation contrôlée arithmétique, mais vous passez l'opérateur non contrôlé + à reduce - pas exactement des pommes aux pommes.