Bagaimana cara mengoptimalkan untuk-pemahaman dan loop di Scala?

Jadi Scala seharusnya secepat Java. Saya meninjau kembali beberapa masalah Project Euler di Scala yang awalnya saya tangani di Jawa. Khususnya Masalah 5: "Berapakah angka positif terkecil yang secara merata dapat dibagi oleh semua angka dari 1 hingga 20?"

Inilah solusi Java saya, yang membutuhkan 0,7 detik untuk selesai di mesin saya:

public class P005_evenly_divisible implements Runnable{
    final int t = 20;

    public void run() {
        int i = 10;
        while(!isEvenlyDivisible(i, t)){
            i += 2;
        }
        System.out.println(i);
    }

    boolean isEvenlyDivisible(int a, int b){
        for (int i = 2; i <= b; i++) {
            if (a % i != 0) 
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        new P005_evenly_divisible().run();
    }
}

Inilah "terjemahan langsung" saya ke Scala, yang membutuhkan waktu 103 detik (147 kali lebih lama!)

object P005_JavaStyle {
    val t:Int = 20;
    def run {
        var i = 10
        while(!isEvenlyDivisible(i,t))
            i += 2
        println(i)
    }
    def isEvenlyDivisible(a:Int, b:Int):Boolean = {
        for (i <- 2 to b)
            if (a % i != 0)
                return false
        return true
    }
    def main(args : Array[String]) {
        run
    }
}

Akhirnya, inilah upaya saya untuk pemrograman fungsional, yang membutuhkan waktu 39 detik (55 kali lebih lama)

object P005 extends App{
    def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
    def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
    println (find (2))
}

Menggunakan Scala 2.9.0.1 pada Windows 7 64-bit. Bagaimana cara saya meningkatkan kinerja? Apakah saya melakukan sesuatu yang salah? Atau Java jauh lebih cepat?

Masalah dalam kasus khusus ini adalah Anda kembali dari dalam untuk-ekspresi. Itu pada gilirannya akan diterjemahkan menjadi lemparan NonLocalReturnException, yang ditangkap pada metode melampirkan. Pengoptimal dapat menghilangkan foreach tetapi belum bisa menghilangkan lemparan / tangkapan. Dan melempar / menangkap itu mahal. Tetapi karena pengembalian bersarang seperti itu jarang terjadi dalam program Scala, pengoptimal belum menangani kasus ini. Ada pekerjaan yang sedang dilakukan untuk meningkatkan pengoptimal yang diharapkan akan menyelesaikan masalah ini segera.

Masalahnya kemungkinan besar adalah penggunaan forpemahaman dalam metode ini isEvenlyDivisible. Mengganti fordengan whileloop setara harus menghilangkan perbedaan kinerja dengan Java.

Berbeda dengan forloop Jawa , forpemahaman Scala sebenarnya adalah gula sintaksis untuk metode tingkat tinggi; dalam hal ini, Anda memanggil foreachmetode pada Rangeobjek. Scalafor sangat umum, tetapi terkadang menyebabkan kinerja yang menyakitkan.

Anda mungkin ingin mencoba -optimize bendera di Scala versi 2.9. Kinerja yang diamati mungkin tergantung pada JVM tertentu yang digunakan, dan pengoptimal JIT memiliki waktu "pemanasan" yang cukup untuk mengidentifikasi dan mengoptimalkan hot-spot.

Diskusi baru-baru ini di milis menunjukkan bahwa tim Scala sedang berupaya meningkatkan forkinerja dalam kasus-kasus sederhana:

• http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
• http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

Berikut adalah masalah dalam pelacak bug: https://issues.scala-lang.org/browse/SI-4633

Pembaruan 5/28 :

• Sebagai solusi jangka pendek, plugin ScalaCL (alpha) akan mengubah loop Scala sederhana menjadi setara dengan whileloop.
• Sebagai solusi jangka panjang yang potensial, tim dari EPFL dan Stanford berkolaborasi pada proyek yang memungkinkan kompilasi run-time dari "virtual" Scala untuk kinerja yang sangat tinggi. Misalnya, beberapa loop fungsional idiomatik dapat menyatu pada saat run-time menjadi bytecode JVM yang optimal, atau ke target lain seperti GPU. Sistem ini dapat dikembangkan, memungkinkan DSL dan transformasi yang ditentukan pengguna. Lihat publikasi dan catatan kursus Stanford . Kode awal tersedia di Github, dengan rilis yang dimaksudkan dalam beberapa bulan mendatang.

Sebagai tindak lanjut, saya mencoba flag -optimize dan mengurangi waktu berjalan dari 103 menjadi 76 detik, tapi itu masih 107x lebih lambat dari Java atau loop sementara.

Kemudian saya melihat versi "fungsional":

object P005 extends App{
  def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

dan mencoba mencari cara untuk menyingkirkan "forall" secara ringkas. Saya gagal total dan muncul

object P005_V2 extends App {
  def isDivis(x:Int):Boolean = {
    var i = 1
    while(i <= 20) {
      if (x % i != 0) return false
      i += 1
    }
    return true
  }
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

dimana solusi 5-line saya yang licik telah menggelembung menjadi 12 baris. Namun, versi ini berjalan dalam 0,71 detik , kecepatan yang sama dengan versi Java asli, dan 56 kali lebih cepat dari versi di atas menggunakan "forall" (40,2 dtk)! (lihat EDIT di bawah untuk alasan mengapa ini lebih cepat dari Java)

Jelas langkah saya selanjutnya adalah menerjemahkan kembali di atas ke Jawa, tetapi Jawa tidak bisa mengatasinya dan melempar StackOverflowError dengan n sekitar tanda 22000.

Saya kemudian menggaruk kepala saya sebentar dan mengganti "sementara" dengan rekursi ekor yang lebih sedikit, yang menghemat beberapa baris, berjalan sama cepatnya, tetapi mari kita hadapi itu, lebih membingungkan untuk dibaca:

object P005_V3 extends App {
  def isDivis(x:Int, i:Int):Boolean = 
    if(i > 20) true
    else if(x % i != 0) false
    else isDivis(x, i+1)

