F#
F # Wskazówki i porady dotyczące wydajności

.NET Framework algorithm ASP.NET C# Language Entity Framework Haskell Language GNU/Linux Scala Language Microsoft SQL Server wpf
Szukaj…


Wykorzystanie rekurencji ogona do efektywnego iteracji

Pochodzący z języków imperatywnych wielu programistów zastanawia się, jak napisać for-loop która kończy działanie wcześniej, ponieważ F# nie obsługuje break , continue ani return . Odpowiedzią w F# jest użycie rekurencji ogona, która jest elastycznym i idiomatycznym sposobem na iterację przy jednoczesnym zapewnieniu doskonałej wydajności.

Powiedzmy, że chcemy zaimplementować tryFind dla List . Jeśli F# obsługuje return , napiszemy tryFind trochę tak: 

let tryFind predicate vs =
  for v in vs do
    if predicate v then
      return Some v
  None

To nie działa w F# . Zamiast tego piszemy funkcję za pomocą rekurencji ogona: 

let tryFind predicate vs =
  let rec loop = function
    | v::vs -> if predicate v then 
                   Some v 
               else 
                   loop vs
    | _ -> None
  loop vs

Rekurencja ogona działa w F# ponieważ gdy kompilator F# wykryje, że funkcja jest rekurencyjna, przepisuje rekursję na wydajną while-loop . Za pomocą ILSpy możemy zobaczyć, że jest to prawdą w przypadku naszej loop funkcji: 

internal static FSharpOption<a> loop@3-10<a>(FSharpFunc<a, bool> predicate, FSharpList<a> _arg1)
{
  while (_arg1.TailOrNull != null)
  {
    FSharpList<a> fSharpList = _arg1;
    FSharpList<a> vs = fSharpList.TailOrNull;
    a v = fSharpList.HeadOrDefault;
    if (predicate.Invoke(v))
    {
      return FSharpOption<a>.Some(v);
    }
    FSharpFunc<a, bool> arg_2D_0 = predicate;
    _arg1 = vs;
    predicate = arg_2D_0;
  }
  return null;
}

Poza kilkoma niepotrzebnymi przypisaniami (które, mam nadzieję, że JIT-er wyeliminuje), jest to w zasadzie wydajna pętla.

Ponadto rekurencja ogona jest idiomatyczna dla F# ponieważ pozwala nam uniknąć stanu zmiennego. Rozważmy sum funkcji, która sumuje wszystkie elementy w List . Oczywista pierwsza próba byłaby następująca: 

let sum vs =
  let mutable s = LanguagePrimitives.GenericZero
  for v in vs do
    s <- s + v
  s

Jeśli przepiszemy pętlę do rekurencji ogona, możemy uniknąć stanu zmiennego: 

let sum vs =
  let rec loop s = function
    | v::vs -> loop (s + v) vs
    | _ -> s
  loop LanguagePrimitives.GenericZero vs

W celu zwiększenia wydajności kompilator F# przekształca to w while-loop która wykorzystuje stan zmienny.

Zmierz i zweryfikuj swoje założenia dotyczące wydajności

Ten przykład został napisany z myślą o języku F# , ale pomysły mają zastosowanie we wszystkich środowiskach

Pierwszą zasadą przy optymalizacji wydajności jest nie poleganie na założeniach; zawsze mierz i weryfikuj swoje założenia.

Ponieważ nie piszemy kodu maszynowego bezpośrednio, trudno jest przewidzieć, w jaki sposób kompilator i JIT: er przekształcają program w kod maszynowy. Dlatego musimy zmierzyć czas wykonania, aby zobaczyć oczekiwaną poprawę wydajności i sprawdzić, czy rzeczywisty program nie zawiera żadnych ukrytych kosztów ogólnych.

Weryfikacja jest dość prostym procesem, który polega na inżynierii wstecznej pliku wykonywalnego przy użyciu na przykład narzędzi takich jak ILSpy . JIT: er komplikuje weryfikację, ponieważ oglądanie rzeczywistego kodu maszynowego jest trudne, ale wykonalne. Jednak zwykle badanie IL-code daje duże korzyści.

