TrieMap method getOrElseUpdate is not thread-safe

[scabug]

The ScalaDoc states that a scala.collection.concurrent.TrieMap is thread-safe:

A concurrent hash-trie or TrieMap is a concurrent thread-safe lock-free implementation of a hash array mapped trie.

But the method getOrElseUpdate of scala.collection.mutable.MapLike is not overridden and is therefore not thread safe:

  def getOrElseUpdate(key: A, op: => B): B =
    get(key) match {
      case Some(v) => v
      case None => val d = op; this(key) = d; d
    }

This issue can be recreated with the following code:

import scala.collection.concurrent.TrieMap

object TrieMapApp extends App {
  object ApplyMeOnce {
    var applied = false
    def apply() = synchronized {
      require(!applied)
      applied = true
    }
  }

  val map = TrieMap.empty[String, Unit]

  val runnable = new Runnable {
    def run() = {
      try {
        map.getOrElseUpdate("Result", ApplyMeOnce())
      } catch {
        case e: Exception => exception = Some(e)
      }
    }
  }

  var exception: Option[Exception] = None

  while (exception == None) {
    1 to 10 map { i => new Thread(runnable, i.toString) } foreach { thread => thread.start() }
    println(exception)
  }
  println(exception)
}

Please let me know if you need more information.

As a workaround you can write:

synchronized { map.getOrElseUpdate("Result", ApplyMeOnce()) }

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-7943?orig=1
Reporter: Matthew Roberts (mattroberts297)
Affected Versions: 2.10.2, 2.10.3

[scabug]

@retronym said:
Alex, could you please take a look at this?

[scabug]

@axel22 said:
Sure.
This can be solved easily by implementing getOrElseUpdate with a combination of get and putIfAbsent.
The downside that the TrieMap might occasionally evaluate the call-by-name parameter even if it does not store it into the tree in the end.

This bug report complains about exactly that - it expects
A real problem with getOrElseUpdate not addressed in this bug report is that there is currently no

There are 4 solutions:

1. Relax the contract of getOrElseUpdate to potentially allow evaluating the call-by-name parameter.
2. Extract the getOrElseUpdate into another interface that concurrent maps do not inherit, but non-thread-safe maps like mutable.HashMap do.
3. Have ParTrieMap throw an exception for getOrElseUpdate.
4. There is a really dirty hack which involves modifying the Ctrie data-structure to be able to store call-by-name (or lazy, if you will) nodes that are evaluated the first time somebody hits them. Proper blocking synchronization in these nodes is a must. I don't like this.

Thoughts?

Btw, the proposed workaround with synchronized will fix the example in this bug report, but won't solve the issues, as there might exist other concurrent calls to e.g. put.

[scabug]

@retronym said:
Java's concurrent hash map doesn't offer this API AFAIK. So our wrapped version of that also can't implement this method in a way that would be unsurprising to the reporter.

I've always used Guava CacheBuilder for concurrent maps to implement memoization.

I'm not sure what the right approach is, let's discuss it in person next week.

[scabug]

@axel22 said (edited on Oct 31, 2013 4:02:19 PM UTC):
Ok. I think it might be solved with solution 4) by introducing a new kind of a leaf node to Ctrie called LazyNode, that holds a lazy value initialized only once instead of a strict SNode. So seems doable, but not sure if it's worth it - there might be other ConcurrentMap implementations in the future, or wrappers around concurrent maps from elsewhere, and seems to me that those will never work without hacking the implementation of the thing being wrapped.

[scabug]

@axel22 said (edited on Oct 31, 2013 4:04:35 PM UTC):
But, if you think that memoization is useful, I could implement this functionality separately from getOrElseUpdate and expose it on the TrieMap s.
I'm not so sure if it should be on the general ConcurrentMap s.

[scabug]

@axel22 said (edited on Oct 31, 2013 4:41:24 PM UTC):
Although, after further thought, it also seems to me that you could simulate this memoization behaviour easily:

import collection._

