0

From there

Trying to introduce memoization into the recursion algorithm.

case class Memo[A,B](f: A => B) extends (A => B) {
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A) = cache getOrElseUpdate (x, f(x))
}

private val fib: Memo[Int, BigInt] = Memo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2) 
}

def foo(n: Int) = {
  fib(n)
}

Does it mean that if we use mutable state and functional value (defined by val.. well almost functional value) then it is not thread-safe?

(val fib - looks like global scoped mutable variable/object)

michal.jakubeczy
  • 8,221
  • 1
  • 59
  • 63
ses
  • 13,174
  • 31
  • 123
  • 226
  • 1
    Here you can rescue thread safety by using a `var` holding an immutable `Map` that is replaced on each update and which must be marked `@volatile`. Alternatively, you can use the (somewhat) thread-safe, mutable `Map` type `TrieMap`. See http://stackoverflow.com/questions/21286823/is-there-a-replacement-for-while-loop-for-update-of-concurrentmap-with-scala-tri/21287424#21287424 for an important caveat. – Randall Schulz Apr 22 '14 at 00:05
  • Actually given multithreading doesn't help much when constructing memoization: http://stackoverflow.com/a/20462893/2073130, use memoization for DP in single-thread only. By that way, regular `mutable.Map` would be sufficient. – lcn Dec 15 '14 at 18:31

1 Answers1

0

I'd say yes, there can be a problem if more threads are calling foo at the same time. Even though I was thinking that if you're only adding to the map and always the same value for a key, there is no guarantee that it must work. If implementation of getOrElseUpdate method of Map is for whatever reason stateful, it would not work. The contract of mutable Map is by definition not thread-safe.

If you can, add synchronization to your map and you're fine:

private val cache = new HashMap[A, B] with SynchronizedMap[A, B]
Rado Buransky
  • 3,252
  • 18
  • 25
  • @DNA In the question there is only single instance of `Memo`. If you're trying to propose another solution, yes that's even better, but I tried to answer his question. – Rado Buransky Apr 21 '14 at 20:59
  • Yes, I'd thought that `fib` was a `def` not a `val`, so you are quite right. – DNA Apr 21 '14 at 21:00