Trudniejszym problemem jest pomiar; trudniejsze, ponieważ trudne jest ustawienie realistycznych sytuacji, które pozwalają zmierzyć ulepszenia kodu. Wciąż pomiar jest nieoceniony.

Analiza prostych funkcji F #

Przeanalizujmy kilka prostych funkcji F# które gromadzą wszystkie liczby całkowite w 1..n zapisane na różne sposoby. Ponieważ zakres jest prostą serią arytmetyczną, wynik można obliczyć bezpośrednio, ale na potrzeby tego przykładu iterujemy po całym zakresie.

Najpierw określamy kilka przydatnych funkcji do pomiaru czasu potrzebnego funkcji: 

// now () returns current time in milliseconds since start
let now : unit -> int64 =
  let sw = System.Diagnostics.Stopwatch ()
  sw.Start ()
  fun () -> sw.ElapsedMilliseconds

// time estimates the time 'action' repeated a number of times
let time repeat action : int64*'T =
  let v = action ()  // Warm-up and compute value

  let b = now ()
  for i = 1 to repeat do
    action () |> ignore
  let e = now ()

  e - b, v

time biegnie wielokrotnie. Musimy przeprowadzić testy przez kilkaset milisekund, aby zmniejszyć wariancję.

Następnie definiujemy kilka funkcji, które gromadzą wszystkie liczby całkowite w 1..n na różne sposoby. 

// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
  List.init (n + 1) id
  |> List.sum

// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
  Seq.init (n + 1) id
  |> Seq.sum

// Accumulates all integers 1..n using 'for-expression'
let accumulateUsingFor n =
  let mutable sum = 0
  for i = 1 to n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
  let mutable sum = 0
  for i in [1..n] do
    sum <- sum + i
  sum

// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
  let mutable sum = 0
  for i in 1..2..n do
    sum <- sum + i
  sum

// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
  let mutable sum = 0L
  for i in 1L..int64 n do
    sum <- sum + i
  sum |> int

// Accumulates all integers n..1 using 'for-expression' in reverse order
let accumulateUsingReverseFor n =
  let mutable sum = 0
  for i = n downto 1 do
    sum <- sum + i
  sum

// Accumulates all 64 integers n..1 using 'tail-recursion' in reverse order
let accumulateUsingReverseTailRecursion n =
  let rec loop sum i =
    if i > 0 then
      loop (sum + i) (i - 1)
    else
      sum
  loop 0 n

Zakładamy, że wynik jest taki sam (z wyjątkiem jednej funkcji, która wykorzystuje przyrost 2 ), ale występuje różnica w wydajności. Aby to zmierzyć, zdefiniowano następującą funkcję: 

let testRun (path : string) =
  use testResult = new System.IO.StreamWriter (path)
  let write   (l : string)  = testResult.WriteLine l
  let writef  fmt           = FSharp.Core.Printf.kprintf write fmt

  write "Name\tTotal\tOuter\tInner\tCC0\tCC1\tCC2\tTime\tResult"

  // total is the total number of iterations being executed
  let total   = 10000000
  // outers let us variate the relation between the inner and outer loop
  //  this is often useful when the algorithm allocates different amount of memory
  //  depending on the input size. This can affect cache locality
  let outers  = [| 1000; 10000; 100000 |]
  for outer in outers do
    let inner = total / outer

    // multiplier is used to increase resolution of certain tests that are significantly
    //  faster than the slower ones

    let testCases =
      [|
    //   Name of test                         multiplier    action
        "List"                              , 1           , accumulateUsingList
        "Seq"                               , 1           , accumulateUsingSeq
        "for-expression"                    , 100         , accumulateUsingFor
        "foreach-expression"                , 100         , accumulateUsingForEach
        "foreach-expression over List"      , 1           , accumulateUsingForEachOverList
        "foreach-expression increment of 2" , 1           , accumulateUsingForEachStep2
        "foreach-expression over 64 bit"    , 1           , accumulateUsingForEach64
        "reverse for-expression"            , 100         , accumulateUsingReverseFor
        "reverse tail-recursion"            , 100         , accumulateUsingReverseTailRecursion
      |]
    for name, multiplier, a in testCases do
      System.GC.Collect (2, System.GCCollectionMode.Forced, true)
      let cc g = System.GC.CollectionCount g

      printfn "Accumulate using %s with outer=%d and inner=%d ..." name outer inner

      // Collect collection counters before test run
      let pcc0, pcc1, pcc2 = cc 0, cc 1, cc 2

      let ms, result       = time (outer*multiplier) (fun () -> a inner)
      let ms               = (float ms / float multiplier)

      // Collect collection counters after test run
      let acc0, acc1, acc2 = cc 0, cc 1, cc 2
      let cc0, cc1, cc2    = acc0 - pcc0, acc1 - pcc1, acc1 - pcc1
      printfn "  ... took: %f ms, GC collection count %d,%d,%d and produced %A" ms cc0 cc1 cc2 result

      writef "%s\t%d\t%d\t%d\t%d\t%d\t%d\t%f\t%d" name total outer inner cc0 cc1 cc2 ms result

