Performance regression in Scala 2.13 for creation of lists using `mutable.ListBuffer`

[plokhotnyuk]

For small lists it can be slowdown in ~1.5x times with OpenJDK and in ~7x times with GraalVM.
Most parsers which use it to bind parsed data to List or Seq (because List is a default implementation of Seq) from text or binary messages are affected.

Code of the benchmark to reproduce:

import java.util.concurrent.TimeUnit
import org.openjdk.jmh.annotations._
import scala.collection.mutable.ListBuffer

@State(Scope.Thread)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 1, jvmArgs = Array(
  "-server",
  "-Xms2g",
  "-Xmx2g",
  "-XX:NewSize=1g",
  "-XX:MaxNewSize=1g",
  "-XX:InitialCodeCacheSize=512m",
  "-XX:ReservedCodeCacheSize=512m",
  "-XX:+UseParallelGC",
  "-XX:-UseBiasedLocking",
  "-XX:+AlwaysPreTouch"))
@BenchmarkMode(Array(Mode.Throughput))
@OutputTimeUnit(TimeUnit.SECONDS)
class ListBufferBenchmark {
  @Param(Array("1", "10", "100"))
  var size: Int = 1000

  @Benchmark
  def intListCreation: List[Int] = {
    val squares = new ListBuffer[Int]()
    var i = 0
    val l = size
    while (i < l) {
      squares += i * i
      i += 1
    }
    squares.toList
  }
}

Command to run:

sbt -java-home /usr/lib/jvm/jdk-11 -no-colors ++2.13.0 'jmh:run ListBufferBenchmark'

Results for Scala 2.13.0 with OpenJDK 11.0.3:

