수색…
효율적인 반복을 위해 tail-recursion 사용
명령형 언어에서 오는 많은 개발자들은 F# 이 break , continue 또는 return 지원하지 않기 때문에 일찍 종료되는 for-loop 를 작성하는 방법을 궁금해합니다. F# 의 대답은 tail-recursion 을 사용하는 것입니다. tail-recursion 은 유연하고 관용적 인 방법으로 반복적으로 사용하면서 우수한 성능을 제공합니다.
List tryFind 를 구현하려고한다고 가정 tryFind . F# return 을 지원한다면 우리는 다음과 같이 tryFind 작성합니다.
let tryFind predicate vs =
for v in vs do
if predicate v then
return Some v
None
F# 에서는 작동하지 않습니다. 대신 tail-recursion을 사용하여 함수를 작성합니다.
let tryFind predicate vs =
let rec loop = function
| v::vs -> if predicate v then
Some v
else
loop vs
| _ -> None
loop vs
F# 컴파일러가 함수가 tail-recursive임을 감지하면 효율적인 while-loop 로 재귀를 다시 작성하기 때문에 F# 에서는 테일 재귀가 효율적입니다. ILSpy 를 사용하면 함수 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;
}
불필요한 과제 외에도 (JIT-er이 제거하면) 이는 본질적으로 효율적인 루프입니다.
또한 꼬리 - 재귀는 F# 대해 관용적인데, 변경 가능한 상태를 피할 수 있기 때문입니다. List 모든 요소를 sum 함수를 생각해보십시오. 확실한 첫 번째 시도는 다음과 같습니다.
let sum vs =
let mutable s = LanguagePrimitives.GenericZero
for v in vs do
s <- s + v
s
루프를 tail-recursion으로 다시 작성하면 변경 가능한 상태를 피할 수 있습니다.
let sum vs =
let rec loop s = function
| v::vs -> loop (s + v) vs
| _ -> s
loop LanguagePrimitives.GenericZero vs
효율성을 위해 F# 컴파일러는 변경 가능한 상태를 사용하는 while-loop 로 변환합니다.
실적 가정 측정 및 검증
이 예제는 F# 을 염두에두고 작성되었지만 아이디어는 모든 환경에 적용 할 수 있습니다.
성능을 최적화 할 때 첫 번째 규칙은 가정에 의존하지 않는 것입니다. 항상 가정을 측정하고 확인하십시오.
기계 코드를 직접 작성하지는 않기 때문에 컴파일러와 JIT가 프로그램을 기계 코드로 변환하는 방법을 예측하기는 어렵습니다. 그래서 우리는 예상되는 성능 향상을 얻고 실제 프로그램에 숨겨진 오버 헤드가 없는지 확인하기 위해 실행 시간을 측정해야합니다.
검증은 ILSpy 와 같은 도구를 사용하여 실행 파일을 리버스 엔지니어링하는 아주 간단한 프로세스입니다. JIT : er는 실제 기계 코드가 까다 롭지 만 실행 가능하다는 점에서 확인을 복잡하게 만듭니다. 그러나 보통 IL-code 검사하면 큰 이득을 얻습니다.
더 어려운 문제는 측정입니다. 코드 개선을 측정 할 수있는 현실적인 상황을 설정하는 것이 까다로운 작업이기 때문에 어렵습니다. 아직도 측정은 매우 중요합니다.
간단한 F # 함수 분석하기
여러 가지 다른 방법으로 쓰여진 1..n 에서 모든 정수를 누적하는 간단한 F# 함수를 살펴 보겠습니다. 범위가 간단한 산술 계열이므로 결과를 직접 계산할 수 있지만이 예제에서는 범위를 반복합니다.
먼저 함수가 수행하는 시간을 측정하기위한 몇 가지 유용한 함수를 정의합니다.
// 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 은 반복적으로 동작을 실행하여 변화를 줄이기 위해 수백 밀리 초 동안 테스트를 실행해야합니다.
그런 다음 1..n 에서 모든 정수를 누적하는 몇 가지 함수를 여러 가지 방법으로 정의합니다.
// 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
우리는 결과가 동일하다고 가정합니다 ( 2 증가분을 사용하는 함수 중 하나는 제외). 그러나 성능 차이가 있습니다. 이를 측정하기 위해 다음과 같은 기능이 정의됩니다 :
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
.NET 4.5.2 x64에서 실행되는 동안의 테스트 결과 :
우리는 극적인 차이를 보았고 결과 중 일부는 예기치 않게 나쁜 것입니다.
나쁜 경우를 살펴 보겠습니다.
명부
// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
List.init (n + 1) id
|> List.sum
여기서 일어나는 일은 모든 정수를 포함하는 전체 목록입니다. 1..n 은 합계를 사용하여 생성되고 줄입니다. 이 범위를 반복 및 누적하는 것보다 비용이 많이 들며 for 루프보다 약 42 배 느립니다.
또한 코드가 많은 객체를 할당했기 때문에 테스트 실행 중에 GC가 약 100x 실행되었음을 알 수 있습니다. 이것은 또한 CPU 비용이 듭니다.
순서
// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
Seq.init (n + 1) id
|> Seq.sum
Seq 버전은 전체 List 할당하지 않기 때문에 for 루프보다 270x 느리다는 사실이 놀랍습니다. 또한 GC가 661x를 실행했습니다.
Seq 는 항목 당 작업량이 매우 적을 때 비효율적입니다 (이 경우 정수 두 개를 집계).
요점은 Seq 을 절대 사용하지 않는 것입니다. 요점은 측정입니다.
( Manofstick 편집 : Seq.init 이 심각한 성능 문제의 원인입니다 Seq.init (n+1) id 대신 { 0 .. n } 표현식을 사용하는 것이 훨씬 효율적입니다. 이 PR 이 병합되어 릴리스 될 때. 비록 릴리스 이후에도 원래 Seq.init ... |> Seq.sum 은 여전히 느리지 만 다소 반 직관적으로 Seq.init ... |> Seq.map id |> Seq.sum 은 매우 빠를 것입니다. 이것은 Seq.init 의 구현과의 하위 호환성을 유지하기위한 것이 었습니다. Current 초기에 계산하지 않고 Lazy 객체로 래핑합니다. 이 PR . 편집자 주 : 유감스럽게도 메모가 깔끔하게 나옵니다.하지만 개선이 가까워 질 때 사람들이 Seq를 연기하는 것을 원하지는 않습니다. 그 시대가 오면 차트를 업데이트하는 것이 좋을 것입니다. 이 페이지에 있습니다. )
목록에 대한 foreach-expression
// 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
이 두 기능의 차이는 매우 미묘하지만 성능 차이는 약 76x가 아닙니다. 왜? 나쁜 코드를 리버스 엔지니어링하여 보겠습니다.
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 는 효율적인 while 루프로 구현되지만 for i in [1..n] 으로 변환됩니다.
FSharpList<int> fSharpList =
SeqModule.ToList<int>(
Operators.CreateSequence<int>(
Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
이것은 처음에 1..n 이상의 Seq 를 만들고 마지막으로 ToList 호출 함을 의미합니다.
비싼.
foreach- 표현식 증가분 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
다시 한번이 두 함수의 차이점은 미묘하지만 성능 차이는 잔인합니다. ~ 25x
다시 ILSpy 실행 해 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 는 1..2..n 이상으로 생성 된 후 열거자를 사용하여 Seq 를 반복합니다.
우리는 F# 이 다음과 같은 것을 만들 것을 기대하고있었습니다 :
public static int accumulateUsingForEachStep2(int n)
{
int sum = 0;
for (int i = 1; i < n; i += 2)
{
sum += i;
}
return sum;
}
그러나 F# 컴파일러는 하나씩 증가하는 int32 범위에 대해 효율적인 for 루프 만 지원합니다. 다른 모든 경우에는 Operators.OperatorIntrinsics.RangeInt32 돌아갑니다. 다음의 놀라운 결과를 설명 할 것입니다.
64 비트 이상의 foreach-expression
// 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
이것은 for 루프보다 ~ 47x 느리게 수행됩니다. 유일한 차이점은 64 비트 정수를 반복한다는 것입니다. ILSpy 는 왜 우리에게 ILSpy 보여줍니다 :
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# 은 int32 숫자에 대해 루프 용으로 만 효율적으로 지원하며 대체 Operators.OperatorIntrinsics.RangeInt64 를 사용해야합니다.
다른 경우는 대략 비슷합니다.
성능이 더 큰 테스트 실행을위한 저하 이유는 호출의 오버 헤드 것입니다 action 우리가 적게 일을로 성장하고 action .
CPU 레지스터를 절약 할 수 있으므로 0 반복하면 성능상의 이점을 얻을 수 있지만이 경우 CPU에는 여분의 레지스터가 있으므로 차이가없는 것으로 보입니다.
결론
측정은 중요합니다. 그렇지 않으면 모든 대안이 동일하다고 생각할 수도 있기 때문입니다. 그러나 일부 대안은 다른 것보다 ~ 270x 느립니다.
검증 단계에서는 실행 파일을 리버스 엔지니어링하면 우리가 예상했던 성능을 얻었거나 얻지 못한 이유 를 설명 할 수 있습니다. 또한 인증은 적절한 측정을 수행하기가 너무 어려운 경우 실적을 예측하는 데 도움이 될 수 있습니다.
항상 실적을 예측하기는 어렵습니다. 측정, 항상 실적 가정을 확인하십시오.
다른 F # 데이터 파이프 라인 비교
F# 에는 List , Seq 및 Array 와 같이 데이터 파이프 라인을 생성하는 여러 옵션이 있습니다.
메모리 사용 및 성능 측면에서 어떤 데이터 파이프 라인이 더 바람직합니까?
이를 위해 다양한 파이프 라인을 사용하여 성능과 메모리 사용량을 비교합니다.
데이터 파이프 라인
오버 헤드를 측정하기 위해 처리되는 항목 당 CPU 비용이 낮은 데이터 파이프 라인을 사용합니다.
let seqTest n =
Seq.init (n + 1) id
|> Seq.map int64
|> Seq.filter (fun v -> v % 2L = 0L)
|> Seq.map ((+) 1L)
|> Seq.sum
우리는 모든 대안에 대해 동등한 파이프 라인을 만들고 비교할 것입니다.
우리는 n 의 크기를 다양하게 할 것이지만 전체 작업 수는 같게 만듭니다.
데이터 파이프 라인 대안
다음 대안을 비교해 보겠습니다.
- 명령형 코드
- 배열 (비 게으름)
- 목록 (비 게으름)
- LINQ (Lazy pull stream)
- Seq (지연 스트림)
- Nessos (Lazy pull / push stream)
- PullStream (단순 풀 스트림)
- PushStream (단순 푸시 스트림)
데이터 파이프 라인은 아니지만 Imperative 코드와 비교할 것입니다. 이는 CPU가 코드를 실행하는 방식과 가장 일치하기 때문입니다. 이는 데이터 파이프 라인의 성능 오버 헤드를 측정 할 수 있도록 결과를 계산하는 가장 빠른 방법입니다.
Array 와 List 는 각 단계에서 전체 Array / List 를 계산하므로 메모리 오버 헤드가 예상됩니다.
LINQ 와 Seq 는 모두 lazy pull stream 인 IEnumerable<'T> 를 기반으로합니다 (pull은 소비자 스트림이 생성자 스트림에서 데이터를 가져 오는 것을 의미합니다). 따라서 우리는 성능과 메모리 사용량이 동일 할 것으로 기대합니다.
Nessos 는 푸시 앤 풀 (Java Stream 처럼)을 모두 지원하는 고성능 스트림 라이브러리입니다.
PullStream과 PushStream은 Pull & Push 스트림을 단순하게 구현 한 것입니다.
실행 결과 : F # 4.0 - .NET 4.6.1 - x64
막대는 경과 시간을 나타내며, 낮을수록 좋습니다. 유용한 작업의 총량은 모든 테스트에서 동일하므로 결과가 비슷합니다. 이것은 또한 실행이 적 으면 더 큰 데이터 세트를 의미 함을 의미합니다.
평소처럼 측정 할 때 흥미로운 결과를 볼 수 있습니다.
-
List성능 저하는 대용량 데이터 세트의 다른 대안과 비교됩니다. 이는GC나 캐시 지역이 좋지 않기 때문일 수 있습니다. -
Array성능이 예상보다 향상되었습니다. -
LINQ는Seq보다 성능이 뛰어납니다. 둘 다IEnumerable<'T>기반으로하기 때문에 예상치 못한 결과입니다. 그러나Seq내부적으로 모든 알고리즘에 대한 일반 임베디션을 기반으로하며LINQ는 특수 알고리즘을 사용합니다. -
Push는Pull보다 성능이 좋습니다. 푸시 데이터 파이프 라인의 검사 횟수가 - 단순한
Push데이터 파이프 라인은Nessos와 유사합니다. 그러나Nessos는 끌어 오기와 병렬 처리를 지원합니다. - 작은 데이터 파이프 라인의 경우
Nessos의 성능은 파이프 라인 설치 오버 헤드 때문에 저하 될 수 있습니다. - 예상대로
Imperative코드가 가장 잘 수행되었습니다.
실행중인 GC 수집 횟수 : F # 4.0 - .NET 4.6.1 - x64
막대는 시험 중 총 GC 수집 횟수를 보여 주며 더 낮은 것이 좋습니다. 이것은 데이터 파이프 라인에 의해 생성되는 객체의 수를 측정합니다.
평소처럼 측정 할 때 흥미로운 결과를 볼 수 있습니다.
-
List것으로 예상되는 것보다 더 많은 개체 생성되는Array때문에List기본적으로 노드의 단일 링크 목록입니다. 배열은 연속적인 메모리 영역입니다. - 기본 숫자를 보면
List&Array는 2 세대 컬렉션을 강제합니다. 이런 종류의 수집은 비싸다. -
Seq이 놀랍도록 많은 수의 콜렉션을 촉발시키고 있습니다. 이런 점에서List보다 훨씬 놀랍습니다. -
LINQ,Nessos,Push및Pull은 거의 실행되지 않는 콜렉션을 트리거합니다. 그러나 개체가 할당되므로GC결국 실행해야합니다. -
Imperative코드가 객체를 할당하지 않았기 때문에 예상대로GC콜렉션이 트리거되지 않았습니다.
결론
모든 데이터 파이프 라인은 모든 테스트 케이스에서 동일한 양의 유용한 작업을 수행하지만, 서로 다른 파이프 라인 간의 성능 및 메모리 사용량에 큰 차이가 있음을 알 수 있습니다.
또한 데이터 파이프 라인의 오버 헤드는 처리되는 데이터의 크기에 따라 다릅니다. 예를 들어, 작은 크기의 경우 Array 는 매우 잘 수행됩니다.
오버 헤드를 측정하기 위해서는 파이프 라인의 각 단계에서 수행되는 작업량이 매우 작습니다. 실제 작업에서는 Seq 의 오버 헤드가 중요하지 않을 수 있습니다. 실제 작업 시간이 더 오래 걸리기 때문입니다.
더 많은 관심이 메모리 사용량 차이입니다. GC 는 무료가 아니며 장기간 사용하는 어플리케이션이 GC 압력을 낮추는 데 유익합니다.
성능 및 메모리 사용에 관심이있는 F# 개발자 에게는 Nessos Streams 를 체크 아웃하는 것이 좋습니다.
전략적으로 배치 된 최고의 성능이 필요하면 Imperative 코드를 고려해 볼 가치가 있습니다.
마지막으로, 성능에 관해서는 가정을하지 마십시오. 측정 및 검증.
전체 소스 코드 :
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