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


131

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?


2
kompilujesz lub interpretujesz używając powłoki Scala?
AhmetB - Google

Jest na to lepszy sposób niż podział próbny ( wskazówka ).
hammar

2
nie pokazujesz, w jakim czasie to ustalasz. Czy próbowałeś po prostu określić czas runmetody?
Aaron Novstrup

2
@hammar - tak, po prostu zrobiłem to na papierze: zapisz czynniki pierwsze dla każdej liczby, zaczynając od wysokiego, a następnie skreśl współczynniki, które już masz dla wyższych liczb, więc kończysz z (5 * 2 * 2) * (19) * (3 * 3) * (17) * (2 * 2) * () * (7) * (13) * () * (11) = 232792560
Luigi Plinge

2
+1 To najciekawsze pytanie, jakie widziałem od tygodni na SO (ma też najlepszą odpowiedź, jaką widziałem od dłuższego czasu).
Mia Clarke

Odpowiedzi:


111

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.


9
Dość ciężkie, że powrót staje się wyjątkiem. Jestem pewien, że jest gdzieś udokumentowany, ale pachnie niezrozumiałą, ukrytą magią. Czy to naprawdę jedyny sposób?
skrebbel

10
Jeśli powrót następuje od wewnątrz zamknięcia, wydaje się, że jest to najlepsza dostępna opcja. Zwroty z zewnętrznych zamknięć są oczywiście tłumaczone bezpośrednio na instrukcje zwrotu w kodzie bajtowym.
Martin Odersky

1
Jestem pewien, że coś przeoczyłem, ale dlaczego zamiast tego nie skompilować zwrotu z wnętrza zamknięcia, aby ustawić załączoną flagę logiczną i wartość zwracaną, i sprawdzić, czy po powrocie wywołania zamknięcia?
Luke Hutteman

9
Dlaczego jego algorytm funkcjonalny jest nadal 55 razy wolniejszy? Wygląda na to, że nie powinien cierpieć z powodu tak okropnego występu
Eliasz

5
Teraz, w 2014 roku, przetestowałem to ponownie i dla mnie wydajność jest następująca: java -> 0.3s; scala -> 3,6 s; zoptymalizowana skala -> 3,5 s; scala funkcjonalna -> 4s; Wygląda znacznie lepiej niż 3 lata temu, ale ... Mimo to różnica jest zbyt duża. Czy możemy spodziewać się większej poprawy wydajności? Innymi słowy, Martin, czy w teorii zostało jeszcze coś do możliwych optymalizacji?
sasha.sochka

80

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:

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.

6
Świetnie, zastąpiłem pętlę while i działa dokładnie z taką samą prędkością (+/- <1%) jak wersja Java. Dzięki ... prawie straciłem wiarę w Scalę na minutę! Teraz po prostu muszę popracować nad dobrym funkcjonalnym algorytmem ... :)
Luigi Plinge

25
Warto zauważyć, że rekurencyjne funkcje ogonowe są również tak szybkie, jak pętle while (ponieważ obie są konwertowane na bardzo podobny lub identyczny kod bajtowy).
Rex Kerr

7
To mnie też kiedyś dopadło. Musiałem przetłumaczyć algorytm z używania funkcji kolekcji na zagnieżdżone pętle while (poziom 6!) Z powodu niesamowitego spowolnienia. To jest coś, co musi być mocno ukierunkowane, imho; Po co mi fajny styl programowania, jeśli nie mogę go używać, gdy potrzebuję przyzwoitej (uwaga: nie błyskawicznej) wydajności?
Raphael

7
Kiedy więc jest forodpowiedni?
OscarRyz,

1
@OscarRyz - a for in scala w większości zachowuje się jak for (:) w java.
Mike Axiak

31

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


1
isDivis-metoda może być zapisany jako: def isDivis(x: Int, i: Int): Boolean = if (i > 20) true else if (x % i != 0) false else isDivis(x, i+1). Zauważ, że w Scali if-else jest wyrażeniem, które zawsze zwraca wartość. Nie ma tu potrzeby słowa kluczowego return.
kiritsuku

3
Twoja ostatnia wersja ( P005_V3) może być krótsza, bardziej deklaratywna i jaśniejsza IMHO, pisząc:def isDivis(x: Int, i: Int): Boolean = (i > 20) || (x % i == 0) && isDivis(x, i+1)
Blaisorblade

@Blaisorblade Nie. To przerwałoby rekurencyjność ogona, która jest wymagana do przetłumaczenia na pętlę while w kodzie bajtowym, co z kolei przyspiesza wykonanie.
gzm0

4
Rozumiem twój punkt widzenia, ale mój przykład jest wciąż rekurencyjny od czasów && i || użyj oceny zwarcia, co zostało potwierdzone przez @tailrec: gist.github.com/Blaisorblade/5672562
Blaisorblade

8

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.


7

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)  

3

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.


2

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

Pytania porównują wydajność określonej logiki w różnych językach. Nie ma znaczenia, czy algorytm jest optymalny dla problemu.
smartnut007

1

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 .. :)


Jest bardzo podobny do mojej wersji funkcjonalnej. Możesz napisać mój jako def r(n:Int):Int = if ((1 to 20) forall {n % _ == 0}) n else r (n+2); r(2), który jest o 4 znaki krótszy niż napis Pawła. :) Jednak nie udaję, że mój kod jest dobry - kiedy pisałem to pytanie, zakodowałem w sumie około 30 linijek Scali.
Luigi Plinge
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.