Tracking change and innovation in the enterprise software development community
Free Book Offer
SOA Demystified
$40 Value
QCon London 2010!
March 10-12, 100
Speakers, 80 sessions,
"THE" team leads and,
architects conference.
Scaling Scrum
in the enterprise?
ScrumWorks Pro
can help.
Start a trial today
Posted by Jean-Jacques Dubray on Nov 18, 2008
In this new article, Dr. Alexey Yakubovich, discusses the limits of code optimization in the context of the Singleton pattern implementation and offers an enhanced implementation that prevents some of the side effects of code optimization in current JVMs. He explains:
The main purpose of this article is to test the “boundary conditions” of the programming language optimization.
The core of Alexey's argument is to introduce a new method in the Singleton pattern's implementation
a method with the signature static boolean oracle(int h) and one very special quality – there is no way for java compiler or java runtime to predict the value produced by this method.
Right Collaboration Architecture Drives Business Transformation
Technical Debt and Design Death
Understand and Align BPM, SOA, and Lean Six Sigma: 43 page IBM Redguide
Architectures Behind Facebook, Skype, Sky.com, Bwin, League of Legends @ QConLondon
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.
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
}
Which I believe is part of why DCL is broken under the old memory model prior to 1.5. The JMM requires an "atomic sync" between i-thread's local and main memory on exit of the synchronized block, but it doesn't prohibit a (partial or re-ordered) earlier write-back. At least this is my understanding of the JMM and the difficulties with DCL. Could you elaborate on how hashCode() or oracle(int) is supposed to affect visibility, that is how, when and in which order i-thread's local memory is made visible to other threads? ("per-thread as-if-serial" semantics are not violated or even affected by the order of write-back to main memory as this is not observable by i-thread in any way).
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.
So what values would W-thread see for instance's fields if it would access them? How does one determine exactly when instance construction (creation/initialization etc.) is completed? E.g. in thread i-thread:
instance = new Singleton();
// do something with instance
How would i-thread ever notice that initialization is not completed when instance is assigned due to some re-ordering optimizations etc.? It must not, because otherwise "per-thread as-if-serial" semantics (and I guess Java itself) would be broken.
So the incomplete construction can only be observed from a different thread other than i-thread; e.g. w-thread. Now how does w-thread determine if instance construction has completed? Well, it reads instance's field(s) in order to see their values. And this is basically where I started in my last reply. In your proof, you focus on whether instance construction is completed; but the real issue is not whether instance creation is actually completed or not, but if it is also observed as being completed, that is if the completed consturction also becomes visible to other threads different from i-thread. And it is not an issue of re-ordering execution (that is machine instructions), but re-ordering memory transfers from i-threads working memory (that is CPU registers and multi-level caches) to main memory, i.e. when values become visible to other threads.
You wrote:
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.
Yes, it may be finished in i-thread, but is it finished for w-thread, too? Even if we assume that Singleton instance creation is "complete" (meaning here all it's field values are initialized etc.) in i-thread when bInited is set to true, in the absence of synchronization there is no guarantee when and in which order the operations performed on i-thread's working memory are transferred to main memory and thereby made visible to other threads like w-thread. w-thread might see a stale value that has a more up-to-date value in i-thread's local working memory.
This is explained e.g. here: gee.cs.oswego.edu/dl/cpj/jmm.html
Some quotes:
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.
and:
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.
I gave a possible scenario in my last reply. The worst case is that bInited and instance reference are up-to-date when w-thread reads them, but (one or more of) Singleton instance's fields contain stale values. Without synchronization, i-thread and w-thread might have a different (inconsistent) view on the contents of memory. What I don't understand is exactly how your proposal with hashCode() and gOracle is supposed to solve these visibility issues.
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.
I have to admit I'm a bit disappointed by your reply, because (again) you did not address any of the issues I brought up in my comments. I provided an example scenario and described what is not clear to me wrt. visibility, yet you ignore this topic completely.
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.
Yes, this is the step in your reasoning that I'd like to talk about. But you did not explain it anywhere; the JMM offers several quite specific guarantees, but you didn't specify which of those your assumptions are actually based on. Although I elaborated on that same issue twice now, I'll then use your last reply to do so again. (assuming M-memory == main memory, W-memory == W's working memory, ...)
Case A is trivial, because both threads actually synchronize on the same monitor.
Case B:
Sub-case B1:
Because W-thread didn’t modify bInited (yet), bInited was synchronized from M-memory before t0, say at tm1 < t0.
I find the term "synchronized" a bit misleading here. Since w-thread is not synchronized when checking bInited or instance (in FIRST CHECK), there is effectively no synchronization. Let's say w-thread's working memory is updated from main memory.
Yes, all that might be true, but that's not the point here.
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.
Yes, again all that might be true, but it's not the question. You're saying that at time t0 bInited and instance were "synchronized" so that w-thread sees their latest values (true and != null, respectively). And that at t0 instance points at a fully constructed object. Now you simply assume that once the up-to-date values of bInited and instance become visible, the completed construction (i.e. the contents of i-thread's working memory holding instance's field values) has also somehow become visible to main memory and subsequently w-thread's working memory at this point in time, even though w-thread accesses bInited and instance without synchronization (in FIRST CHECK). But how is this guaranteed by the JMM, hashCode() or gOracle? In the absence of synchronization, I don't see such a guarantee. (See my previous comments). w-thread might still see stale (default) values for instance's fields, because they have not been transferred from i-thread's working memory -- where construction is actually complete at t0 -- to main memory to w-thread's working memory. To repeat myself: when and in which order write-back to main memory (or update of w-thread's working memory) happens does not affect "per-thread as-if-serial" (or ITS here) for i-thread in any way, because it is not aware of CPU registers, multi-level caches, other threads and so forth.
You wrote that you "would expect either (I) follow the reasonings and find the error or … agree.", but I'm not pointing out an error, but a step in your reasoning that is based on assumptions without you providing evidence of exactly how this is supported by guarantees made by the JMM; or in short: why does the visibility of bInit and instance to w-thread imply the visibility of instance's fields to other threads such as w-thread in the absence of synchronization? So before being able to agree or disagree (and find an error, for that matter), I'd like to hear your comments on that specific issue. "I(instance) points to a fully constructed object at moment t0" doesn't really say anything per se, because without synchronization whether construction is observed to be complete or not depends on the point of view (the thread): For one thread, construction might be completed, while for another at the same time, maybe not...
(Apologies for the excessive quoting/emphasis, but I wanted to make sure that this time my question becomes clear).
<//blockquote>
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
Brian Marick takes us through a quick tour of the most important values and challenges to adopting Agile successfully (they aren't the typical challenges and values we hear in the community).
The line between development and architecture is tricky. Does it exist at all? Is an ivory tower actually needed? There's a balance in the middle, but how do you move from developer to architect?
The word 'authority' sometimes produces an allergic response in hard-line agilists. Freedom and authority – both are bad if misused and both are good if used in right spirit for a noble cause.
"Getting Started with Grails" brings you up to speed on this modern web framework. Companies as varied as LinkedIn, Wired, and Taco Bell are all using Grails. Are you ready to get started as well?
Those familiar with only ITIL V2 often scoff at the thought that ITIL could serve as a governance framework for SOA. With ITIL V3, the focus of the framework shifted towards service-orientation.
SpringSource CTO Adrian Colyer discusses AspectJ, SpringSource's dm Server and tc Server products, OSGi and Scrum.
Heroku's Adam Wiggins talks about Rails, Background Jobs, Add-Ons, Ruby, and how Heroku manages to work around Ruby's inefficiencies using Erlang and other languages.
For Grady Booch the foundation of a good architecture is patterns, SOA being just one of many patterns. In this Second Life presentation, Booch attempts to bring more clarity on what architecture is.
20 comments
Watch Thread Reply