Scala оптимизация со специализированными типами: сумма с длинными - PullRequest
Новая
       20

Scala оптимизация со специализированными типами: сумма с длинными

0 голосов
/ 06 апреля 2020

У меня есть следующий простой код 

val longs: Vector[Long] = (1L to 1000000L).toVector

и предположительно эквивалентный Java

def jLongs: java.util.stream.LongStream = java.util.stream.LongStream
    .iterate(1L, (i: Long) => i <= 1000000L, (i: Long) => i + 1L)

Когда я запускаю бенчмарк со следующим кодом 

@State(Scope.Benchmark)
@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.MILLISECONDS)
class BoxingScala {
  val longs: Vector[Long] = (1L to 1000000L).toVector
  def jLongs: java.util.stream.LongStream = java.util.stream.LongStream
    .iterate(1L, (i: Long) => i <= 1000000L, (i: Long) => i + 1L)

  @Benchmark def a: Long = longs.sum

  @Benchmark def b: java.lang.Long = jLongs.sum()
}

Я понял, что код Java примерно на 400% быстрее. Когда я пытаюсь понять, почему, я нахожу этот байт-код: 

  // access flags 0x1
  public a()J
  @Lorg/openjdk/jmh/annotations/Benchmark;()
   L0
    LINENUMBER <benchmark a> L0
    ALOAD 0
    INVOKEVIRTUAL gurghet/BoxingScala.longs ()Lscala/collection/immutable/Vector;
    GETSTATIC scala/math/Numeric$LongIsIntegral$.MODULE$ : Lscala/math/Numeric$LongIsIntegral$;
    INVOKEVIRTUAL scala/collection/immutable/Vector.sum (Lscala/math/Numeric;)Ljava/lang/Object;
    INVOKESTATIC scala/runtime/BoxesRunTime.unboxToLong (Ljava/lang/Object;)J
    LRETURN
   L1
    LOCALVARIABLE this Lgurghet/BoxingScala; L0 L1 0
    MAXSTACK = 2
    MAXLOCALS = 1

  // access flags 0x1
  public b()Ljava/lang/Long;
  @Lorg/openjdk/jmh/annotations/Benchmark;()
   L0
    LINENUMBER <benchmark b> L0
    GETSTATIC scala/Predef$.MODULE$ : Lscala/Predef$;
    ALOAD 0
    INVOKEVIRTUAL gurghet/BoxingScala.jLongs ()Ljava/util/stream/LongStream;
    INVOKEINTERFACE java/util/stream/LongStream.sum ()J (itf)
    INVOKEVIRTUAL scala/Predef$.long2Long (J)Ljava/lang/Long;
    ARETURN
   L1
    LOCALVARIABLE this Lgurghet/BoxingScala; L0 L1 0
    MAXSTACK = 3
    MAXLOCALS = 1

, где longs инициализируется 

 L1
    LINENUMBER <init> L1
    ALOAD 0
    NEW scala/runtime/RichLong
    DUP
    GETSTATIC scala/Predef$.MODULE$ : Lscala/Predef$;
    LCONST_1
    INVOKEVIRTUAL scala/Predef$.longWrapper (J)J
    INVOKESPECIAL scala/runtime/RichLong.<init> (J)V
    LDC 1000000
    INVOKESTATIC scala/runtime/BoxesRunTime.boxToLong (J)Ljava/lang/Long;
    INVOKEVIRTUAL scala/runtime/RichLong.to (Ljava/lang/Object;)Lscala/collection/immutable/NumericRange$Inclusive;
    INVOKEVIRTUAL scala/collection/immutable/NumericRange$Inclusive.toVector ()Lscala/collection/immutable/Vector;
    PUTFIELD gurghet/BoxingScala.longs : Lscala/collection/immutable/Vector;

Так что мне кажется, что версия scala принудительная загрузить миллион объектов.

Это причина, почему это так медленно? Как я могу сказать, специализироваться для длинных?

Кроме того, интересно и противоречит интуитивному факту, что, хотя код java возвращает объект, в scala возвращается примитивный длинный (ср. ARETURN против LRETURN).

1 Ответ

2 голосов
/ 06 апреля 2020

Смотреть на байт-код бесполезно. Разница в том, что Stream равно . A LongStream производит элементы по запросу. Это не структура данных; это управляющая структура - скрытое l oop по сравнению с другим источником данных. Ваш Java сводится к 

var sum: Long = 0
for(i <- 1L to 1000000L) sum += i;

A Vector - это фактическая структура данных, которая фактически должна хранить 100000 long с, что делает вашу Scala версию по существу 

val oops = new Array[java.lang.Long](1000000) // boxed!
for(i <- 0 until 1000000) oops(i) = i + 1
var sum: Long = 0
for(i <- 0 until 1000000) sum += oops(i)

Нет абсолютно никакой эквивалентности между ними. Также обратите внимание, что 1L to 1000000L является NumericRange[Long], который уже является коллекцией Scala, и (1 to 1000000L).sum намного быстрее, чем любой из них, поскольку он использует простую арифметическую формулу c для вычислить результат. Самым близким к LongStream на самом деле является SeqView[Long], который вы можете получить как (1L to 1000000).view. Если вы позвоните по этому поводу sum, я считаю, что библиотека коллекций недостаточно умна, чтобы упростить ее до вызова sum для NumericRange, и вместо этого выполнит ее итерацию, как в версии Java, делая сравнение. Тем не менее, он не будет специализироваться на Long, поэтому он будет иметь штраф за бокс.

...