В каких ситуациях списки в F # оптимизируются компилятором?

Question

В каких ситуациях списки в F # оптимизируются компилятором F # для массивов, циклов for, циклов while и т. Д. Без создания фактического списка отдельных связанных данных?

Например:

[1..1000] |> List.map something

Может быть оптимизирован для цикла for без создания фактического списка. Но я не знаю, делает ли это компилятор на самом деле.

Отображение списков меньшего размера можно оптимизировать с помощью разворачивания цикла и т. Д.

Answer 1

В каких ситуациях списки в F # оптимизируются компилятором F # для массивов, циклов for, циклов и т. Д. Без создания фактического списка одиночных связанных данных?

Никогда.

Ваши последующие комментарии поучительны, потому что вы предполагаете, что это недостаток в F #:

... это должно быть достаточно умно, чтобы сделать это.Подобно компилятору Haskell ...

В некоторой степени верно.

... Компилятор Haskell делает много таких оптимизаций ...

Верно.

Однако на самом деле это действительно плохая идея.В частности, вы стремитесь к оптимизации, когда вам действительно нужна производительность.Haskell предлагает множество экзотических оптимизаций, но его характеристики производительности действительно плохие.Более того, свойства Haskell, которые делают эту оптимизацию доступной, требуют огромных жертв в других местах:

• Чистота значительно затрудняет совместимость, поэтому Microsoft убила Haskell.NET, и Haskell живет только с собственной несовместимой виртуальной машиной.
• ГХ в виртуальной машине Haskell был оптимизирован для чисто функционального кода за счет мутации.
• Чисто функциональные структуры данных обычно в 10 раз медленнее своих императивных эквивалентов, иногда асимптотически медленнее, а в некоторых случаяхнет известного чисто функционального эквивалента.
• Лень и чистота идут рука об руку («строгая оценка - это канонический побочный эффект»), а лень не только сильно снижает производительность, но и делает ее крайне непредсказуемой.
• Огромное количество оптимизаций, добавленных в Haskell в попытке бороться с этой низкой производительностью (например, анализ строгости), делает производительность еще менее предсказуемой.
• Непредсказуемое поведение кэша делает возможным масштабированиеy непредсказуемый на многоядерных процессорах.

Для тривиального примера неоплачиваемых оптимизаций смотрите не более чем идиоматическая двухстрочная быстрая сортировка в Haskell, которая, несмотря на все свои оптимизации, остается в тысячи раз медленнее, чемБыстрая сортировка Седжвика в C. Теоретически, достаточно умный компилятор Haskell может оптимизировать такой исходный код в эффективную программу.На практике, самые совершенные в мире компиляторы Haskell не могут даже сделать это для тривиальной программы, состоящей из двух строк и гораздо менее реального программного обеспечения.

Исходный код для программ на Haskell в Игра по тестированию компьютерного языка приведите несколько наглядных примеров того, насколько ужасным становится код на Haskell при его оптимизации.

Я хочу, чтобы язык программирования:

• имел простой метод компиляции, обеспечивающий предсказуемость производительности.
• Упростите оптимизацию вручную там, где требуется оптимизация.
• Высокий потолок производительности, чтобы я мог приблизиться к оптимальной производительности при необходимости.

F # удовлетворяет этим требованиям.

Answer 2

Я думаю, что "никогда" - это ответ.

Answer 3

Легко увидеть, если вы посмотрите на разборку - которую довольно легко прочитать

    // method line 4
    .method public static
           default void main@ ()  cil managed
    {
        // Method begins at RVA 0x2078
    .entrypoint
    // Code size 34 (0x22)
    .maxstack 6
    IL_0000:  newobj instance void class Test2/clo@2::'.ctor'()
    IL_0005:  ldc.i4.1
    IL_0006:  ldc.i4.1
    IL_0007:  ldc.i4 1000
    IL_000c:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> class [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32)
    IL_0011:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> class [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_0016:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> class [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToList<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_001b:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!1> class [FSharp.Core]Microsoft.FSharp.Collections.ListModule::Map<int32, int32> (class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,!!1>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0>)
    IL_0020:  pop
    IL_0021:  ret
    } // end of method $Test2::main@

  } // end of class <StartupCode$test2>.$Test2
}

Вы можете увидеть, что при 000c и 0011 создается перечислимое, а затем0016 последовательность преобразуется в список

Так что в этом случае оптимизация не происходит.Фактически, компилятору было бы очень трудно выполнить такую ​​оптимизацию, поскольку между Seq.Map и List.Map может быть любое количество различий (что является самой простой оптимизацией, так как это позволит избежать временного списка).

Answer 4

Хотя этот вопрос был задан некоторое время назад, текущая ситуация несколько отличается.

Многие из функций модуля списка на самом деле используют массив для внутреннего использования.

Например, текущая реализацияof pairwise

    [<CompiledName("Pairwise")>]
    let pairwise (list: 'T list) =
        let array = List.toArray list
        if array.Length < 2 then [] else
        List.init (array.Length-1) (fun i -> array.[i],array.[i+1])

также FoldBack (хотя только для списков длиной более 4)

    // this version doesn't causes stack overflow - it uses a private stack 
    [<CompiledName("FoldBack")>]
    let foldBack<'T,'State> f (list:'T list) (acc:'State) = 
        let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        match list with 
        | [] -> acc
        | [h] -> f.Invoke(h,acc)
        | [h1;h2] -> f.Invoke(h1,f.Invoke(h2,acc))
        | [h1;h2;h3] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,acc)))
        | [h1;h2;h3;h4] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,f.Invoke(h4,acc))))
        | _ -> 
            // It is faster to allocate and iterate an array than to create all those 
            // highly nested stacks.  It also means we won't get stack overflows here. 
            let arr = toArray list
            let arrn = arr.Length
            foldArraySubRight f arr 0 (arrn - 1) acc

Здесь foldArraySubRight фактически использует итерационный цикл для обработки массива.

Другие функции с похожей оптимизацией включают в себя практически все с именем, например *Back, а также все функции sort* и функцию permute.