Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

TrieMap method getOrElseUpdate is not thread-safe #7943

Closed
scabug opened this issue Oct 30, 2013 · 42 comments
Closed

TrieMap method getOrElseUpdate is not thread-safe #7943

scabug opened this issue Oct 30, 2013 · 42 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Oct 30, 2013

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
Copy link
Author

scabug commented Oct 30, 2013

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
Copy link
Author

scabug commented Oct 31, 2013

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

@scabug
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

@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
Copy link
Author

scabug commented Oct 31, 2013

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

@scabug
Copy link
Author

scabug commented Nov 1, 2013

Matthew Roberts (mattroberts297) said:
Same here. Nice to know! Thanks Jason.

@scabug
Copy link
Author

scabug commented Nov 5, 2013

@axel22 said:
After a 10 minute discussion on the Scala meeting the conclusion was to relax the contract on the general map to allow to evaluate the thunk even though the value might not get stored in the map in the end.

@scabug
Copy link
Author

scabug commented Nov 5, 2013

@scabug
Copy link
Author

scabug commented Feb 10, 2014

@adriaanm said:
Since 2.11.0-RC1 is one week away, pushing all non-blockers without PR to 2.11.1-RC1. Please undo the change if I missed work in progress.

@scabug
Copy link
Author

scabug commented Aug 5, 2014

@gkossakowski said:
The 2.11.2 is out so I'm rescheduling the issue for 2.11.3.

@scabug
Copy link
Author

scabug commented Sep 24, 2014

Mikael Ståldal (mikaelstaldal) said:
Does this mean that in 2.11.3, scala.collection.concurrent.TrieMap will override the getOrElseMethod method in a properly thread-safe and atomic way?

If the contract is relaxed, I guess that this could be done in scala.collection.concurrent.Map instead, like this:

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

@scabug
Copy link
Author

scabug commented Sep 24, 2014

@axel22 said (edited on Sep 24, 2014 1:33:43 PM UTC):
I agree - this is if the contract is relaxed.

The basic problem here is that the semantics of the getOrElseUpdate method do not allow any lock-free (and a lock-based as well, unless the internal locks are somehow exposed) Map implementation. This bug report is not a problem of the TrieMap implementation, but the problem in the collection.Map interface and the collection.concurrent.Map interface.

Once this is fixed in the Map documentation with the following line:

Note: invoking this method may potentially evaluate the expression `op` multiple times without storing it in the map.

a fix similar to what you suggest can be added to the collection.concurrent.Map trait.

@scabug
Copy link
Author

scabug commented Nov 4, 2014

@retronym said:
Updating fix-by version to 2.11.5.

@scabug
Copy link
Author

scabug commented Dec 12, 2014

Morten Andersen-Gott (magott) said (edited on Dec 12, 2014 10:43:23 AM UTC):
Java8 has a version of this, with a new method in the ConcurrentMap:
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentMap.html#computeIfAbsent-K-java.util.function.Function-

Which also does not guarantee that the mapping function is called only once under racy conditions

@scabug
Copy link
Author

scabug commented Feb 10, 2015

Andrei Pozolotin (andrei.pozolotin) said:
so, whats the verdict: 1) will you make it atomic 2) or will you document that it is NOT atomic?

@scabug
Copy link
Author

scabug commented Feb 10, 2015

@axel22 said:
2) it will be documented as non-atomic.

@scabug
Copy link
Author

scabug commented Feb 10, 2015

Jeff Olson (jdolson) said:
Wait, I thought the accepted solution was to make it atomic but document the fact that the mapping function may be invoked more than once (as with the Java 8 ConcurrentMap implementation). Having it not be atomic is incredibly annoying, especially when the fix is so trivial.

@scabug
Copy link
Author

scabug commented Feb 10, 2015

@axel22 said:
Note - since the ConcurrentMap interface is enriched in Java 8, we might also consider doing this in Scala.
Since it's only a matter of time before we do, I will implement a computeIfAbsent method in TrieMap and override the getOrElseUpdate to call that.

Eventually, we want to do the same in ConcurrentMap, computeIfAbsent being abstract.

