Is there potential hunger in this code or is it just me?
I am trying to learn Scala and find it a great language. I learned from "The Beginning of Scala" by David Pollack. Chapter 3 is a piece of code that illustrates how to write multi-threaded code without synchronized blocks (this code is copied from the book, it's available for download from the Apress site , I'm not going to break any laws here):
import java.util.concurrent.atomic. {AtomicReference => AtomR, AtomicLong}
import java.util.Random
import scala.collection.immutable.TreeHashMap
object Multics {
type MT = Map [String, Int]
val info: AtomR [MT] = new AtomR (TreeHashMap.empty)
val clashCnt = new AtomicLong
def main (argv: Array [String]) {
runThread {
repeatEvery (1000) {
println ("Clash Count:" + clashCnt + "Total:" +
info.get.foldLeft (0) (_ + _._ 2))
}}
for (i old + (name -> 0)}
repeatEvery (ran.nextInt (100)) {
doSet (info) {old => old + (name -> (old (name) + 1))}
cnt = cnt + 1
if (cnt! = info.get () (name))
throw new Exception ("Thread:" + name + "failed")
}}
}
def runThread (f: => Unit) =
(new Thread (new Runnable {def run (): Unit = f})). start
def doSet [T] (atom: AtomR [T]) (update: T => T) {
val old = atom.get
if (atom.compareAndSet (old, update (old))) ()
else {
clashCnt.incrementAndGet
doSet (atom) (update)
}
}
def repeatEvery (len: => Int) (body: => Unit): Unit = {
try {
while (true) {
Thread.sleep (len)
body
}
} catch {
case e => e.printStackTrace; System.exit (1)
}
}
}
From what I understand, doSet
there is a potential starvation issue in the function (a sloppy flow can always collide and throw a StackOverflowException). Is this correct, and if so, how can this code be improved to fix this issue?
source to share
First of all, I think the big patch of code you pasted from the example book is missing; it makes it difficult to understand your question.
Second, it is true that doSet () could potentially be called many times recursively, but StackOverflowException in this case will not occur due to one savings: tail recursion. doSet () is called recursively at the end of the function (after processing the recursive call, no further processing is processed) and cannot be overridden (defined inside the object), which allows it to be optimized in a loop without any stack overhead.
2.8.0 has the @ scala.annotation.tailrec annotation, which, when used in def, ensures that the recursive call inside def is indeed tail recursive.
source to share
It looks like it uses Compare and Swap instead of "blocking" ( http://en.wikipedia.org/wiki/Compare-and-swap ).
The general idea with this approach is that you loop until you can consistently set the value.
I don't know enough about this to answer if there is a hungry problem. I guess there is a problem of fasting in theory, but in practice everything will be fine.
source to share