Programowanie funkcjonalne - czy niezmienność jest droga? [Zamknięte]

Pytanie składa się z dwóch części. Pierwsza jest koncepcyjna. Następny dotyczy tego samego pytania bardziej konkretnie w Scali.

1. Czy używanie tylko niezmiennych struktur danych w języku programowania powoduje, że implementacja niektórych algorytmów / logiki jest z natury bardziej kosztowna obliczeniowo w praktyce? Wynika to z faktu, że niezmienność jest podstawowym założeniem języków czysto funkcjonalnych. Czy są inne czynniki, które mają na to wpływ?
2. Weźmy bardziej konkretny przykład. Quicksort jest generalnie nauczany i implementowany przy użyciu operacji mutowalnych na strukturze danych w pamięci. Jak zaimplementować coś takiego w funkcjonalny sposób PURE z porównywalnym narzutem obliczeniowym i pamięci masowej do wersji mutowalnej. Szczególnie w Scali. Poniżej zamieściłem kilka prostych testów porównawczych.

Więcej szczegółów:

Pochodzę z imperatywnego doświadczenia w programowaniu (C ++, Java). Eksplorowałem programowanie funkcjonalne, w szczególności Scala.

Niektóre z podstawowych zasad czystego programowania funkcyjnego:

1. Funkcje są obywatelami pierwszej kategorii.
2. Funkcje nie mają skutków ubocznych, dlatego obiekty / struktury danych są niezmienne .

Chociaż nowoczesne maszyny JVM są niezwykle wydajne w tworzeniu obiektów, a usuwanie elementów bezużytecznych jest bardzo niedrogie w przypadku obiektów krótkotrwałych, prawdopodobnie nadal lepiej jest zminimalizować tworzenie obiektów, prawda? Przynajmniej w aplikacji jednowątkowej, w której współbieżność i blokowanie nie stanowią problemu. Ponieważ Scala jest paradygmatem hybrydowym, w razie potrzeby można napisać kod imperatywny ze zmiennymi obiektami. Ale jako ktoś, kto spędził wiele lat na próbach ponownego wykorzystania obiektów i zminimalizowania alokacji. Chciałbym dobrze zrozumieć szkołę myślenia, która by na to nawet nie pozwoliła.

W konkretnym przypadku byłem trochę zaskoczony tym fragmentem kodu w tym samouczku 6 . Ma wersję Java Quicksort, po której następuje ładnie wyglądająca implementacja Scala tego samego.

Oto moja próba porównania wdrożeń. Nie wykonałem szczegółowego profilowania. Ale przypuszczam, że wersja Scala jest wolniejsza, ponieważ liczba przydzielonych obiektów jest liniowa (jeden na wywołanie rekurencji). Czy jest jakaś szansa, że ​​w grę wchodzą optymalizacje połączeń końcowych? Jeśli mam rację, Scala obsługuje optymalizację wywołań końcowych dla wywołań samorekurencyjnych. Powinien więc tylko pomagać. Używam Scala 2.8.

Wersja 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;
    }
}

Wersja 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 <)))
    }
}

Kod Scala do porównywania implementacji

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"))

Wyniki

Czas w milisekundach dla pięciu kolejnych przebiegów

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

Ponieważ latają tutaj nieporozumienia , chciałbym wyjaśnić kilka kwestii.

• „Lokalne” sortowanie szybkie nie jest w rzeczywistości na miejscu (iz definicji szybkie sortowanie nie jest na miejscu). Wymaga dodatkowej pamięci w postaci miejsca na stosie dla kroku rekurencyjnego, który w najlepszym przypadku jest rzędu O (log n ), ale O w najgorszym przypadku ( n ).

• Implementacja funkcjonalnego wariantu quicksort, który działa na tablicach, mija się z celem. Tablice nigdy nie są niezmienne.

