Как оптимизировать для-понимания и циклов в Scala? - PullRequest
Новая
       34

Как оптимизировать для-понимания и циклов в Scala?

131 голосов
/ 27 мая 2011

Итак, Scala должен быть таким же быстрым, как Java. Я возвращаюсь к некоторым Project Euler проблемам в Scala, которые я изначально решал в Java. Конкретно, проблема 5: «Какое наименьшее положительное число делится равномерно на все числа от 1 до 20?»

Вот мое решение Java, которое занимает 0,7 секунды на моем компьютере: 

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

Вот мой «прямой перевод» на Scala, который занимает 103 секунды (в 147 раз дольше!) 

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

Наконец, вот моя попытка функционального программирования, которая занимает 39 секунд (в 55 раз дольше) 

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

Использование Scala 2.9.0.1 в Windows 7 64-bit. Как мне улучшить производительность? Я делаю что-то неправильно? Или Java намного быстрее?

Ответы [ 8 ]

111 голосов
/ 16 июня 2011

Проблема в данном конкретном случае заключается в том, что вы возвращаетесь из-за выражения. Это, в свою очередь, преобразуется в исключение NonLocalReturnException, которое перехватывается при включении метода. Оптимизатор может исключить foreach, но пока не может устранить бросок / улов. И бросать / ловить это дорого. Но поскольку такие вложенные возвраты редко встречаются в программах Scala, оптимизатор еще не рассмотрел этот случай. Продолжается работа по улучшению оптимизатора, который, надеюсь, скоро решит эту проблему.

80 голосов
/ 27 мая 2011

Скорее всего, проблема заключается в использовании for понимания в методе isEvenlyDivisible. Замена for эквивалентным циклом while должна устранить разницу в производительности с Java.

В отличие от циклов for в Java, for понимания Scala на самом деле являются синтаксическим сахаром для методов более высокого порядка; в этом случае вы вызываете метод foreach для объекта Range. for у Скалы очень общий, но иногда приводит к болезненным результатам.

Возможно, вы захотите попробовать флаг -optimize в Scala версии 2.9. Наблюдаемая производительность может зависеть от конкретной используемой JVM и от того, что оптимизатор JIT имеет достаточное время для «прогрева» для выявления и оптимизации горячих точек.

Недавние обсуждения в списке рассылки показывают, что команда Scala работает над улучшением производительности for в простых случаях:

Вот проблема в трекере ошибок: https://issues.scala -lang.org / просмотр / SI-4633

Обновление 5/28 :

  • В качестве краткосрочного решения плагин ScalaCL (альфа) преобразует простые циклы Scala в эквивалент while циклов.
  • В качестве потенциального долгосрочного решения команды из EPFL и Stanford совместно работают над проектом , позволяющим компилировать "виртуальную" Scala во время выполнения для очень высокой производительности. Например, несколько идиоматических функциональных циклов могут быть объединены во время выполнения в оптимальный байт-код JVM или в другую цель, такую ​​как графический процессор. Система является расширяемой, что позволяет задавать пользовательские DSL и преобразования. Ознакомьтесь с публикациями и Stanford с примечаниями к курсу . Предварительный код доступен на Github, выпуск планируется в ближайшие месяцы.
31 голосов
/ 28 мая 2011

В качестве продолжения я попробовал флаг -optimize, и он сократил время выполнения с 103 до 76 секунд, но это все равно в 107 раз медленнее, чем Java или цикл while.

Тогда я смотрел на «функциональную» версию: 

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

и пытается выяснить, как избавиться от «суеты» в сжатой форме. Я с треском провалился и придумал 

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

, в результате чего мое хитрое пятистрочное решение увеличилось до 12 строчек. Однако эта версия работает за 0,71 секунды , с той же скоростью, что и исходная версия Java, и в 56 раз быстрее, чем указанная выше версия, используя "forall" (40,2 с)! (см. РЕДАКТИРОВАТЬ ниже, почему это быстрее, чем Java)

Очевидно, что моим следующим шагом было перевести вышеупомянутое обратно в Java, но Java не может с этим справиться и выдает ошибку StackOverflowError с n вокруг отметки 22000.

Затем я немного почесал голову и заменил «while» на более длинную хвостовую рекурсию, которая экономит пару строк, работает так же быстро, но, давайте посмотрим правде в глаза, читать немного сложнее: 

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

