F#
F # Tipps und Tricks zur Leistung
Suche…
Verwenden der Schwanzrekursion für eine effiziente Iteration
Viele Entwickler fragen sich, wie man eine for-loop schreibt, die früh break , da F# keine break , continue oder return . Die Antwort in F# ist die Verwendung der Tail-Rekursion, die eine flexible und idiomatische Methode zur Iteration ist und gleichzeitig eine hervorragende Leistung bietet.
tryFind wir möchten tryFind for List implementieren. Wenn F# die return unterstützt, würden wir tryFind so schreiben:
let tryFind predicate vs =
for v in vs do
if predicate v then
return Some v
None
Das funktioniert in F# . Stattdessen schreiben wir die Funktion mit Tail-Rekursion:
let tryFind predicate vs =
let rec loop = function
| v::vs -> if predicate v then
Some v
else
loop vs
| _ -> None
loop vs
Tail-Rekursion ist in F# performant. Wenn der F# -Compiler erkennt, dass eine Funktion Tail-Recursive ist, schreibt sie die Rekursion in eine effiziente while-loop . Mit ILSpy können wir sehen , dass dies für unsere Funktion wahr loop :
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;
}
Abgesehen von einigen unnötigen Zuweisungen (wodurch der JIT-er hoffentlich beseitigt) ist dies im Wesentlichen eine effiziente Schleife.
Darüber hinaus ist die Rekursion des Schwanzes für F# idiomatisch, da wir den veränderlichen Zustand vermeiden können. Betrachten Sie eine sum , die alle Elemente in einer List summiert. Ein offensichtlicher erster Versuch wäre folgender:
let sum vs =
let mutable s = LanguagePrimitives.GenericZero
for v in vs do
s <- s + v
s
Wenn wir die Schleife in Tail-Rekursion umschreiben, können wir den veränderbaren Zustand vermeiden:
let sum vs =
let rec loop s = function
| v::vs -> loop (s + v) vs
| _ -> s
loop LanguagePrimitives.GenericZero vs
Aus Effizienzgründen wandelt der F# -Compiler dies in eine while-loop , die den veränderbaren Zustand verwendet.
Messen und überprüfen Sie Ihre Leistungsannahmen
Dieses Beispiel wurde mit Blick auf F# geschrieben, aber die Ideen sind in allen Umgebungen anwendbar
Die erste Regel bei der Optimierung der Leistung besteht darin, sich nicht auf die Annahme zu verlassen. Messen und überprüfen Sie immer Ihre Annahmen.
Da wir nicht direkt Maschinencode schreiben, lässt sich schwer vorhersagen, wie der Compiler und JIT: er Ihr Programm in Maschinencode umwandeln. Aus diesem Grund müssen wir die Ausführungszeit messen, um zu sehen, dass wir die erwartete Leistungsverbesserung erzielen, und sicherstellen, dass das eigentliche Programm keinen versteckten Aufwand enthält.
Bei der Überprüfung handelt es sich um einen recht einfachen Prozess, bei dem die ausführbare Datei mithilfe von Tools wie ILSpy zurückentwickelt wird . Der JIT: er macht Verification dadurch komplizierter, dass das Anzeigen des tatsächlichen Maschinencodes schwierig ist, aber machbar ist. Die Untersuchung des IL-code führt jedoch meist zu großen Vorteilen.
Das schwierigere Problem ist Messen; schwieriger, weil es schwierig ist, realistische Situationen aufzubauen, in denen Verbesserungen des Codes gemessen werden können. Messen ist immer noch von unschätzbarem Wert.
Analyse einfacher F # -Funktionen
1..n wir uns einige einfache F# -Funktionen an, die alle ganzzahligen Zahlen in 1..n auf verschiedene Weise ansammeln. Da es sich bei dem Bereich um eine einfache Arithmetikreihe handelt, kann das Ergebnis direkt berechnet werden. In diesem Beispiel durchlaufen wir jedoch den Bereich.
Zuerst definieren wir einige nützliche Funktionen zum Messen der Zeit, die eine Funktion benötigt:
// 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 läuft eine Aktion wiederholt ab. Wir müssen die Tests einige hundert Millisekunden lang ausführen, um die Varianz zu reduzieren.
Dann definieren wir einige Funktionen, die alle ganzen Zahlen in 1..n auf unterschiedliche Weise ansammeln.
// 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
Wir gehen davon aus, dass das Ergebnis dasselbe ist (mit Ausnahme einer der Funktionen, die ein Inkrement von 2 ), aber es besteht ein Leistungsunterschied. Um dies zu messen, ist folgende Funktion definiert:
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
Das Testergebnis beim Ausführen unter .NET 4.5.2 x64:
Wir sehen dramatische Unterschiede und einige der Ergebnisse sind unerwartet schlecht.
Schauen wir uns die schlechten Fälle an:
Liste
// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
List.init (n + 1) id
|> List.sum
Was hier passiert, ist eine vollständige Liste mit allen ganzen Zahlen 1..n die mit einer Summe erstellt und reduziert wird. Dies sollte teurer sein als nur das Iterieren und Akkumulieren über den Bereich, es scheint etwa ~ 42x langsamer als die for-Schleife zu sein.
Darüber hinaus sehen wir, dass der GC während des Testlaufs etwa 100x ausgeführt wurde, da der Code viele Objekte zugewiesen hat. Dies kostet auch CPU.
Seq
// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
Seq.init (n + 1) id
|> Seq.sum
Die Seq Version weist keine vollständige List daher ist es etwas überraschend, dass diese ~ 270x langsamer ist als die for-Schleife. Außerdem sehen wir, dass der GC 661x ausgeführt hat.
Seq ist ineffizient, wenn der Arbeitsaufwand pro Artikel sehr gering ist (in diesem Fall werden zwei ganze Zahlen zusammengefasst).
Es geht darum, niemals Seq . Der Punkt ist zu messen.
( manofstick edit: Seq.init ist der Täter dieses schwerwiegenden Leistungsproblems. Es ist viel effizienter, anstelle von Seq.init (n+1) id den Ausdruck { 0 .. n } verwenden. Dies wird noch viel effizienter Wenn dieses PR zusammengeführt und veröffentlicht wird, Seq.init ... |> Seq.sum die ursprüngliche Seq.init ... |> Seq.sum auch nach der Veröffentlichung immer noch langsam, aber etwas kontrapunktisch, Seq.init ... |> Seq.map id |> Seq.sum wird ziemlich schnell sein, um die Abwärtskompatibilität mit der Implementierung von Seq.init aufrechtzuerhalten, die Current anfangs berechnet, sondern sie in ein Lazy Objekt Seq.init - obwohl auch dies aufgrund von etwas besser sein sollte Diese PR . Hinweis für den Redakteur: Entschuldigung, das ist eine Art wandernde Notizen, aber ich möchte nicht, dass die Leute von Seq abgeschoben werden, wenn die Verbesserung unmittelbar bevorsteht. Wenn dies der Fall ist, wäre es gut, die Charts zu aktualisieren das sind auf dieser Seite. )
foreach-expression über 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
Der Unterschied zwischen diesen beiden Funktionen ist sehr subtil, der Leistungsunterschied beträgt jedoch nicht ~ 76x. Warum? Lassen Sie uns den fehlerhaften Code zurückentwickeln:
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 wird als effiziente while Schleife implementiert, aber for i in [1..n] wird for i in [1..n] konvertiert:
FSharpList<int> fSharpList =
SeqModule.ToList<int>(
Operators.CreateSequence<int>(
Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
Dies bedeutet, dass wir zuerst eine Seq über 1..n und schließlich ToList .
Teuer.
foreach-expression-Inkrement von 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
Wieder ist der Unterschied zwischen diesen beiden Funktionen geringfügig, aber der Leistungsunterschied ist brutal: ~ 25x
Lassen Sie uns noch einmal ILSpy ausführen:
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;
}
Ein Seq wird über 1..2..n und dann mit dem Enumerator über Seq iteriert.
Wir erwarteten, dass F# so etwas kreiert:
public static int accumulateUsingForEachStep2(int n)
{
int sum = 0;
for (int i = 1; i < n; i += 2)
{
sum += i;
}
return sum;
}
F# -Compiler unterstützt jedoch nur effizient für Schleifen über int32-Bereiche, die um eins erhöht werden. In allen anderen Fällen wird auf Operators.OperatorIntrinsics.RangeInt32 . Was das nächste überraschende Ergebnis erklären wird
foreach-expression über 64 bit
// 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
Dies ist ~ 47x langsamer als die for-Schleife. Der einzige Unterschied besteht darin, dass wir über 64-Bit-Ganzzahlen iterieren. ILSpy zeigt uns warum:
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# unterstützt nur effizient für Schleifen für int32 Zahlen die Fallback- Operators.OperatorIntrinsics.RangeInt64 .
Die anderen Fälle verhalten sich ungefähr ähnlich:
Der Grund, warum sich die Leistung bei größeren Testläufen verschlechtert, ist, dass der Aufwand für das Aufrufen der action wächst, da wir immer weniger Arbeit in action .
Eine Schleife auf 0 kann manchmal zu Leistungsvorteilen führen, da dadurch ein CPU-Register gespeichert werden könnte. In diesem Fall hat die CPU jedoch Register, um zu sparen, sodass es keinen Unterschied zu machen scheint.
Fazit
Das Messen ist wichtig, weil wir sonst denken könnten, dass alle diese Alternativen gleichwertig sind, aber einige Alternativen sind ~ 270x langsamer als andere.
Der Überprüfungsschritt beinhaltet das Reverse Engineering der ausführbaren Datei. Dies hilft uns zu erklären, warum wir die erwartete Leistung erzielt haben oder nicht. Darüber hinaus hilft uns die Verifizierung, die Leistung vorherzusagen, wenn es zu schwierig ist, eine korrekte Messung durchzuführen.
Es ist schwierig, die Leistung dort immer vorherzusagen. Messen, immer Überprüfen Sie Ihre Leistungsannahmen.
Vergleich verschiedener F # -Datenpipelines
In F# gibt es viele Optionen zum Erstellen von Datenpipelines, z. B. List , Seq und Array .
Welche Daten-Pipeline ist aus Sicht des Speichers und der Leistung vorzuziehen?
Um dies zu beantworten, vergleichen wir Leistung und Speicherauslastung mit verschiedenen Pipelines.
Datenpipeline
Um den Overhead zu messen, verwenden wir eine Datenpipeline mit niedrigen CPU-Kosten pro verarbeitetem Artikel:
let seqTest n =
Seq.init (n + 1) id
|> Seq.map int64
|> Seq.filter (fun v -> v % 2L = 0L)
|> Seq.map ((+) 1L)
|> Seq.sum
Wir werden gleichwertige Pipelines für alle Alternativen erstellen und vergleichen.
Wir werden die Größe von n variieren, aber die Gesamtzahl der Arbeit sei gleich.
Alternativen für die Datenpipeline
Wir werden die folgenden Alternativen vergleichen:
- Imperativer Code
- Array (nicht faul)
- Liste (nicht faul)
- LINQ (Lazy Pull Stream)
- Seq (Lazy Pull Stream)
- Nessos (Lazy Pull / Push Stream)
- PullStream (Vereinfachter Pullstream)
- PushStream (Simplistic Push Stream)
Obwohl es sich nicht um eine Datenpipeline handelt, werden wir sie mit Imperative Code vergleichen, da diese am ehesten der Art entspricht, wie die CPU Code ausführt. Dies sollte der schnellste Weg sein, um das Ergebnis zu berechnen, mit dem wir den Performance-Overhead von Datenpipelines messen können.
Array und List berechnen in jedem Schritt ein vollständiges Array / eine List daher erwarten wir Speicherüberhang.
LINQ und Seq basieren beide auf IEnumerable<'T> was ein Lazy-Pull-Stream ist (Pull bedeutet, dass der Consumer-Stream Daten aus dem Producer-Stream zieht). Wir erwarten daher, dass Leistung und Speicherbedarf identisch sind.
Nessos ist eine leistungsstarke Stream-Bibliothek, die Push & Pull (wie Java Stream ) unterstützt.
PullStream und PushStream sind vereinfachte Implementierungen von Pull & Push Streams.
Leistung Ergebnisse beim Ausführen auf: F # 4.0 - .NET 4.6.1 - x64
Die Balken zeigen die verstrichene Zeit an, je niedriger ist besser. Die Gesamtmenge der nützlichen Arbeit ist für alle Tests gleich, daher sind die Ergebnisse vergleichbar. Dies bedeutet auch, dass wenige Läufe größere Datensätze implizieren.
Wie üblich beim Messen sieht man interessante Ergebnisse.
-
Listschlechte Leistung derListwird mit anderen Alternativen für große Datensätze verglichen. Dies kann aufGCoder eine schlechte Cache-Lokalität zurückzuführen sein. -
ArrayLeistung besser als erwartet. -
LINQbesser alsSeq. Dies ist unerwartet, da beide aufIEnumerable<'T>basieren.Seqbasiert jedoch intern auf einer generischen Implementierung für alle Algorithmen, währendLINQspezielle Algorithmen verwendet. -
Pushbesser alsPull. Dies ist zu erwarten, da die Push-Datenpipeline weniger Prüfungen aufweist - Die vereinfachten
PushDatenpipelines sind mitNessosvergleichbar.Nessosunterstützt jedoch Zug und Parallelität. - Bei kleinen
Nessosverschlechtert sich die Leistung vonNessosmöglicherweise, da der Pipeline-Setup-Overhead zunimmt. - Wie erwartet hat der
ImperativeCode die bestenImperativeerzielt
Anzahl der GC-Sammlungen beim Ausführen auf: F # 4.0 - .NET 4.6.1 - x64
Die Balken zeigen die Gesamtzahl der GC Erfassungszählungen während des Tests an. Weniger ist besser. Dies ist ein Maß dafür, wie viele Objekte von der Datenpipeline erstellt werden.
Wie üblich beim Messen sieht man interessante Ergebnisse.
-
Listerwartungsgemäß mehr Objekte alsArrayda eineListim Wesentlichen eine einzelne verknüpfte Liste von Knoten ist. Ein Array ist ein kontinuierlicher Speicherbereich. - Betrachten Sie die zugrunde liegenden Zahlen, und zwar sowohl
List&Array2 Generationssammlungen. Diese Art der Sammlung ist teuer. -
Seqlöst überraschend viele Sammlungen aus. Es ist in dieser Hinsicht überraschend noch schlimmer alsList. -
LINQ,Nessos,PushundPulllöst für wenige Läufe keine Sammlungen aus. Objekte werden jedoch zugewiesen, sodass derGCeventuell ausgeführt werden muss. - Da der
ImperativeCode keine ObjekteGC, wurden erwartungsgemäß keineGCSammlungen ausgelöst.
Fazit
Alle Datenpipelines leisten in allen Testfällen die gleiche Menge an nützlicher Arbeit, aber wir sehen erhebliche Unterschiede in der Leistung und im Speicherbedarf zwischen den verschiedenen Pipelines.
Darüber hinaus stellen wir fest, dass der Overhead von Datenpipelines je nach Größe der verarbeiteten Daten unterschiedlich ist. Bei kleinen Größen Array zum Beispiel recht gut.
Man sollte bedenken, dass der Arbeitsaufwand in jedem Schritt der Pipeline sehr gering ist, um den Aufwand zu messen. In "echten" Situationen spielt der Aufwand für Seq möglicherweise keine Rolle, da die eigentliche Arbeit zeitaufwändiger ist.
Noch wichtiger sind die Unterschiede bei der Speichernutzung. GC ist nicht frei und es ist vorteilhaft für lange laufende Anwendungen, um den GC Druck zu reduzieren.
Für F# -Entwickler, die über Leistung und Speicherauslastung besorgt sind, wird empfohlen, Nessos Streams auszuprobieren .
Wenn Sie erstklassige Leistung benötigen, die strategisch platziert ist, ist der Imperative Code eine Überlegung wert.
Schließlich, wenn es um Leistung geht, machen Sie keine Annahmen. Messen und überprüfen.
Vollständiger Quellcode:
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