• „Właściwa” funkcjonalna implementacja quicksort korzysta z niezmiennych list. Oczywiście nie jest na miejscu, ale ma ten sam najgorszy asymptotyczny czas wykonywania ( O ( n ^ 2)) i złożoność przestrzeni ( O ( n )), co wersja proceduralna w miejscu.

  Średnio jego czas działania jest nadal porównywalny z czasem trwania wariantu lokalnego ( O ( n log n )). Jednak jego złożoność przestrzenna nadal wynosi O ( n ).

Istnieją dwie oczywiste wady funkcjonalnej implementacji quicksort. W dalszej części rozważmy tę implementację referencyjną w Haskell (nie znam Scali…) z wprowadzenia Haskell :

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

1. Pierwsza wada to wybór elementu obrotowego , który jest bardzo nieelastyczny. Siła nowoczesnych wdrożeń quicksort zależy w dużej mierze od mądrego wyboru pivota (porównaj „Engineering a sort function” Bentley i in. ). Powyższy algorytm jest słaby pod tym względem, co znacznie obniża średnią wydajność.

2. Po drugie, ten algorytm wykorzystuje konkatenację list (zamiast konstrukcji list), która jest plikiem operacją O ( n ). Nie wpływa to na asymptotyczną złożoność, ale jest to wymierny czynnik.

Trzecia wada jest nieco ukryta: w przeciwieństwie do wariantu „na miejscu”, ta implementacja nieustannie żąda pamięci ze sterty dla komórek wad z listy i potencjalnie rozprasza pamięć w każdym miejscu. W rezultacie ten algorytm ma bardzo słabą lokalizację pamięci podręcznej . Nie wiem, czy inteligentne podzielniki w nowoczesnych funkcjonalnych językach programowania mogą to złagodzić - ale na nowoczesnych maszynach chybienia pamięci podręcznej stały się głównym zabójcą wydajności.

Jaki jest wniosek? W przeciwieństwie do innych, nie powiedziałbym, że szybkie sortowanie jest z natury niezbędne i dlatego źle działa w środowisku FP. Wręcz przeciwnie, argumentowałbym, że quicksort jest doskonałym przykładem funkcjonalnego algorytmu: bezproblemowo przekłada się na niezmienne środowisko, jego asymptotyczny czas działania i złożoność przestrzeni są na równi z implementacją proceduralną, a nawet jego implementacja proceduralna wykorzystuje rekursję.

Ale ten algorytm nadal działa gorzej, gdy jest ograniczony do niezmiennej domeny. Powodem tego jest to, że algorytm ma szczególną właściwość czerpania korzyści z wielu (czasami niskiego poziomu) dostrajania, które można skutecznie przeprowadzić tylko na tablicach. Naiwny opis quicksort pomija wszystkie te zawiłości (zarówno w wariancie funkcjonalnym, jak i proceduralnym).

Po przeczytaniu „Inżynierii funkcji sortowania” nie mogę już uważać szybkiego sortowania za elegancki algorytm. Wykonany sprawnie, to niezgrabny bałagan, dzieło inżyniera, a nie artysty (nie dewaluować inżynierii! Ma to swoją własną estetykę).

Chciałbym jednak również zwrócić uwagę, że ten punkt dotyczy szczególnie szybkiego sortowania. Nie każdy algorytm jest podatny na tego samego rodzaju modyfikacje na niskim poziomie. Naprawdę dużo algorytmów i struktur danych można wyrazić bez utraty wydajności w niezmiennym środowisku.

A nawet niezmienność zmniejszyć koszty wydajności, eliminując potrzebę kosztownych kopii lub synchronizacji między wątkami.

A zatem, odpowiadając na pierwotne pytanie, „ czy niezmienność jest droga? ”- W tym szczególnym przypadku szybkiego sortowania istnieje koszt, który jest rzeczywiście wynikiem niezmienności. Ale generalnie nie .

Jest wiele rzeczy, które są złe w tym jako wzorzec programowania funkcjonalnego. Najważniejsze to:

