Benchmarking Scala with ScalaMeter, Pt. 2 (Scala DCP #004)
Tags: scala, challenge, beginners, dailycodingproblem
Published: 2020-03-27 13:20:02

[Daily Coding Problem](https://dailycodingproblem.com/) is a website which will send a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Scala, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

### Problem

This is a continuation of [my earlier post](https://dev.to/awwsmm/benchmarking-scala-with-scalameter-pt-1-scala-dcp-004-28c4), where I provided three different methods for solving Daily Coding Problem #004 using Scala. In this second section, I'll benchmark these three solutions (in time and memory usage) using [ScalaMeter](https://index.scala-lang.org/scalameter/scalameter), a [Scala-focused benchmarking tool](http://scalameter.github.io/) which is [preferred by some Scala language developers over JMH](https://github.com/scala/collection-strawman/pull/19) and has previously been featured [here on DEV.to](https://dev.to/frosnerd/microbenchmarking-your-scala-code-4885)!

### Strategy

ScalaMeter's website has [an easy-to-follow example](http://scalameter.github.io/home/gettingstarted/0.7/simplemicrobenchmark/index.html) showing how to do a simple benchmark. Essentially what we do is generate some sample data, then pass it to each method we want to benchmark. Of the [available predefined test configurations](http://scalameter.github.io/home/gettingstarted/0.7/configuration/index.html), the one which works best for this example is [`Bench.OfflineReport`](https://www.javadoc.io/doc/com.storm-enroute/scalameter_2.13/latest/org/scalameter/Bench$$OfflineReport.html). This will run each benchmark in a separate JVM and generate an HTML report for easy visualization.

> You can see [the other available configurations in ScalaMeter's scaladoc](https://www.javadoc.io/doc/com.storm-enroute/scalameter_2.13/latest/org/scalameter/index.html).

There are some bugs you have to work around since the documentation on the website is out of date, and things like [running multiple test classes](https://github.com/scalameter/scalameter/issues/159) as a suite of tests don't quite work. If you want a nicely-formatted HTML report, the best solution I've found so far is to simple put all of your code into a single benchmark `object` which `extends Bench.OfflineReport`:

```scala
object Benchmark extends Bench.OfflineReport {

  // benchmarks go here!

}
```

I put my three methods, as well as the random array generator, into another object called `DCP004` and import them at the top of `Benchmark`. My first working benchmark looked something like:

```scala
object Benchmark extends Bench.OfflineReport {
  import DCP004._

  performance of "Example #1: randArray(5, 0, 1)" in {

    val arrayLength = Gen.single("n")(5)
    val arrays = for (n <- arrayLength) yield randArray(n, 0, 1)

    using(arrays) curve "findMissingMutable" in findMissingMutable
    using(arrays) curve "findMissingInPlace" in findMissingInPlace
    using(arrays) curve "findMissingSet" in findMissingSet
  }

  // ...
}
```

In the above snippet, the methods `findMissingMutable()`, `findMissingInPlace()`, `findMissingSet()`, and `randArray()` are all defined in the `DCP004` object. The sample data are created by [`Gen`](https://www.javadoc.io/doc/com.storm-enroute/scalameter_2.13/latest/org/scalameter/Gen$.html)erators, which [create warmup data, as well](http://scalameter.github.io/home/gettingstarted/0.7/generators/index.html).

> If you're unfamiliar with the concept of _warming up_ the JVM, especially during benchmarking, check out [this SO post](https://stackoverflow.com/a/36198763/2925434), which gives a short overview.

`arrayLength` is what you might call a "pure" generator. It's defined by a method built into ScalaMeter. But ScalaMeter provides only a handful of built-in generators:

 - [`Gen.single()`](https://www.javadoc.io/static/com.storm-enroute/scalameter_2.13/0.19/org/scalameter/Gen$.html#single[T](axisName:String)(v:T)(implicitevidence$1:org.scalameter.picklers.Pickler[T]):org.scalameter.Gen[T]) -- which generates a single predefined value over and over
 - [`Gen.range()`](https://www.javadoc.io/static/com.storm-enroute/scalameter_2.13/0.19/org/scalameter/Gen$.html#range(axisName:String)(from:Int,upto:Int,hop:Int):org.scalameter.Gen[Int]) -- which generates a range of `Int`s, given a minimum value, maximum value, and step size
 - [`Gen.exponential()`](https://www.javadoc.io/static/com.storm-enroute/scalameter_2.13/0.19/org/scalameter/Gen$.html#exponential(axisName:String)(from:Int,until:Int,factor:Int):org.scalameter.Gen[Int]) -- which generates an exponential range of `Int`s, given a minimum value, maximum value, and multiplicative factor

...and a few others. Note that `exponential()` and `range()` only generate `Int` values and have to be processed to generate, for instance, `Double`s. You can build _composed generators_ from these basic generators by using `for` expressions. For example:

```scala
val answers = Gen.single("ASCII *")(42)
val decimals = for (answer <- answers) yield answer / 100.0
```

...this will generate the decimal value `0.42` over and over each time the `decimals` generator is used. In my example above, instead of just generating `Double`s, I use a composed generator to generate entire random arrays:

```scala
val arrayLength = Gen.single("n")(5)
val arrays = for (n <- arrayLength) yield randArray(n, 0, 1)
```

These arrays are then passed to each of the `using` statements, which each spawn a new JVM, independent of any other `using` statements, perform a full warm-up, then benchmark the included code. The `curve "name"` syntax allows us to generate an HTML report with multiple named curves, so all of our results can be easily compared. Here's an example of what that HTML report might look like:

![Simple Benchmarking HTML Report](https://dev-to-uploads.s3.amazonaws.com/i/di3pwgxad8vwguoolflr.png)

In the sidebar, we have a legend / menu which tells us what each of the bars represent:

![Simple Benchmarking Legend](https://dev-to-uploads.s3.amazonaws.com/i/di46mbaimcsggyzw6mzb.png)

Selecting and deselecting these `curve`s, which we defined in our code above, will make them disappear and reappear in the plot. Also notice the x-axis selection at the bottom of the plot area. When we run tests with more x-values, we'll have the option of selecting additional points here. In fact, let's do that right now:

```scala
  performance of "Example #2: randArray(n, 0, 1) -- linear" in {

    val arrayLength = Gen.range("n")(100, 1000, 100)
    val arrays = for (n <- arrayLength) yield randArray(n, 0, 1)

    using(arrays) curve "findMissingMutable" in { findMissingMutable }
    using(arrays) curve "findMissingInPlace" in { findMissingInPlace }
    using(arrays) curve "findMissingSet" in { findMissingSet }
  }
```

This is the second benchmark I've included inside `object Benchmark`. It uses a `range` generator to generate values on the range `[100, 1000]` (inclusive on both ends) with an interval of `100`. So, using a composed generator, we can generate random arrays of length `100`, `200`, `300`, ..., `1000`, and time how long it takes our implementations to find the smallest missing positive integer in the array. This code will generate a different plot in our HTML report, something like:

![Benchmark with linearly-spaced array lengths](https://dev-to-uploads.s3.amazonaws.com/i/k6bndx7xkmns1y2rpxwx.png)

We can start to see some trends now. It looks like `findMissingInPlace` (purple) and `findMissingSet` (brown) are more or less comparable in the time it takes them to find the smallest missing positive integer in their respective arrays. But `findMissingMutable` (red) seems to blow them out of the water, requiring only `0.02` ms on average for `n = 1000`, while `findMissingInPlace` and `findMissingSet` require `0.30` and `0.20` ms, respectively -- ten times slower!

> You can find the values of the points in the plots by inspecting the `data.js` file which is created when an `OfflineReport` HTML report is generated. The data are presented in JSON format and all benchmark times are reported in milliseconds. Or, if you don't want to sift through the JSON data, you can screenshot the plot and use Ankit Rohatgi's [WebPlotDigitizer](https://apps.automeris.io/wpd/) to get approximate values -- that's what I did.

Will this trend hold for larger values of `n`? There's only one way to find out...

```scala
  performance of "Example #3: randArray(n, 0, 1) -- exponential" in {

    val arrayLength = Gen.exponential("n")(2, Math.pow(2, 16).toInt, 2)
    val arrays = for (n <- arrayLength) yield randArray(n, 0, 1)

    using(arrays) curve "findMissingMutable" in { findMissingMutable }
    using(arrays) curve "findMissingInPlace" in { findMissingInPlace }
    using(arrays) curve "findMissingSet" in { findMissingSet }
  }
```

To get even bigger arrays, I decided to use an `exponential` generator, starting with arrays of length `2` and doubling up to `65536` (`2^16`). What does this benchmark look like? I'm glad you asked:

![Benchmark with exponentially-spaced array lengths](https://dev-to-uploads.s3.amazonaws.com/i/rnhjsnlh08321blp7k0t.png)

`findMissingInPlace` (silver) and `findMissingSet` (mustard) are statistically indistinguishable performance-wise, over this range. If you want a solid Scala-style solution, and you're not extremely concerned with performance, either of these implementations should be fine.

__However__, if you are concerned about the running time of the algorithm, neither of these implementations can compete with `findMissingMutable`, our Java-style solution which absolutely destroys the other implementations, requiring an order of magnitude less time to solve this problem. There is not a single point on this graph where `findMissingMutable` isn't the most performant solution.

So that's it! `findMissingMutable` wins!

---

...okay, you're right, I only looked at the length of the arrays and not the other parameters, `fracBad` and `maxScaling`. Luckily, ([we can easily run multidimensional benchmarks using ScalaMeter](https://github.com/scalameter/scalameter/issues/95)). All we have to do is use another composed generator -- this time, with multiple [_enumerators_](https://docs.scala-lang.org/tour/for-comprehensions.html) which are all simple generators themselves:

```scala
  performance of "Example #4: randArray(a, b, c)" in {

    val arrayLength = Gen.exponential("n")(2, Math.pow(2, 20).toInt, 2)
    val pctBad = Gen.range("fracBad")(0, 100, 5)
    val pctScaling = Gen.range("maxScaling")(25, 300, 5)

    val arrays = for {
      length <- arrayLength
      bad <- pctBad
      scale <- pctScaling
    } yield randArray(length, bad / 100.0, scale / 100.0)

    using(arrays) curve "findMissingMutable" in { findMissingMutable }
    using(arrays) curve "findMissingInPlace" in { findMissingInPlace }
    using(arrays) curve "findMissingSet" in { findMissingSet }
  }
```

ScalaMeter is smart enough to understand that we want to benchmark these methods across all of the 3-dimensional points defined by the `arrayLength`, `pctBad`, and `pctScaling` ranges. I let the array length get all the way up to 1 million elements (`2^20`), and tested `fracBad` and `maxScaling` over a huge range of values. This test took a few hours to run on my personal laptop and the results...

![Multidimensional benchmark](https://dev-to-uploads.s3.amazonaws.com/i/cw0h5brakdi2idy2spyw.png)

...are a bit difficult to understand? You could, of course, pull this data out of the JSON file and plot it in a more robust environment (maybe an R shell?), but you inspect it very easily in ScalaMeter, which -- at the moment -- only offers line and bar plots by default.

> ScalaMeter's documentation suggests that you should be able to [create your own custom chart types](http://scalameter.github.io/home/gettingstarted/0.7/reporters/index.html), but the source code [seems to suggest otherwise](https://github.com/scalameter/scalameter/search?q=ChartReporter&unscoped_q=ChartReporter). (This functionality seems to be missing entirely.)

We can tidy the plot a bit by only looking at particular ranges of values, though. __By dragging the boxes underneath the plot, we can select a different parameter to plot on the x-axis.__ It looks like `fracBad` affects the outcome much more drastically than `maxScaling`...

![Impact of `fracBad` on performance](https://dev-to-uploads.s3.amazonaws.com/i/ez1tc66ej718hbr0z6uu.png)

...at least over the ranges we've provided:

![Impact of `fracBad` on performance](https://dev-to-uploads.s3.amazonaws.com/i/6uw714kwy4ejj0xb628m.png)

I say this because, in the plot above, the performance of the algorithms as a function of `fracBad` can be found along the x-axis. For `findMissingSet` (orange) this is a range of about `275` ms down to about `2` ms, over 2 orders of magnitude. But when looking at any particular value of `fracBad`, say `45` percent, the performance range relative to the median performance is much smaller -- about `115` ms to about `140` ms. Only about a 15% variation relative to a median of about `130` ms.

So let's pick one value of `fracBad` and look at the performance as a function of `n` and `maxScaling`:

![Impact of `maxScaling` and `n` on performance](https://dev-to-uploads.s3.amazonaws.com/i/kg54z4ceubw9hftja35j.png)

In every case, `findMissingMutable` (light blue) is the fastest implementation, by about an order of magnitude over `findMissingInPlace` (dark blue) and `findMissingSet` (orange). I think it's safe to say that `findMissingMutable` is far and away the most performant of these three algorithms. And, since it's an in-place algorithm, it's likely the most performant in terms of memory usage, as well.

I say "most likely" because I've tried to benchmark the memory footprint of these algorithms using ScalaMeter but have so far been unable to do so. [According to ScalaMeter's documentation](https://scalameter.github.io/home/gettingstarted/0.5/executors/), "ScalaMeter can measure memory footprint starting from version 0.4. `Measurer.MemoryFootprint` is a measurer the measures the memory footprint of the object the return value of the benchmark snippet references."

This is fine, but our algorithms only _return_ `Int`s. What we really want to measure is not the memory footprint of the return value but the memory required while running the particular algorithms. As far as I can tell, this is not currently possible with ScalaMeter.

> Also, because of the way it calculates memory footprints, ScalaMeter can sometimes yield confusing [(even negative)](https://github.com/scalameter/scalameter/issues/201) results for memory usage.

[This tutorial only scratches the surface of what's available in ScalaMeter](http://scalameter.github.io/home/gettingstarted/0.7/executors/index.html). You can choose to ignore measurements in which the garbage collector runs, introduce noise into your measurements, remove outliers, specify the minimum and maximum number of warmup runs, run regression tests, and more. ScalaMeter also nicely integrates with sbt, the Scala Build Tool.

All in all, I'm moderately happy with ScalaMeter. It's a nice library for doing small performance comparisons among competing implementations of an algorithm. However, it doesn't seem to be very well-documented. The Scaladoc itself offers almost no help when it comes to trying to implement things which aren't specifically spelled out on the website or in people's responses to ScalaMeter's GitHub issues. It's a library which has the potential to be very beginner-friendly, but has a long way to go to realising that promise, in my opinion.

You can play around with the HTML report I generated at [awwsmm.com/resources/DCP/ScalaMeter](https://awwsmm.com/resources/DCP/ScalaMeter/).

---

All the code for my Daily Coding Problems solutions is available at [github.com/awwsmm/daily](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by <a href='https://ko-fi.com/Z8Z811E9B'>buying me a coffee</a>!