@scabug
Copy link
Author

scabug commented Feb 10, 2015

@axel22 said:
scala/scala#4314

@scabug
Copy link
Author

scabug commented Feb 10, 2015

Andrei Pozolotin (andrei.pozolotin) said:
just to confirm the verdict:
3) invocation will be atomic, but mapping function may be applied more the once
?

@scabug
Copy link
Author

scabug commented Feb 10, 2015

@axel22 said (edited on Feb 10, 2015 9:21:22 PM UTC):
Yes.

Specifically, in the case of the TrieMap, we could additionally make the invocation atomic and make sure that the mapping function is applied only once.
Note that this is not the case with all concurrent map implementations, and the concurrent.Map interface will not be able to guarantee this.

@scabug
Copy link
Author

scabug commented Feb 10, 2015

Morten Andersen-Gott (magott) said:
This is what is the case with the Java implementations. j.u.c.ConcurrentHashMap guarantees at most one (atomic) update per key, while j.u.c.ConcurrentMap only guarantees atomic updates (may be called more than once per key).

@scabug
Copy link
Author

scabug commented Feb 11, 2015

Andrei Pozolotin (andrei.pozolotin) said:
re: "we can make the invocation atomic and make sure that the mapping function is applied only once"
I am curious if you accept campaign contributions? I mean, how much will it take to make "applied only once" happen? :-)

@scabug
Copy link
Author

scabug commented Feb 11, 2015

@axel22 said:
The j.u.c.ConcurrentHashMap guarantees at most one mapping function invocation per computeIfAbsent, and once if the new value is also added to the map. It can do this because it uses locks under-the-hood.

In TrieMap, which is lock-free, we could achieve the invoke-mapping-function-only-if-inserted effect by creating a lazy node within the map.
Note that this means that the mapping function might be invoked after the computeIfAbsent returns, or even by some other thread. So:

  • this solution would not have exactly correspond to j.u.c.ConcurrentHashMap behavior - there is a difference in semantics, and we don't win consistency
  • the primary use-case for putting a side-effect into the mapping function (as is sometimes done with getOrElseUpdate) becomes bogus, in fact, non-thread-safe
  • the secondary use-case (better performance, due to not invoking mapping function O(P) times where P is the number of concurrent threads accessing the same key) has an unclear performance win, because the mapping function should be short and inexpensive anyway (see j.u.c.ConcurrentMap docs - long mapping functions and contention on the same key have terrible performance either way

For these reasons, I'd be inclined to push back and say that it's not worth it.

@scabug
Copy link
Author

scabug commented Feb 11, 2015

Andrei Pozolotin (andrei.pozolotin) said:
well, since "make the invocation atomic and make sure that the mapping function is applied only once"
seems to be a critical use case, you would merely annoy users by forcing them to use synchronized
every time they touch getOrElseUpdate. then they would flock to this page in anger :-)

probably you could relax the "purity" of TrieMap and start "using locks under-the-hood"?

@scabug
Copy link
Author

scabug commented Feb 11, 2015

@axel22 said (edited on Feb 11, 2015 7:12:31 PM UTC):
I assure you that I do not care about the "purity" with regards to locks here, nor do I have an emotional attachment to lock-free algorithms, if that's what you're aiming at :)
Quite the opposite - I feel that combining mutability, lock-freedom, locks and lazyness in an innovative and elegant way is exciting.

I do, however, care about purity and simplicity of any implementation, and I have an emotional attachment to the maintainers. :)
Keeping things simple makes the next maintainer happy, and less prone towards deprecating the whole thing in a wave of fury.
A good anecdotal example from the Scala community for this is the latest pattern matcher in the Scala compiler - although the previous one was more efficient, and knew how to optimize overlapping match cases better, the new pattern matcher rewrite is simpler to understand, less buggy and easier to maintain.

Why do I think extra, unwarranted complexity is the case here?

First, the test case in this bug report always fails at least at the latest in the second iteration of the loop - that's because the test case is checking the wrong thing - one should replace object with class.

Second, let's see what the angry mob has to say:

  1. Change the concurrent.Map and mutable.Map interfaces so that getOrElseUpdate always requires the execute-mapping-only-if-inserted semantics. By doing this, a large class of potential concurrent map implementations (pure with regards to lock-freedom) become unavailable (this includes j.u.c.ConcurrentMap implementations too - rest assured that j.u.c.ConcurrentMap designers had good reasons).
  2. So, obviously, concurrent.Map and mutable.Map cannot assume execute-mapping-only-if-inserted semantics. Sooner or later, there will be angry mutable.Map-reference-holding-mob running our way, and crying out that their side-effecting initializer got executed even though the key was not added into the map.
    Point is - this is something that no mutable.Map-reference-holder should expect otherwise.
  3. That leaves us specifically with clients that hold a reference to a TrieMap. These are the guys who know what the concrete type of their map is, so they better know its current semantics are no stronger than that of mutable.Map. Liskov substitution principle should not leave them hanging.
    Point is:
    a) the angry mob has no legitimate reason to complain
    b) this is a bug report in the sense that getOrElseUpdate should return that which has at some point in time appeared in the map (!which is not the case for mutable.MapLike, so that should legitimately be fixed) - the execute-mapping-only-if-inserted is a feature request, an added benefit

Third, how would you even implement this correctly?
This is uglier than you think.

  1. The TrieMap implementation is currently lock-free. We do want to keep it that way. This is not because of some superiority of lock-based algorithms over lock-free ones (both have advantages and disadvantages). This is simply because we don't want to rewrite everything. Otherwise, we might just write another data structure to begin with.
  2. So, we need to ensure that a getOrElseUpdate implementation has the execute-only-if-inserted semantics. As argued in this thread, this could be achieved by having a LazyNode, which takes a thunk and evaluates it the first time some thread reads the node.
    This requires introducing another recursive insertif method.
  3. Does this solve the problem? No, it does not. Side-effects were the main argument for execute-only-if-inserted semantics, so the callers will not observe them unless the LazyNode initializer gets executed. We could fix this with by having the thread A that calls getOrElseUpdate also initialize the value in the LazyNode after the node is added to the tree. That way we have our side-effects before getOrElseUpdate returns.
  4. This should work, right? Surprise, surprise - it doesn't. Thread B, which calls get, can still access the lazy node before thread A manages to evaluate it. That means that we cannot define LazyNode like this:
class LazyNode(key: K, thunk: () => V) {
  lazy val value = thunk()
}

Instead, we must write a custom lock around value, which is already locked by thread A before the LazyNode is added to the trie, and is subsequently unlocked after value gets initialized.

So, you see, it's possible, it's just that it's somewhat complex.

Fourth, after thinking about it in the background mode for some time today, the execute-mapping-only-if-inserted semantics is less useful than you think. Here's why - assume that thread A calls getOrElseUpdate defined like this:

def getOrElseUpdate(k: K, op: =>V): V = {
  get(k) match {
    case Some(v) => v
    case None =>
      val v = op
      putIfAbsent(k, v) // mutable.MapLike implementation -> update(k, v)
      v
}

(note: this is different from the current mutable.MapLike implementation)

How could a thread B that calls update(k, v) interfere?

  1. before the get(k) - this is fine
  2. between the get(k) and before the putIfAbsent(k, v) - this sounds scary, but it's actually fine. The putIfAbsent call will observe the concurrent update, and will not update the map. Unfortunately, the thunk op will get executed by now. I claim that this is not a problem - this is equivalent to putIfAbsent inserting the op value an infinitesimaly small amount of time before the thread B did the update(k, v).
    In other words - user programs cannot observe this.
  3. after putIfAbsent(k, v) - this is fine

There is one other situation where a program could observe this - I challenge you to find it.

So, I feel convinced that an execute-mapping-only-if-inserted semantics are not worth it here. In any case, I would not run blindly into adding the possibly unnecessary complexity.
However, my recent PR does not preclude the possibility of making this change - I'll do it if more people come in anger, or if I hear enough people yelling :)
Also, you are free to go ahead and try to convince that it can be done in a simple and understandable manner.

@scabug
Copy link
Author

scabug commented Feb 11, 2015

Andrei Pozolotin (andrei.pozolotin) said:
Thank you for the write up, great stuff. Sorry, I am not up to the challenge :-) Still, your argument against making
https://github.com/scala/scala/pull/4319/files#diff-eed29b659bb871d5e45a11c95a05ad33R897
to look like {code} override def getOrElseUpdate(k: K, op: =>V): V = this.synchronized { {code}
to me sounds like a contradiction. No need to respond - just more yelling from the angry mob :-)