• Używasz prymitywów, które mogą wymagać zapakowania / rozpakowania. Nie próbujesz testować narzutu zawijania prymitywnych obiektów, próbujesz przetestować niezmienność.
• Wybrałeś algorytm, w którym operacja w miejscu jest niezwykle skuteczna (i można to udowodnić). Jeśli chcesz pokazać, że istnieją algorytmy, które są szybsze, gdy są implementowane mutacyjnie, to jest to dobry wybór; w przeciwnym razie może to być mylące.
• Używasz złej funkcji synchronizacji. Posługiwać sięSystem.nanoTime .
• Benchmark jest zbyt krótki, abyś mógł mieć pewność, że kompilacja JIT nie będzie znaczącą częścią mierzonego czasu.
• Tablica nie jest podzielona w efektywny sposób.
• Tablice są zmienne, więc używanie ich z FP i tak jest dziwnym porównaniem.

To porównanie jest więc świetną ilustracją, że musisz szczegółowo zrozumieć swój język (i algorytm), aby napisać kod o wysokiej wydajności. Ale to nie jest dobre porównanie FP vs non-FP. Jeśli chcesz, sprawdź Haskell vs. C ++ w Computer Languages ​​Benchmark Game . Wiadomo, że kara zwykle nie przekracza współczynnika 2 lub 3, ale tak naprawdę to zależy. (Żadnych obietnic, że ludzie z Haskellów napisali również najszybsze możliwe algorytmy, ale przynajmniej niektórzy z nich prawdopodobnie próbowali! Z drugiej strony, niektóre z Haskellów wywołują biblioteki C ...)

Teraz załóżmy, że potrzebujesz bardziej rozsądnego testu porównawczego Quicksort, uznając, że jest to prawdopodobnie jeden z najgorszych przypadków w porównaniu z algorytmami FP w porównaniu z algorytmami zmiennymi, i ignorując problem struktury danych (tj. Udając, że możemy mieć niezmienną tablicę):

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
  }
}

Zwróć uwagę na modyfikację funkcjonalnego Quicksort, aby przeszukiwał dane tylko raz, jeśli to w ogóle możliwe, i porównanie z wbudowanym sortowaniem. Po uruchomieniu otrzymujemy coś takiego:

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

Tak więc, oprócz tego, że dowiedzieliśmy się, że próba napisania własnego sortowania jest złym pomysłem, okazuje się, że za niezmienne szybkie sortowanie grozi ~ 3-krotna kara, jeśli ta ostatnia zostanie wdrożona dość ostrożnie. (Możesz również napisać metodę trójdzielną, która zwraca trzy tablice: mniejsze niż, równe i większe niż oś obrotu. Może to nieco przyspieszyć działanie).

Nie sądzę, aby wersja Scala była w rzeczywistości rekurencyjna, ponieważ używasz Array.concat.

Również dlatego, że jest to idiomatyczny kod Scala, nie oznacza to, że jest to najlepszy sposób na zrobienie tego.

Najlepszym sposobem na to byłoby użycie jednej z wbudowanych funkcji sortowania Scali. W ten sposób zyskujesz gwarancję niezmienności i wiesz, że masz szybki algorytm.

Zobacz pytanie o przepełnienie stosu Jak posortować tablicę w Scali? dla przykładu.

Niezmienność nie jest droga. Z pewnością może to być kosztowne, jeśli zmierzysz niewielki podzbiór zadań, które program musi wykonać, i wybierzesz rozwiązanie oparte na zmienności podczas rozruchu - na przykład pomiar quicksort.

Mówiąc prościej, nie posortujesz szybko, gdy używasz czysto funkcjonalnych języków.

Rozważmy to z innej perspektywy. Rozważmy te dwie funkcje:

// 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)
}

Sprawdźcie to, a przekonacie się, że kod wykorzystujący zmienne struktury danych ma znacznie gorszą wydajność, ponieważ musi skopiować tablicę, podczas gdy niezmienny kod nie musi się tym zajmować.

Kiedy programujesz z niezmiennymi strukturami danych, tworzysz strukturę kodu, aby wykorzystać jego mocne strony. Nie chodzi tylko o typ danych ani nawet o poszczególne algorytmy. Program zostanie zaprojektowany w inny sposób.

