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"

author	commits	additions	deletions	blame lines
Martin Odersky	2,280	146,133	85,391	66,698
Dmitry Petrashko	628	158,249	50,201	83,713
Samuel Gruetter	19	62,324	12,510	36,615
Others	144	5,315	2,108	4,161

Sources of slowdowns:

Libraries
User code

Library as a source of slowdown

Java Scala


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

Java	Scala 2.11	Scala 2.12.0-M3	ScalaBlitz	Linker	ScalaJS
45ms	872ms	680ms	42ms	68ms¹	2440ms

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:

Fast Maintainable


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 rules	Macros & Inline
Defined	Anywhere in the program & libraries	inside implementation
Applied	Based on analysis	Syntax only
Influences typing	No	Yes
Works with Java methods	Yes	No
Works across libraries	Yes	No
Best for	simple declarative rules	full-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.

Precise Types Bring Performance

About me:

Dotty contributor stats:

Sources of slowdowns:

Library as a source of slowdown

Why?

Java cycle body:

Why?

Scala cycle body:

Benchmarks

Maintainability vs Performance:

Maintainability vs Performance:

Plan: Integration with ScalaCheck

Thank you!

See my other talks.

Q&A