Wynik testu podczas pracy na .NET 4.5.2 x64:

Wyniki testu na .NET 4.5.2 x64

Widzimy dramatyczną różnicę, a niektóre wyniki są nieoczekiwanie złe.

Spójrzmy na złe przypadki:

Lista 

// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
  List.init (n + 1) id
  |> List.sum

To, co się tutaj dzieje, to pełna lista zawierająca wszystkie liczby całkowite 1..n jest tworzony i redukowany za pomocą sumy. Powinno to być droższe niż tylko iteracja i akumulacja w całym zakresie, wydaje się około 42 razy wolniejsze niż pętla for.

Ponadto widzimy, że GC działało około 100 razy podczas uruchomienia testowego, ponieważ kod przydzielił wiele obiektów. To również kosztuje procesor.

Seq 

// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
  Seq.init (n + 1) id
  |> Seq.sum

Wersja Seq nie przydziela pełnej List więc trochę zaskakujące jest to, że ~ 270x wolniej niż w pętli for. Ponadto widzimy, że GC wykonał 661x.

Seq jest nieefektywna, gdy ilość pracy na element jest bardzo mała (w tym przypadku sumując dwie liczby całkowite).

Nie chodzi o to, aby nigdy nie używać Seq . Chodzi o to, aby zmierzyć.

( edycja manofstick: Seq.init jest winowajcą tego poważnego problemu z wydajnością. O wiele skuteczniejsze jest użycie wyrażenia { 0 .. n } zamiast Seq.init (n+1) id . To stanie się znacznie bardziej wydajne kiedy ten PR zostanie scalony i wydany. Jednak nawet po wydaniu oryginalny Seq.init ... |> Seq.sum będzie nadal Seq.init ... |> Seq.sum powoli, ale nieco sprzecznie z intuicją, Seq.init ... |> Seq.map id |> Seq.sum będzie dość szybki. Miało to na celu zachowanie kompatybilności wstecznej z implementacją Seq.init , która początkowo nie oblicza Current , ale raczej owija je w obiekt Lazy - chociaż to również powinno działać nieco lepiej ze względu na ten PR Uwaga dla redaktora: przepraszam, to jest trochę gadatliwych notatek, ale nie chcę, aby ludzie byli zniechęcani Seq, gdy poprawa jest tuż za rogiem ... Gdy nadejdzie ten czas, dobrze byłoby zaktualizować wykresy które są na tej stronie ).

wyrażenie foreach nad Listą 

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
  let mutable sum = 0
  for i in [1..n] do
    sum <- sum + i
  sum

Różnica między tymi dwoma funkcjami jest bardzo subtelna, ale różnica w wydajności nie jest z grubsza ~ 76x. Dlaczego? Przebudujmy zły kod: 

public static int accumulateUsingForEach(int n)
{
  int sum = 0;
  int i = 1;
  if (n >= i)
  {
    do
    {
      sum += i;
      i++;
    }
    while (i != n + 1);
  }
  return sum;
}

