TrieMap.getOrElseUpdate

[Mikael Ståldal]

How does the getOrElseUpdate method from scala.collection.mutable.MapLike work on a TrieMap?

Will it be properly thread-safe and atomic? Will it protect against race conditions, so that for any given key only one value is ever added to the map (given that no other mutating method is used)?




[Sonnenschein]

Yes, it will. Scaladoc states:
"A concurrent hash-trie or TrieMap is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations."

[Tim Underwood]

Are you sure about that?  According to the Scaladocs for scala.collection.concurrent.TrieMap[1], the implementation for getOrElseUpdate comes from scala.collection.mutable.MapLike[2] which looks like:

def getOrElseUpdate(key: A, op: => B): B =

get(key) match {

case Some(v) => v

case None => val d = op; this(key) = d; d

}

That doesn't look very thread safe to me.

-Tim

[1] - http://www.scala-lang.org/api/current/index.html#scala.collection.concurrent.TrieMap@getOrElseUpdate%28key:A,op:=%3EB%29:B

[2] - https://github.com/scala/scala/blob/v2.11.2/src/library/scala/collection/mutable/MapLike.scala#L185

[Mikael Ståldal]

That's what I suspected as well.

Is there any way to accomplish this?

Will this work?

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

op
    putIfAbsent(key, d).getOrElse(d)  
}  

[Nils Kilden-Pedersen]

On Wed, Sep 17, 2014 at 10:08 AM, Tim Underwood <timund...@gmail.com> wrote:

Are you sure about that?  According to the Scaladocs for scala.collection.concurrent.TrieMap[1], the implementation for getOrElseUpdate comes from scala.collection.mutable.MapLike[2] which looks like:

def getOrElseUpdate(key: A, op: => B): B =

get(key) match {

case Some(v) => v

case None => val d = op; this(key) = d; d

}

That doesn't look very thread safe to me.

It isn’t. getOrElseUpdate is not a concurrent method. Use putIfAbsent for something like this.

-Tim

[1] - http://www.scala-lang.org/api/current/index.html#scala.collection.concurrent.TrieMap@getOrElseUpdate%28key:A,op:=%3EB%29:B

[2] - https://github.com/scala/scala/blob/v2.11.2/src/library/scala/collection/mutable/MapLike.scala#L185

On Wednesday, September 17, 2014 7:25:45 AM UTC-7, Sonnenschein wrote:

Yes, it will. Scaladoc states:
"A concurrent hash-trie or TrieMap is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations."

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

​

[Tim Underwood]

I've used patterns similar to this in a rich wrapper over Java's ConcurrentHashMap to accomplish what you are trying to do when I want to minimize unnecessary evaluations of the op parameter
but when it's okay if op is evaluated and then doesn't get stored in the map.

-Tim

[Jason Zaugg]

On Wed, Sep 17, 2014 at 11:38 PM, Mikael Ståldal <m...@appearnetworks.com> wrote:

How does the getOrElseUpdate method from scala.collection.mutable.MapLike work on a TrieMap?

Will it be properly thread-safe and atomic? Will it protect against race conditions, so that for any given key only one value is ever added to the map (given that no other mutating method is used)?

There is an interesting discussion about this method in SI-7943

-jason