<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    Hello,<br>
    <br>
    I have a question regarding the performance of `notifyAll` calls
    compared to entering and exiting monitors on the JVM.<br>
    Some background - recently there has been a lot of talk on the Scala
    mailing lists about changing the Scala lazy vals implementation<br>
    which is currently deadlock-prone in cases where there is no reason
    for it to be.<br>
    We have an alternative design that we are trying to evaluate in
    terms of correctness and performance.<br>
    <br>
    The full discussion is available here:<br>
<a class="moz-txt-link-freetext" href="https://groups.google.com/group/scala-internals/browse_thread/thread/702801329e64f11f">https://groups.google.com/group/scala-internals/browse_thread/thread/702801329e64f11f</a><br>
    <br>
    I illustrate these changes with the hand-written version of our lazy
    vals implementation.<br>
    This is written in Scala, but the features I use should be intuitive
    and directly translatable to Java.<br>
    This is a lazy val declaration:<br>
    <br>
    <meta charset="utf-8">
      class LazyCell(x: Int) {<br>
        lazy val value = 0<br>
      }<br>
    <br>
    This is what our compiler currently does for a `lazy val`
    declaration:<br>
    <br>
    <meta charset="utf-8">
      final class LazySimCell(x: Int) {<br>
        @volatile var bitmap_0: Boolean = false<br>
        var value_0: Int = _<br>
        private def value_lzycompute(): Int = {<br>
          this.synchronized {<br>
            if (bitmap_0) {<br>
              value_0 = 0<br>
              bitmap_0 = true<br>
            }<br>
          }<br>
          value_0<br>
        }<br>
        def value = if (bitmap_0) value_0 else value_lzycompute()<br>
      }<br>
    <br>
    The problem with this design is that if a `lazy val` right hand side
    depends on `lazy val`s in different objects cyclically, but lazy
    vals dependencies themselves<br>
    do not form a cycle, then this can lead to deadlocks.<br>
    <br>
    We want to replace having a single synchronized block in the
    double-checked locking pattern with two blocks.<br>
    In the new design a thread T1 arriving at the first synchronized
    block synchronizes on `this` and announces that the it will
    initialize the lazy val.<br>
    Subsequent readers of the lazy val then wait until they are
    notified.<br>
    T1 then computes the value.<br>
    T1 then enters the second synchronized block, assigns the result to
    the object field and notifies any waiting threads (other readers).<br>
    <br>
    This is the newly proposed design, hand-written:<br>
    <br>
    <meta charset="utf-8">
       final class LazySimCellVersion2(x: Int) {<br>
        @volatile var bitmap_0: Byte = 0.toByte<br>
        var value_0: Int = _<br>
        private def value_lzycompute(): Int = {<br>
          this.synchronized {<br>
            if (bitmap_0 == 0.toByte) {<br>
              bitmap_0 = 1.toByte<br>
            } else {<br>
              while (bitmap_0 == 1.toByte) {<br>
                this.wait()<br>
              }<br>
              return value_0<br>
            }<br>
          }<br>
          val result = 0<br>
          this.synchronized {<br>
            value_0 = result<br>
            bitmap_0 = 2.toByte<br>
            this.notifyAll()<br>
          }<br>
          value_0<br>
        }<br>
        def value = if (bitmap_0 == 2.toByte) value_0 else
    value_lzycompute()<br>
      }<br>
    <br>
    I have run microbenchmarks to compare the two designs in a
    non-contended mode as follows.<br>
    I measured the following:<br>
    - instantiating an object with a value<br>
    - instantiating an object and initializing its lazy value<br>
    - same thing, but with manually implemented lazy vals with boolean
    bitmaps<br>
    - same thing, but with byte bitmaps<br>
    - the proposed lazy value change with 2 synchronizations blocks, but
    without a notifying potential waiters<br>
    - same thing, but with a notify call<br>
    repeated 1000000 through 5000000 times, in steps of 1000000.<br>
    The instantiated object is assigned to a field each time, to discard
    potential VM optimizations.<br>
    The initialization code is composed of creating an integer literal
    `0` - I chose to minimum amount<br>
    of computation to avoid having the computation costs amortize the
    lazy-val-related initialization costs.<br>
    This should thus be the borderline case where the program does
    nothing else but instantiate objects and initialize their lazy vals.<br>
    <br>
    My platform:<br>
    i7-2600, quad-core, hyperthreading, 3.4GHz<br>
    MacOS X 10.7.5<br>
    Java 7, update 4, 64-bit<br>
    Scala 2.10.1<br>
    <br>
    The reports themselves are here:<br>
    <br>
    <a class="moz-txt-link-freetext"
      href="http://lampwww.epfl.ch/%7Eprokopec/lazyvals/report/">http://lampwww.epfl.ch/~prokopec/lazyvals/report/</a><br>
    <br>
    The repository with the executable microbenchmarks with the code
    that produced these:<br>
    <br>
    <a class="moz-txt-link-freetext"
      href="https://github.com/axel22/lazy-val-bench">https://github.com/axel22/lazy-val-bench</a><br>
    <a class="moz-txt-link-freetext"
href="https://github.com/axel22/lazy-val-bench/blob/master/src/test/scala/example/SyncBench.scala">https://github.com/axel22/lazy-val-bench/blob/master/src/test/scala/example/SyncBench.scala</a><br>
    <br>
    In this benchmark, the 2 synchronized blocks design with a notify is
    5 times slower than the current lazy val implementation - and just
    adding/removing the line with the `notifyAll` call changes things
    considerably.<br>
    <br>
    My question:<br>
    Is this expected? Is the cost of a `notifyAll` call expected to be
    this high?<br>
    If it is, is there an alternative, more efficient way to wake up the
    other threads waiting on `this` object?<br>
    <br>
    Thank you,<br>
    Aleksandar Prokopec<br>
    <br>
    <br>
    <pre class="moz-signature" cols="72"> 


--
Aleksandar Prokopec
Doctoral Assistant
LAMP, IC, EPFL
<a class="moz-txt-link-freetext" href="http://people.epfl.ch/aleksandar.prokopec">http://people.epfl.ch/aleksandar.prokopec</a>
</pre>
  </body>
</html>