Caché coût de performances en Scala?

Question

Je suis tombé sur cette vieille question et a fait l'expérience suivante avec scala 2.10.3.

J'ai réécrit la Scala version à l'utilisation explicite de la queue de la récursivité:

import scala.annotation.tailrec

object ScalaMain {
  private val t = 20

  private def run() {
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    println(i)
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
  }

  def main(args: Array[String]) {
    val t1 = System.currentTimeMillis()
    var i = 0
    while (i < 20) {
      run()
      i += 1
    }
    val t2 = System.currentTimeMillis()
    println("time: " + (t2 - t1))
  }
}

et par rapport à la suite de la version Java. J'ai sciemment fait les fonctions non-statique pour une comparaison équitable avec Scala:

public class JavaMain {
    private final int t = 20;

    private void run() {
        int i = 10;
        while (!isEvenlyDivisible(2, i, t))
            i += 2;
        System.out.println(i);
    }

    private boolean isEvenlyDivisible(int i, int a, int b) {
        if (i > b) return true;
        else return (a % i == 0) && isEvenlyDivisible(i+1, a, b);
    }

    public static void main(String[] args) {
        JavaMain o = new JavaMain();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 20; ++i)
          o.run();
        long t2 = System.currentTimeMillis();
        System.out.println("time: " + (t2 - t1));
    }
}

Voici le résultat sur mon ordinateur:

> java JavaMain
....
time: 9651
> scala ScalaMain
....
time: 20592

C'est scala 2.10.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_51).

Ma question est quel est le coût caché avec la scala version?

Merci beaucoup.

Answer 1

Ainsi, OP benchmarking n'est pas l'idéal. Des tonnes d'effets doivent être atténués, y compris l'échauffement, l'élimination du code mort, fourches, etc. Heureusement, JMH déjà prend soin de beaucoup de choses, et a des bindings pour Java et Scala. Veuillez suivre les procédures sur JMH page pour obtenir l'indice de référence du projet, vous pouvez transplanter les indices de référence ci-dessous.

C'est l'exemple de Java de référence:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
public class JavaBench {

    @Param({"1", "5", "10", "15", "20"})
    int t;

    private int run() {
        int i = 10;
        while(!isEvenlyDivisible(2, i, t))
            i += 2;
        return i;
    }

    private boolean isEvenlyDivisible(int i, int a, int b) {
        if (i > b)
            return true;
        else
            return (a % i == 0) && isEvenlyDivisible(i + 1, a, b);
    }

    @GenerateMicroBenchmark
    public int test() {
        return run();
    }

}

...et c'est l'exemple de la Scala de référence:

@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
class ScalaBench {

  @Param(Array("1", "5", "10", "15", "20"))
  var t: Int = _

  private def run(): Int = {
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    i
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i + 1, a, b)
  }

  @GenerateMicroBenchmark
  def test(): Int = {
    run()
  }

}

Si vous exécutez ces sur JDK 8 GA, Linux x86_64, alors vous aurez:

Benchmark             (t)   Mode   Samples         Mean   Mean error    Units
o.s.ScalaBench.test     1   avgt        15        0.005        0.000    us/op
o.s.ScalaBench.test     5   avgt        15        0.489        0.001    us/op
o.s.ScalaBench.test    10   avgt        15       23.672        0.087    us/op
o.s.ScalaBench.test    15   avgt        15     3406.492        9.239    us/op
o.s.ScalaBench.test    20   avgt        15  2483221.694     5973.236    us/op

Benchmark            (t)   Mode   Samples         Mean   Mean error    Units
o.s.JavaBench.test     1   avgt        15        0.002        0.000    us/op
o.s.JavaBench.test     5   avgt        15        0.254        0.007    us/op
o.s.JavaBench.test    10   avgt        15       12.578        0.098    us/op
o.s.JavaBench.test    15   avgt        15     1628.694       11.282    us/op
o.s.JavaBench.test    20   avgt        15  1066113.157    11274.385    us/op

Avis nous jonglons t pour voir si l'effet est local pour la valeur particulière de l' t. Il n'est pas, l'effet est systématique, et la version de Java étant deux fois plus rapide.

PrintAssembly permettra de jeter quelque lumière sur ce point. Celui-ci est le plus chaud de bloc dans la Scala de référence:

0x00007fe759199d42: test   %r8d,%r8d
0x00007fe759199d45: je     0x00007fe759199d76  ;*irem
                                               ; - org.sample.ScalaBench::isEvenlyDivisible@11 (line 52)
                                               ; - org.sample.ScalaBench::run@10 (line 45)
0x00007fe759199d47: mov    %ecx,%eax
0x00007fe759199d49: cmp    $0x80000000,%eax
0x00007fe759199d4e: jne    0x00007fe759199d58
0x00007fe759199d50: xor    %edx,%edx
0x00007fe759199d52: cmp    $0xffffffffffffffff,%r8d
0x00007fe759199d56: je     0x00007fe759199d5c
0x00007fe759199d58: cltd   
0x00007fe759199d59: idiv   %r8d