  def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2)
  println (find (2))
}

Jadi rekursi ekor Scala menang, tetapi saya terkejut bahwa sesuatu yang sederhana seperti loop "for" (dan metode "forall") pada dasarnya rusak dan harus diganti dengan "whiles" yang tidak tepat dan verbose, atau rekursi ekor . Banyak alasan saya mencoba Scala adalah karena sintaksis yang ringkas, tetapi tidak baik jika kode saya akan berjalan 100 kali lebih lambat!

EDIT : (dihapus)

EDIT OF EDIT : Perbedaan sebelumnya antara waktu operasi 2.5s dan 0.7s sepenuhnya karena apakah JVM 32-bit atau 64-bit digunakan. Scala dari baris perintah menggunakan apa pun yang diatur oleh JAVA_HOME, sementara Java menggunakan 64-bit jika tersedia terlepas. IDE memiliki pengaturannya sendiri. Beberapa pengukuran di sini: Waktu eksekusi scala di Eclipse

Jawaban untuk pemahaman adalah benar, tetapi itu bukan keseluruhan cerita. Anda harus mencatat bahwa penggunaan returnin isEvenlyDivisibletidak gratis. Penggunaan kembali di dalam for, memaksa kompiler scala untuk menghasilkan pengembalian non-lokal (yaitu untuk kembali di luar fungsinya).

Ini dilakukan melalui penggunaan pengecualian untuk keluar dari loop. Hal yang sama terjadi jika Anda membangun abstraksi kontrol Anda sendiri, misalnya:

def loop[T](times: Int, default: T)(body: ()=>T) : T = {
    var count = 0
    var result: T = default
    while(count < times) {
        result = body()
        count += 1
    }
    result
}

def foo() : Int= {
    loop(5, 0) {
        println("Hi")
        return 5
    }
}

foo()

Ini mencetak "Hai" hanya sekali.

Perhatikan bahwa returndi fookeluar foo(yang adalah apa yang Anda harapkan). Karena ekspresi kurung adalah fungsi literal, yang dapat Anda lihat di tanda tangan loopini memaksa kompiler untuk menghasilkan pengembalian non lokal, yaitu returnkekuatan yang Anda keluar foo, bukan hanya itu body.

Di Jawa (yaitu JVM) satu-satunya cara untuk menerapkan perilaku tersebut adalah dengan melemparkan pengecualian.

Kembali ke isEvenlyDivisible:

def isEvenlyDivisible(a:Int, b:Int):Boolean = {
  for (i <- 2 to b) 
    if (a % i != 0) return false
  return true
}

Itu if (a % i != 0) return false adalah fungsi literal yang memiliki pengembalian, sehingga setiap kali pengembalian dipukul, runtime harus melempar dan menangkap pengecualian, yang menyebabkan overhead GC yang cukup besar.

Beberapa cara untuk mempercepat forall metode yang saya temukan:

Asli: 41,3 dtk

def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}

Pra-instantiating rentang, jadi kami tidak membuat rentang baru setiap kali: 9.0 dtk

val r = (1 to 20)
def isDivis(x:Int) = r forall {x % _ == 0}

Mengonversi ke Daftar alih-alih Rentang: 4,8 dtk

val rl = (1 to 20).toList
def isDivis(x:Int) = rl forall {x % _ == 0}

Saya mencoba beberapa koleksi lain tetapi Daftar paling cepat (walaupun masih 7x lebih lambat daripada jika kita menghindari Range dan fungsi tingkat tinggi sama sekali).

Walaupun saya baru di Scala, saya kira kompiler dapat dengan mudah mengimplementasikan perolehan kinerja yang cepat dan signifikan dengan hanya secara otomatis mengganti Range literals dalam metode (seperti di atas) dengan konstanta Range dalam cakupan terluar. Atau lebih baik, magang seperti Strings literals in Java.

catatan kaki : Array hampir sama dengan Range, tetapi yang menarik, mucikari forallmetode baru (ditampilkan di bawah) menghasilkan eksekusi 24% lebih cepat pada 64-bit, dan 8% lebih cepat pada 32-bit. Ketika saya mengurangi ukuran perhitungan dengan mengurangi jumlah faktor dari 20 menjadi 15 perbedaannya menghilang, jadi mungkin itu adalah efek pengumpulan sampah. Apa pun penyebabnya, ini penting saat beroperasi di bawah beban penuh untuk waktu yang lama.

Seorang mucikari serupa untuk Daftar juga menghasilkan kinerja sekitar 10% lebih baik.

