Pemrograman fungsional - apakah keabadian mahal? [Tutup]

Pertanyaannya ada dalam dua bagian. Yang pertama adalah konseptual. Berikutnya melihat pertanyaan yang sama secara lebih konkrit di Scala.

1. Apakah hanya menggunakan struktur data yang tidak dapat diubah dalam bahasa pemrograman membuat penerapan algoritme / logika tertentu secara inheren lebih mahal secara komputasi dalam praktiknya? Ini menarik fakta bahwa keabadian adalah prinsip inti dari bahasa fungsional murni. Apakah ada faktor lain yang mempengaruhi hal ini?
2. Mari kita ambil contoh yang lebih konkret. Quicksort umumnya diajarkan dan diimplementasikan menggunakan operasi yang dapat berubah pada struktur data dalam memori. Bagaimana seseorang mengimplementasikan hal seperti itu dengan cara fungsional PURE dengan overhead komputasi dan penyimpanan yang sebanding dengan versi yang bisa berubah. Khususnya di Scala. Saya telah menyertakan beberapa tolok ukur kasar di bawah ini.

Keterangan lebih lanjut:

Saya berasal dari latar belakang pemrograman imperatif (C ++, Java). Saya telah menjelajahi pemrograman fungsional, khususnya Scala.

Beberapa prinsip utama pemrograman fungsional murni:

1. Fungsi adalah warga negara kelas satu.
2. Fungsi tidak memiliki efek samping dan karenanya objek / struktur data tidak dapat diubah .

Meskipun JVM modern sangat efisien dengan pembuatan objek dan pengumpulan sampah sangat murah untuk objek berumur pendek, mungkin lebih baik meminimalkan pembuatan objek, bukan? Setidaknya dalam aplikasi single-threaded di mana konkurensi dan penguncian tidak menjadi masalah. Karena Scala adalah paradigma hybrid, seseorang dapat memilih untuk menulis kode imperatif dengan objek yang bisa berubah jika perlu. Tapi, sebagai seseorang yang telah menghabiskan banyak waktu mencoba menggunakan kembali objek dan meminimalkan alokasi. Saya ingin pemahaman yang baik tentang aliran pemikiran yang bahkan tidak mengizinkan hal itu.

Sebagai kasus khusus, saya sedikit terkejut dengan potongan kode ini dalam tutorial 6 ini . Ini memiliki Quicksort versi Java yang diikuti dengan implementasi Scala yang tampak rapi.

Berikut adalah upaya saya untuk mengukur implementasi. Saya belum melakukan profil mendetail. Tapi, tebakan saya adalah bahwa versi Scala lebih lambat karena jumlah objek yang dialokasikan adalah linier (satu per panggilan rekursi). Adakah kemungkinan bahwa pengoptimalan panggilan ekor bisa ikut bermain? Jika saya benar, Scala mendukung pengoptimalan panggilan ekor untuk panggilan rekursif sendiri. Jadi, seharusnya hanya membantu saja. Saya menggunakan Scala 2.8.

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

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

Kode Scala untuk membandingkan implementasi

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

Hasil

Waktu dalam milidetik untuk lima kali berturut-turut

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

Karena ada beberapa kesalahpahaman terbang di sekitar sini, saya ingin mengklarifikasi beberapa poin.

• Quicksort "di tempat" tidak benar-benar di tempatnya (dan quicksort tidak dengan definisi di tempat). Diperlukan penyimpanan tambahan berupa ruang stack untuk langkah rekursif, yaitu dengan urutan O (log n ) pada kasus terbaik, tetapi O ( n ) pada kasus terburuk.

• Menerapkan varian fungsional quicksort yang beroperasi pada array akan mengalahkan tujuan tersebut. Array tidak pernah berubah.

• Implementasi fungsional quicksort yang "tepat" menggunakan daftar yang tidak dapat diubah. Ini tentu saja tidak di tempatnya tetapi memiliki runtime asimtotik kasus terburuk yang sama ( O ( n ^ 2)) dan kompleksitas ruang ( O ( n )) sebagai versi di tempat prosedural.

  Rata-rata, waktu berjalannya masih setara dengan varian di tempat ( O ( n log n )). Kompleksitas ruangnya, bagaimanapun, masih O ( n ).

