Como otimizar as compreensões e loops no Scala?

Portanto, Scala deve ser tão rápido quanto Java. Estou revisitando alguns problemas do Project Euler no Scala que originalmente lidei em Java. Especificamente Problema 5: "Qual é o menor número positivo que é igualmente divisível por todos os números de 1 a 20?"

Aqui está minha solução Java, que leva 0,7 segundos para ser concluída na minha máquina:

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

Aqui está minha "tradução direta" para Scala, que leva 103 segundos (147 vezes mais!)

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

Finalmente, aqui está minha tentativa de programação funcional, que leva 39 segundos (55 vezes mais)

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

Usando o Scala 2.9.0.1 no Windows 7 de 64 bits. Como melhoro o desempenho? Estou fazendo algo errado? Ou o Java é muito mais rápido?

O problema nesse caso específico é que você retorna de dentro da expressão. Por sua vez, isso é traduzido em um lançamento de NonLocalReturnException, que é capturado no método anexo. O otimizador pode eliminar o foreach, mas ainda não pode eliminar o lançamento / captura. E jogar / pegar é caro. Mas como esses retornos aninhados são raros nos programas Scala, o otimizador ainda não abordou esse caso. Há trabalho em andamento para melhorar o otimizador que, esperamos, resolva esse problema em breve.

O problema provavelmente é o uso de uma forcompreensão no método isEvenlyDivisible. A substituição forpor um whileloop equivalente deve eliminar a diferença de desempenho com Java.

Ao contrário dos forloops de Java , as forcompreensões do Scala são na verdade açúcar sintático para métodos de ordem superior; Nesse caso, você está chamando o foreachmétodo em um Rangeobjeto. O Scala foré muito geral, mas às vezes leva a um desempenho doloroso.

Você pode tentar a -optimizebandeira no Scala versão 2.9. O desempenho observado pode depender da JVM específica em uso e do otimizador de JIT com tempo de "aquecimento" suficiente para identificar e otimizar pontos de acesso.

Discussões recentes na lista de discussão indicam que a equipe Scala está trabalhando para melhorar o fordesempenho em casos simples:

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

Aqui está o problema no rastreador de erros: https://issues.scala-lang.org/browse/SI-4633

Atualização 5/28 :

• Como uma solução de curto prazo, o plugin ScalaCL (alpha) transformará loops simples do Scala no equivalente a whileloops.
• Como uma solução potencial de longo prazo, as equipes da EPFL e Stanford estão colaborando em um projeto que permite a compilação em tempo de execução do Scala "virtual" para um desempenho muito alto. Por exemplo, vários loops funcionais idiomáticos podem ser combinados em tempo de execução no bytecode ideal da JVM ou com outro destino, como uma GPU. O sistema é extensível, permitindo DSLs e transformações definidas pelo usuário. Confira as publicações e as notas do curso de Stanford . O código preliminar está disponível no Github, com um lançamento previsto nos próximos meses.

Como acompanhamento, tentei o sinalizador -optimize e ele reduziu o tempo de execução de 103 para 76 segundos, mas ainda é 107x mais lento que o Java ou um loop while.

Então eu estava olhando para a versão "funcional":

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

e tentando descobrir como se livrar do "forall" de maneira concisa. Eu falhei miseravelmente e inventei

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

em que minha solução astuta de 5 linhas aumentou para 12 linhas. No entanto, esta versão é executada em 0,71 segundos , a mesma velocidade que a versão Java original e 56 vezes mais rápida que a versão acima usando "forall" (40,2 s)! (veja EDITAR abaixo para saber por que isso é mais rápido que Java)

Obviamente, meu próximo passo foi converter o código acima em Java, mas o Java não pode lidar com isso e lança um StackOverflowError com n em torno da marca 22000.

Em seguida, coçou a cabeça um pouco e substituí o "while" por um pouco mais de recursão na cauda, ​​o que economiza algumas linhas, corre tão rápido quanto, mas, convenhamos, é mais confuso ler:

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