Итак, хвостовая рекурсия Scala выигрывает день, но я удивлен, что что-то простое, такое как цикл «for» (и метод «forall»), по существу нарушено и должно быть заменено неэлегичным и многословным «whiles», или хвостовая рекурсия. Во многом я пытаюсь использовать Scala из-за лаконичного синтаксиса, но не очень хорошо, если мой код будет работать в 100 раз медленнее!

РЕДАКТИРОВАТЬ : (удалено)

РЕДАКТИРОВАНИЕ РЕДАКТИРОВАНИЯ : Прежние расхождения между временами выполнения от 2,5 с до 0,7 с были полностью обусловлены тем, использовались ли 32-битные или 64-битные JVM. Scala из командной строки использует все, что установлено JAVA_HOME, в то время как Java использует 64-битную версию, если она доступна независимо. IDE имеют свои собственные настройки. Некоторые измерения здесь: Время выполнения Scala в Eclipse

8 голосов
/ 16 июня 2011

Правильный ответ о понимании, но это не вся история. Обратите внимание, что использование return в isEvenlyDivisible не является бесплатным. Использование return внутри for заставляет компилятор scala генерировать нелокальный возврат (т. Е. Возвращать вне своей функции).

Это делается с помощью исключения для выхода из цикла. То же самое происходит, если вы создаете свои собственные контрольные абстракции, например: 

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

Печать "Привет" только один раз.

Обратите внимание, что return в foo выходит foo (это то, что вы ожидаете). Поскольку выражение в скобках является функциональным литералом, который вы можете увидеть в сигнатуре loop, это заставляет компилятор генерировать нелокальное возвращение, то есть return заставляет вас выйти из foo, а не только из body.

В Java (то есть JVM) единственный способ реализовать такое поведение - вызвать исключение.

Возвращаясь к 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 - это функциональный литерал с возвращаемым значением, поэтому каждый раз, когда возвращается значение, среда выполнения должна выдавать и перехватывать исключение, которое вызывает немало накладных расходов GC.

6 голосов
/ 19 июня 2011

Некоторые способы ускорить обнаруженный мною forall метод:

Оригинал: 41,3 с 

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

Предварительная реализация диапазона, поэтому мыне создавайте новый диапазон каждый раз: 9,0 с 

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

Преобразование в список вместо диапазона: 4,8 с 

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

Я пробовал несколько других коллекций, но List был быстрее (хотя все еще в 7 раз медленнее, чем если бы мы вообще избегали функции Range и высшего порядка).

Хотя я новичок в Scala, я бы предположил, чтоКомпилятор может легко реализовать быстрый и значительный выигрыш в производительности, просто автоматически заменяя литералы Range в методах (как указано выше) на константы Range во внешней области видимости.Или, лучше, интернировать их как строковые литералы в Java.

сноска : массивы были примерно такими же, как Range, но, что интересно, использование нового метода forall (показанного ниже) привело к 24% более быстрому выполнению на 64-битной платформе,и на 8% быстрее на 32-битной.Когда я уменьшил размер вычисления, уменьшив количество факторов с 20 до 15, разница исчезла, так что, возможно, это эффект сбора мусора.Независимо от причины, это важно при работе под полной нагрузкой в ​​течение длительных периодов.

Подобный сводник для List также привел к повышению производительности примерно на 10%. 

  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 голосов
/ 05 июля 2011

Я просто хотел бы прокомментировать для людей, которые могут потерять веру в Scala из-за таких проблем, что подобные проблемы возникают при работе практически на всех функциональных языках.Если вы оптимизируете фолд в Haskell, вам часто придется переписывать его как рекурсивный цикл, оптимизированный для хвостовых вызовов, иначе у вас возникнут проблемы с производительностью и памятью, с которыми приходится сталкиваться.К сожалению, FP еще не оптимизированы до такой степени, что нам не нужно думать о таких вещах, но это совсем не проблема, специфичная для Scala.

2 голосов
/ 06 октября 2012

Проблемы, специфичные для Scala, уже обсуждались, но главная проблема в том, что использование алгоритма грубой силы не очень круто. Учтите это (намного быстрее, чем оригинальный код 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
}))
1 голос
/ 05 июля 2011

Попробуйте однострочник, указанный в решении Scala для Project Euler

Указанное время, по крайней мере, быстрее вашего, хотя и далеко от цикла while ..:)

...