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:

Sources of slowdowns:

• Libraries
• User code

Library as a source of slowdown

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
}

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

Have ~same cost:

• single boxing(allocation)
• 5 dynamic dispatches
• 15 static dispatches
• 20 additions

Scala allows building convenient libraries:

• higher-order types
• generic methods
• generic classes
• multiple inheritance
• pattern matching
• lazy evaluation
• garbage collection

Does JVM support these features:

• higher-order types
• generic methods
• generic classes
• multiple inheritance
• pattern matching
• lazy evaluation
• garbage collection

All of those features need to be lowered by compiler.

Lowering is done in a conservative way.

Compiler needs to lower generics:

def plus[T](a: T, b: T)(implicit num: Numeric[T]): T =
  num.plus(a, b)

is compiled into

def plus(a: Object, b: Object, num: Numeric): Object =
  num.plus(a, b)

How does plus(1, 1) look like?

unbox(plus(box(1), box(1), intNum))

What if the compiler cloned generics

def plus(a: Int, b: Int, num: Numeric[Int]): Int =
  num.plus(a, b)
def plus(a: Long, b: Long, num: Numeric[Long]): Long =
  num.plus(a, b)
def plus(a: Double, b: Double, num: Numeric[Double]): Double =
  num.plus(a, b)
...

Scala has 9 primitive types:

• int, long, short, byte, char
• float, double
• boolean, void

+ we need a reference type.

= 10 types total.

class T[A1, A2, ..., An]

How many combinations are there?

10 ^ n

class T[A1, A2, ..., An] {
  def foo[B1, B2, ..., Bn] =  ...
}

How many combinations are there?

10 ^ (n + m)

Ok, you don't need all specializations of all methods.

Dragos(2010): Ask your user!

@specialized (2010)

• Mark type arguments to be specialized
• can specify what types should be used
• limitation - no inheritance.

@miniboxed (2012)

• Made it simpler by having 3^n instead of 10^n
• some performance degradation
• handles inheritance
• has problems with arrays
• complicated implementation

Let's say you develop a library:

For demonstration, take scala.Function3[A1, A2, A3, R]

• Should you specialize?
• what types should you specialize for?
• One size fits them all?

@specialization\miniboxing break modularity

Are there other options?

trait Function3[-T1, -T2, -T3, +R]

How many specializations are needed?

• Specialization: 10000 classes
• Miniboxing: 81 classes

Wrong question!

How many specializations are needed in your code?

Imprecise question!

How many specializations are needed in your app including libraries?

Auto specialization in the Dotty linker

• takes your program & libraries
• analyzes how you use them
• sees what instantiations are needed
• specializes them
• no need to annotate types and break modularity.

Implementation artifact:

Type-arguments and term-args are treated in the same way.

def foo[T](x: Seq[T], id: Int) = x(id)

• Type specialization removes boxing
• Term specialization removes virtual dispatch

Benchmarks

val arr = (1 to 10000000).toArray
arr.reduce(_ + _).toDouble / arr.length

Compilation time

Auto specialization: Limitations

• slows down compilation(~1.50x on average)
• requires dependencies to have TASTY
• does not help if library does tricks:
• uses null as a special value
• has typed API but untyped internals

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:

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

We need library specific optimizations

Library defined rewrite rules

x.length == 0

becomes

x.isEmpty

import dotty.linker._

@rewrites
object CollectionOptimization {
  def isEmpty(x: Seq[Int]) =
    Rewrite(from = x.length == 0,
            to   = x.isEmpty)

Conditional rewrites: Constants

def bigIntShift(bi: BigInt, a: Int)(implicit evi: IsLiteral[a.type]) =
  Rewrite(from = bi / a,
     to =
      if (Integer.bitCount(a) == 1)
        bi >> Integer.numberOfTrailingZeros(a)
      else bi / a
     )

BigInt(10) / 2

becomes

if (Integer.bitCount(2) == 1)
  BigInt(10) >> Integer.numberOfTrailingZeros(2)
else BigInt(10) / 2

Conditional rewrites: Purity

List(1, 2, 3).filter(_ > 1).filter(_ > 2)

becomes

List(1, 2, 3).filter(x => x > 1 && x > 2)

def twoFilters(x: List[Int], a: Int => Boolean, b: Int => Boolean)
  (implicit apure: IsPure[a.type]) =
    Rewrite(from = x.filter(a).filter(b),
            to   = x.filter(x => a(x) && b(x)))

Custom warnings and error messages

def parallelReduceLeft(ps: ParSeq[Int]) =
  ps.reduceLeft(_ + _)

[warn] TestPar.scala:40: reduceLeft on a parallel collection makes no sense
[warn]     List(1, 2, 3).toPar.reduceLeft(_ + _)
[warn]                        ^

def customFancyWarning(ps: ParSeq[Int], x: (Int, Int) => Int) =
    Warn(pattern = ps.reduceLeft(x)),
             msg = "reduceLeft on a parallel collection makes no sense")

Easy logging

import java.util.Logging._

def traceOpt(l: Logger, x: Any) =
    Rewrite(from = l.info(x),
              to = if (l.isLoggable(INFO)) l.log(TRACE, x)
            )

Easy debug messages

def prettyPrint(l: Logger, x: Any)(implicit source: Source[x.type]) =
    Rewrite(from = l.prettyPrint(x),
              to = println(source + " = " + x))

Do you have to choose between macros and rules?

No!

def metaExample[T](x: List[T]) =
Rewrite(from = x.toString,
          to = meta { /* entry point to interpreted scala.meta macros */})

Macros More in Eugene's talk tomorrow.

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.

Current status:

• prototype, unstable
• HotSpot currently randomly segfaults when running optimized List.flatMap
• Lines of code(cf @specialized 2000+, @miniboxing 5000+)
  • Analysis: 1300
  • Specialization: 900
  • Rewrites: 500
• some collections do not benefit(vector)
• List\Array\Range\ListBuffer\etc work perfectly
• https://github.com/dotty-linker/dotty

Standing on the shoulders of giants:

• Dragos: @specialized
• Ureche: @miniboxing
• Burmako: TASTY
• Lhotak: Static analysis
• Odersky: Dotty & supervision

Thank you!

See my other talks.