Article: The Limits of Code Optimization: a new Singleton Pattern Implementation

Hi,
the link for "Java theory and practice: Fixing the Java Memory Model" by Brian Goetz is broken... can you post the correct one?
Thanks!

Daniele

Joshua Bloch claims that it works in Java 5.0+

java.sun.com/developer/technicalArticles/Interv...

Correction: This wasn't about singletons but lazy initialization. Sorry about that.

However, it's still an interesting link - he mentions the approach of using a single-element enum to get a singleton.

a) Why don't we take the principles of dependency injection (a class isn't responsible for object lifecycle issues), and apply them equally to singletons. Tell the IOC container to only instantiate 1 object, and pass that to everything that needs it.
b) If we are using singleton in a situation where the single instance is crucial to data integrity, maybe a re-design is in order, after all, the design is unlikely to be distributable.

www.javaworld.com/jw-02-2001/jw-0209-double.htm...

I agree. This is essensially the same as in the ". The "Double-Checked Locking is Broken" Declaration" for 1.5 and later - combination of volatile and volatile (only declaration published four years yearlier). And the same as i stated in the begining of the current work:

"Worth mentioning is that in the work “The ‘Double-Checked Locking is Broken’ "

However, I believe I formulated a mode general statement, which accidentally works for 1.4 too...

Also the original title was not like this - "a new Singleton Pattern Implementation", the title was ... "Singleton, gOracle Oracle and limits of code optimization". I don't claim that this is the first correct "Double check locking" singleton implementetion. And in text there is no such statement. Just a little confusion with the title, which is not exactly my fault, but it is much better this way than no way.

Is it just me, or is there no link to the article in this news post??

Here is a link to a related article on DeveloperWorks.

But these days, generally I either (1) do not lazy-initialize singletons, or (2) let the DI container manage singletons.

Yep, this article in #1 in my reference list. Well, you use what you think is right, still there are plenty artivles on the topic, some changes since 2002 in java too (new 1.5 memory model).

Is it just me, or is there no link to the article in this news post??

Here is a link to a related article on DeveloperWorks.

But these days, generally I either (1) do not lazy-initialize singletons, or (2) let the DI container manage singletons.

Still singleton is one of 23 patterns in the Gang of Four book, one of majors.

Nothing lasts forever, I think this is one GOF pattern which is headed for anti-pattern status, it is certainly already there in my mind. It may be an entertaining intellectual exercise, but in reality there are simpler and more reliable ways of achieving the same goal.

It might be that I'm totally missing your point, but I think the proposal doesn't fix DCL. The problem is not to guarantee that construction of the singleton instance is completed, but making the completed construction safely visible to other threads; that is, it's a question of safe publication (see Goetz, Java Concurrency in Practice, Chap. 3 + 16). Inside the thread that is constructing the singleton instance ("i-thread"), the JVM guarantes "per-thread as-if-serial" semantics hold true, no matter what optimizations the environment might apply. But with more than one thread, a "happens-before" relationship needs to be established using synchronization (or volatile in 1.5+).

So even if one can guarantee that the singleton instance construction is complete in i-thread when bInit is set to true, there is no guarantee that this construction is made visible to w-thread atomically. Since the FIRST CHECK uses no synchronization and neither bInited nor instance is declare volatile, it should be legal under the JMM that w-thread observes both bInited == true and instance != null, but nevertheless sees stale (default) values for instance's fields even though instance construction was completed in i-thread when bInited was set to true. This is because w-thread and i-thread are different threads of execution, and in the absence of synchronization there is no "happens-before" relationship, so the values for bInited, instance and instance's fields might be written back to main memory from i-threads local memory (and observerd by w-thread) in any order, in particular nothing prohibits bInited and instance getting written back before instance's fields. Ex.:

synchronized (Singleton.class) {
    instance = new Singleton();
    // re-ordering is permitted;  Singleton instance is published,
    // but instance's default field values get written back to main
    // memory before they're initialized by constructor, i.e. main
    // memory holds stale values (the problem with the original DCL)
    int hash = instance.hashCode();
    bInited = oracle(hash);  // true, gets written to main mem
    // at this point a w-thread could observe bInited == true &&
    // instance != null, but nevertheless stale values for
    // instance's fields as they've not been written back yet
}

I think it is waste of effort to try to solve something that is already solved. Nice and elegant solution for singleton initialization problem can by found here

