Precise Types Bring Performance

Dmitry Petrashko

About me:

  • https://github.com/darkdimius/
  • doing PhD at EPFL
  • previously worked on ScalaBlitz (up to 24x faster collections)
  • since March 2014 building on Dotty under supervision of Martin.
  • since March 2015 working on Dotty Linker and supervising students working on Dotty.

Dotty contributor stats:

alias blame-lines="git ls-tree -r -z --name-only HEAD -- | egrep -z -Z -E '\.(scala)$'\
| xargs -0 -n1 git blame --line-porcelain | grep "^author "| sort | uniq -c | sort -nr"
authorcommitsadditionsdeletionsblame lines
Martin Odersky2,280
146,133
85,391
66,698
Dmitry Petrashko628
158,249
50,201
83,713
Samuel Gruetter19
62,324
12,510
36,615
Others144
5,315
2,108
4,161

Sources of slowdowns:

  • Libraries
  • User code

Library as a source of slowdown

JavaScala

public double average(int[] data) {
 int sum = 0;
 for(int i = 0; i < data.length; i++) {
   sum += data[i];
 }
 return sum * 1.0d / data.length
}

def average(x: Array[Int]) = {
  x.reduce(_ + _) * 1.0 / x.size
}
45 msec 872 msec

Why?


public double average(int[] data) {
 int sum = 0;
 for(int i = 0; i < data.length; i++) {
   sum += data[i];
 }
 return sum * 1.0d / data.length
}
                    

Java cycle body:

  • Range check;
  • Addition;
  • Index Increment.

Why?


def reduce(op: Function2[Obj, Obj, Obj]): Obj = {
  var first = true
  var acc: Obj = null
  this.foreach{ e =>
    if (first) {
      acc = e
      first = false
    } else acc = op.apply(acc, e)
  }
  acc
}

def foreach(f: Funtion1[Obj, Obj]) {
  var i = 0
  val len = length
  while (i < len) {
    f.apply(this(i));
    i += 1
  }
}

Scala cycle body:

  • Range check;
  • boxing of element
  • dynamic dispatch(foreach arg)
  • predicate check(first?)
  • dynamic dispatch(reduce arg)
  • Addition;
  • boxing inside addition.
  • Index Increment.

Benchmarks


val arr = (1 to 10000000).toArray
arr.reduce(_ + _).toDouble / arr.length
JavaScala 2.11Scala 2.12.0-M3ScalaBlitzLinkerScalaJS
45ms872ms 680ms 42ms 68ms2440ms


Maintainability vs Performance:


val x = List[Int](1, 2, 3)
if (x.size == 0) {
  // doStuff
}

val x = List[Int](1, 2, 3)
if (x.isEmpty) {
  // doStuff
}

Maintainability vs Performance:

FastMaintainable

val counts =
  textFile.flatMap{line =>
      line.split(" ")
        .filter(word => word.contains("a"))
        .map(word => (word, 1))
    }
    .reduceByKey(_ + _)

val counts =
  textFile.flatMap(line => line.split(" "))
    .filter(word => word.contains("a"))
    .map(word => (word, 1))
    .reduceByKey(_ + _)
Rewrite rulesMacros & Inline
DefinedAnywhere in the program & librariesinside implementation
AppliedBased on analysisSyntax only
Influences typingNoYes
Works with Java methodsYesNo
Works across librariesYesNo
Best forsimple declarative rulesfull-blown metaprogramming

Plan: Integration with ScalaCheck


$ sbt test
+ Collections.twoFilters: OK, passed 100 tests.
+ Collections.isEmpty: OK, passed 100 tests.
+ Collections.twoDrops: OK, passed 100 tests.
+ Collections.mapFlatMap: OK, passed 100 tests.
+ Collections.mapMap: OK, passed 100 tests.

Thank you!

See my other talks.

Q&A