public static int accumulateUsingForEachOverList(int n)
{
  int sum = 0;
  FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
  for (FSharpList<int> tailOrNull = fSharpList.TailOrNull; tailOrNull != null; tailOrNull = fSharpList.TailOrNull)
  {
    int i = fSharpList.HeadOrDefault;
    sum += i;
    fSharpList = tailOrNull;
  }
  return sum;
}

accumulateUsingForEach realizowany jest jako skuteczny while pętla ale for i in [1..n] przekształca się: 

FSharpList<int> fSharpList =
  SeqModule.ToList<int>(
    Operators.CreateSequence<int>(
      Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));

Oznacza to, że najpierw tworzymy Seq ponad 1..n a na koniec wywołuje ToList .

Kosztowny.

przyrost wyrażenia foreach o 2 

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
  let mutable sum = 0
  for i in 1..2..n do
    sum <- sum + i
  sum

Po raz kolejny różnica między tymi dwiema funkcjami jest subtelna, ale różnica w wydajności jest brutalna: ~ 25x

Jeszcze raz ILSpy : 

public static int accumulateUsingForEachStep2(int n)
{
  int sum = 0;
  IEnumerable<int> enumerable = Operators.OperatorIntrinsics.RangeInt32(1, 2, n);
  foreach (int i in enumerable)
  {
    sum += i;
  }
  return sum;
}

Seq jest tworzony na 1..2..n a następnie 1..2..n na Seq za pomocą modułu wyliczającego.

Spodziewaliśmy się, że F# stworzy coś takiego: 

public static int accumulateUsingForEachStep2(int n)
{
  int sum = 0;
  for (int i = 1; i < n; i += 2)
  {
    sum += i;
  }
  return sum;
}

Jednak kompilator F# obsługuje tylko wydajne pętle w zakresach int32, które zwiększają się o jeden. We wszystkich innych przypadkach opiera się na Operators.OperatorIntrinsics.RangeInt32 . Co wyjaśni następny zaskakujący wynik

wyrażenie foreach ponad 64-bitowe 

// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
  let mutable sum = 0L
  for i in 1L..int64 n do
    sum <- sum + i
  sum |> int

To działa ~ 47x wolniej niż pętla for, jedyną różnicą jest to, że iterujemy liczby całkowite 64-bitowe. ILSpy pokazuje nam, dlaczego: 

public static int accumulateUsingForEach64(int n)
{
  long sum = 0L;
  IEnumerable<long> enumerable = Operators.OperatorIntrinsics.RangeInt64(1L, 1L, (long)n);
  foreach (long i in enumerable)
  {
    sum += i;
  }
  return (int)sum;
}

F# obsługuje tylko wydajne pętle dla liczb int32 , musi używać rezerwowych Operators.OperatorIntrinsics.RangeInt64 .

Pozostałe przypadki działają mniej więcej podobnie:

Wyniki testu na .NET 4.5.2 x64

Powodem spadku wydajności w przypadku większych przebiegów testowych jest wzrost obciążenia związanego z wywoływaniem action ponieważ wykonujemy coraz mniej pracy w action .

Pętla w kierunku 0 może czasem przynieść korzyści w zakresie wydajności, ponieważ może zaoszczędzić rejestr procesora, ale w tym przypadku procesor ma rejestry do oszczędzenia, więc nie wydaje się, żeby to miało znaczenie.

Wniosek

Pomiary są ważne, ponieważ w przeciwnym razie moglibyśmy uznać, że wszystkie te alternatywy są równoważne, ale niektóre alternatywy są ~ 270x wolniejsze niż inne.

Krok Weryfikacja obejmuje inżynierię odwrotną, plik wykonywalny pomaga nam wyjaśnić, dlaczego uzyskaliśmy lub nie osiągnęliśmy oczekiwanej wydajności. Ponadto weryfikacja może pomóc nam przewidzieć wydajność w przypadkach, gdy wykonanie odpowiedniego pomiaru jest zbyt trudne.

Trudno tam zawsze przewidzieć wydajność. Mierz, zawsze weryfikuj swoje założenia dotyczące wydajności.

Porównanie różnych potoków danych F #

