Jak zoptymalizować pod kątem zrozumień i pętli w Scali?

Więc Scala ma być tak szybka jak Java. Wracam do niektórych problemów Projektu Euler w Scali, którymi pierwotnie zajmowałem się w Javie. W szczególności Problem 5: „Jaka jest najmniejsza liczba dodatnia, która jest równo podzielna przez wszystkie liczby od 1 do 20?”

Oto moje rozwiązanie Java, które zajmuje 0,7 sekundy na moim komputerze:

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();
    }
}

Oto moje „bezpośrednie tłumaczenie” na Scala, które trwa 103 sekundy (147 razy dłużej!)

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

Na koniec moja próba programowania funkcjonalnego, która trwa 39 sekund (55 razy dłużej)

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

Korzystanie ze Scala 2.9.0.1 w systemie Windows 7 64-bitowym. Jak poprawić wydajność? czy robię coś źle? A może Java jest po prostu dużo szybsza?

Problem w tym konkretnym przypadku polega na tym, że powracasz z wewnątrz wyrażenia for. To z kolei jest tłumaczone na rzut NonLocalReturnException, który jest przechwytywany w otaczającej metodzie. Optymalizator może wyeliminować wszystkich, ale nie może jeszcze wyeliminować rzutu / złapania. A rzucanie / łapanie jest drogie. Ponieważ jednak takie zagnieżdżone zwroty są rzadkie w programach Scala, optymalizator nie zajął się jeszcze tym przypadkiem. Trwają prace nad ulepszeniem optymalizatora, który, miejmy nadzieję, wkrótce rozwiąże ten problem.

Problem polega najprawdopodobniej na zastosowaniu forzrozumienia w metodzie isEvenlyDivisible. Zastąpienie forrównoważną whilepętlą powinno wyeliminować różnicę w wydajności w przypadku języka Java.

W przeciwieństwie do forpętli Javy, wyrażenia Scali forsą w rzeczywistości cukrem syntaktycznym dla metod wyższego rzędu; w tym przypadku wywołujesz foreachmetodę na Rangeobiekcie. Scala forjest bardzo ogólna, ale czasami prowadzi do bolesnych wyników.

Możesz spróbować -optimizeflagi w Scali w wersji 2.9. Zaobserwowana wydajność może zależeć od używanej maszyny JVM oraz od optymalizatora JIT, który ma wystarczający czas „rozgrzewania”, aby zidentyfikować i zoptymalizować punkty aktywne.

Ostatnie dyskusje na liście mailingowej wskazują, że zespół Scala pracuje nad poprawą forwydajności w prostych przypadkach:

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

Oto problem w narzędziu do śledzenia błędów: https://issues.scala-lang.org/browse/SI-4633

Aktualizacja 28.05 . :

• Jako rozwiązanie krótkoterminowe, wtyczka ScalaCL (alfa) przekształci proste pętle Scala w odpowiedniki whilepętli.
• Jako potencjalne rozwiązanie długoterminowe, zespoły z EPFL i Stanford współpracują nad projektem umożliwiającym kompilację w czasie wykonywania „wirtualnej” Scali o bardzo wysokiej wydajności. Na przykład wiele idiomatycznych pętli funkcjonalnych może zostać połączonych w czasie wykonywania w optymalny kod bajtowy maszyny JVM lub z innym celem, takim jak GPU. System jest rozszerzalny, umożliwiając definiowane przez użytkownika DSL i transformacje. Sprawdź publikacje i notatki z kursów Stanford . Wstępny kod jest dostępny na Github, a jego wydanie planowane jest w najbliższych miesiącach.

W ramach kontynuacji wypróbowałem flagę -optimize, która skróciła czas działania z 103 do 76 sekund, ale jest to nadal 107 razy wolniejsze niż Java lub pętla while.

Potem patrzyłem na wersję „funkcjonalną”:

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

i próbując dowiedzieć się, jak w zwięzły sposób pozbyć się „forall”. Zawiodłem żałośnie i wpadłem na pomysł

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

dzięki czemu moje sprytne 5-liniowe rozwiązanie rozrosło się do 12 linii. Jednak ta wersja działa w 0,71 sekundy , z taką samą szybkością jak oryginalna wersja Java i 56 razy szybciej niż wersja powyżej przy użyciu funkcji „forall” (40,2 s)! (zobacz EDYCJA poniżej, aby dowiedzieć się, dlaczego jest to szybsze niż Java)

Oczywiście moim następnym krokiem było przetłumaczenie powyższego z powrotem na Javę, ale Java nie może tego obsłużyć i zgłasza StackOverflowError z n wokół znaku 22000.

Potem podrapałem się trochę po głowie i zastąpiłem „chwilę” nieco większą rekurencją ogonową, która oszczędza kilka linii, działa równie szybko, ale spójrzmy prawdzie w oczy, jest bardziej myląca:

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

