Lazy vals implementation

[Oleg G.]

Current lazy val implementation uses volatile field, but as i've read
at http://www.ibm.com/developerworks/library/j-jtp03304/:

Under the new memory model, this "fix" to double-checked locking
renders the idiom thread-safe. But that still doesn't mean that you
should use this idiom! The whole point of double-checked locking was
that it was supposed to be a performance optimization, designed to
eliminate synchronization on the common code path, largely because
synchronization was relatively expensive in very early JDKs. Not only
has uncontended synchronization gotten a lot cheaper since then, but
the new changes to the semantics of volatile make it relatively more
expensive than the old semantics on some platforms. (Effectively, each
read or write to a volatile field is like "half" a synchronization --
a read of a volatile has the same memory semantics as a monitor
acquire, and a write of a volatile has the same semantics as a monitor
release.) So if the goal of double-checked locking is supposed to
offer improved performance over a more straightforward synchronized
approach, this "fixed" version doesn't help very much either.

What if we swap the getter after initialization? Like this:

Class A {
 private var _name: String = null;
 private var nameGetter: () => String = defaultNameGetter
 private def defaultNameGetter(): String = {
   nameGetter.synchronized {
     if (_name == null) {
       _name = "Joe"
       nameGetter = fastNameGetter
     }
   }
   _name
 }
 private def fastNameGetter(): String = { _name }
 def name: String = nameGetter()
}

object Test {
 def main(args: Array[String]) {
   val a = new A
   println(a.name)
 }
}

It's an additional 'var' for each lazy field, so it could be a
compiler option: either you choose speed with this additinal var or
memory with volatile.

Am i missing something?

[Iulian Dragos-2]

On Wed, Oct 21, 2009 at 6:14 PM, Oleg G <ojowoo@...> wrote:

What if we swap the getter after initialization? Like this:

Class A {
 private var _name: String = null;
 private var nameGetter: () => String = defaultNameGetter
 private def defaultNameGetter(): String = {
  nameGetter.synchronized {
    if (_name == null) {
      _name = "Joe"
      nameGetter = fastNameGetter
    }
  }
  _name
 }
 private def fastNameGetter(): String = { _name }
 def name: String = nameGetter()
}

object Test {
 def main(args: Array[String]) {
  val a = new A
  println(a.name)
 }
}

It's an additional 'var' for each lazy field, so it could be a
compiler option: either you choose speed with this additinal var or
memory with volatile.

Your solution could work. However, it seems highly optimistic of you to call it 'fast'. All field accesses to a lazy value would go through an additional indirection, and the final call is an interface call (Function1.apply). Plus there's boxing involved, if your lazy value happens to be of a primitive type.

You still need an initialized flag per lazy value (testing for null does not work, maybe the lazy field will be initialized to null). And the closure involves another object, basically doubling the memory requirements per lazy field.

Since you suggest changing something that works on the basis of being slow, could you provide some measurements that lead you to this conclusion?

iulian
 

Am i missing something?

--
« Je déteste la montagne, ça cache le paysage »
Alphonse Allais

[bearfeeder]

Scala's lazy implementation was reviewed by a room full of people at the JVM Language summit.  Folks were thumbs up about the implementation.

On Wed, Oct 21, 2009 at 9:14 AM, Oleg G <ojowoo@...> wrote:

Current lazy val implementation uses volatile field, but as i've read
at http://www.ibm.com/developerworks/library/j-jtp03304/:

Under the new memory model, this "fix" to double-checked locking
renders the idiom thread-safe. But that still doesn't mean that you
should use this idiom! The whole point of double-checked locking was
that it was supposed to be a performance optimization, designed to
eliminate synchronization on the common code path, largely because
synchronization was relatively expensive in very early JDKs. Not only
has uncontended synchronization gotten a lot cheaper since then, but
the new changes to the semantics of volatile make it relatively more
expensive than the old semantics on some platforms. (Effectively, each
read or write to a volatile field is like "half" a synchronization --
a read of a volatile has the same memory semantics as a monitor
acquire, and a write of a volatile has the same semantics as a monitor
release.) So if the goal of double-checked locking is supposed to
offer improved performance over a more straightforward synchronized
approach, this "fixed" version doesn't help very much either.

What if we swap the getter after initialization? Like this:

