Функциональное программирование - стоит ли неизменность дорого? [закрыто]

Вопрос состоит из двух частей. Первый концептуальный. Далее мы рассмотрим тот же вопрос более конкретно в Scala.

1. Делает ли использование только неизменяемых структур данных на языке программирования выполнение определенных алгоритмов / логики более затратным с точки зрения вычислений на практике? Это приводит к тому факту, что неизменяемость является основным принципом чисто функциональных языков. Есть ли другие факторы, влияющие на это?
2. Возьмем более конкретный пример. Быстрая сортировка обычно преподается и реализуется с использованием изменяемых операций над структурой данных в памяти. Как реализовать такую ​​вещь функциональным образом PURE с сопоставимыми вычислительными затратами и затратами на хранение по сравнению с изменяемой версией. В частности, в Scala. Ниже я привел несколько грубых тестов.

Подробнее:

Я вырос в императивном программировании (C ++, Java). Я изучаю функциональное программирование, в частности Scala.

Некоторые из основных принципов чистого функционального программирования:

1. Функции - граждане первого класса.
2. Функции не имеют побочных эффектов и, следовательно, объекты / структуры данных неизменяемы .

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

В конкретном случае я был немного удивлен этим фрагментом кода в этом уроке 6 . У него есть Java-версия Quicksort, за которой следует изящная реализация на Scala.

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

Версия Java

public class QuickSortJ {

    public static void sort(int[] xs) {
      sort(xs, 0, xs.length -1 );
    }

    static void sort(int[] xs, int l, int r) {
      if (r >= l) return;
      int pivot = xs[l];
      int a = l; int b = r;
      while (a <= b){
        while (xs[a] <= pivot) a++;
        while (xs[b] > pivot) b--;
        if (a < b) swap(xs, a, b);
      }
      sort(xs, l, b);
      sort(xs, a, r);
    }

    static void swap(int[] arr, int i, int j) {
      int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
}

Версия Scala

object QuickSortS {

  def sort(xs: Array[Int]): Array[Int] =
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
}

Код Scala для сравнения реализаций

import java.util.Date
import scala.testing.Benchmark

class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {

  val ints = new Array[Int](100000);

  override def prefix = name
  override def setUp = {
    val ran = new java.util.Random(5);
    for (i <- 0 to ints.length - 1)
      ints(i) = ran.nextInt();
  }
  override def run = sortfn(ints)
}

val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut   = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java   " )

benchImmut.main( Array("5"))
benchMut.main( Array("5"))

Полученные результаты

Время в миллисекундах для пяти последовательных запусков

Immutable/Functional/Scala    467    178    184    187    183
Mutable/Imperative/Java        51     14     12     12     12

Поскольку здесь существует несколько заблуждений , я хотел бы прояснить некоторые моменты.

• Быстрая сортировка «на месте» на самом деле не на месте (и быстрая сортировка не на месте по определению). Это требует дополнительного хранилища в виде пространства стека для рекурсивного шага, который имеет порядок O (log n ) в лучшем случае и O ( n ) в худшем случае.

• Реализация функционального варианта быстрой сортировки, работающего с массивами, не дает цели. Массивы никогда не бывают неизменными.

• «Правильная» функциональная реализация быстрой сортировки использует неизменяемые списки. Это, конечно, не на месте, но у него такое же асимптотическое время выполнения наихудшего случая ( O ( n ^ 2)) и сложность пространства ( O ( n )), что и у процедурной версии на месте.