[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                            (size)   Mode  Cnt          Score        Error  Units
[info] ListBufferBenchmark.intListCreation       1  thrpt    5  129974588.015 ± 249971.629  ops/s
[info] ListBufferBenchmark.intListCreation      10  thrpt    5   15160739.436 ±   6815.066  ops/s
[info] ListBufferBenchmark.intListCreation     100  thrpt    5    1415746.679 ±  12507.797  ops/s

Results for Scala 2.12.8 with OpenJDK 11.0.3:

[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                            (size)   Mode  Cnt          Score         Error  Units
[info] ListBufferBenchmark.intListCreation       1  thrpt    5  184201868.557 ± 1525301.419  ops/s
[info] ListBufferBenchmark.intListCreation      10  thrpt    5   21833324.557 ±  540564.835  ops/s
[info] ListBufferBenchmark.intListCreation     100  thrpt    5    1767339.444 ±   23828.567  ops/s

Results for Scala 2.13.0 with GraalVM CE 19.1:

[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                            (size)   Mode  Cnt         Score        Error  Units
[info] ListBufferBenchmark.intListCreation       1  thrpt    5  33947057.954 ± 509483.584  ops/s
[info] ListBufferBenchmark.intListCreation      10  thrpt    5   6072784.266 ±  22838.907  ops/s
[info] ListBufferBenchmark.intListCreation     100  thrpt    5    624114.322 ±   4138.885  ops/s

Results for Scala 2.12.8 with GraalVM CE 19.1:

[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                            (size)   Mode  Cnt          Score        Error  Units
[info] ListBufferBenchmark.intListCreation       1  thrpt    5  238624457.791 ± 859161.435  ops/s
[info] ListBufferBenchmark.intListCreation      10  thrpt    5   30777424.910 ± 427876.116  ops/s
[info] ListBufferBenchmark.intListCreation     100  thrpt    5    1989475.540 ±  21622.259  ops/s

[plokhotnyuk]

I suppose that the root cause of slowdown is the releaseFence() call that was added in the following commit:
scala/scala@6541df7

@retronym wdyt?

[Ichoran]

If it is releaseFence there isn't much we can do. It is absolutely required to avoid a correctness issue with 2.12.8 that could make it dangerous to use List in a threaded environment.

The issue is this. Suppose you map a 2-element list. You have:

a :: b :: Nil

The map operation, since it can't know how long the list is, uses a ListBuffer which walks through in order producing

f(a) :: Nil

at first; then it walks to the next one and mutates the next pointer to yield

f(a) :: f(b) :: Nil

It then returns the head of the list, and everything is cool because nobody else has access to mutate the next pointer.

Unfortunately, that is only true within the same thread. If you hand f(a) :: ? off to some other thread, it isn't guaranteed to see the change without a releaseFence.

So you give it to the other thread and it occasionally sees, instead, f(a) :: Nil because the pointer change is still floating around in the CPU and hasn't made it out to main memory yet (or due to some other caching issue, like the other CPU relying on its cache instead of going to main memory).

This is just terrible. The whole rhetoric around immutable collections is that they're great for concurrent use because they don't change, and here you have a difficult to reproduce, stochastically appearing bug that mutates what you can see about your List.

Fortunately, this is difficult to trigger, but we absolutely have to keep the fix for this.

So, what is the workaround? Well, if you know the sizes, you can always build the list up manually using :: instead of using something that relies on ListBuffer. Alternatively, perhaps some of the methods of List can speculatively try to unroll the operation on the stack, and then if it gets too deep they could give up and switch to ListBuffer.

Anyway, this is not an easy problem, and you very much can't just say, "Well, releaseFence made it slower, so let's remove it again". It's there for a very good reason. (Also, there are other reasons the benchmarks could change, so it would be good to do them over again in 2.13 with List duplicated into, say, Lyst and LystBuffer, with the y-version missing the fence. Have to duplicate :: too, so it's a bit of work.)

[plokhotnyuk]

@Ichoran could you share a source of the test which reproduces the issue explained above? which data structure or API is used to pass an instance of a recently created list in it? usually, any concurrency aware implementation which is going to pass data between threads use fences to do it safely, so no need to do it prematurely for construction of each list instance...

[Ichoran]

I don't remember a test case and I don't have time to write one. I'd guess that something like this would work, but I don't have time to test/optimize it:

class Sketch {
  @volatile var xs = 0 :: 1 :: Nil
  val t1, t2 = new Thread {
    private[this] var n = 10000000
    override def run() {
      while (n > 0) {
        xs = xs.map(_ + 1)
        n -= 1
      }
    }
  }
  def test() {
    t1.start()
    t2.start()
    t1.join()
    t2.join()
    println(xs)
  }
}

You'll expect to see things skipped, but the list should always have two elements, and the values should always be 1 apart.

(When I run this I don't see errors, but the errors were never consistently found anyway. I'm not sure where the old reports are.)

[plokhotnyuk]

@Ichoran this test will pass always because access to volatile vars in JVM uses store/load fences

BTW, JFYK: https://dzone.com/articles/cpu-cache-flushing-fallacy

"The cache sub-system is considered the "source of truth" for mainstream systems. If memory is fetched from the cache it is never stale; the cache is the master copy when data exists in both the cache and main-memory. This style of memory management is known as write-back whereby data in the cache is only written back to main-memory when the cache-line is evicted because a new line is taking its place."

[Ichoran]

Yeah, so drop the @volatile and maybe make other changes. Like I said I don't have time to replicate the error.

You're right that I wasn't accurate with regard to cache; it's the register/cache boundary, not the cache/main memory boundary that can lead to inconsistent views of things. I think the result is architecture-dependent, too. In any case, the JMM doesn't promise that you can see b in the second thread unless you enforce ordering somehow, and people have observed it in practice although I haven't ever been able to on my machines IIRC (including running the exact test that they say gave errors on theirs).

So I'm not entirely surprised that I failed once again to see anything.

[plokhotnyuk]

@Ichoran If you drop the volatile annotation you will lose fences and, possibly, for some combination of JVM/CPU you will get that kind of data races which you are going to reproduce.

But it should not be the reason for adding fences in immutable collections that don't grow on demand (like a stream) in Scala.

Please see charts bellow with results of benchmarks where JSON array of 128 boolean values was parsed to List[Boolean] on different JVMs. For smaller sizes the slowdown is much worse.

Scala 2.12.8:

Scala 2.13.0:

[jsfwa]

@plokhotnyuk, @Ichoran this is an example of an issue described above

But it looks like this behavior is relevant and easily reproducible(at least in my case) only for JDK8, and works correctly for the newer java versions
Also, all evidence of that unexpected behavior are pretty old and indirectly confirm unnecessity of "good reasoning" barriers without actual purpose for modern jvm
Actually can be easily reproducible, but still doesn't justify inner barriers

[plokhotnyuk]

@jsfwa in that gist thread the root problem not in List or ListBuffer.

In the 1st sample it is just missing fences when accessing X.x variable from 50 threads. Nobody passes messages in such way these days, a lot of concurrent structures and APIs (like futures, actors, concurrent streams) are used instead and each has own mechanics to make the passing of immutable messages safely.

In the 2nd Message is mutable and if it is already shared between threads store/load fences for _words should be used too, like in this commit. BTW, the original snippet for Message doesn't compile, I suppose, the author tried to write something like that:

class Message(val text: String) {
  private[this] var _words: List[String] = _

  def words: List[String] = {
    var res = _words 
    if (res == null) {
      res = text.split("""\s""").toList
      _words = res
    }
    res
  }
}

Why not just use lazy val here?

[jsfwa]

@plokhotnyuk I totally agree that everyone should use fences and other tricks with concurrent writers

Mentioned gist is a part of this discussion, since a tail of :: is mutable, guys decided to enforce thread-safety

Sadly the cost is too high, hope they will revert the changes

[plokhotnyuk]

In this PR I have tried to mitigate the issue by appending lists manually. For JDK 11.0.3 it works even faster that with ListBuffer, but when running on GraalVM EE 19.1 the slowdown still exists and a flame graph report shows that there is the releaseFence call in the :: (cons) constructor:

JDK 11.0.3 + Scala 2.13.0:

GraalVM EE 19.1 + Scala 2.13.0:

[retronym]

@plokhotnyuk What CPU architecture are you testing on? I assume x86 but want to be sure.