W języku F# istnieje wiele opcji tworzenia potoków danych, na przykład: List , Seq i Array .

Jaki potok danych jest lepszy z punktu widzenia wykorzystania pamięci i wydajności?

Aby odpowiedzieć na to pytanie, porównamy wydajność i wykorzystanie pamięci za pomocą różnych potoków.

Potok danych

Aby zmierzyć narzut, użyjemy potoku danych o niskim koszcie procesora na przetworzone produkty: 

let seqTest n =
  Seq.init (n + 1) id
  |> Seq.map    int64
  |> Seq.filter (fun v -> v % 2L = 0L)
  |> Seq.map    ((+) 1L)
  |> Seq.sum

Stworzymy równoważne rurociągi dla wszystkich alternatyw i porównamy je.

Zmienimy rozmiar n ale niech łączna liczba prac będzie taka sama.

Alternatywy dla potoku danych

Porównamy następujące alternatywy:

  1. Kod imperatywny
  2. Tablica (nie leniwa)
  3. Lista (nie leniwa)
  4. LINQ (Lazy pull stream)
  5. Seq (Lazy pull stream)
  6. Nessos (Lazy pull / push stream)
  7. PullStream (uproszczony strumień ściągania)
  8. PushStream (uproszczony strumień push)

Chociaż nie jest to potok danych, porównamy go z kodem Imperative ponieważ najbardziej odpowiada on procesowi wykonywania kodu przez procesor. Powinien to być najszybszy możliwy sposób obliczenia wyniku, pozwalający nam zmierzyć narzut wydajności rurociągów danych.

Array i List obliczają pełną Array / List na każdym kroku, więc oczekujemy narzutu pamięci.

LINQ i Seq są oparte na IEnumerable<'T> który jest leniwym strumieniem ściągania (pull oznacza, że strumień konsumenta wyciąga dane ze strumienia producenta). Dlatego oczekujemy, że wydajność i wykorzystanie pamięci będą identyczne.

Nessos to wysokowydajna biblioteka strumieniowa, która obsługuje zarówno push i pull (jak Java Stream ).

PullStream i PushStream to uproszczone implementacje strumieni Pull & Push .

Wydajność Wynika z działania na: F # 4.0 - .NET 4.6.1 - x64

Wydajność Wynika z działania na: F # 4.0 - .NET 4.6.1 - x64

Słupki pokazują upływ czasu, im niższy, tym lepiej. Całkowita ilość użytecznej pracy jest taka sama dla wszystkich testów, więc wyniki są porównywalne. Oznacza to również, że kilka przebiegów oznacza większe zbiory danych.

Jak zwykle podczas pomiaru widać ciekawe wyniki.

  1. Niska wydajność List jest porównywana z innymi alternatywami dla dużych zestawów danych. Może to być spowodowane GC lub słabą lokalizacją pamięci podręcznej.
  2. Wydajność Array lepsza niż oczekiwano.
  3. LINQ działa lepiej niż Seq , jest to nieoczekiwane, ponieważ oba są oparte na IEnumerable<'T> . Jednak Seq wewnętrznie opiera się na impetacji ogólnej dla wszystkich algorytmów, podczas gdy LINQ używa specjalistycznych algorytmów.
  4. Push działa lepiej niż Pull . Jest to oczekiwane, ponieważ potok danych wypychanych ma mniej kontroli
  5. Uproszczone potoki danych Push porównywalnie z Nessos . Jednak Nessos obsługuje ściąganie i równoległość.
  6. W przypadku małych potoków danych wydajność Nessos obniżyć, ponieważ narzut związany z konfiguracją potoków.
  7. Zgodnie z oczekiwaniami kod Imperative działał najlepiej

Liczba kolekcji GC od uruchomienia: F # 4.0 - .NET 4.6.1 - x64

Liczba kolekcji GC od uruchomienia: F # 4.0 - .NET 4.6.1 - x64

Słupki pokazują całkowitą liczbę zliczeń GC podczas testu, im niższa, tym lepsza. Jest to pomiar liczby obiektów tworzonych przez potok danych.

