Функциональное программирование Scala медленнее, чем традиционное кодирование?

Это микробенчмарк, и он зависит от того, как компилятор оптимизирует ваш код. Здесь у вас 3 цикла,

zip . map . fold

Теперь я уверен, что компилятор Scala не может объединить эти три цикла в один цикл, а базовый тип данных строгий, поэтому каждое (.) соответствует созданию промежуточного массива. В императивном/минимальном решении буфер будет использоваться каждый раз заново, избегая копий.

Теперь, понимание того, что означает композиция этих трех функций, является ключом к пониманию производительности в функциональном языке программирования - и действительно, в Haskell эти три цикла будут оптимизированы в один цикл, который повторно использует базовый буфер - но Scala не может этого сделать.

Однако есть преимущества в использовании комбинаторного подхода - различая эти три функции, будет легче распараллелить код (заменить map на parMap и т.д.). На самом деле, при правильном выборе типа массива (например, параллельный массив) достаточно умный компилятор сможет автоматически распараллелить ваш код, что даст больше выигрыша в производительности.

Итак, подведем итоги:

• наивные переводы могут иметь неожиданные копии и неэффективности
• умные FP-компиляторы устраняют эти накладные расходы (но Scala пока не может)
• придерживаясь высокоуровневого подхода, вы окупите себя, если захотите перенацелить свой код, например, распараллелить его

Я не являюсь опытным программистом на Scala, поэтому, вероятно, есть более эффективный метод, но как насчет чего-то вроде этого? Это может быть оптимизировано для хвостового вызова, поэтому производительность должна быть в порядке.

def multiply_and_sum(l1:List[Int], l2:List[Int], sum:Int):Int = {
    if (l1 != Nil && l2 != Nil) {
        multiply_and_sum(l1.tail, l2.tail, sum + (l1.head * l2.head))
    }
    else {
        sum
    }
}

val first = Array(1,2,3,4,5)
val second = Array(6,7,8,9,10)
multiply_and_sum(first.toList, second.toList, 0)  //Returns: 130

Библиотека коллекций Scala является полностью универсальной, и предоставляемые операции выбираются для максимальных возможностей, а не для максимальной скорости. Поэтому, да, если вы используете функциональную парадигму в Scala, не обращая внимания (особенно если вы используете примитивные типы данных), ваш код будет выполняться дольше (в большинстве случаев), чем если вы используете императивную/итеративную парадигму, не обращая внимания.

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

class FastFloatOps(a: Array[Float]) {
  def fastMapOnto(f: Float => Float) = {
    var i = 0
    while (i < a.length) { a(i) = f(a(i)); i += 1 }
    this
  }
  def fastMapWith(b: Array[Float])(f: (Float,Float) => Float) = {
    val len = a.length min b.length
    val c = new Array[Float](len)
    var i = 0
    while (i < len) { c(i) = f(a(i),b(i)); i += 1 }
    c
  }
  def fastReduce(f: (Float,Float) => Float) = {
    if (a.length==0) Float.NaN
    else {
      var r = a(0)
      var i = 1
      while (i < a.length) { r = f(r,a(i)); i += 1 }
      r
    }
  }
}
implicit def farray2fastfarray(a: Array[Float]) = new FastFloatOps(a)

и тогда эти операции будут выполняться намного быстрее. (Еще быстрее, если вы используете Double и 2.8. RC1, потому что тогда функции (Double,Double)=>Double будут специализированными, а не общими; если вы используете что-то более раннее, вы можете создать свой собственный абстрактный класс F { def f(a: Float) : Float } и затем вызвать с помощью new F { def f(a: Float) = a*a } вместо (a: Float) => a*a. )

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

Чтобы ответить на вопрос в заголовке: Простые функциональные конструкции могут быть медленнее императивных на JVM.

Но если рассматривать только простые конструкции, то с таким же успехом можно отбросить все современные языки и остановиться на Си или ассемблере. Если посмотреть на перестрелку языков программирования, то C всегда выигрывает.

Так почему же стоит выбрать современный язык? Потому что он позволяет выразить более чистый дизайн. Более чистый дизайн приводит к увеличению производительности при работе приложения в целом. Даже если некоторые низкоуровневые методы могут быть медленнее. Один из моих любимых примеров - производительность BuildR по сравнению с Maven. BuildR написан на Ruby, интерпретируемом, медленном языке. Maven написан на Java. Сборка в BuildR выполняется в два раза быстрее, чем в Maven. Это объясняется в основном дизайном BuildR, который является облегченным по сравнению с Maven.

Вот решение dbyrnes с массивами ( Предполагая, что должны использоваться массивы) и просто перебираем индекс:

def multiplyAndSum (l1: Array[Int], l2: Array[Int]) : Int = 
{
    def productSum (idx: Int, sum: Int) : Int = 
        if (idx < l1.length)
            productSum (idx + 1, sum + (l1(idx) * l2(idx))) else 
                sum
    if (l2.length == l1.length) 
        productSum (0, 0) else 
    error ("lengths don't fit " + l1.length + " != " + l2.length) 
}


val first = (1 to 500).map (_ * 1.1) toArray                                                
val second = (11 to 510).map (_ * 1.2) toArray     
def loopi (n: Int) = (1 to n).foreach (dummy => multiplyAndSum (first, second))
println (timed (loopi (100*1000)))

На это требуется примерно 1/40 времени подхода со списком. У меня не установлен 2.8, так что вам придется протестировать @tailrec самостоятельно. :)

Я сделал несколько вариаций этого со Scala 2.8. Версия цикла такая, как вы написали, но функциональная версия немного отличается:

(xs, ys).zipped map (_ * _) reduceLeft(_ + _)

Я работал с Double вместо Float, потому что в настоящее время специализация работает только для Double. Затем я протестировал с массивами и векторами в качестве несущего типа. Кроме того, я протестировал варианты Boxed, которые работают с java.lang.Double вместо примитивных Double, чтобы измерить влияние боксирования и дебоксирования примитивных типов. Вот что я получил (работа на серверной виртуальной машине Java 1.6_10, Scala 2.8 RC1, 5 запусков на тест).

loopArray               461             437             436             437             435
reduceArray             6573            6544            6718            6828            6554
loopVector              5877            5773            5775            5791            5657
reduceVector            5064            4880            4844            4828            4926

loopArrayBoxed          2627            2551            2569            2537            2546
reduceArrayBoxed        4809            4434            4496            4434            4365
loopVectorBoxed         7577            7450            7456            7463            7432
reduceVectorBoxed       5116            4903            5006            4957            5122

Первое, что бросается в глаза, это то, что наибольшая разница наблюдается между циклами примитивных массивов и функциональными сокращениями примитивных массивов. Она составляет примерно 15 раз вместо 40, которые вы видели, что отражает улучшения в Scala 2.8 по сравнению с 2.7. Тем не менее, циклы примитивных массивов являются самыми быстрыми из всех тестов, в то время как редукции примитивных массивов - самые медленные. Причина в том, что примитивные массивы Java и общие операции просто не очень хорошо подходят друг другу. Доступ к элементам примитивных массивов Java из общих функций требует много боксирования/небоксирования, а иногда даже требует отражения. В будущих версиях Scala класс Array будет специализирован, и тогда мы увидим некоторое улучшение. Но сейчас это то, что есть.

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

Если устранить накладные расходы на боксирование/небоксирование, работая только с боксированными значениями java.lang.Double, картина меняется. Теперь reduce над массивами работает чуть менее чем в 2 раза медленнее, чем looping, вместо прежней разницы в 15 раз. Это более точно соответствует накладным расходам, присущим трем циклам с промежуточными структурами данных вместо объединенного цикла императивной версии. Цикл над векторами теперь является самым медленным решением, в то время как сокращение над векторами немного медленнее, чем сокращение над массивами.

Итак, общий ответ таков: это зависит от ситуации. Если у вас есть узкие циклы над массивами примитивных значений, нет ничего лучше императивного цикла. И нет никаких проблем с написанием таких циклов, потому что они не длиннее и не менее понятны, чем функциональные версии. Во всех остальных ситуациях FP-решение выглядит конкурентоспособным.

У Дона Стюарта есть прекрасный ответ, но может быть неочевидно, как переход от одного цикла к трем приводит к замедлению в 40 раз. Я добавлю к его ответу, что Scala компилируется в байт-коды JVM, и не только компилятор Scala не объединяет три цикла в один, но и компилятор Scala почти наверняка выделяет все промежуточные массивы. Общеизвестно, что реализации JVM не предназначены для обработки скорости распределения, требуемой функциональными языками .Распределение - это значительные затраты в функциональных программах, и это одно из преобразований слияния циклов, которое Дон Стюарт и его коллеги реализовали для Haskell, настолько мощны: они устраняют большое количество распределений. Когда у вас нет этих преобразований, плюс вы используете дорогостоящий распределитель, такой как на типичной JVM, именно отсюда происходит большое замедление.

Scala - отличное средство для экспериментов с выразительной силой необычного сочетания языковых идей: классов, миксинов, модулей, функций и так далее. Но это относительно молодой исследовательский язык, и он работает на JVM, поэтому неразумно ожидать высокой производительности, за исключением того кода, в котором JVM хороши. Если вы хотите поэкспериментировать с сочетанием языковых идей, которые предлагает Scala, отлично - это действительно интересный дизайн - но не ожидайте такой же производительности на чистом функциональном коде, которую вы получили бы со зрелым компилятором для функционального языка, например GHC или MLton .

Является ли функциональное программирование на Scala медленнее, чем традиционное кодирование?

Не обязательно . Работа с первоклассными функциями, сопоставлением с образцом и каррированием не должна быть особенно медленной. Но с Scala больше, чем с другими реализациями других функциональных языков, вам действительно нужно следить за распределением - они могут быть очень дорогими.

Ваше функциональное решение работает медленно, потому что оно генерирует ненужные временные структуры данных. Их удаление известно как вырубка леса, и это легко сделать на строгих функциональных языках, превратив ваши анонимные функции в одну анонимную функцию и используя один агрегатор. Например, ваше решение, написанное на F # с использованием zip , map и reduce :

let dot xs ys = Array.zip xs ys |> Array.map (fun (x, y) -> x * y) -> Array.reduce ( * )

может быть переписано с использованием fold2 , чтобы избегайте всех временных структур данных:

let dot xs ys = Array.fold2 (fun t x y -> t + x * y) 0.0 xs ys

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