Class A {
 private var _name: String = null;
 private var nameGetter: () => String = defaultNameGetter
 private def defaultNameGetter(): String = {
  nameGetter.synchronized {
    if (_name == null) {
      _name = "Joe"
      nameGetter = fastNameGetter
    }
  }
  _name
 }
 private def fastNameGetter(): String = { _name }
 def name: String = nameGetter()
}

object Test {
 def main(args: Array[String]) {
  val a = new A
  println(a.name)
 }
}

It's an additional 'var' for each lazy field, so it could be a
compiler option: either you choose speed with this additinal var or
memory with volatile.

Am i missing something?

--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Surf the harmonics

[Oleg G.]

Thanks for the answer, Iulian!

Looks like i've missed a lot of things.. But i just dont feel
comfortable with synchronization (or volatile-related things) on every
access to a field while we only need all the stuff at initialization
time.

So there can not be a good 'swap the getter' solution?

[Paul Phillips-3]

On Thu, Oct 22, 2009 at 12:03:24AM +0700, Oleg G wrote:
> Looks like i've missed a lot of things.. But i just dont feel
> comfortable with synchronization (or volatile-related things) on every
> access to a field while we only need all the stuff at initialization
> time.

I know what you mean, but that is the burn with concurrency -- you may
only "need" it that first time, but you never know if THIS is the first
time unless you check somehow.  And if you check, you are in a race, so
you have to coordinate somehow.

> So there can not be a good 'swap the getter' solution?

Seems like there are two birds we could peg here if we solved the issues
with null, because the equivalent of "lazy val: String with NotNull"
could now safely be initialized to null and updated in place.  I doubt
you can get much cheaper than a null check.

--
Paul Phillips      | Before a man speaks it is always safe to assume
Vivid              | that he is a fool.  After he speaks, it is seldom
Empiricist         | necessary to assume it.
ha! spill, pupil   |     -- H. L. Mencken

[Oleg G.]

What about this java code if it could be used as template for
compiler-generated code:

public class Test {
        public static interface IntHolderFor<T> {
                public int get(T t);
        }
       
        public static class Record {
                public static class SimpleIntFieldHolderForRecord implements
IntHolderFor<Record> {
                        private final int value;
                        public SimpleIntFieldHolderForRecord(int initialValue) { value =
initialValue; }
                        @Override public int get(Record r) { return value; }
                }
               
                public static class LazyIntFieldHolderForRecord implements
IntHolderFor<Record> {
                        @Override public synchronized int get(Record r) {
                                if (r.field instanceof LazyIntFieldHolderForRecord) {
                                        r.field = new SimpleIntFieldHolderForRecord(initField());
                                }
                                return r.field.get(r);
                        }
                }

                private IntHolderFor<Record> field = new LazyIntFieldHolderForRecord();
                private static int initField() { return 1; }
               
                public int getField() {return field.get(this);}
        }
       
       
        public static void main(String args[]) {
                Record r = new Record();
                System.out.println("field = " + r.getField());
        }
}

Only additional pointer and indirect call with parameter added, right?

[Oleg G.]

I'll try to measure peformance of this, if its not at least 2 times
faster than volatile stuff then i give up and going to be happy with
volatile fields.

2009/10/22 Oleg G <ojowoo@...>:

> What about this java code if it could be used as template for
> compiler-generated code:
>
> public class Test {
>        public static interface IntHolderFor<T> {
>                public int get(T t);
>        }
>
>        public static class Record {
>                public static class SimpleIntFieldHolderForRecord implements
> IntHolderFor<Record> {
>                        private final int value;
>                        public SimpleIntFieldHolderForRecord(int initialValue) { value =
> initialValue; }
>                        @Override public int get(Record r) { return value; }
>                }
>
>                public static class LazyIntFieldHolderForRecord implements
> IntHolderFor<Record> {
>                        @Override public synchronized int get(Record r) {
>                                if (r.field instanceof LazyIntFieldHolderForRecord) {
>                                        r.field = new SimpleIntFieldHolderForRecord(initField());
>                                }
>                                return r.field.get(r);
>                        }
>                }
>
>                private IntHolderFor<Record> field = new LazyIntFieldHolderForRecord();
>                private static int initField() { return 1; }
>
>                public int getField() {return field.get(this);}
>        }
>
>
>        public static void main(String args[]) {
>                Record r = new Record();
>                System.out.println("field = " + r.getField());
>        }
> }
>
> Only additional pointer and indirect call with parameter added, right?
>