Ada dua kelemahan yang jelas dari implementasi quicksort fungsional. Berikut ini, mari pertimbangkan implementasi referensi ini di Haskell (Saya tidak tahu Scala…) dari pengantar Haskell :

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

1. Kerugian pertama adalah pilihan elemen pivot , yang sangat tidak fleksibel. Kekuatan implementasi quicksort modern sangat bergantung pada pilihan cerdas dari poros (bandingkan "Rekayasa fungsi pengurutan" oleh Bentley et al. ). Algoritme di atas buruk dalam hal itu, yang sangat menurunkan kinerja rata-rata.

2. Kedua, algoritma ini menggunakan penggabungan daftar (sebagai pengganti konstruksi daftar) yang merupakan operasi O ( n ). Ini tidak berdampak pada kompleksitas asimtotik tetapi merupakan faktor yang dapat diukur.

Kerugian ketiga agak tersembunyi: tidak seperti varian "di tempat", penerapan ini terus-menerus meminta memori dari heap untuk sel kontra dari daftar dan berpotensi menyebarkan memori di semua tempat. Akibatnya, algoritme ini memiliki lokasi cache yang sangat buruk . Saya tidak tahu apakah pengalokasi pintar dalam bahasa pemrograman fungsional modern dapat mengurangi hal ini - tetapi pada mesin modern, cache miss telah menjadi pembunuh kinerja utama.

Apa kesimpulannya? Tidak seperti yang lain, saya tidak akan mengatakan bahwa quicksort pada dasarnya penting dan itulah mengapa kinerjanya buruk di lingkungan FP. Justru sebaliknya, saya berpendapat bahwa quicksort adalah contoh sempurna dari algoritme fungsional: ini diterjemahkan dengan mulus ke dalam lingkungan yang tidak dapat diubah, kompleksitas ruang dan waktu berjalan asimtotiknya setara dengan implementasi prosedural, dan bahkan implementasi proseduralnya menggunakan rekursi.

Tapi algoritma ini masih bekerja lebih buruk jika dibatasi pada domain yang tidak dapat diubah. Alasannya adalah karena algoritme memiliki sifat khas yang memanfaatkan banyak penyetelan (terkadang tingkat rendah) yang hanya dapat dilakukan secara efisien pada larik. Deskripsi quicksort yang naif merindukan semua kerumitan ini (baik dalam varian fungsional maupun prosedural).

Setelah membaca "Rekayasa fungsi pengurutan", saya tidak lagi menganggap quicksort sebagai algoritme yang elegan. Diimplementasikan secara efisien, ini adalah kekacauan yang kikuk, karya insinyur, bukan karya seniman (bukan untuk merendahkan teknik! Ini memiliki estetika tersendiri).

Tetapi saya juga ingin menunjukkan bahwa poin ini khusus untuk quicksort. Tidak semua algoritme dapat menerima jenis penyesuaian tingkat rendah yang sama. Benar-benar banyak algoritme dan struktur data - dapat diekspresikan tanpa kehilangan kinerja dalam lingkungan yang tidak dapat diubah.

Dan kekekalan bahkan bisa menurun biaya kinerja dengan menghilangkan kebutuhan salinan yang mahal atau sinkronisasi lintas utas.

Jadi, untuk menjawab pertanyaan awal, “ apakah keabadian mahal? ”- Dalam kasus quicksort tertentu, ada biaya yang memang merupakan akibat dari kekekalan. Tapi secara umum tidak .

Ada banyak hal yang salah dengan ini sebagai tolok ukur pemrograman fungsional. Sorotan meliputi:

• Anda menggunakan primitif, yang mungkin harus dikotak / dibuka. Anda tidak mencoba menguji overhead membungkus objek primitif, Anda mencoba menguji kekekalan.
• Anda telah memilih algoritme di mana operasi di tempat sangat efektif (dan terbukti begitu). Jika Anda ingin menunjukkan bahwa ada algoritme yang lebih cepat ketika diterapkan secara bergiliran, maka ini adalah pilihan yang baik; jika tidak, hal ini mungkin menyesatkan.
• Anda menggunakan fungsi pengaturan waktu yang salah. Gunakan System.nanoTime.
• Tolok ukurnya terlalu pendek bagi Anda untuk yakin bahwa kompilasi JIT tidak akan menjadi bagian penting dari waktu yang diukur.
• Array tidak dibagi secara efisien.
• Array bisa berubah, jadi menggunakannya dengan FP adalah perbandingan yang aneh.

Jadi, perbandingan ini adalah ilustrasi yang bagus bahwa Anda harus memahami bahasa (dan algoritme) Anda secara detail untuk menulis kode berkinerja tinggi. Tapi ini bukan perbandingan yang sangat baik antara FP vs. non-FP. Jika Anda menginginkannya, lihat Haskell vs. C ++ di Game Benchmark Bahasa Komputer . Pesan yang dibawa pulang adalah bahwa hukuman biasanya tidak lebih dari faktor 2 atau 3 atau lebih, tetapi itu sangat tergantung. (Tidak ada janji bahwa orang-orang Haskell telah menulis algoritme tercepat, tetapi setidaknya beberapa dari mereka mungkin mencoba! Kemudian lagi, beberapa Haskell memanggil pustaka C.)

Sekarang, misalkan Anda memang menginginkan tolok ukur Quicksort yang lebih masuk akal, menyadari bahwa ini mungkin salah satu kasus terburuk untuk algoritme FP vs. yang dapat berubah, dan mengabaikan masalah struktur data (yaitu, berpura-pura bahwa kita dapat memiliki Array yang tidak dapat diubah):

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

Perhatikan modifikasi pada Quicksort fungsional sehingga hanya melewati data sekali jika memungkinkan, dan perbandingan dengan jenis bawaan. Ketika kami menjalankannya, kami mendapatkan sesuatu seperti:

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

Jadi, selain belajar bahwa mencoba menulis urutan Anda sendiri adalah ide yang buruk, kami menemukan bahwa ada hukuman ~ 3x untuk quicksort yang tidak dapat diubah jika yang terakhir diterapkan dengan hati-hati. (Anda juga bisa menulis metode trisect yang mengembalikan tiga larik: yang kurang dari, yang sama, dan yang lebih besar dari pivot. Ini mungkin mempercepat sedikit lebih.)

Saya tidak berpikir versi Scala sebenarnya adalah rekursif ekor, karena Anda menggunakan Array.concat.

Selain itu, hanya karena ini adalah kode Scala idiomatik, bukan berarti ini adalah cara terbaik untuk melakukannya.

Cara terbaik untuk melakukannya adalah dengan menggunakan salah satu fungsi penyortiran bawaan Scala. Dengan cara itu Anda mendapatkan jaminan keabadian dan tahu bahwa Anda memiliki algoritme yang cepat.

Lihat pertanyaan Stack Overflow Bagaimana cara mengurutkan array di Scala? sebagai contoh.

Kekekalan tidak mahal. Tentu bisa mahal jika Anda mengukur sebagian kecil tugas yang harus dilakukan program, dan memilih solusi berdasarkan mutabilitas untuk boot - seperti mengukur quicksort.

Sederhananya, Anda tidak melakukan quicksort saat menggunakan bahasa yang murni berfungsi.

Mari pertimbangkan ini dari sudut lain. Mari pertimbangkan dua fungsi ini:

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

Benchmark BAHWA, dan Anda akan menemukan bahwa kode yang menggunakan struktur data yang dapat diubah memiliki kinerja yang jauh lebih buruk, karena ia perlu menyalin larik, sedangkan kode yang tidak dapat diubah tidak perlu memikirkannya.

Saat Anda memprogram dengan struktur data yang tidak dapat diubah, Anda menyusun kode Anda untuk memanfaatkan kekuatannya. Ini bukan hanya tipe data, atau bahkan algoritme individual. Program akan dirancang dengan cara yang berbeda.