Jak zwykle podczas pomiaru widać ciekawe wyniki.

  1. Oczekuje się, że List tworzy więcej obiektów niż Array ponieważ List jest zasadniczo pojedynczą połączoną listą węzłów. Tablica to ciągły obszar pamięci.
  2. Patrząc na podstawowe liczby, zarówno List & Array wymusza kolekcje 2 generacji. Tego rodzaju kolekcja jest droga.
  3. Seq wywołuje zaskakującą liczbę kolekcji. Pod tym względem jest zaskakująco gorszy niż List .
  4. LINQ , Nessos , Push i Pull nie wyzwalają kolekcji dla kilku przebiegów. Jednak obiekty są przydzielane, więc GC końcu będzie musiała uruchomić.
  5. Zgodnie z oczekiwaniami, ponieważ kod Imperative nie przydziela żadnych obiektów, nie uruchomiono żadnych kolekcji GC .

Wniosek

Wszystkie potoki danych wykonują taką samą użyteczną pracę we wszystkich przypadkach testowych, ale widzimy znaczne różnice w wydajności i zużyciu pamięci między różnymi potokami.

Ponadto zauważamy, że narzut potoków danych różni się w zależności od wielkości przetwarzanych danych. Na przykład w przypadku małych rozmiarów Array działa całkiem dobrze.

Należy pamiętać, że ilość pracy wykonanej na każdym etapie rurociągu jest bardzo mała, aby zmierzyć koszty ogólne. W „prawdziwych” sytuacjach narzut Seq może nie mieć znaczenia, ponieważ faktyczna praca jest bardziej czasochłonna.

Bardziej niepokojące są różnice w użyciu pamięci. GC nie jest darmowy i dla długotrwałych aplikacji korzystne jest obniżenie ciśnienia GC .

Dla programistów F# zainteresowanych wydajnością i zużyciem pamięci zaleca się sprawdzenie Nessos Streams .

Jeśli potrzebujesz najwyższej wydajności, strategicznie umieszczony kod Imperative jest wart rozważenia.

Wreszcie, jeśli chodzi o wydajność, nie zakładaj. Zmierz i zweryfikuj.

Pełny kod źródłowy: 