[Oleg G.]

Sorry for the flood, it's just indirect call, no parameter needed:
        public static interface IntHolder {
                public int get();
        }
       
        public static class Record {
                public static class SimpleIntFieldHolderForRecord implements IntHolder {
                        private final int value;
                        public SimpleIntFieldHolderForRecord(int initialValue) { value =
initialValue; }
                        @Override public int get() { return value; }
                }
               
                public static class LazyIntFieldHolderForRecord implements IntHolder {
                        private final Record r;
                        public LazyIntFieldHolderForRecord(Record r) { this.r = r; }
                        @Override public synchronized int get() {
                                if (r.field instanceof LazyIntFieldHolderForRecord) {
                                        r.field = new SimpleIntFieldHolderForRecord(initField());
                                }
                                return r.field.get();
                        }
                }

                private IntHolder field = new LazyIntFieldHolderForRecord(this);
                private static int initField() { return 1; }
               
                public int getField() {return field.get();}
        }

[Oleg G.]

My java code is about 4-5 times slower than volatile-based check.
I could do it all without posting to the mail list, so i'm sorry for
the impatience.
But at least this topic is now discussed and completed with code and
numbers, might help someone :)

Thanks again for all the answers.

P.S. Here is the final Test.java:
public class Test {
        public static interface IntHolder {
                public int get();
        }
       
        public static class Record {
                public static class SimpleIntFieldHolderForRecord implements IntHolder {
                        private final int value;
                        public SimpleIntFieldHolderForRecord(int initialValue) { value =
initialValue; }
                        @Override public int get() { return value; }
                }
               
                public static class LazyIntFieldHolderForRecord implements IntHolder {
                        private final Record r;
                        public LazyIntFieldHolderForRecord(Record r) { this.r = r; }
                        @Override public synchronized int get() {
                                if (r.field instanceof LazyIntFieldHolderForRecord) {
                                        r.field = new SimpleIntFieldHolderForRecord(r.initField());
                                }
                                return r.field.get();
                        }
                }

                private IntHolder field = new LazyIntFieldHolderForRecord(this);
                private int initField() { return 1; }
               
                private volatile boolean flag = false;
                private int f = 0;
                public int getField() {return field.get();}
                /*public int getField() {
                        if (flag) {
                                synchronized(this) {
                                        f = 1;
                                        flag = true;
                                }
                        }
                        return f;
                }*/
        }
       
        public Record r = new Record();
       
        public static class TestThread extends Thread {
                private Record r;
                private int v;
                public TestThread(Record r) { this.r = r; }
                public void run() {
                        for(int i = 0; i < 10000000; i++) {
                                v = r.getField();
                        }
                }
        }
       
        public static void main(String args[]) {
                Test t = new Test();
                Long time = System.currentTimeMillis();
                new TestThread(t.r).run();
                new TestThread(t.r).run();
                new TestThread(t.r).run();
                new TestThread(t.r).run();
                new TestThread(t.r).run();
                System.out.println(System.currentTimeMillis() - time);
        }
}

[Jorge Ortiz-3]

On Wed, Oct 21, 2009 at 10:11 AM, Paul Phillips <paulp@...> wrote:

Seems like there are two birds we could peg here if we solved the issues
with null, because the equivalent of "lazy val: String with NotNull"
could now safely be initialized to null and updated in place.  I doubt
you can get much cheaper than a null check.

No, you cannot. If you don't establish a happens-before relationship, events on another thread are not guaranteed to 1) happen in order, or even 2) happen at all.

You could see the reference change from null to a pointer, but because of reordering, that pointer might be to an unintialized or incorrectly initialized object.

For this reason, all of Oleg's code examples are not only slower but also fundamentally broken.

--j

[Paul Phillips-3]

On Wed, Oct 21, 2009 at 12:50:49PM -0700, Jorge Ortiz wrote:
> You could see the reference change from null to a pointer, but because
> of reordering, that pointer might be to an unintialized or incorrectly
> initialized object.

I meant a volatile null check, avoiding the bitmap$0 lookup.  I realize
there will always have to be some form of coordination, that was the
point of my previous email.

--
Paul Phillips      | Eschew mastication.
Future Perfect     |
Empiricist         |
i pull his palp!   |----------* http://www.improving.org/paulp/ *----------

[Oleg G.]

> For this reason, all of Oleg's code examples are not only slower but also
> fundamentally broken.
Quote from http://www.ibm.com/developerworks/library/j-jtp03304/ again:
The new JMM also seeks to provide a new guarantee of initialization
safety -- that as long as an object is properly constructed (meaning
that a reference to the object is not published before the constructor
has completed), then all threads will see the values for its final
fields that were set in its constructor, regardless of whether or not
synchronization is used to pass the reference from one thread to
another

So it means that we can only know that constructor has completed by
using volatile field assignment after it (which enforces the
happens-before relationship)?

[Jorge Ortiz-3]

You need to take care to safely publish your Test class, because your IntHolder field isn't final.

You can also run afoul of visibility. Quoting your link:

"When a thread exits a synchronized block as part of releasing the associated monitor, the JMM requires that the local processor cache be flushed to main memory. (Actually, the memory model does not talk about caches -- it talks about an abstraction, local memory, which encompasses caches, registers, and other hardware and compiler optimizations.) Similarly, as part of acquiring the monitor when entering a synchronized block, local caches are invalidated so that subsequent reads will go directly to main memory and not the local cache. This process guarantees that when a variable is written by one thread during a synchronized block protected by a given monitor and read by another thread during a synchronized block protected by the same monitor, the write to the variable will be visible by the reading thread. The JMM does not make this guarantee in the absence of synchronization -- which is why synchronization (or its younger sibling, volatile) must be used whenever multiple threads are accessing the same variables."

If the reader thread thread doesn't, before reading the field, acquire the same lock that the writer released after swapping the field, you won't necessarily see the field swap. In which case, initField might be called once by every thread in your program.

--j

On Wed, Oct 21, 2009 at 1:26 PM, Oleg G <ojowoo@...> wrote:

> For this reason, all of Oleg's code examples are not only slower but also
> fundamentally broken.

Quote from http://www.ibm.com/developerworks/library/j-jtp03304/ again:
The new JMM also seeks to provide a new guarantee of initialization
safety -- that as long as an object is properly constructed (meaning
that a reference to the object is not published before the constructor
has completed), then all threads will see the values for its final
fields that were set in its constructor, regardless of whether or not
synchronization is used to pass the reference from one thread to
another

So it means that we can only know that constructor has completed by
using volatile field assignment after it (which enforces the
happens-before relationship)?

[Oleg G.]

> If the reader thread thread doesn't, before reading the field, acquire the
> same lock that the writer released after swapping the field, you won't
> necessarily see the field swap. In which case, initField might be called
> once by every thread in your program.

Thanks for the explaination, Jorge. This is really a fundamental flaw
in my idea.

[Nils Kilden-Pedersen]

Can't we get around volatile access by using the Initialization-on-demand holder idiom?

http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom

I, too, would like to get rid of volatile access for lazy fields.

On Wed, Oct 21, 2009 at 11:30 PM, Oleg G <ojowoo@...> wrote:

> If the reader thread thread doesn't, before reading the field, acquire the
> same lock that the writer released after swapping the field, you won't
> necessarily see the field swap. In which case, initField might be called
> once by every thread in your program.

Thanks for the explaination, Jorge. This is really a fundamental flaw
in my idea.

[Dimitris Andreou]

This applies only for _static_ lazy fields, though.

2009/10/22 Nils Kilden-Pedersen <nilskp@...>:

> Can't we get around volatile access by using the Initialization-on-demand
> holder idiom?
>
> http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom
>
> I, too, would like to get rid of volatile access for lazy fields.
>
> On Wed, Oct 21, 2009 at 11:30 PM, Oleg G <ojowoo@...> wrote:
>>
>> > If the reader thread thread doesn't, before reading the field, acquire
>> > the
>> > same lock that the writer released after swapping the field, you won't
>> > necessarily see the field swap. In which case, initField might be called
>> > once by every thread in your program.
>>
>> Thanks for the explaination, Jorge. This is really a fundamental flaw
>> in my idea.
>
>

[Nils Kilden-Pedersen]

On Thu, Oct 22, 2009 at 8:12 AM, Jim Andreou <jim.andreou@...> wrote:

This applies only for _static_ lazy fields, though.

Hmm, that's true. Maybe Scala can create per instance anonymous classes?

Relax, it's a joke.