Почему выражения последовательности для массивов настолько медленны в F #?

Ответ 1

В таких случаях я всегда проверяю сгенерированный код, используя один из многих хороших декомпиляторов в .NET.

let explicitArray () = 
  let a = Array.zeroCreate count
  for v in 1..count do
    a.[v-1] <- v
  a

Это скомпилировано в эквивалентный С#:

public static int[] explicitArray()
{
    int[] a = ArrayModule.ZeroCreate<int>(10000000);
    for (int v = 1; v < 10000001; v++)
    {
        a[v - 1] = v;
    }
    return a;
}

Это примерно так же эффективно.

let arrayExpression () = 
  [|  for v in 1..count -> v |] 

Это, с другой стороны, становится:

public static int[] arrayExpression()
{
    return SeqModule.ToArray<int>(new [email protected](0, null, 0, 0));
}

Этот эквивалент:

let arrayExpression () = 
  let e = seq { for v in 1..count -> v }
  let a = List() // do not set capacity
  for v in e do
    a.Add(v)
  a.ToArray()

Когда выполняется итерация по seq (псевдоним для IEnumerable), сначала вызывается MoveNext, затем Current. Это виртуальные вызовы, которые JIT: er редко могут встроить. При проверке кода сборки JIT: ed мы видим следующее:

mov         rax,qword ptr [rbp+10h]  
cmp         byte ptr [rax],0  
mov         rcx,qword ptr [rbp+10h]  
lea         r11,[7FFC07830030h]  
# virtual call .MoveNext
call        qword ptr [7FFC07830030h]  
movzx       ecx,al  
# if .MoveNext returns false then exit
test        ecx,ecx  
je          00007FFC079408A0  
mov         rcx,qword ptr [rbp+10h]  
lea         r11,[7FFC07830038h]  
# virtual call .Current
call        qword ptr [7FFC07830038h]  
mov         edx,eax  
mov         rcx,rdi  
# call .Add
call        00007FFC65C8B300  
# loop
jmp         00007FFC07940863  

Если сравнить это с кодом JIT: ed для кода, который использовал ResizeArray (List)

lea         edx,[rdi-1]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
mov         edx,edi  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
lea         edx,[rdi+1]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
lea         edx,[rdi+2]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
add         edi,4  
# loop
cmp         edi,989682h  
jl          00007FFC07910384  

Здесь JIT: er разворачивает цикл 4 раза здесь, и мы имеем только не виртуальные вызовы List.Add.

Это объясняет, почему выражения массива F # медленнее, чем два других примера.

Чтобы исправить это, нужно было бы исправить оптимизатор в F #, чтобы распознать форму выражений, таких как:

seq { for v in 1..count -> v } |> Seq.toArray

И оптимизируйте их в:

let a = Array.zeroCreate count
for v in 1..count do
    a.[v-1] <- v
a

Задача состоит в том, чтобы найти оптимизацию, которая является достаточно общей, чтобы быть полезной, но также не нарушает семантику F #.

Ответ 2

Для усмешек я бросил ваше понимание массива в ILDASM, чтобы посмотреть, что происходит. Я положил let в main и получил следующее:

.locals init ([0] int32[] newVector,
       [1] class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<string[],class [FSharp.Core]Microsoft.FSharp.Core.Unit> V_1,
       [2] string[] V_2)
IL_0000:  nop
IL_0001:  ldc.i4.0
IL_0002:  ldnull
IL_0003:  ldc.i4.0
IL_0004:  ldc.i4.0
IL_0005:  newobj     instance void Program/[email protected]::.ctor(int32,
                                                             class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>,
                                                             int32,
                                                             int32)
IL_000a:  call       !!0[] [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToArray<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
IL_000f:  stloc.0

Итак, создается экземпляр newVector @11, и этот класс наследуется от GeneratedSequenceBase, который сам реализует IENumerable. Это имеет смысл, потому что рядом есть вызов Seq.ToArray. Рассматривая этот класс, нет способа определить, известна ли длина последовательности, даже если она в этом случае познаваема, из-за характера IEnumerable. Это говорит мне, что это должно быть эквивалентно:

let seqArr = seq { for v in 1..10000000 do yield v } |> Seq.toArray

и выбор времени:

Real: 00:00:01.032, CPU: 00:00:01.060, GC gen0: 4, gen1: 4, gen2: 4

для финального бит удовольствия, я поставил вышеописанное понимание последовательности через ILDASM, а класс-оболочка и метод GenerateNext внутри него - инструкция для команды, идентичная пониманию массива. Поэтому я считаю, что очень безопасно заключить, что любое понимание массива формы:

let arr = [| sequence-expr |]

эквивалентен 100%:

let arr = seq { sequence-expr } |> Seq.toArray

И это намечено в документации массива F # со следующей строкой:

Вы также можете использовать выражения последовательности для создания массивов. Ниже приведен пример, который создает массив квадратов целых чисел от 1 до 10.

который действительно говорит "это последовательность, а не ее собственная вещь".