You are right in sense that this is a possible solution - and in my references ("Double-Checked Locking is Broken’ Declaration”) it was discussed, only it was in 2004, three years yealier that in crazybob.org/2007/01/lazy-loading-singletons.html.

My point is LIMITS OF CODE OPTIMIZATION, noy finding the most efficient solution for singleton

Oliver,

That's greate that you got into details. I will answer you later, just can't do it now. I am very glad though that you are interested.

Ok, now I am answering. Well, I believe you are missing couple of points in this your note. Or you see more than you wrote in your comment. The “stale variable” is not the reason why traditional DCL fails, see article references (1-4) where it explained. Shortly, on the contrary, the reason of failure is that other threads (W-thread) see updated value of instance (not null), while the initialization of the “instance” object is not completed. Returning to my construction:

1. The initial (stale) values of bInit is false and of instance is null for any thread, including W-thread. So if W-thread sees the “stale” value of any of those, if will go through “synchronize” block and immediately gets non-stale values there
2. So if w-thread during the “FIRST CHECK” sees at least one stale value, it goes to “synchronize” block
3. The real problem with typical DCL is that W-thread sees a new, updated value of instance, but the initialization of object (in I-thread) is not finished.
4. In my construction, I believe I proved, if W-thread sees bInit==true and instance!=null, the initialization in I-thread is guaranteed been finished before that. This is a whole point of intruding on “oracle”, not danger from stale variables. This is exactly the way to provide “safe publication” and “happens-before”.
5. Not all languages which support synchronization or locking also support “volatile”. And though java 1.4 supports “volatile’, it still does not help to make DCL save this way (using volatile).

Well I could not follow your reasoning, that's why I posted my question. The issues I mentioned are actually discussed in the articles you referred to, so I'll try to clarify.

"Stale" variables is not the reason why "traditional" DCL fails, but it is one of the reasons why it can fail.
You wrote:

Shortly, on the contrary, the reason of failure is that other threads (W-thread) see updated value of instance (not null), while the initialization of the “instance” object is not completed.

instance = new Singleton();
// do something with instance

4. In my construction, I believe I proved, if W-thread sees bInit==true and instance!=null, the initialization in I-thread is guaranteed been finished before that.

The memory model guarantees that, given the eventual occurrence of the above operations, a particular update to a particular field made by one thread will eventually be visible to another. But eventually can be an arbitrarily long time. Long stretches of code in threads that use no synchronization can be hopelessly out of synch with other threads with respect to values of fields.

The model also allows inconsistent visibility in the absence of synchronization. For example, it is possible to obtain a fresh value for one field of an object, but a stale value for another. Similarly, it is possible to read a fresh, updated value of a reference variable, but a stale value of one of the fields of the object now being referenced.

Hi again, Oliver. I understand you general reasoning and general concerns, but I believe that though it abstractly applicable to multithread programming, it has little to do with my particular construct.

You saying “I could not follow your reasoning” and asking: “Yes, it may be finished in i-thread, but is it finished for w-thread, too?” Below I try to explain why it is true. Though I think I did explain it in article too, I just do it in more details here. Only let me to notice, that I would expect either you follow the reasonings and find the error or … agree.

Let’s consider only two threads: i-thread and one W-thread for simplicity. Let’s say that the W-thread reached the FIRST CHECK at the moment t0. Before that some values were copied from M-memory to W-memory

Following 2 cases, A and B are possible

Case A: W(bInited) == false or W(instance)==null (or both).

Does not matter what are values of bInited and instance in M-memory and in I-memory. In this case the W-thread goes to synchronize block, wait until i-thread leaves that block, and enters the block let’s say at moment t1 > t0. Strictly before t1 the following things should happen:

1. i-thread left the synch. block
2. before that i-thread fully created the instance object
3. i-memory been synchronized to M-memory
4. M-memory been synchronized to W-memory

So at t1 the W(instance) points to fully created object and W(bInited)==true. W-thread is happy

Case B: W(bInited==true) and W(instance!=null) (moment t0)

Let’s consider bInited first. There are two sub-cases: B1 and B2

Sub-case B1. When W-thread was launched initially W(bInited) was initialized to false, but at t0 W(bInited) is true

Because W-thread didn’t modify bInited (yet), bInited was synchronized from M-memory before t0, say at tm1 < t0. But how bInited got true in M-memory? Initially bInited was initialized as false in M-memory. So bInited in M-memory was synchronized with bInited from some other thread. Easy to see, that the original thread that caused bInited be set true in M-memory can only be i-thread. So I(bInited) was set to true in i-thread at some moment tm2< tm1. But that exactly means that I(instance) object was fully constructed in i-thread at some moment tm3<tm2 (this is what oracle() provides)

So we have:
I(instance) points at fully constructed object at moment t0
To the moment t0 W(bInited) was synchronized from M-memory, which was synchronized from I-memory.

Sub-case B2. W(bInited) was true from the beginning in W-thread. That means, that when data were copied from M-memory to W-memory at the W-thread startup, bInited was already true in M-memory. Again, how it could be true if originally M(bInited)==false? Only because M(bInited) was synchronized from i-memory. And so on, as in sub-case B1, with the result: Now returning to case B mainstream let’s consider the instance variable. In case B we have W(instance)!=null. Absolutely the same way as for bInited, we conclude:

I(instance) points at fully constructed object at moment t0
To the moment t0 W(bInited) was synchronized from M-memory, which was synchronized from I-memory.

Now, about the same reasoning proves the rest. I can provide it, if you want.>

Hi Alexey.

I understand you general reasoning and general concerns, but I believe that though it abstractly applicable to multithread programming, it has little to do with my particular construct.

You saying “I could not follow your reasoning” and asking: “Yes, it may be finished in i-thread, but is it finished for w-thread, too?” Below I try to explain why it is true. Though I think I did explain it in article too, I just do it in more details here. Only let me to notice, that I would expect either you follow the reasonings and find the error or … agree.

Because W-thread didn’t modify bInited (yet), bInited was synchronized from M-memory before t0, say at tm1 < t0.

But how bInited got true in M-memory? Initially bInited was initialized as false in M-memory. So bInited in M-memory was synchronized with bInited from some other thread. Easy to see, that the original thread that caused bInited be set true in M-memory can only be i-thread. So I(bInited) was set to true in i-thread at some moment tm2< tm1. But that exactly means that I(instance) object was fully constructed in i-thread at some moment tm3<tm2 (this is what oracle() provides)
>

So we have:
I(instance) points at fully constructed object at moment t0
To the moment t0 W(bInited) was synchronized from M-memory, which was synchronized from I-memory.

Oliver,

I am value your opinion and would be interested to talk more. At the same time I think it probably better to move discussion to out personal emails. I don't know yours; I suggest you drop me message on mine: alexeyy4@yahoo.com. I then write you back, and may be we even can talk on phone.

Thanks

Alexey