Jak zoptymalizować składanie i pętle w Scali?

Problemem jest najprawdopodobniej użycie for zrozumienia w metodzie isEvenlyDivisible. Zastąpienie pętli for równoważną pętlą while powinno wyeliminować różnicę w wydajności w Javie.

W przeciwieństwie do pętli Javy for, składnia Scali for jest cukrem składniowym dla metod wyższego rzędu; w tym przypadku wywołujesz metodę foreach na obiekcie Range. Scala for jest bardzo ogólna, ale czasami prowadzi do bolesnej wydajności.

Możesz spróbować -optimize flaga w Scali w wersji 2.9. Obserwowana wydajność może zależeć od konkretnego JVM w użyciu, a JIT optimizer ma wystarczający czas "rozgrzewania", aby zidentyfikować i zoptymalizować hot-spoty.

Ostatnie dyskusje na liście dyskusyjnej wskazują, że zespół Scala pracuje nad poprawą wydajności for w simple przypadki:

• 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 bug trackerze: https://issues.scala-lang.org/browse/SI-4633

Aktualizacja 5/28:

• jako rozwiązanie krótkoterminowe, Wtyczka ScalaCL (alpha) przekształci proste pętle Scala do odpowiednika while pętli.
[21]} jako potencjalne rozwiązanie długoterminowe, zespoły z EPFL i Stanford są współpracują nad projektem umożliwiającym kompilację "wirtualnej" Scali {23]} dla bardzo wysokiej wydajności. Na przykład, wiele idiomatycznych pętli funkcyjnych może być połączonych w czasie wykonywania w optymalny bajt JVM lub do innego celu, takiego jak GPU. System jest rozszerzalny, umożliwiając zdefiniowane przez użytkownika DSL i transformacje. Zobacz też publications and Stanford course notes . Wstępny kod jest dostępny na Githubie, a jego wydanie planowane jest na najbliższe miesiące.

Jako kontynuację wypróbowałem flagę-optimize, która skróciła czas pracy z 103 do 76 sekund, ale nadal jest to 107x 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óbuje dowiedzieć się, jak pozbyć się" forall " w zwięzły sposób. Zawiodłem nędznie i wymyśliłem

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

Oczywiście moim następnym krokiem było przetłumaczenie powyższego z powrotem na Javę, ale Java nie może sobie z tym poradzić i rzuca StackOverflowError z n wokół znaku 22000.

Potem podrapałem się trochę po głowie i zastąpiłem "while" trochę większą rekurencją ogona, która oszczędza kilka linii, biegnie równie szybko, ale spójrzmy prawdzie w oczy, jest bardziej mylące do przeczytania:

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

Więc rekurencja ogonowa Scali wygrywa dzień, ale jestem zaskoczony, że coś tak prostego jak pętla " for "(I metoda" forall") jest zasadniczo zepsute i musi zostać zastąpione przez nieeleganckie i słowne" whiles", lub rekurencja ogonowa. Wiele z powodów, dla których próbuję Scali Jest ze względu na zwięzłą składnię, ale to nie jest dobre, jeśli mój kod ma działać 100 razy wolniej!

EDIT : (deleted)

EDIT of EDIT : dawne rozbieżności między czasy uruchomienia 2,5 s i 0,7 s były całkowicie spowodowane tym, czy używane były 32-bitowe czy 64-bitowe JVMs. Scala z linii poleceń używa tego, co jest ustawione przez JAVA_HOME, podczas gdy Java używa 64-bitowego, jeśli jest dostępny niezależnie od tego. IDE mają swoje własne ustawienia. Niektóre pomiary tutaj: Czas wykonania Scali w Eclipse

Odpowiedź o zrozumieniu jest słuszna, ale to nie jest cała historia. Należy pamiętać, że użycie return w isEvenlyDivisible nie jest bezpłatne. Użycie return wewnątrz for zmusza kompilator scala do generowania nielokalnego zwrotu (tzn. powrotu poza jego funkcją).

Odbywa się to poprzez użycie wyjątku do wyjścia z pętli. To samo dzieje się, gdy budujesz 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()

To drukuje "cześć" tylko raz.

Uwaga że return w foo wyjścia foo (czego można się spodziewać). Ponieważ wyrażenie w nawiasach jest funkcją literalną, co widać w podpisie {[8] } wymusza to na kompilatorze generowanie nielokalnego zwrotu, to znaczy return wymusza wyjście foo, a nie tylko body.

W Javie (tj. JVM) jedynym sposobem implementacji takiego zachowania jest wyrzucenie wyjątku.

Powrót do isEvenlyDivisible:

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

if (a % i != 0) return false jest funkcją, która ma return, więc za każdym razem, gdy return jest trafiony, runtime musi rzucić i złapać wyjątek, co powoduje sporo narzutu GC.

Kilka sposobów na przyspieszenie metody forall odkryłem:

Oryginał: 41.3 s

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

Wstępnie tworzymy zakres, więc nie tworzymy za każdym razem nowego zakresu: 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}

Próbowałem kilku innych kolekcji, ale lista była najszybsza (chociaż nadal 7x wolniejsza niż Jeśli w ogóle unikniemy funkcji Range i wyższego rzędu).

Skoro jestem nowy w Scali, to chyba kompilator mógł łatwo zaimplementować szybki i znaczący wzrost wydajności, po prostu automatycznie zastępując literały zakresu w metodach (jak wyżej) stałymi zakresu w najbardziej oddalonym zakresie. Albo lepiej, intern je jak ciągi literałów w Javie.

Przypis : Tablice były mniej więcej takie same jak Range, ale co ciekawe, zastosowanie nowej metody forall (pokazanej poniżej) skutkowało o 24% szybszym wykonaniem na 64-bitach, a o 8% szybszym na 32-bitach. Kiedy zmniejszyłem rozmiar obliczeniowy poprzez zmniejszenie liczba czynników od 20 do 15 różnica zniknęła, więc może to efekt śmieci. Bez względu na przyczynę jest to istotne podczas pracy pod pełnym obciążeniem przez dłuższy czas.

  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ę przez takie problemy, że tego rodzaju problemy pojawiają się w wydajności prawie wszystkich języków funkcyjnych. Jeśli optymalizujesz fałd w Haskell, często będziesz musiał napisać go ponownie jako rekurencyjną pętlę zoptymalizowaną pod kątem ogona, w przeciwnym razie będziesz miał problemy z wydajnością i pamięcią.

Wiem, że to niefortunne, że FPs nie są jeszcze zoptymalizowane do tego stopnia, że nie musimy myśleć o takich rzeczach jak to, ale nie jest to żaden problem szczególny dla Scali.

Problemy specyficzne dla Scali zostały już omówione, ale głównym problemem jest to, że używanie algorytmu brute-force nie jest zbyt fajne. Rozważ to (znacznie szybciej niż oryginalny kod Javy):

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 jednowarstwową podaną w roztworze Scala dla projektu Euler

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