...et ce qui est similaire bloc en Java:

0x00007f4a811848cf: movslq %ebp,%r10
0x00007f4a811848d2: mov    %ebp,%r9d
0x00007f4a811848d5: sar    $0x1f,%r9d
0x00007f4a811848d9: imul   $0x55555556,%r10,%r10
0x00007f4a811848e0: sar    $0x20,%r10
0x00007f4a811848e4: mov    %r10d,%r11d
0x00007f4a811848e7: sub    %r9d,%r11d         ;*irem
                                              ; - org.sample.JavaBench::isEvenlyDivisible@9 (line 63)
                                              ; - org.sample.JavaBench::isEvenlyDivisible@19 (line 63)
                                              ; - org.sample.JavaBench::run@10 (line 54)

Notez que dans la version Java, le compilateur utilisé la ruse pour la traduction reste entier de calcul dans la multiplication et le déplacement à droite (voir Hacker Plaisir, Ch. 10, Sect. 19). Cela est possible lorsque le compilateur détecte nous calculer le reste à l'encontre de la constante, ce qui suggère la version Java de frapper doux optimisation, mais Scala version n'a pas. Vous pouvez creuser dans le pseudo-code de démontage pour comprendre ce caprice dans scalac sont intervenus, mais le but de cet exercice est surprenant d'infimes différences de génération de code sont amplifiés par les benchmarks beaucoup.

P. S. Donc beaucoup pour @tailrec...

Mise à JOUR: UNE explication plus approfondie de l'effet: http://shipilev.net/blog/2014/java-scala-divided-we-fail/

Answer 2

J'ai changé l' val

private val t = 20

pour une définition de constante

private final val t = 20

et a obtenu un gain de performances significatif, maintenant, il semble que les deux versions effectuer presque aussi [sur mon système, consultez la section mise à jour et commentaires].

Je n'ai pas regardé dans le bytecode, mais si vous utilisez val t = 20 vous pouvez le voir à l'aide de javap qu'il s'agit d'une méthode (et cette version est aussi lent que l'un avec l' private val).

Donc je suppose que même un private val implique l'appel d'une méthode, et ce n'est pas directement comparable avec un final en Java.

Mise à jour

Sur mon système, j'ai eu ces résultats

Java version : heure: 14725

Scala version: heure: 13228

À l'aide de OpenJDK 1.7 sur un Linux 32 Bits.

Dans mon expérience, Oracle JDK sur un système 64 Bits ne fait meilleurs, donc c'est probablement ce qui explique que d'autres mesures de rendement, des résultats encore meilleurs en faveur de la Scala version.

Comme pour la Scala version mieux je suppose que la queue de la récursivité d'optimisation n'ont un effet (voir la réponse de Phil, si la version de Java est réécrit pour utiliser une boucle au lieu de la récursivité, il effectue également de nouveau).

Answer 3

J'ai regardé cette question et a édité la version Scala avoir t à l'intérieur d' run:

object ScalaMain {
  private def run() {
    val t = 20
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    println(i)
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
  }

  def main(args: Array[String]) {
    val t1 = System.currentTimeMillis()
    var i = 0
    while (i < 20) {
      run()
      i += 1
    }
    val t2 = System.currentTimeMillis()
    println("time: " + (t2 - t1))
  }
}

La nouvelle version Scala fonctionne maintenant deux fois plus rapide que l'original Java:

> fsc ScalaMain.scala
> scala ScalaMain
....
time: 6373
> fsc -optimize ScalaMain.scala
....
time: 4703

J'ai compris c'est parce que Java ne pas avoir de queue appels. L'optimisation de code Java avec boucle au lieu de la récursivité fonctionne tout aussi vite:

public class JavaMain {
    private static final int t = 20;

    private void run() {
        int i = 10;
        while (!isEvenlyDivisible(i, t))
            i += 2;
        System.out.println(i);
    }

    private 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) {
        JavaMain o = new JavaMain();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 20; ++i)
            o.run();
        long t2 = System.currentTimeMillis();
        System.out.println("time: " + (t2 - t1));
    }
}

Maintenant, ma confusion est entièrement résolu:

> java JavaMain
....
time: 4795

En conclusion, l'original de la Scala version a été lente parce que je n'ai pas déclarer t être final (directement ou indirectement, du Béryllium's réponse souligne). Et l'original de la version de Java a été lente en raison du manque de queue appels.

Answer 4

Pour faire la Java version complètement équivalent à votre Scala code que vous avez besoin de changer comme ça.

private int t = 20;


private int t() {
    return this.t;
}

private void run() {
    int i = 10;
    while (!isEvenlyDivisible(2, i, t()))
        i += 2;
    System.out.println(i);
}

Il est plus lent parce que la JVM ne peut pas optimiser les appels de méthode.