module PushStream =
  type Receiver<'T> = 'T -> bool
  type Stream<'T>   = Receiver<'T> -> unit

  let inline filter (f : 'T -> bool) (s : Stream<'T>) : Stream<'T> =
    fun r -> s (fun v -> if f v then r v else true)

  let inline map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
    fun r -> s (fun v -> r (m v))

  let inline range b e : Stream<int> =
    fun r ->
      let rec loop i = if i <= e && r i then loop (i + 1)
      loop b

  let inline sum (s : Stream<'T>) : 'T =
    let mutable state = LanguagePrimitives.GenericZero<'T>
    s (fun v -> state <- state + v; true)
    state

module PullStream =

  [<Struct>]
  [<NoComparison>]
  [<NoEqualityAttribute>]
  type Maybe<'T>(v : 'T, hasValue : bool) =
    member    x.Value        = v
    member    x.HasValue     = hasValue
    override  x.ToString ()  =
      if hasValue then
        sprintf "Just %A" v
      else
        "Nothing"

  let Nothing<'T>     = Maybe<'T> (Unchecked.defaultof<'T>, false)
  let inline Just v   = Maybe<'T> (v, true)

  type Iterator<'T> = unit -> Maybe<'T>
  type Stream<'T>   = unit -> Iterator<'T>

  let filter (f : 'T -> bool) (s : Stream<'T>) : Stream<'T> =
    fun () ->
      let i = s ()
      let rec pop () =
        let mv = i ()
        if mv.HasValue then
          let v = mv.Value
          if f v then Just v else pop ()
        else
          Nothing
      pop

  let map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
    fun () ->
      let i = s ()
      let pop () =
        let mv = i ()
        if mv.HasValue then
          Just (m mv.Value)
        else
          Nothing
      pop

  let range b e : Stream<int> =
    fun () ->
      let mutable i = b
      fun () ->
        if i <= e then
          let p = i
          i <- i + 1
          Just p
        else
          Nothing

  let inline sum (s : Stream<'T>) : 'T =
    let i = s ()
    let rec loop state =
      let mv = i ()
      if mv.HasValue then
        loop (state + mv.Value)
      else
        state
    loop LanguagePrimitives.GenericZero<'T>

module PerfTest =

  open System.Linq
#if USE_NESSOS
  open Nessos.Streams
#endif

  let now =
    let sw = System.Diagnostics.Stopwatch ()
    sw.Start ()
    fun () -> sw.ElapsedMilliseconds

  let time n a =
    let inline cc i       = System.GC.CollectionCount i

    let v                 = a ()

    System.GC.Collect (2, System.GCCollectionMode.Forced, true)

    let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
    let b                 = now ()

    for i in 1..n do
      a () |> ignore

    let e = now ()
    let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

    v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2

  let arrayTest n =
    Array.init (n + 1) id
    |> Array.map    int64
    |> Array.filter (fun v -> v % 2L = 0L)
    |> Array.map    ((+) 1L)
    |> Array.sum

  let imperativeTest n =
    let rec loop s i =
      if i >= 0L then
        if i % 2L = 0L then
          loop (s + i + 1L) (i - 1L)
        else
          loop s (i - 1L)
      else
        s
    loop 0L (int64 n)

  let linqTest n =
    (((Enumerable.Range(0, n + 1)).Select int64).Where(fun v -> v % 2L = 0L)).Select((+) 1L).Sum()

  let listTest n =
    List.init (n + 1) id
    |> List.map     int64
    |> List.filter  (fun v -> v % 2L = 0L)
    |> List.map     ((+) 1L)
    |> List.sum

#if USE_NESSOS
  let nessosTest n =
    Stream.initInfinite id
    |> Stream.take    (n + 1)
    |> Stream.map     int64
    |> Stream.filter  (fun v -> v % 2L = 0L)
    |> Stream.map     ((+) 1L)
    |> Stream.sum
#endif

  let pullTest n =
    PullStream.range 0 n
    |> PullStream.map     int64
    |> PullStream.filter  (fun v -> v % 2L = 0L)
    |> PullStream.map     ((+) 1L)
    |> PullStream.sum

  let pushTest n =
    PushStream.range 0 n
    |> PushStream.map     int64
    |> PushStream.filter  (fun v -> v % 2L = 0L)
    |> PushStream.map     ((+) 1L)
    |> PushStream.sum

  let seqTest n =
    Seq.init (n + 1) id
    |> Seq.map    int64
    |> Seq.filter (fun v -> v % 2L = 0L)
    |> Seq.map    ((+) 1L)
    |> Seq.sum

  let perfTest (path : string) =
    let testCases =
      [|
        "array"       , arrayTest       
        "imperative"  , imperativeTest  
        "linq"        , linqTest        
        "list"        , listTest        
        "seq"         , seqTest         
#if USE_NESSOS
        "nessos"      , nessosTest      
#endif
        "pull"        , pullTest        
        "push"        , pushTest        
      |]
    use out                   = new System.IO.StreamWriter (path)
    let write (msg : string)  = out.WriteLine msg
    let writef fmt            = FSharp.Core.Printf.kprintf write fmt

    write "Name\tTotal\tOuter\tInner\tElapsed\tCC0\tCC1\tCC2\tResult"

    let total   = 10000000
    let outers = [| 10; 1000; 1000000 |]
    for outer in outers do
      let inner = total / outer
      for name, a in testCases do
        printfn "Running %s with total=%d, outer=%d, inner=%d ..." name total outer inner
        let v, ms, cc0, cc1, cc2 = time outer (fun () -> a inner)
        printfn "  ... %d ms, cc0=%d, cc1=%d, cc2=%d, result=%A" ms cc0 cc1 cc2 v
        writef "%s\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d" name total outer inner ms cc0 cc1 cc2 v

[<EntryPoint>]
let main argv =
  System.Environment.CurrentDirectory <- System.AppDomain.CurrentDomain.BaseDirectory
  PerfTest.perfTest "perf.tsv"
  0


Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow