Quantcast

[scala] Lazy val and synchronized

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[scala] Lazy val and synchronized

Andrew.Foggin
On the 'lazyvals' branch it looks like

class LazyTest {
    lazy val msg = "Lazy"
}


is compiled to something equivalent to the following Java code:

class LazyTest {
    public int bitmap$0;
    private String msg;

    public String msg() {
        if ((bitmap$0 & 1) == 0) {
            synchronized (this) {
                if ((bitmap$0 & 1) == 0) {
                    synchronized (this) {
                        msg = "OK";
                    }
                }
                bitmap$0 = bitmap$0 | 1;
            }
        }
        return msg;
    }

    ...
}


i.e. double-checked locking with an additional redundant synchronized block.  I think it would be preferable to have no synchronization by default and to allow the 'synchronized' modifier on a lazy val.

Which raises another issue: 'synchronized' seems to be missing from the language specification, apart from being used in an example in Section 5.3.3.

Finally, I don't think 'bitmap$0' needs to be 'public'. (And I think a boolean named something like 'lazy$msg' would be more orthogonal as well as easier to implement, but that's a really minor issue)

Regards,

Andrew



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Jamie Webb-2
On 2007-06-24 19:22:09 Andrew Foggin wrote:

> On the 'lazyvals' branch it looks like
>
> class LazyTest {
>     lazy val msg = "Lazy"
> }
>
> is compiled to something equivalent to the following Java code:
>
> class LazyTest {
>     public int bitmap$0;
>     private String msg;

I hope there's a 'volatile' in here, otherwise the DCL is a waste of
time.

>
>     public String msg() {
>         if ((bitmap$0 & 1) == 0) {
>             synchronized (this) {
>                 if ((bitmap$0 & 1) == 0) {
>                     synchronized (this) {
>                         msg = "OK";
>                     }
>                 }
>                 bitmap$0 = bitmap$0 | 1;
>             }
>         }
>         return msg;
>     }
>
>     ...
> }

I posted a more efficient way to do this in:

http://article.gmane.org/gmane.comp.lang.scala.user/278/

> i.e. double-checked locking with an additional redundant synchronized
> block.  I think it would be preferable to have no synchronization by
> default and to allow the 'synchronized' modifier on a lazy val.

I agree.

> Which raises another issue: 'synchronized' seems to be missing from
> the language specification, apart from being used in an example in
> Section 5.3.3.

In Scala, synchronized is just a method on objects.

/J
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Andrew.Foggin
Jamie Webb wrote:
Which raises another issue: 'synchronized' seems to be missing from
the language specification, apart from being used in an example in
Section 5.3.3.
    

In Scala, synchronized is just a method on objects.

  
Ahh...  defined on AnyRef. Thanks.

In that case a '@synchronized' annotation or some equivalent would be useful.

Andrew
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Stepan Koltsov
In reply to this post by Jamie Webb-2
On 6/24/07, Jamie Webb <[hidden email]> wrote:

> On 2007-06-24 19:22:09 Andrew Foggin wrote:
> >     public String msg() {
> >         if ((bitmap$0 & 1) == 0) {
> >             synchronized (this) {
> >                 if ((bitmap$0 & 1) == 0) {
> >                     synchronized (this) {
> >                         msg = "OK";
> >                     }
> >                 }
> >                 bitmap$0 = bitmap$0 | 1;
> >             }
> >         }
> >         return msg;
> >     }
> >
> >     ...
> > }
>
> I posted a more efficient way to do this in:
>
> http://article.gmane.org/gmane.comp.lang.scala.user/278/

Jamie,

I think AtomicIntegerFieldUpdater + value holder is faster then AtomicReference.

Also, seems like compareAndSet and weakCompareAndSet do the same
things (according to JDK sources).

===
object Lazy {
    val UNINIT = 1
    val LOCKED = 2
    val FAILED = 3
    val INIT = 4
}

class Bebe {
    import Lazy._

    @volatile
    private var _foo: String = null

    // this should be static field of class Bebe
    private val _fooUpdater =
java.util.concurrent.atomic.AtomicIntegerFieldUpdater.newUpdater(classOf[Bebe],
"_fooState")

    @volatile
    private var _fooState = UNINIT

    private def _fooCompute = "bebe"

    def foo = {
        var state = _fooState
        if (state == UNINIT && _fooUpdater.compareAndSet(this, UNINIT,
LOCKED)) {
            try {
                val value = _fooCompute
                _foo = value
                _fooUpdater.set(this, INIT)
                value
            } catch {
                case e =>
                    _fooUpdater.set(this, FAILED)
                    throw e
            }
        } else {
            while (state == LOCKED) {
                Thread.`yield`()
                state = _fooState
            }
            if (state == FAILED) throw new Exception("lazy eval failed")
            _foo
        }
    }
}
===

--
Stepan
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Miles Sabin
Stepan Koltsov wrote,
> Also, seems like compareAndSet and weakCompareAndSet do the same
> things (according to JDK sources).

I thought that was processor architecture dependent ... were you looking
at architecture independent code?

Cheers,


Miles
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Stepan Koltsov
Both compareAndSet and weakCompareAndSet call Unsafe.compareAndSet (in
Sun JDK 1.5), architecture independent code is there.

On 6/24/07, Miles Sabin <[hidden email]> wrote:
> Stepan Koltsov wrote,
> > Also, seems like compareAndSet and weakCompareAndSet do the same
> > things (according to JDK sources).
>
> I thought that was processor architecture dependent ... were you looking
> at architecture independent code?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Jamie Webb-2
In reply to this post by Stepan Koltsov
On 2007-06-24 19:20:18 Stepan Koltsov wrote:
> Jamie,
>
> I think AtomicIntegerFieldUpdater + value holder is faster then
> AtomicReference.

I don't believe so, though certainly the code I posted could stand some
tweaking, and it may be better to keep the state separate (especially
if the lazy val is of a primitive type).

> Also, seems like compareAndSet and weakCompareAndSet do the same
> things (according to JDK sources).

Well, that's not guaranteed to remain the case, but yes I imagine
there's nothing to gain by doing one followed by the other.

/J
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: [scala] Lazy val and synchronized

Judson, Ross
In reply to this post by Jamie Webb-2
I put another sample implementation of threadsafe lazy values on the
Wiki...this one uses the JDK's abstract queued synchronizer as its
basis, and should therefore be about as fast as the JDK gets.

RJ

http://scala.sygneca.com/code/alternate-lazy-values

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Jamie Webb-2
On 2007-06-25 17:14:22 Judson, Ross wrote:
> I put another sample implementation of threadsafe lazy values on the
> Wiki...this one uses the JDK's abstract queued synchronizer as its
> basis, and should therefore be about as fast as the JDK gets.
>
> RJ
>
> http://scala.sygneca.com/code/alternate-lazy-values

No, this will be much slower than either DCL or the Atomic variations.
I think it's probably slower than just synchronising too. The trouble
is that AbstractQueuedSynchronizer is extremely heavy: it's designed
to offer more functionality than monitors, for cases when locks need
to be held for a long time, not for speed in the uncontended case.

(I'm assuming in all this that races for lazy evaluation are extremely
rare; that seems reasonable, especially given that Scala's inner object
implementation currently requires that they /never/ happen.)

I'm also not convinced that your implementation is thread-safe: I think
result and exception need to be volatile, for the same reason as in
DCL.

In summary, as far as I can tell:

- Volatile is the fastest way the JDK provides for passing structured
data between threads.

- Atomic* is the thinnest available wrapper around volatile that
provides the additional test-and-set operation we need for lazy
evaluation.

- The regular vs reflective versions of Atomic* provide different
tradeoffs (an extra allocation vs somewhat slower accesses,
respectively), but I expect that the regular version is a better fit in
this case.

- There's actually rather little performance difference between DCL
and doing the locking manually using Atomic*, but the latter avoids
synchronising on the parent object (of course a separate monitor
object could be added, but that would remove any advantage DCL has).

/J
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Alex Boisvert-3
Have you also considered using the initialize-on-demand holder pattern?
http://www-128.ibm.com/developerworks/java/library/j-jtp03304/


On 6/26/07, Jamie Webb <[hidden email]> wrote:
On 2007-06-25 17:14:22 Judson, Ross wrote:
> I put another sample implementation of threadsafe lazy values on the
> Wiki...this one uses the JDK's abstract queued synchronizer as its
> basis, and should therefore be about as fast as the JDK gets.
>
> RJ
>
> http://scala.sygneca.com/code/alternate-lazy-values

No, this will be much slower than either DCL or the Atomic variations.
I think it's probably slower than just synchronising too. The trouble
is that AbstractQueuedSynchronizer is extremely heavy: it's designed
to offer more functionality than monitors, for cases when locks need
to be held for a long time, not for speed in the uncontended case.

(I'm assuming in all this that races for lazy evaluation are extremely
rare; that seems reasonable, especially given that Scala's inner object
implementation currently requires that they /never/ happen.)

I'm also not convinced that your implementation is thread-safe: I think
result and exception need to be volatile, for the same reason as in
DCL.

In summary, as far as I can tell:

- Volatile is the fastest way the JDK provides for passing structured
data between threads.

- Atomic* is the thinnest available wrapper around volatile that
provides the additional test-and-set operation we need for lazy
evaluation.

- The regular vs reflective versions of Atomic* provide different
tradeoffs (an extra allocation vs somewhat slower accesses,
respectively), but I expect that the regular version is a better fit in
this case.

- There's actually rather little performance difference between DCL
and doing the locking manually using Atomic*, but the latter avoids
synchronising on the parent object (of course a separate monitor
object could be added, but that would remove any advantage DCL has).

/J

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Jamie Webb-2
On 2007-06-26 07:39:49 Alex Boisvert wrote:
> Have you also considered using the initialize-on-demand holder
> pattern?
> http://www-128.ibm.com/developerworks/java/library/j-jtp03304/

This is indeed how Scala handles top-level objects. AFAIK it can't be
applied to inner objects or lazy vals unfortunately.

/J
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: [scala] Lazy val and synchronized

Judson, Ross
In reply to this post by Jamie Webb-2
There's nothing to do but bench it, of course :)  Offhand I'm inclined
to agree with parts of your assessment...but it's probably important to
examine the effects of the spin loop being used to wait for another
thread, and note that if there is heavy concurrent/multiproc usage of a
lazy value the AQS may have advantages.

My lazy code was a direct port of the java.util.concurrent.FutureTask,
minus the cancellation support. The concurrency packages have had some
very heavy testing. FutureTask is very similar to a lazy value, and Sun
chose to implement it with AQS for a reason, although I don't know what
that reason is. There may be a mysterious edge case out there somewhere.

RJ


-----Original Message-----
From: Jamie Webb [mailto:[hidden email]]
Sent: Tuesday, June 26, 2007 8:48 AM
To: [hidden email]
Subject: Re: [scala] Lazy val and synchronized

On 2007-06-25 17:14:22 Judson, Ross wrote:
> I put another sample implementation of threadsafe lazy values on the
> Wiki...this one uses the JDK's abstract queued synchronizer as its
> basis, and should therefore be about as fast as the JDK gets.
>
> RJ
>
> http://scala.sygneca.com/code/alternate-lazy-values

No, this will be much slower than either DCL or the Atomic variations.
...
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Blair Zajac-3
In reply to this post by Jamie Webb-2
Jamie Webb wrote:

> On 2007-06-26 07:39:49 Alex Boisvert wrote:
>> Have you also considered using the initialize-on-demand holder
>> pattern?
>> http://www-128.ibm.com/developerworks/java/library/j-jtp03304/
>
> This is indeed how Scala handles top-level objects. AFAIK it can't be
> applied to inner objects or lazy vals unfortunately.
>
> /J
>

I was looking at using Spring dependency injection to set var's in objects and
ended up looking to see how objects are implements.  It looks like the generated
code is different than the implementation in the article:

$ cat object.scala
object Static
{
}


$ javap -c Static\$
Compiled from "object.scala"
public final class Static$ extends java.lang.Object implements scala.ScalaObject{
public static final Static$ MODULE$;

public static {};
   Code:
    0:   new     #9; //class Static$
    3:   dup
    4:   invokespecial   #12; //Method "<init>":()V
    7:   return

public Static$();
   Code:
    0:   aload_0
    1:   invokespecial   #16; //Method java/lang/Object."<init>":()V
    4:   aload_0
    5:   putstatic       #18; //Field MODULE$:LStatic$;
    8:   return
...
...
...
}

There's no private static inner class as suggested by the article.

Regards,
Blair
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Jamie Webb-2
On 2007-07-17 13:20:32 Blair Zajac wrote:

> Jamie Webb wrote:
> > On 2007-06-26 07:39:49 Alex Boisvert wrote:
> >> Have you also considered using the initialize-on-demand holder
> >> pattern?
> >> http://www-128.ibm.com/developerworks/java/library/j-jtp03304/
> >
> > This is indeed how Scala handles top-level objects. AFAIK it can't
> > be applied to inner objects or lazy vals unfortunately.
> >
> > /J
> >
>
> I was looking at using Spring dependency injection to set var's in
> objects and ended up looking to see how objects are implements.  It
> looks like the generated code is different than the implementation in
> the article:
...
> There's no private static inner class as suggested by the article.

I'm not sure where you're seeing that, but in any case the significant
detail is that object construction happens inside the static
initialiser of the 'holder' class. The nature of the object being
constructed is not really relevant. In the case of Scala, the object
and its holder are the same class.

/J
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Blair Zajac-3
Jamie Webb wrote:

> On 2007-07-17 13:20:32 Blair Zajac wrote:
>> Jamie Webb wrote:
>>> On 2007-06-26 07:39:49 Alex Boisvert wrote:
>>>> Have you also considered using the initialize-on-demand holder
>>>> pattern?
>>>> http://www-128.ibm.com/developerworks/java/library/j-jtp03304/
>>> This is indeed how Scala handles top-level objects. AFAIK it can't
>>> be applied to inner objects or lazy vals unfortunately.
>>>
>>> /J
>>>
>> I was looking at using Spring dependency injection to set var's in
>> objects and ended up looking to see how objects are implements.  It
>> looks like the generated code is different than the implementation in
>> the article:
> ...
>> There's no private static inner class as suggested by the article.
>
> I'm not sure where you're seeing that, but in any case the significant
> detail is that object construction happens inside the static
> initialiser of the 'holder' class. The nature of the object being
> constructed is not really relevant. In the case of Scala, the object
> and its holder are the same class.

The code there was generated by using scalac and Sun's javap -c to print the
class file.

The one thing I don't like about this implementation is that from a Java level,
or say a Spring dependency injection, if one isn't careful, one can get multiple
Scala objects, and it appears that the constructor for the object puts itself
into the static MODULE$ field, so if you had a Java code constructing the
object, the singleton would be replaced.

Blair

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [scala] Lazy val and synchronized

Iulian Dragos-2
Blair Zajac wrote:
 > The one thing I don't like about this implementation is that from a Java
> level, or say a Spring dependency injection, if one isn't careful, one
> can get multiple Scala objects, and it appears that the constructor for
> the object puts itself into the static MODULE$ field, so if you had a
> Java code constructing the object, the singleton would be replaced.

Blair,

You are right, so let me explain why it is done like this. Basically, it
is recursion. During object construction, the object being constructed
can be referenced by user code. That means we have to put the instance
in its static field as soon as possible, and that means right after
calling the super constructor. If we made this assignment in the static
initializer, as one would normally do, the object constructor would see
the object being constructor to be null. Consider a slightly more
complicated example:

object Obj {
  println("before")
  val x = "abc"
  val y = Obj.x
  val z = new Foo
  println("after")
}

class Foo {
  // we don't want a null pointer exception here
  println(Obj.x)
}

object Main extends Application {
  Obj.y // dereference the object, to trigger lazy initialization
}

Obj's constructor uses the instance being constructed both directly (val
y) and indirectly (val z).

Allowing such programs seemed useful enough to trade against some issues
when Java accesses Scala code. On the other hand, I think encoding of
top level objects can still be improved, so any ideas are more than welcome!

Cheers,
Iulian
Loading...