  val ra = (1 to 20).toArray
  def isDivis(x:Int) = ra forall2 {x % _ == 0}

  case class PimpedSeq[A](s: IndexedSeq[A]) {
    def forall2 (p: A => Boolean): Boolean = {      
      var i = 0
      while (i < s.length) {
        if (!p(s(i))) return false
        i += 1
      }
      true
    }    
  }  
  implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in)  

Saya hanya ingin berkomentar untuk orang-orang yang mungkin tidak percaya pada Scala tentang masalah-masalah seperti ini bahwa masalah-masalah seperti ini muncul dalam kinerja hampir semua bahasa fungsional. Jika Anda mengoptimalkan lipatan di Haskell, Anda harus sering menulis ulang sebagai pengulangan yang dioptimalkan ekor-panggilan rekursif, atau Anda akan memiliki masalah kinerja dan memori untuk bersaing.

Saya tahu sangat disayangkan bahwa FP belum dioptimalkan ke titik di mana kita tidak perlu memikirkan hal-hal seperti ini, tetapi ini sama sekali bukan masalah khusus untuk Scala.

Masalah khusus untuk Scala telah dibahas, tetapi masalah utamanya adalah menggunakan algoritma brute-force tidak terlalu keren. Pertimbangkan ini (jauh lebih cepat daripada kode Java asli):

def gcd(a: Int, b: Int): Int = {
    if (a == 0)
        b
    else
        gcd(b % a, a)
}
print (1 to 20 reduce ((a, b) => {
  a / gcd(a, b) * b
}))

Coba satu-liner yang diberikan dalam solusi Scala untuk Project Euler

Waktu yang diberikan setidaknya lebih cepat dari milikmu, meskipun jauh dari loop sementara .. :)