Tak więc rekurencja ogona Scali wygrywa dzień, ale jestem zaskoczony, że coś tak prostego jak pętla „for” (i metoda „forall”) jest w zasadzie zepsute i musi zostać zastąpione przez nieeleganckie i rozwlekłe „whiles” lub rekurencję ogonową . Wiele powodów, dla których próbuję Scala, jest zwięzła składnia, ale nie jest dobrze, jeśli mój kod będzie działał 100 razy wolniej!

EDYCJA : (usunięty)

EDYCJA EDYCJI: Wcześniejsze rozbieżności między czasem działania 2,5 s a 0,7 s wynikały wyłącznie z tego, czy używane były 32-bitowe czy 64-bitowe maszyny JVM. Scala z wiersza poleceń używa wszystkiego, co jest ustawione przez JAVA_HOME, podczas gdy Java używa 64-bitowej, jeśli jest dostępna, niezależnie. IDE mają własne ustawienia. Oto kilka pomiarów: Czasy wykonania Scali w Eclipse

Odpowiedź dotycząca zrozumienia jest właściwa, ale to nie wszystko. Należy pamiętać, że korzystanie z returnin isEvenlyDivisiblenie jest darmowe. Użycie return wewnątrz for, zmusza kompilator scala do wygenerowania nielokalnego zwrotu (tj. Powrotu poza swoją funkcję).

Odbywa się to poprzez użycie wyjątku do wyjścia z pętli. To samo dzieje się, gdy tworzysz własne abstrakcje kontrolne, na przykład:

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

Spowoduje to wyświetlenie „Cześć” tylko raz.

Zwróć uwagę, że returnin foowyjścia foo(czego można się spodziewać). Ponieważ wyrażenie w nawiasach kwadratowych jest literałem funkcji, co widać w sygnaturze, loopwymusza to na kompilatorze wygenerowanie nielokalnego zwrotu, to znaczy returnwymusza wyjście foo, a nie tylko body.

W Javie (tj. JVM) jedynym sposobem zaimplementowania takiego zachowania jest zgłoszenie wyjątku.

Wracając do isEvenlyDivisible:

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

Jest if (a % i != 0) return falseto literał funkcji, który ma zwrot, więc za każdym razem, gdy ten znak jest trafiony, środowisko wykonawcze musi wyrzucić i złapać wyjątek, co powoduje sporo narzutu GC.

Kilka sposobów na przyspieszenie forallmetody, którą odkryłem:

Oryginał: 41,3 s

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

Wstępne tworzenie instancji zakresu, więc nie tworzymy nowego zakresu za każdym razem: 9,0 s

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

Konwersja do listy zamiast zakresu: 4,8 s

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

Wypróbowałem kilka innych kolekcji, ale List był najszybszy (chociaż nadal 7x wolniej niż gdybyśmy w ogóle uniknęli funkcji Range i wyższego rzędu).

Chociaż jestem nowy w Scali, myślę, że kompilator mógłby łatwo zaimplementować szybki i znaczący wzrost wydajności, po prostu automatycznie zastępując literały Range w metodach (jak powyżej) stałymi Range w najbardziej zewnętrznym zakresie. Albo lepiej, internuj je jak literały Strings w Javie.

przypis : Tablice były mniej więcej takie same jak Range, ale co ciekawe, pimowanie nowej forallmetody (pokazanej poniżej) skutkowało 24% szybszym wykonaniem na 64-bitowym i 8% szybszym na 32-bitowym. Kiedy zmniejszyłem rozmiar obliczeń, zmniejszając liczbę czynników z 20 do 15, różnica zniknęła, więc może to efekt zbierania śmieci. Niezależnie od przyczyny, jest to istotne podczas długotrwałej pracy pod pełnym obciążeniem.

Podobny alfons dla listy również spowodował około 10% lepszą wydajność.

  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)  

Chciałem tylko skomentować dla ludzi, którzy mogą stracić wiarę w Scalę z powodu takich problemów, że tego rodzaju problemy pojawiają się w działaniu prawie wszystkich języków funkcjonalnych. Jeśli optymalizujesz fałdowanie w Haskell, często będziesz musiał ponownie napisać go jako cykliczną pętlę zoptymalizowaną pod kątem wywołań ogonowych, w przeciwnym razie będziesz mieć problemy z wydajnością i pamięcią.

Wiem, że to niefortunne, że FP nie są jeszcze zoptymalizowane do tego stopnia, że ​​nie musimy myśleć o takich rzeczach, ale to wcale nie jest problem specyficzny dla Scali.

Problemy specyficzne dla Scali zostały już omówione, ale głównym problemem jest to, że użycie algorytmu brutalnej siły nie jest zbyt fajne. Rozważ to (znacznie szybciej niż oryginalny kod Java):

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

Wypróbuj jedną linijkę podaną w rozwiązaniu Scala dla Project Euler

Podany czas jest co najmniej szybszy niż Twój, choć daleko od pętli while .. :)