  В среднем, его время работы остается на одном уровне со временем работы на месте ( O ( n log n )). Однако его пространственная сложность по-прежнему O ( n ).

У функциональной реализации быстрой сортировки есть два очевидных недостатка . Далее давайте рассмотрим эту эталонную реализацию в Haskell (я не знаю Scala…) из введения Haskell :

qsort []     = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where lesser  = (filter (< x) xs)
          greater = (filter (>= x) xs)

1. Первый недостаток - выбор поворотного элемента , который очень негибкий. Сила современных реализаций быстрой сортировки во многом зависит от умного выбора точки поворота (сравните «Разработка функции сортировки» Бентли и др. ). Вышеупомянутый алгоритм плох в этом отношении, что значительно снижает среднюю производительность.

2. Во-вторых, этот алгоритм использует конкатенацию списков (вместо построения списка), что является операцией O ( n ). Это не влияет на асимптотическую сложность, но это измеримый фактор.

Третий недостаток несколько скрыт: в отличие от варианта «на месте» эта реализация постоянно запрашивает память из кучи для cons-ячеек списка и потенциально разбрасывает память повсюду. В результате этот алгоритм имеет очень плохую локализацию кеша . Я не знаю, могут ли интеллектуальные распределители в современных языках функционального программирования смягчить это, но на современных машинах промахи в кэше стали серьезным убийцей производительности.

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

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

Прочитав «Разработка функции сортировки», я больше не могу считать быструю сортировку элегантным алгоритмом. Реализованный эффективно, это неуклюжий беспорядок, работа инженера, а не художника (чтобы не обесценить инженерию! В этом есть своя эстетика).

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

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

Итак, отвечая на исходный вопрос: « дорого ли стоит неизменность? ”- В частном случае быстрой сортировки есть стоимость, которая действительно является результатом неизменности. Но в целом нет .

В этом тесте функционального программирования есть много ошибок. Основные моменты включают:

• Вы используете примитивы, которые, возможно, придется распаковывать / распаковывать. Вы не пытаетесь проверить накладные расходы на перенос примитивных объектов, вы пытаетесь проверить неизменяемость.
• Вы выбрали алгоритм, в котором операция на месте необычайно эффективна (и это доказуемо). Если вы хотите показать, что существуют более быстрые алгоритмы, если они реализованы изменчиво, то это хороший выбор; в противном случае это может ввести в заблуждение.
• Вы используете неправильную функцию отсчета времени. Используйте System.nanoTime.
• Тест слишком короткий, чтобы вы могли быть уверены, что JIT-компиляция не займет значительную часть измеренного времени.
• Массив разбивается неэффективно.
• Массивы изменяемы, поэтому использование их с FP - в любом случае странное сравнение.

Итак, это сравнение является отличной иллюстрацией того, что вы должны подробно понимать свой язык (и алгоритм), чтобы писать высокопроизводительный код. Но это не очень хорошее сравнение FP и non-FP. Если вы этого хотите, посмотрите Haskell vs. C ++ в игре Computer Languages ​​Benchmark Game . Вывод здесь состоит в том, что штраф обычно не превышает двух или трех раз, но это действительно зависит от обстоятельств. (Нет никаких обещаний, что люди, работающие с Haskell, тоже написали максимально быстрые алгоритмы, но, по крайней мере, некоторые из них, вероятно, пытались! Опять же, некоторые из Haskell вызывают библиотеки C ....)

Теперь предположим, что вам нужен более разумный тест Quicksort, осознавая, что это, вероятно, один из худших случаев для FP и изменяемых алгоритмов, и игнорируя проблему структуры данных (т.е. притворяясь, что у нас может быть неизменяемый массив):

object QSortExample {
  // Imperative mutable quicksort
  def swap(xs: Array[String])(a: Int, b: Int) {
    val t = xs(a); xs(a) = xs(b); xs(b) = t
  }
  def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) {
    val pivot = xs((l+r)/2)
    var a = l
    var b = r
    while (a <= b) {
      while (xs(a) < pivot) a += 1
      while (xs(b) > pivot) b -= 1
      if (a <= b) {
        swap(xs)(a,b)
        a += 1
        b -= 1
      }
    }
    if (l<b) muQSort(xs)(l, b)
    if (b<r) muQSort(xs)(a, r)
  }

  // Functional quicksort
  def fpSort(xs: Array[String]): Array[String] = {
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length/2)
      val (small,big) = xs.partition(_ < pivot)
      if (small.length == 0) {
        val (bigger,same) = big.partition(_ > pivot)
        same ++ fpSort(bigger)
      }
      else fpSort(small) ++ fpSort(big)
    }
  }

  // Utility function to repeat something n times
  def repeat[A](n: Int, f: => A): A = {
    if (n <= 1) f else { f; repeat(n-1,f) }
  }

  // This runs the benchmark
  def bench(n: Int, xs: Array[String], silent: Boolean = false) {
    // Utility to report how long something took
    def ptime[A](f: => A) = {
      val t0 = System.nanoTime
      val ans = f
      if (!silent) printf("elapsed: %.3f sec\n",(System.nanoTime-t0)*1e-9)
      ans
    }

    if (!silent) print("Scala builtin ")
    ptime { repeat(n, {
      val ys = xs.clone
      ys.sorted
    }) }
    if (!silent) print("Mutable ")
    ptime { repeat(n, {
      val ys = xs.clone
      muQSort(ys)()
      ys
    }) }
    if (!silent) print("Immutable ")
    ptime { repeat(n, {
      fpSort(xs)
    }) }
  }

  def main(args: Array[String]) {
    val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar)
    val unsorted = letters.grouped(5).map(_.mkString).toList.toArray

    repeat(3,bench(1,unsorted,silent=true))  // Warmup
    repeat(3,bench(10,unsorted))     // Actual benchmark
  }
}

