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.

[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.

[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.