mutable.HashMap getOrElseUpdate not reentrant in 2.12

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

mutable.HashMap getOrElseUpdate not reentrant in 2.12

Jan Vanek
An example where this shows:

import
scala.collection.mutable

object TestHashMap {
abstract class M {
val map = new mutable.HashMap[Int, Int]

def get(n: Int): Int

def create(n: Int): Int = {
if (n <= 0)
n
else
1 + get(n - 1)
}

def test(n: Int): Unit = {
get(n)
for (i <- 0 to n)
println(i + " => " + map(i))
}
}

object M1 extends M {
def get(n: Int): Int = map.getOrElseUpdate(n, create(n))
}

object M2 extends M {
def get(n: Int): Int = getOrElseUpdate(map, n, create(n))

def getOrElseUpdate[K, V](map: mutable.HashMap[K, V], key: K, defaultValue: => V): V = {
if (map.contains(key))
map(key)
else {
val value = defaultValue
map.put(key, value)
value
}
}
}

def main(args: Array[String]): Unit = {
M2.test(100)
M1.test(100)
}
}


There is an optimization in 2.12. to compute the hash table index only once. If the table size changes during the defaultValue call, the index could/should be recomputed. The code could be changed from this:


override def getOrElseUpdate(key: A, defaultValue: => B): B = {
val i = index(elemHashCode(key))
val entry = findEntry(key, i)
if (entry != null) entry.value
else addEntry(createNewEntry(key, defaultValue), i)
}


to something like this:


def getOrElseUpdate(key: A, defaultValue: => B): B = {
val h = elemHashCode(key)
val i = index(h)
val entry = findEntry(key, i)
if (entry != null) entry.value
else {
val tl = table.length
val value = defaultValue
val e = createNewEntry(key, value)
if (tableSize >= threshold || tl != table.length) addEntry(e) else addEntry0(e, i)
value
}
}


During the addEntry the hash code will be recomputed again, but that doesn't happen to often, maybe.

Regards,
Jan

--
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 [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: mutable.HashMap getOrElseUpdate not reentrant in 2.12

Jason Zaugg
Thanks for reporting. I've opened SI-10187 to track this.

Java 9 has actually outlawed mutation of the map in an analagous method, computeIfAbsent, as their HashMap implementation in 8 has the same bug:
scala> {
  val hm = new java.util.HashMap[String, String]; 
  def add() = 1 to 100000 foreach (i => hm.put(i.toString, ""));
  hm.computeIfAbsent("0", k => { add(); "" }); 
  hm.containsKey("0")
}
res12: Boolean = false

Regards,

Jason


On Tue, 14 Feb 2017 at 06:24 Jan Vanek <[hidden email]> wrote:
An example where this shows:

--
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 [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: mutable.HashMap getOrElseUpdate not reentrant in 2.12

Jan Vanek
Thanks. If it were clear how it should behave when the mutation during the defaultValue call adds the value for the same key, and if it was possible to still implement it efficiently, I think it would be good to allow it. However, out of my 10 usages of this method I needed the mutation in 1 case, so I have no problem with outlawing it at all.

Regards,
Jan


On 02/13/2017 11:36 PM, Jason Zaugg wrote:
Thanks for reporting. I've opened SI-10187 to track this.

Java 9 has actually outlawed mutation of the map in an analagous method, computeIfAbsent, as their HashMap implementation in 8 has the same bug:
scala> {
  val hm = new java.util.HashMap[String, String]; 
  def add() = 1 to 100000 foreach (i => hm.put(i.toString, ""));
  hm.computeIfAbsent("0", k => { add(); "" }); 
  hm.containsKey("0")
}
res12: Boolean = false

Regards,

Jason


On Tue, 14 Feb 2017 at 06:24 Jan Vanek <[hidden email]> wrote:
An example where this shows:


--
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 [hidden email].
For more options, visit https://groups.google.com/d/optout.