Обратите внимание на модификацию функциональной быстрой сортировки, чтобы она просматривала данные только один раз, если это вообще возможно, и сравнение со встроенной сортировкой. Когда мы запускаем его, мы получаем что-то вроде:

Scala builtin elapsed: 0.349 sec
Mutable elapsed: 0.445 sec
Immutable elapsed: 1.373 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.441 sec
Immutable elapsed: 1.374 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.442 sec
Immutable elapsed: 1.383 sec

Итак, помимо того, что мы узнали, что попытка написать свою собственную сортировку - плохая идея, мы обнаружили, что есть ~ 3-кратный штраф за неизменяемую быструю сортировку, если последняя реализована несколько осторожно. (Вы также можете написать метод trisect, который возвращает три массива: меньшие, равные и большие, чем точка поворота. Это может немного ускорить процесс.)

Я не думаю, что версия Scala на самом деле хвостовая рекурсивная, поскольку вы используете Array.concat.

Кроме того, то, что это идиоматический код Scala, не означает, что это лучший способ сделать это.

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

См. Вопрос о переполнении стека. Как отсортировать массив в Scala? для примера.

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

Проще говоря, вы не используете быструю сортировку при использовании чисто функциональных языков.

Давайте посмотрим на это под другим углом. Рассмотрим эти две функции:

// Version using mutable data structures
def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = {
  def posIndex(i: Int): Int = {
    if (i < arr.length) {
      if (p(arr(i)))
        i
      else
        posIndex(i + 1)
    } else {
      -1
    }
  }

  var index = posIndex(0)

  if (index < 0) Array.empty
  else {
    var result = new Array[T](arr.length - index)
    Array.copy(arr, index, result, 0, arr.length - index)
    result
  }
}

// Immutable data structure:

def tailFrom[T](list: List[T], p: T => Boolean): List[T] = {
  def recurse(sublist: List[T]): List[T] = {
    if (sublist.isEmpty) sublist
    else if (p(sublist.head)) sublist
    else recurse(sublist.tail)
  }
  recurse(list)
}

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

Когда вы программируете с неизменяемыми структурами данных, вы структурируете свой код, чтобы воспользоваться его сильными сторонами. Это не просто тип данных или даже отдельные алгоритмы. Программа будет оформлена иначе.

Вот почему бенчмаркинг обычно бессмысленен. Либо вы выбираете алгоритмы, которые естественны для того или иного стиля, и этот стиль побеждает, либо вы тестируете все приложение, что часто непрактично.

Сортировка массива - это самая насущная задача во вселенной. Неудивительно, что многие элегантные «неизменяемые» стратегии / реализации терпят неудачу в микробенчмарке «сортировка массива». Однако это не означает, что неизменность стоит дорого "в целом". Есть много задач, в которых неизменяемые реализации будут работать сравнимо с изменяемыми, но сортировка массивов часто не входит в их число.

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

Стоимость неизменности в Scala

Вот версия, которая почти такая же быстрая, как Java. ;)

object QuickSortS {
  def sort(xs: Array[Int]): Array[Int] = {
    val res = new Array[Int](xs.size)
    xs.copyToArray(res)
    (new QuickSortJ).sort(res)
    res
  }
}

Эта версия делает копию массива, сортирует ее на месте с использованием версии Java и возвращает копию. Scala не заставляет вас внутренне использовать неизменяемую структуру.

Таким образом, преимущество Scala в том, что вы можете использовать изменчивость и неизменность по своему усмотрению. Недостаток заключается в том, что если вы сделаете это неправильно, вы не получите преимуществ неизменности.

Известно, что QuickSort быстрее выполняется на месте, так что это вряд ли справедливое сравнение!

Сказав это ... Array.concat? По крайней мере, вы показываете, как тип коллекции, оптимизированный для императивного программирования, работает особенно медленно, когда вы пытаетесь использовать его в функциональном алгоритме; почти любой другой выбор будет быстрее!

Еще один очень важный момент , чтобы рассмотреть, возможно , в самый важный вопрос при сравнении двух подходов: «как хорошо делает эту шкалу к нескольким узлам / ядер»

Скорее всего, если вы ищете неизменяемую быструю сортировку, то вы делаете это потому, что вам действительно нужна параллельная быстрая сортировка. В Википедии есть ссылки на эту тему: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

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

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

Интересно, как это будет сочетаться с однопоточным императивным подходом ...

Возможно, поэтому более важный вопрос:

«Учитывая, что отдельные ядра не будут работать быстрее, а синхронизация / блокировка представляют собой реальную проблему для распараллеливания, стоит ли изменяемость дорого обходиться?»

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