@scabug
Copy link
Author

scabug commented Feb 11, 2015

@axel22 said (edited on Feb 11, 2015 11:03:21 PM UTC):
Problem here is that if you add this.synchronized to getOrElseUpdate, you suddenly have to add it around all other methods in TrieMap.

Unless carefully designed tricks are employed (such as the locked Lazy node described earlier), introducing a single lock to a lock-free data structure operation, usually pollutes all other operations with the need for locking :/

@scabug
Copy link
Author

scabug commented Feb 12, 2015

Jeff Olson (jdolson) said:
This bug report, and most of the conversation, seems to surround the question of whether or not op is executed exactly once, and only if inserted. But this is not the primary issue with the current implementation in my opinion. When I say that getOrElseUpdate is not atomic, I mean that it may return a value that is not, and never was, in the map. If I have multiple threads all calling getOrElseUpdate (and no one calling any other update operation) then only one thread should successfully update the map and all threads should get the value that the first inserted. This is not the case with the current implementation, nor the implementation proposed by Aleksandar above. An implementation that achieves this is quite trivial:

  override def getOrElseUpdate(key: A, op: => B): B = get(key) match {
    case Some(v) => v
    case None =>
      val v = op
      putIfAbsent(key, v).getOrElse(v)
  }

This should be the default implementation in scala.collection.concurrent.Map (and any pull request that does not include something equivalent is woefully incomplete). Of course, implementations like TrieMap should feel free to override the default implementation if they can achieve the same effect more efficiently or if they wish to add execute-only-if-inserted semantics.

Aside:
There is no need to add a computeIfAbsent function. This is something I would argue against anyway. I'd rather see a

def adjust(key: A, op: Option[B] => Option[B]): Unit

function added to the mutable.Map interface, with the additional restriction in concurrent.Map that the whole operation is atomic. Note that this is the equivalent function to Java 8's compute function with null being replaced by Option.

@scabug
Copy link
Author

scabug commented Feb 12, 2015

@axel22 said:
Not sure if my cell-phone replies reached here or the list, but here they are:

  1. That the item returned was at some point in the map, is what my PR is specifically addressing (ignore the implementation proposed above, the PR is different and correct).
  2. The default in concurrent.Map that you propose is the way to go! Great, and I'll submit a PR, unless you beat me to it.
  3. The computeIfAbsent part is debatable. We previously strived for concurrent.Map trait to mirror the j.u.c.ConcurrentMap interface. For conversion purposes and for consistency, I'd be inclined to keep it that way, and add the new method, especially since it can be implemented with a reasonable default. The adjust method does exactly what compute does, modulo the fact that there is no key involved in the adjust you propose.

@scabug
Copy link
Author

scabug commented Feb 19, 2015

@adriaanm said:
scala/scala#4319

@scabug scabug closed this as completed Feb 19, 2015
@scabug
Copy link
Author

scabug commented Feb 20, 2015

Andrei Pozolotin (andrei.pozolotin) said:
thank you

@scabug scabug added this to the 2.11.6 milestone Apr 7, 2017
chick added a commit to chipsalliance/treadle that referenced this issue Apr 1, 2019
- For BitMasks use TrieMap and a more careful get or update scheme
- Reference: [github.com/scala/bug/issues/7943](scala/bug#7943)
chick added a commit to chipsalliance/treadle that referenced this issue Apr 2, 2019
- For BitMasks use TrieMap and a more careful get or update scheme
- Reference: [github.com/scala/bug/issues/7943](scala/bug#7943)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants