Является ли функциональное программирование Scala более медленным, чем традиционное кодирование?
В одной из моих первых попыток создать функциональный код я столкнулся с проблемой производительности.
Я начал с общей задачи - умножить элементы двух массивов и подвести итоги:
var first:Array[Float] ...
var second:Array[Float] ...
var sum=0f;
for (ix<-0 until first.length)
sum += first(ix) * second(ix);
Вот как я реформировал работу:
sum = first.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)
Когда я проверил два подхода, второй метод занял в 40 раз больше времени!
Почему второй метод занимает гораздо больше времени? Как я могу изменить работу так, чтобы она была и эффективна по скорости, и использовала стиль функционального программирования?
9 ответов
Основные причины, по которым эти два примера отличаются по скорости:
- быстрее не используются никакие дженерики, поэтому он не сталкивается с боксом / распаковкой.
- чем быстрее не создаются временные коллекции, тем самым избегаются дополнительные копии памяти.
Давайте рассмотрим медленный по частям. Первый:
first.zip(second)
Это создает новый массив, массив Tuple2, Он скопирует все элементы из обоих массивов в Tuple2 объекты, а затем скопировать ссылку на каждый из этих объектов в третий массив. Теперь обратите внимание, что Tuple2 параметризован, поэтому не может хранить Float непосредственно. Вместо этого новые экземпляры java.lang.Float создаются для каждого номера, номера сохраняются в них, а затем ссылка для каждого из них сохраняется в Tuple2,
map{ case (a,b) => a*b }
Теперь четвертый массив создан. Чтобы вычислить значения этих элементов, необходимо прочитать ссылку на кортеж из третьего массива, прочитать ссылку на java.lang.Float хранятся в них, читают цифры, умножают, создают новые java.lang.Float сохранить результат, а затем передать эту ссылку обратно, которая будет снова разыменована для сохранения в массиве (массивы не стираются по типу).
Мы еще не закончили. Вот следующая часть:
reduceLeft(_+_)
Тот относительно безвреден, за исключением того, что он все еще делает бокс / распаковку и java.lang.Float создание на итерации, так как reduceLeft получает Function2, который параметризован.
Scala 2.8 представляет функцию, называемую специализацией, которая избавляет от многих этих проблем с боксом / распаковкой. Но давайте рассмотрим альтернативные более быстрые версии. Мы могли бы, например, сделать map а также reduceLeft за один шаг:
sum = first.zip(second).foldLeft(0f) { case (a, (b, c)) => a + b * c }
Мы могли бы использовать view (Scala 2.8) или projection (Scala 2.7), чтобы вообще не создавать промежуточные коллекции:
sum = first.view.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)
Этот последний не сильно экономит, на самом деле, так что я думаю, что нестрогость, будучи "потерянной" довольно быстро (то есть, один из этих методов является строгим даже в представлении). Есть также альтернативный способ архивирования, который не является строгим (то есть, избегает некоторых промежуточных результатов) по умолчанию:
sum = (first,second).zipped.map{ case (a,b) => a*b }.reduceLeft(_+_)
Это дает гораздо лучший результат, чем первый. Лучше чем foldLeft один, хотя и ненамного. К сожалению, мы не можем вместе zipped с foldLeft потому что первый не поддерживает второй.
Последний - самый быстрый, который я смог получить. Быстрее, только со специализацией. Сейчас, Function2 бывает специализированным, но для Int, Long а также Double, Другие примитивы были исключены, так как специализация значительно увеличивает размер кода для каждого примитива. Хотя на моих тестах Double на самом деле занимает больше времени. Это может быть результатом того, что он в два раза больше, или я могу ошибаться.
Итак, в конце концов, проблема заключается в комбинации факторов, в том числе в создании промежуточных копий элементов и в способе обработки Java (JVM) примитивов и обобщений. Подобный код в Haskell, использующий суперкомпиляцию, будет равен чему-либо, кроме ассемблера. На JVM вы должны знать о компромиссах и быть готовыми к оптимизации критического кода.
Я сделал несколько вариаций этого с Scala 2.8. Версия цикла, как вы пишете, но функциональная версия немного отличается:
(xs, ys).zipped map (_ * _) reduceLeft(_ + _)
Я работал с Double вместо Float, потому что в настоящее время специализация только для Double. Затем я проверил с массивами и векторами в качестве типа носителя. Кроме того, я протестировал варианты в штучной упаковке, которые работают на java.lang. Double вместо примитивных двойников, чтобы измерить эффект примитивного типа упаковки и распаковки. Вот что я получил (под управлением Java 1.6_10 серверная виртуальная машина, Scala 2.8 RC1, 5 запусков на тест).
loopArray 461 437 436 437 435 limitArray 6573 6544 6718 6828 6554 loopVector 5877 5773 5775 5791 5657 ReductionVector 5064 4880 4844 4828 4926 loopArrayBoxed 2627 2551 2569 2537 2546 limitArrayBoxed 4809 4434 4496 4434 4365 loopVectorBoxed 7577 7450 7456 7463 7432 ReductionVectorBoxed 5116 4903 5006 4957 5122
Первое, на что нужно обратить внимание, - это то, что самое большое различие между циклами примитивных массивов и уменьшением функциональных возможностей примитивных массивов. Это примерно в 15 раз вместо 40, которые вы видели, что отражает улучшения в Scala 2.8 по сравнению с 2.7. Тем не менее, примитивные циклы массивов являются самыми быстрыми из всех тестов, тогда как примитивные сокращения массивов являются самыми медленными. Причина в том, что примитивные массивы Java и общие операции просто не очень хорошо подходят. Доступ к элементам примитивных массивов Java из универсальных функций требует большого количества упаковки / распаковки и иногда даже требует рефлексии. Будущие версии Scala будут специализироваться на классе Array, и тогда мы увидим некоторое улучшение. Но сейчас это то, что есть.
Если вы переходите от массивов к векторам, вы замечаете несколько вещей. Во-первых, уменьшенная версия теперь быстрее, чем императивный цикл! Это потому, что уменьшение вектора может использовать эффективные массовые операции. Во-вторых, уменьшение вектора происходит быстрее, чем уменьшение массива, что иллюстрирует внутренние издержки, которые массивы примитивных типов представляют для общих функций высшего порядка.
Если вы устраните накладные расходы, связанные с упаковкой / распаковкой, работая только с коробочными значениями java.lang.Double, картина изменится. Теперь уменьшение массивов чуть менее чем в 2 раза медленнее, чем зацикливание, вместо 15-кратной разницы ранее. Это более близко аппроксимирует внутреннюю нагрузку трех циклов с промежуточными структурами данных вместо объединенного цикла императивной версии. Циклическая передача по векторам теперь является самым медленным решением, тогда как сокращение по векторам немного медленнее, чем сокращение по массивам.
Таким образом, общий ответ: это зависит. Если у вас жесткие циклы над массивами примитивных значений, ничто не сравнится с императивным циклом. И нет проблем при написании циклов, потому что они ни длиннее, ни менее понятны, чем функциональные версии. Во всех других ситуациях решение FP выглядит конкурентоспособным.
Это микробенчмарк, и он зависит от того, как компилятор оптимизирует ваш код. У вас есть 3 петли, составленные здесь,
почтовый индекс карта. складка
Теперь я уверен, что компилятор Scala не может объединить эти три цикла в один цикл, а базовый тип данных является строгим, поэтому каждый (.) Соответствует создаваемому промежуточному массиву. Императивное / изменяемое решение будет использовать буфер каждый раз, избегая копий.
Теперь понимание того, что означает составление этих трех функций, является ключом к пониманию производительности в функциональном языке программирования - и действительно, в Haskell эти три цикла будут оптимизированы в один цикл, который повторно использует базовый буфер - но Scala не может сделать тот.
Однако использование подхода комбинатора имеет свои преимущества - если различать эти три функции, будет проще распараллелить код (замените map на parMap и т. Д.). Фактически, при правильном типе массива (например, параллельном массиве), достаточно умный компилятор сможет автоматически распараллеливать ваш код, обеспечивая более высокую производительность.
Итак, в итоге:
- Наивные переводы могут иметь неожиданные копии и неэффективность
- умные компиляторы FP снимают эту нагрузку (но Scala пока не может)
- придерживаться подхода высокого уровня окупается, если вы хотите перенастроить свой код, например, распараллелить его
У Дона Стюарта есть хороший ответ, но, возможно, не очевидно, как переход от одного цикла к трем приводит к замедлению в 40 раз. Я добавлю к его ответу, что Scala компилируется в байт-коды JVM, и компилятор Scala не только не объединяет три цикла в один, но компилятор Scala почти наверняка выделяет все промежуточные массивы. Общеизвестно, что реализации JVM не предназначены для обработки уровней выделения, требуемых функциональными языками. Распределение - это значительная стоимость в функциональных программах, и это одно из преобразований слияния петель, которое Дон Стюарт и его коллеги реализовали для Haskell, настолько мощно: они устраняют большое количество выделений. Когда у вас нет этих преобразований, плюс вы используете дорогой распределитель, такой как в типичной JVM, вот откуда и происходит большое замедление.
Scala - отличный инструмент для экспериментов с выразительной силой необычного сочетания языковых идей: классов, миксинов, модулей, функций и так далее. Но это относительно молодой исследовательский язык, и он работает на JVM, поэтому ожидать высокой производительности неразумно, за исключением того кода, который хорош для JVM. Если вы хотите поэкспериментировать со смесью языковых идей, которые предлагает Scala, это здорово - это действительно интересный дизайн - но не ожидайте, что производительность в чистом функциональном коде будет такой же, как в зрелом компиляторе для функционального языка, например GHC или MLton.
Является ли функциональное программирование scala более медленным, чем традиционное кодирование?
Не обязательно Вещи, чтобы сделать с первоклассными функциями, сопоставлением с образцом и карри, не должны быть особенно медленными. Но в Scala больше, чем в других реализациях других функциональных языков, вам действительно нужно следить за распределением ресурсов- они могут быть очень дорогими.
Библиотека коллекций 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 будет специализированным, а не общим; если вы используете что-то ранее, вы можете создать свой собственный abstract class F { def f(a: Float) : Float } а затем позвонить с new F { def f(a: Float) = a*a } вместо (a: Float) => a*a.)
В любом случае, дело в том, что не функциональный стиль делает функциональное кодирование в 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
Чтобы ответить на вопрос в заголовке: Простые функциональные конструкции могут быть медленнее, чем обязательно на JVM.
Но, если мы рассмотрим только простые конструкции, мы могли бы также выбросить все современные языки и придерживаться C или ассемблера. Если вы посмотрите на перестрелку на языке программирования, C всегда побеждает.
Так зачем выбирать современный язык? Потому что это позволяет выразить более чистый дизайн. Более чистый дизайн приводит к повышению производительности в целом в работе приложения. Даже если некоторые методы низкого уровня могут быть медленнее. Один из моих любимых примеров - производительность BuildR vs. Maven. BuildR написан на Ruby, интерпретируемом, медленном языке. Maven написан на Java. Сборка в BuildR в два раза быстрее, чем в Maven. Это связано, в основном, с дизайном BuildR, который легче по сравнению с Maven.
Ваше функциональное решение медленное, потому что оно генерирует ненужные временные структуры данных. Удаление их называется вырубкой лесов, и это легко сделать на строгих функциональных языках, свернув анонимные функции в одну анонимную функцию и используя один агрегатор. Например, ваше решение написано на 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 чтобы функция высшего порядка была встроена в функциональный аргумент, после чего вы восстанавливаете оптимальную производительность императивного цикла.
Вот решение 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.:)