Portanto, a recursão da cauda de Scala vence o dia, mas estou surpreso que algo tão simples quanto um loop "for" (e o método "forall") esteja essencialmente quebrado e precise ser substituído por "whiles" deselegantes e detalhados ou recursão da cauda . Muitas das razões pelas quais estou experimentando o Scala são por causa da sintaxe concisa, mas não é bom se meu código for executado 100 vezes mais lento!

EDITAR : (excluído)

EDIT OF EDIT : As discrepâncias anteriores entre os tempos de execução de 2,5s e 0,7s eram inteiramente devidas ao fato de as JVMs de 32 ou 64 bits estarem sendo usadas. O Scala na linha de comando usa o que é definido por JAVA_HOME, enquanto o Java usa 64 bits, se disponível, independentemente. Os IDEs têm suas próprias configurações. Algumas medidas aqui: Tempos de execução do Scala no Eclipse

A resposta sobre a compreensão está certa, mas não é a história toda. Você deve observar que o uso de returnin isEvenlyDivisiblenão é gratuito. O uso de return dentro do for, força o compilador scala a gerar um retorno não local (ou seja, retornar fora de sua função).

Isso é feito através do uso de uma exceção para sair do loop. O mesmo acontece se você criar suas próprias abstrações de controle, por exemplo:

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

Isso imprime "Oi" apenas uma vez.

Note que o returnem foosaídas foo(que é o que você esperaria). Como a expressão entre colchetes é uma função literal, que você pode ver na assinatura loopdisso força o compilador a gerar um retorno não local, ou seja, as returnforças que você deve sair foo, não apenas obody .

Em Java (ou seja, a JVM), a única maneira de implementar esse comportamento é lançar uma exceção.

Voltando a isEvenlyDivisible:

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

A if (a % i != 0) return falseé uma literal de função que tem um retorno; portanto, toda vez que o retorno é atingido, o tempo de execução deve gerar e capturar uma exceção, o que causa um pouco de sobrecarga do GC.

Algumas maneiras de acelerar o forall método que eu descobri:

O original: 41.3 s

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

Pré-instanciando o intervalo, para não criarmos um novo intervalo sempre: 9,0 s

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

Convertendo para uma lista em vez de um intervalo: 4.8 s

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

Tentei algumas outras coleções, mas a Lista foi mais rápida (embora ainda 7 vezes mais lenta do que se evitássemos a função Faixa e ordem superior).

Embora eu seja novo no Scala, acho que o compilador pode implementar facilmente um ganho de desempenho rápido e significativo, simplesmente substituindo automaticamente literais Range nos métodos (como acima) por constantes Range no escopo mais externo. Ou melhor, interne-os como strings literais em Java.

nota de rodapé : as matrizes eram quase as mesmas que Range, mas, curiosamente, criando um novoforall método (mostrado abaixo) resultou em uma execução 24% mais rápida em 64 bits e 8% mais rápida em 32 bits. Quando reduzi o tamanho do cálculo, reduzindo o número de fatores de 20 para 15, a diferença desapareceu, talvez seja um efeito de coleta de lixo. Qualquer que seja a causa, é significativo ao operar sob carga máxima por longos períodos.

Um proxeneta semelhante para a List também resultou em um desempenho 10% melhor.

  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)  

Eu só queria comentar para as pessoas que podem perder a fé no Scala sobre questões como esta que esses tipos de problemas surgem no desempenho de praticamente todas as linguagens funcionais. Se você estiver otimizando uma dobra no Haskell, geralmente precisará reescrevê-la como um loop otimizado de chamada de cauda recursiva; caso contrário, terá problemas de desempenho e memória para lidar.

Eu sei que é lamentável que os FPs ainda não estejam otimizados a ponto de não precisarmos pensar em coisas como essa, mas esse não é um problema específico da Scala.

Problemas específicos do Scala já foram discutidos, mas o principal problema é que o uso de um algoritmo de força bruta não é muito legal. Considere isso (muito mais rápido que o código Java original):

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

Experimente o one-liner fornecido na solução Scala for Project Euler

O tempo indicado é pelo menos mais rápido que o seu, embora longe do loop while .. :)