Havlak benchmark for Kotlin: call for participation


#1

Hello,

I took the Scala/Java sources from Robert Hundt’s Havlak benchmark and “ported” them to Kotlin. That benchmark was initially done to get an estimate how Google Go compares in performance to other languages like C/C++, Scala, Java, and others. See ws3-1-Hundt.pdf.https://days2011.scala-lang.org/sites/days2011/files/ws3-1-Hundt.pdf

The port to Kotlin is 99.5% finished. There is some bug somewhere as the Kotlin program completes much too quickly. When LoopTesterApp.main is run (vm args -server -Xss15500k must be provided to prevent stack overflow) it says:

# of loops: 1 (including 1 artificial root node) # of BBs  : 252013

Which is wrong. It should be:

# of loops: 121002 (including 1 artificial root node) # of BBs  : 252013

Now I’ve spent quite some time on this and the Groovy port (which is finished) and would like to spend my week-ends on something else. I’ve uploaded the Kotlin code to Github: https://github.com/oplohmann/havlak-jvm-languages. Anybody who feels like tracing down the bug and fixing it (and maybe improving the Kotlin code …) is cordially invited to join in. I want to write a report somewhen that includes the measurements for Xtend. Then all JVM languages that integrate well with Java are covered. Don’t worry, anybody who helped out in getting the Kotlin version to run will certainly receive some honorable mentioning once I will sit down to write that report ;-).

Cheers, Oliver


#2

Hi, Oliver

You can see draft version of my port at:
https://github.com/bashor/benchmarks_kt/blob/master/jvm/src/Havlak_from_dart.kt
https://github.com/bashor/benchmarks_kt/tree/master/jvm/src/havlak

Maybe it will help you... For example, if you want fix your version, you can replace some your classes of my classes to understand what piece is not working properly Or you can just take my implementation, but this is not the final version.


#3

Hi bashor,

thanks for your work. I think I will stick with your code as it seems to be better idiomatic Kotlin. Couldn’t resist to do a quick test run before getting to work (all measurements using JDK1.7):

Java: 52070 ms
Kotlin: 35985 ms
Scala: 27024 ms
Scala ArrayList: 47276 ms
Groovy static with indy: 59814 ms
Groovy static without indy: 62309 ms
Groovy dynamic without indy: 84566 ms

So Kotlin is doing extremely well. I replaced the functional lists iused in the Scala version with plain ArrayLists to be more fair with the other languages. The result was that performance dropped from 27024 ms to  47276 ms. Wonder what they do with those functional lists …

More later. Have to start the day now, but will write a report about the whole undertaking and paste a link here. May take 1-2 weeks though.

Regards, Oliver


#4

Okay, I fixed my own crude Kotlin code now (it is commited to github). And alas, it takes 64166 ms... This makes me think whether the Scala code was tweaked in that benchmark. Seems like it can be done very easily.

– Oliver


#5

Just replaced in ScalaArrayList all Scala Sets with Java HashSets and now the calculation time increases to 76820 ms ...


#6

Well, interest in this Kotlin performance comparison wasn't really overwhelming. There is one update I want to share that is still worth being mentioned, I think. I changed in the HavlakLoopFinder.findLoops() method this code:

var nonBackPreds = Array<MutableSet<Int>>(size, {HashSet<Int>()}) var backPreds = Array<MutableList<Int>>(size, {ArrayList<Int>()}) var number = HashMap<BasicBlock, Int>() var header = Array<Int>(size, {0}) var types = Array<BasicBlockClass>(size, {BasicBlockClass.BB_LAST}) var last = Array<Int>(size, {0}) var nodes = Array<UnionFindNode>(size, {UnionFindNode()})

to this code:

val nonBackPreds = ArrayList<ArrayList<Int>>(size) val backPreds = ArrayList<ArrayList<Int>>(size) val number = HashMap<BasicBlock, Int>() val header = ArrayList<Int>(size) val types = ArrayList<Int>(size) val last = ArrayList<Int>(size) val nodes = ArrayList<UnionFindNode>(size)

size.times {
  nonBackPreds.add(ArrayList<Int>())
  backPreds.add(ArrayList<Int>())
  header.add(0)
  types.add(0)
  last.add(0)
  nodes.add(UnionFindNode())
}


So I’m doing it now in this regard the same way as bashor. I would say the change is legal in the sense that it does not signify a language-specific optimization making the performance comparison with Scala/Java/Groovy “unfair”.

The execution time is now 49040 ms. This is still a bit faster than the Java version with 52070 ms. My Havlak port to Kotlin is basically a direct port from the Scala code. So you can say that Kotlin does quite a bit better than Scala and still a bit better than Java. And Kotlin is now 0.5. There is still a lot of room for further oipimization till Kotlin 1.0 :-). By the way, it looks like the Array class in Kotlin or its initializer does not perform as well as class ArrayList.

– Oliver


#7

bashor did some nice work to improve the Kotlin code, which is more idiomatic now. AFAIKS it is about beautifying the code only and not about performance tuning.The code is here. If run on the same machine, the other measurements in this thread were made on, it takes 56672 ms. Then bashor did some additional performance tuning. The code of this is here. For this version the execution time is 20246 ms. Ikke dårligt ...

– Oliver


#8

Hello,

I took kotlin-initial for a spin with M7 (0.7.270). First, the code was changed to work with M7. The M7 code can be found here: kotlin-initial-m7. Only thing I did was removing those constructor { } statements mit ;{ }. Everything else compiled fine. With pre-M7 the benchmark takes around 52.070 ms to run (see link). I think it was Kotlin 0.5.162 (embarassingly, I’m not exactly sure, but it was some M5 version).  With M7 it takes on the same machine with the same JDK (JDK1.7.0_06) around 71.000 ms (I repeated it several times). So there seems to be a little performance degradation. Just thought I should pass this on. The earlier it is detected the easier it is to do something about it ;-).

Regards, Oliver


#9

Thanks a lot for your report, we will investigate