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

Question

Так что 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 намного быстрее?

Answer 1

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

В качестве продолжения я попробовал флаг -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 не может обработать это и выдает ошибку StackruError с 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

Answer 4

Ответ о понимании правильный, но это не вся история. Вы должны отметить, что использование return в isEvenlyDivisible не бесплатно. Использование возврата внутри 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.

Answer 5

Несколько способов ускорить 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)  

Answer 6

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

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

Answer 7

Проблемы, специфичные для 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
}))

Answer 8

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

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