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

Ответы

Ответ 1

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

Ответ 2

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

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

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

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

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

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

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

Ответ 3

В качестве продолжения я попробовал флаг -optimize и сократил время работы от 103 до 76 секунд, но это все еще на 107x медленнее, чем 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))
}

благодаря чему мое хитрое пятилинейное решение имеет 12 линий. Однако эта версия работает 0,71 секунды, с той же скоростью, что и исходная версия Java, и в 56 раз быстрее, чем версия выше с использованием "forall" (40,2 с)! (см. ниже EDIT, почему это быстрее, чем 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 раз медленнее!

EDIT: (удалено)

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

Ответ 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 in 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.

Ответ 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 был самым быстрым (хотя все же на 7x медленнее, чем если бы мы вообще избегали функции 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)

Ответ 6

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

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

Ответ 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
}))

Ответ 8

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

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