Производительность F #: Что делает этот код таким медленным?

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

Например, можно представить, что F # расширяет это выражение в эффективный цикл for:

[3..2..(int (sqrt (float n)))]
|> List.tryFind (fun i -> n%i=0)
|> Option.isNone

Однако в настоящее время это не так. Вместо этого он создает List который охватывает диапазон с помощью внутренних операторов и передает его List.tryFind, Это дорого по сравнению с реальной работой, которую мы любим делать (операция с модулем). ILSpy декомпилирует приведенный выше код в нечто вроде этого:

public static bool is_prime(int _arg1)
{
switch (_arg1)
{
case 2:
return true;
default:
return _arg1 >= 2 && _arg1 % 2 != 0 && ListModule.TryFind<int>(new Program.Original.is_prime@10(_arg1), SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(3, 2, (int)Math.Sqrt((double)_arg1))))) == null;
}
}

Эти операторы не так эффективны, как могли бы быть (AFAIK, в настоящее время это улучшается), но независимо от того, насколько эффективно выделение List а затем искать его не будет бить цикл.

Это означает, что is_prime не так эффективно, как могло бы быть. Вместо этого можно сделать что-то вроде этого:

let is_prime = function
| 1                 -> false
| 2                 -> true
| v when v % 2 = 0  -> false
| v ->
let stop = v |> float |> sqrt |> int
let rec loop vv =
if vv <= stop then
(v % vv) <> 0 && loop (vv + 2)
else
true
loop 3

Эта версия is_prime полагается на оптимизацию хвостового вызова в F # для расширения цикла в эффективный цикл for (вы можете увидеть это с помощью ILSpy). ILSpy декомпилирует цикл примерно так:

while (vv <= stop)
{
if (_arg1 % vv == 0)
{
return false;
}
int arg_13_0 = _arg1;
int arg_11_0 = stop;
vv += 2;
stop = arg_11_0;
_arg1 = arg_13_0;
}

Этот цикл не выделяет память и является довольно эффективным циклом. Можно увидеть некоторые бессмысленные задания, но, надеюсь, JIT: er их устранит. я уверен is_prime может быть улучшено еще дальше.

Когда используешь Seq в исполняемом коде нужно помнить, что он ленив и не использует памятки по умолчанию (см. Seq.cache). Поэтому можно легко снова и снова выполнять одну и ту же работу (см. Ответ @rmunn).

К тому же Seq не особенно эффективен из-за того, как IEnumerable/IEnumerator разработаны. Лучшими вариантами являются, например, Nessos Streams (доступно на nuget).

На случай, если вам интересно, я сделал быструю реализацию, основанную на простом Push Stream, который выглядит прилично производительным:

// Receiver<'T> is a callback that receives a value.
//  Returns true if it wants more values, false otherwise.
type Receiver<'T> = 'T -> bool
// Stream<'T> is function that accepts a Receiver<'T>
//  This means Stream<'T> is a push stream (as opposed to Seq that uses pull)
type Stream<'T>   = Receiver<'T> -> unit

// is_prime returns true if the input is prime, false otherwise
let is_prime = function
| 1                 -> false
| 2                 -> true
| v when v % 2 = 0  -> false
| v ->
let stop = v |> float |> sqrt |> int
let rec loop vv =
if vv <= stop then
(v % vv) <> 0 && loop (vv + 2)
else
true
loop 3

// tryFind looks for the first value in the input stream for f v = true.
//  If found tryFind returns Some v, None otherwise
let tryFind f (s : Stream<'T>) : 'T option =
let res = ref None
s (fun v -> if f v then res := Some v; false else true)
!res

// diagonals generates a tuple stream of all diagonal values
//  The first value is the side length, the second value is the diagonal value
let diagonals : Stream<int*int> =
fun r ->
let rec loop side v =
let step  = side - 1
if r (side, v + 1*step) && r (side, v + 2*step) && r (side, v + 3*step) && r (side, v + 4*step) then
loop (side + 2) (v + 4*step)
if r (1, 1) then loop 3 1

// ratio computes the streaming ratio for f v = true
let ratio f (s : Stream<'T>) : Stream<float*'T> =
fun r ->
let inc r = r := !r + 1.
let acc   = ref 0.
let count = ref 0.
s (fun v -> (inc count; if f v then inc acc); r (!acc/(!count), v))

let result =
diagonals
|> ratio (snd >> is_prime)
|> tryFind (fun (r, (_, v)) -> v > 1 && r < 0.1)