Блог

Я довольно новичок в программировании на f#, и хотя мне это очень нравится, одна вещь, которая меня беспокоит, — это то, как часто написание кода «правильным» способом в f# приводит к тому, что он невероятно медленный. Я работал над нейронной сетью в f#, и мой код невероятно медленный по сравнению с моими реализациями на других языках. Одним из конкретных случаев являются следующие функции линейной алгебры:

 // Dot Product

// Slow
let rec dotProduct (vector1 : float []) (vector2 : float []) : float =

    if vector1 |> Array.length = 0 then
        0.0
    else
        vector1.[0] * vector2.[0]   (dotProduct (vector1 |> Array.tail) (vector2 |> Array.tail))

// Fast
let dotProduct (vector1 : float []) (vector2 : float [])  =
    Array.fold2 (fun state x y -> state   x * y) 0.0 vector1 vector2
 

 // Matrix Vector Product

// Slow

let matrixVectorProduct (matrix : float [,]) (vector : float[]) : float [] =
    [|
        for i = 0 to (matrix |> Array2D.length1) - 1 do
            yield dotProduct matrix.[i, 0..] vector
    |]

// Fast
let matrixVectorProduct (matrix : float [,]) (vector : float[]) : float [] =
    
    let mutable product = Array.zeroCreate (matrix |> Array2D.length1)
    
    for i = 0 to (matrix |> Array2D.length1) - 1 do
        product.[i] <- (dotProduct matrix.[i, 0..] vector)
    
    product
 

Мне было интересно, может ли кто-нибудь с большим опытом работы с f# объяснить, почему именно второй случай быстрее с каждым примером, с точки зрения того, как компьютер интерпретирует мой код. Самая большая проблема в кодировании на языке высокого уровня, таком как f#, заключается в том, что трудно понять, как оптимизируется и выполняется ваш код по сравнению с программированием на языке низкого уровня.

Для первого примера кода:

Ваша медленная dotProduct функция выполняет две вещи, влияющие на производительность процессора, в порядке воздействия:

1. Перераспределение массива при каждом рекурсивном вызове
2. Не используя хвостовую рекурсию

2 — й пункт на самом деле не так уж важен по сравнению с тем, что я измерил.

Для второго образца:

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

Однако есть еще один способ ускорить ваш код продукта dot: просто выполните простой цикл!

 let dotProductLoop (vector1 : float []) (vector2 : float []) : float =
    let mutable acc = 0.0

    for idx = 0 to vector1.Length - 1 do
        acc <- acc   (vector1.[idx] * vector2.[idx])
    
    acc
 

Вы заметите, что [fold2][1] это более или менее делает это, но это сопряжено с некоторыми незначительными накладными расходами.

Я использовал каждый подход в качестве эталона, чтобы увидеть некоторые сравнительные результаты. Как вы можете видеть, циклический подход даже быстрее, чем fold2 вызов, но оба они настолько быстрее, чем ваша первоначальная реализация, что это явный выигрыш.

 
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19042.1288 (20H2/October2020Update)
AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK=6.0.100-rc.2.21505.57
  [Host]     : .NET 6.0.0 (6.0.21.48005), X64 RyuJIT DEBUG
  DefaultJob : .NET 6.0.0 (6.0.21.48005), X64 RyuJIT


 

Еще одна вещь, которую вы можете сделать, если вы привержены написанию рекурсивного кода, — это иметь частную вспомогательную функцию, которая выполняет хвостовую рекурсию Span или ReadonlySpan :

 let rec private dotProductImpl (vector1 : Span<float>) (vector2 : Span<float>) (acc: float) =
        if vector1.Length = 0 then
            acc
        else
            dotProductImpl (vector1.Slice(1)) (vector2.Slice(1)) (acc   vector1.[0] * vector2.[0])
 

Функция, вызывающая это, будет работать так же хорошо, как и цикл, который я предложил.