Itulah mengapa pembandingan biasanya tidak ada artinya. Entah Anda memilih algoritme yang alami untuk satu gaya atau lainnya, dan gaya itu menang, atau Anda membandingkan keseluruhan aplikasi, yang seringkali tidak praktis.

Mengurutkan array adalah, seperti, tugas paling penting di alam semesta. Tidaklah mengherankan bahwa banyak strategi / implementasi yang 'tidak dapat diubah' gagal dengan buruk pada microbenchmark 'sort an array'. Ini tidak berarti bahwa kekekalan itu mahal "secara umum". Ada banyak tugas di mana implementasi yang tidak dapat diubah akan bekerja sama dengan yang dapat diubah, tetapi penyortiran array sering kali bukan salah satunya.

Jika Anda hanya menulis ulang algoritme imperatif dan struktur data ke dalam bahasa fungsional, itu memang akan mahal dan tidak berguna. Untuk membuat semuanya bersinar, Anda harus menggunakan fitur yang hanya tersedia dalam pemrograman fungsional: persistensi struktur data, evaluasi malas, dll.

Biaya kekekalan dalam Scala

Ini adalah versi yang hampir secepat versi 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
  }
}

Versi ini membuat salinan dari array, mengurutkannya menggunakan versi Java dan mengembalikan salinannya. Scala tidak memaksa Anda untuk menggunakan struktur yang tidak dapat diubah secara internal.

Jadi, manfaat Scala adalah Anda dapat memanfaatkan mutabilitas dan kekekalan sesuai keinginan Anda. Kerugiannya adalah jika Anda melakukan kesalahan itu, Anda tidak benar-benar mendapatkan manfaat dari kekekalan.

QuickSort dikenal lebih cepat jika dilakukan di tempat, jadi ini bukan perbandingan yang adil!

Karena itu ... Array.concat? Jika tidak ada yang lain, Anda menunjukkan bagaimana jenis kumpulan yang dioptimalkan untuk pemrograman imperatif sangat lambat saat Anda mencoba dan menggunakannya dalam algoritme fungsional; hampir semua pilihan lain akan lebih cepat!

Hal lain yang sangat penting untuk dipertimbangkan, mungkin masalah yang paling penting ketika membandingkan dua pendekatan adalah: "seberapa baik skala ini keluar ke beberapa node / inti?"

Kemungkinannya adalah, jika Anda mencari quicksort yang tidak dapat diubah maka Anda melakukannya karena sebenarnya Anda menginginkan quicksort paralel. Wikipedia memiliki beberapa kutipan tentang subjek ini: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

Versi scala dapat dengan mudah bercabang sebelum fungsi berulang, memungkinkannya dengan sangat cepat mengurutkan daftar yang berisi miliaran entri jika Anda memiliki cukup inti.

Saat ini, GPU di sistem saya memiliki 128 core yang tersedia untuk saya jika saya bisa menjalankan kode Scala di atasnya, dan ini ada di sistem desktop sederhana dua tahun di belakang generasi saat ini.

Bagaimana itu bisa bertentangan dengan pendekatan imperatif utas tunggal, saya bertanya-tanya ...

Mungkin pertanyaan yang lebih penting adalah:

"Mengingat bahwa inti individu tidak akan menjadi lebih cepat, dan sinkronisasi / penguncian menghadirkan tantangan nyata untuk paralelisasi, apakah mutabilitas mahal?"

Dikatakan bahwa pemrograman OO menggunakan abstraksi untuk menyembunyikan kompleksitas, dan pemrograman fungsional menggunakan kekekalan untuk menghilangkan kompleksitas. Dalam dunia hybrid Scala, kita dapat menggunakan OO untuk menyembunyikan kode imperatif sehingga tidak ada kode aplikasi yang lebih bijak. Memang perpustakaan koleksi menggunakan banyak kode imperatif tetapi itu tidak berarti kita tidak boleh menggunakannya. Seperti yang dikatakan orang lain, jika digunakan dengan hati-hati, Anda benar-benar mendapatkan yang terbaik dari kedua dunia di sini.