Dlatego benchmarking jest zwykle bez znaczenia. Albo wybierzesz algorytmy, które są naturalne dla tego czy innego stylu i ten styl wygrywa, albo porównujesz całą aplikację, co często jest niepraktyczne.

Sortowanie tablicy jest najważniejszym zadaniem we wszechświecie. Nie jest zaskakujące, że wiele eleganckich „niezmiennych” strategii / implementacji kończy się niepowodzeniem w przypadku mikroznaku „sortowania tablicy”. Nie oznacza to jednak, że niezmienność jest kosztowna „w ogóle”. Istnieje wiele zadań, w których niezmienne implementacje będą działać podobnie jak modyfikowalne, ale sortowanie tablic często nie jest jednym z nich.

Jeśli po prostu przepisujesz swoje imperatywne algorytmy i struktury danych na język funkcjonalny, będzie to rzeczywiście kosztowne i bezużyteczne. Aby rzeczy świeciły, powinieneś używać funkcji dostępnych tylko w programowaniu funkcjonalnym: trwałość struktur danych, leniwe oceny itp.

Koszt niezmienności w Scali

Oto wersja, która jest prawie tak szybka, jak wersja 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
  }
}

Ta wersja tworzy kopię tablicy, sortuje ją na miejscu przy użyciu wersji Java i zwraca kopię. Scala nie zmusza cię do wewnętrznego używania niezmiennej struktury.

Więc zaletą Scali jest to, że możesz wykorzystać zmienność i niezmienność według własnego uznania. Wadą jest to, że jeśli zrobisz to źle, tak naprawdę nie odniesiesz korzyści z niezmienności.

Wiadomo, że QuickSort działa szybciej, gdy jest wykonywany na miejscu, więc nie jest to uczciwe porównanie!

Powiedziawszy to ... Array.concat? Jeśli nic więcej, pokazujesz, jak typ kolekcji zoptymalizowany pod kątem programowania imperatywnego jest szczególnie powolny, gdy próbujesz go użyć w algorytmie funkcjonalnym; prawie każdy inny wybór byłby szybszy!

Innym bardzo ważnym punktem do rozważenia, może najważniejszą kwestią przy porównywaniu tych dwóch podejść jest: „Jak dobrze czyni tę skalę się w wielu węzłach / rdzeni”

Są szanse, że jeśli szukasz niezmiennego szybkiego sortowania, robisz to, ponieważ w rzeczywistości chcesz równoległego szybkiego sortowania. Wikipedia ma kilka cytatów na ten temat: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

Wersja scala może po prostu rozwidlić przed ponownym wykonaniem funkcji, co pozwala bardzo szybko posortować listę zawierającą miliardy wpisów, jeśli masz wystarczającą liczbę dostępnych rdzeni.

W tej chwili GPU w moim systemie ma dostępne 128 rdzeni, gdybym tylko mógł uruchomić na nim kod Scala, a to jest na prostym komputerze stacjonarnym dwa lata za obecną generacją.

Zastanawiam się, jak to się ma do podejścia imperatywnego jednowątkowego ...

Być może zatem ważniejsze pytanie brzmi:

„Biorąc pod uwagę, że poszczególne rdzenie nie będą działać szybciej, a synchronizacja / blokowanie stanowi prawdziwe wyzwanie dla równoległości, czy zmienność jest kosztowna?”

Mówi się, że programowanie obiektowe używa abstrakcji, aby ukryć złożoność, a programowanie funkcjonalne wykorzystuje niezmienność, aby usunąć złożoność. W hybrydowym świecie Scali możemy użyć OO, aby ukryć kod imperatywny, nie pozostawiając kodu aplikacji mądrzejszego. Rzeczywiście, biblioteki kolekcji używają wielu imperatywnych kodów, ale to nie znaczy, że nie powinniśmy ich używać. Jak powiedzieli inni, ostrożnie używany, naprawdę dostajesz to, co najlepsze z obu światów.