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

Итак, 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 в 64-битной Windows 7. Как мне улучшить производительность? Я делаю что-то неправильно? Или Java просто намного быстрее?

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

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

В отличие от forциклов Java , forпонимания Scala на самом деле являются синтаксическим сахаром для методов более высокого порядка; в этом случае вы вызываете 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

Обновление 28.05 :

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

В качестве продолжения я попробовал флаг -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))
}

и пытаемся понять, как лаконично избавиться от "forall". Я с треском провалился и придумал

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

благодаря чему мое хитрое решение с 5 строками превратилось в 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) по существу не работает и должно быть заменено неэлегантным и многословным while или хвостовой рекурсией. , Во многом я пробую Scala из-за лаконичного синтаксиса, но это плохо, если мой код будет работать в 100 раз медленнее!

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

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

Ответ насчет понимания верен, но это еще не все. Обратите внимание, что использование returnin 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()

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

Обратите внимание, что returnin 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.

Некоторые способы ускорить 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 во внешней области. Или лучше, интернируйте их, как литералы String в 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)  

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

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

Проблемы, характерные для 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
}))

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

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