class Cache[K, V] {
  class LazyCell(compute: =>V) {
    lazy val value = compute
  }
  private val tm = concurrent.TrieMap[K, LazyCell]()
  def getOrElseUpdate(k: K, fresh: =>V): V = {
    val proposedCell = new LazyCell(fresh)
    val existingCellOpt = tm.putIfAbsent(k, proposedCell)
    if (existingCellOpt.nonEmpty) existingCellOpt.get.value
    else proposedCell.value
  }
}

object Main {
  def main(args: Array[String]) {
    val cache = new Cache[String, String]
    val v1 = cache.getOrElseUpdate("key1", { println("val1"); "val1" })
    val v1p = cache.getOrElseUpdate("key1", { println("val1 generation again"); "val1" })
    val v2 = cache.getOrElseUpdate("key2", { println("val2"); "val2" })
  }
}

Note that there's no way of avoiding the thunk creation above, and we're already in object-creation-land, so an additional LazyCell object should not be a huge issue. If it is, you could avoid creating it in most cases by first checking via get if there's an entry in the map already.

This means that any concurrent map that supports putIfAbsent can be wrapped to support getOrElseUpdate. This makes me more convinced that we should remove getOrElse from the ConcurrentMap interface.

[scabug]

Matthew Roberts (mattroberts297) said:
Hi Alex,

Thanks for looking at this. As a user, I'd prefer to have a smaller tightly defined interface (solution 2). Especially when dealing with concurrency. Whilst ideal, I can see solution 4 becoming a headache if the underlying implementation changes or the number of concurrent collections increases.

Thanks again,
Matt.

[scabug]

@retronym said:
Interesting. You probably want to clear the reference to the thunk once you've evaluated to avoid memory leaks, but otherwise that looks like a good pattern. But maybe we're missing something, can it be that easy?

[scabug]

@axel22 said (edited on Oct 31, 2013 5:19:06 PM UTC):
True - though, I'm not sure how we can clear the thunk reference, since a thunk type cannot be a var..

As for easiness - seems to me it should work.
There is only a single possible update to this cache, and that is putIfAbsent.
The putIfAbsent only atomically writes to the cache if the key previously was not there.
That means there is at most one lazy cell value that ends up in the cache.
And value is only called at the points in the code after it has been atomically ensured that the callee cell is already in the cache.
Thus, the thunk only gets evaluated once, and the lazy val in LazyCell is where the blocking synchronization happens.

You could also do a fast path:

def getOrElseUpdate(k: K, fresh: =>V): V = {
    val cell = tm.lookup(k)
    if (cell != null) cell.value
    else {
      val proposedCell = new LazyCell(fresh)
      val existingCellOpt = tm.putIfAbsent(k, proposedCell)
      if (existingCellOpt.nonEmpty) existingCellOpt.get.value
      else proposedCell.value
    }
  }

[scabug]

@axel22 said:
Matt, I agree with you, I'd vote for a more restrictive ConcurrentMap API too.
Especially since putIfAbsent and its friends seems strong enough to express other patterns like one-time memoization.

[scabug]

@retronym said:

  class LazyCell[V](var compute: () =>V) {
    lazy val value = { val temp = compute; compute = null.asInstanceOf[V]; temp }
  }
  def getOrElseUpdate(k: K, fresh: =>V): V = {
    val proposedCell = new LazyCell(() => fresh)
   ...

[scabug]

@axel22 said:
Ah, of course. But does that mean another wrapper function around fresh will be allocated?
Thought that there was some trick with just a reference to the thunk type.

[scabug]

@retronym said (edited on Oct 31, 2013 8:08:32 PM UTC):
That's optimized away:

scala> class C { def foo(a: => Any) = () => a }
defined class C

scala> :javap C
public scala.Function0 foo(scala.Function0);
  Code:
   Stack=1, Locals=2, Args_size=2
   0:	aload_1
   1:	areturn

[scabug]

@axel22 said:
Wow, didn't know that. And the :java command is nice.