BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ
News Articles Presentations Podcasts Guides

Topics

Choose your language

QCon New York

Find real-world practical inspiration from the world’s most innovative software leaders. Attend in-person.
QCon San Francisco

Learn what's next in software from world-class leaders pushing the boundaries. Attend in-person or get video-only pass to recordings.
The Software Architects' Newsletter

Your monthly guide to all the topics, technologies and techniques that every professional needs to know about. Subscribe for free.

InfoQ Homepage Articles The Limits of Code Optimization: a new Singleton Pattern Implementation

QCon San Francisco (Oct 2-6): Learn what's next from software leaders pushing the boundaries.

The Limits of Code Optimization: a new Singleton Pattern Implementation

Leia em Português

This item in japanese

Bookmarks

Nov 14, 2008 9 min read

Write for InfoQ

Join a community of experts. Increase your visibility.
Grow your career.Learn more

I’ve found it a well known fact in the programming world that the java (double-check) singleton pattern is not thread safe and can’t be fixed. Here is a triplet of articles ([1], [2], and [3]) that explain why. These articles offer particular implementations of singleton pattern and very fairly explicate how these implementations can be broken, and then conclude with a generalized statement.

Worth mentioning is that in the work “The ‘Double-Checked Locking is Broken’ Declaration” [4], signed amongst others by Jeremy Manson and Bill Pugh (authors of the java 1.5 memory model), the authors suggested a fix for the double-checked singleton pattern in java 1.5 (the part “Fixing Double-Checked Locking using Volatile”).

Any discussion about java synchronization needs to consider an extensive and not very well defined java optimization. The Java Language Specification Third Edition (JLS3) [5] comments:

The specification provides a great deal of freedom for the implementor to perform a myriad of code transformations, including the reordering of actions and removal of unnecessary synchronization

The main purpose of this article is to test the “boundary conditions” of the programming language optimization. This task requires a non-standard approach, which I try to develop here.

Any offering of a programming language synchronization construct stands on a very shaky ground as long as it does not use general principles: what is allowed and what is not allowed with optimization. My idea is to show that if optimization can break code only by violation well accepted general principles, then such optimization is impossible (or at least, incorrect). And if we stand on this position, we can even make a statement about any programming language, not necessary about java only. Really, java uses the synchronized primitive, C# uses lock, C used POSIX primitives with Mutex, C++ also uses Mutex (on Win32 and Solaris), Python - lock, Ruby Mutex again. The question is then, can we try to generalize by deduction without jumping to a conclusion from specific examples?

The JLS3 uses the following definition of the intra-thread semantics:

The semantics for single threaded programs that allow the complete prediction of the behavior of a thread based on the values seen by read actions within the thread. The actions of each thread in isolation must behave as governed by the semantics of that thread.

We will be using the following weaker form of this definition:

The programming language implementation provides a minimum intra-thread semantics (minimum ITS) if any compile time / runtime optimization keeps the semantics of non-optimized code in a single-thread execution up to the level of any method. (We don’t include the inlined methods here).

It’s easy to show that if minimum ITS is broken on the method level, that it also can be broken on the program level.

Definition:       The programming language implementation provides a minimum synchronization if the language synchronization primitive satisfy the following two conditions:

CS1:    only one thread can enter a synchronized block

CS2:    all shared variables for any thread are updated from the main memory on the entry and saved to the main memory on the exit of a synchronized block

Definition:       The method returning a reference to an object produces a phantom-object effect if it is possible with this method to obtain a reference to not a fully constructed object

In this article I investigate the relative consistency of one singleton implementation (taking a leaf out of the Mathematical Logic book). More precisely, I will try to illustrate the following statement:

A:        If a programming language implementation provides a minimum ITS and minimum synchronization, the usage of the gOracle pattern (*), is consistent

For this purpose I will try to prove the following statement:

B:        If a programming language implementation provides a minimum ITS and minimum synchronization the gOracle pattern (*) can’t produce the phantom-object effect

From now I move to the context of java programming language, but I believe all the following can be adapted to any of the languages listed above.

So what, then, is the gOracle pattern? As the name hints, I will introduce an oracle, something similar to ancient Greeks’ oracle. My oracle will be 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. But I’ll divulge to you a secret – it always produces true. I will later return to the question of how to build such a method, but for now let me assure you that it is easy enough.

Then my gOracle singleton implementation is as follows:

class Singleton   {

    static private Singleton instance = null;

    static private boolean bInited = false;

 

    private Singleton() {…}

 

    public static Singleton getInstance() {

        if (!bInited || instance==null) {          // FIRST CHECK

            synchronized (Singleton.class)  {

                if (!bInited)  {  // INNER IF-BLOCK, SECOND CHECK

                    instance = new Singleton();

                    int hash = instance.hashCode();

                    bInited = oracle(hash);

                }

            }

        }

        return instance;

    }              

    static boolean oracle(int h) {…}

}

Now I start my defense of gOracle.

The key idea is to show that if java optimization results in the phantom-object effect for getInstance() method, than the minimum ITS would be broken. In a sense, that the execution of such an optimized code in a single-thread mode would potentially produce a different results, than the execution of non-optimized code.

 

1. Let’s call i-thread the thread that first enter the synchronized block. This thread will eventually change the value of bInited variable, even if initially only in its local memory

2. Though compiler has ability to transform getInstance() code, and then runtime has ability change the execution order of operations, no such optimization is allowed to break the minimum ITS for the i-thread executed in isolation

3. The result of the call hash = instance.hashCode() is unpredictable before the constructing of the instance object.

NOTE 1: According to the java API, the default hashCode() is typically implemented by converting the internal address of the object into an integer. But if that is not good enough for unpredictability, we can consider implementing hashCode() for Singleton as

Random rand = new Random(Date.getTime());

int hash = rand.nextInt();

and then let compiler or runtime try to predict inside or before the constructor the value of Date.getTime() placed in the original code order after the constructor!

4. The call bInited = oracle(hash) uses the results of the call instance.hashCode()and unpredictable, as we assumed

5. Therefore the compiler or runtime optimization can’t assign the value (true) of the bInited variable before the complete constructing the Singleton object and assigning to the instance variable in the local memory of  the i-thread

6. After the i–thread exits the synchronized block and before any other thread enter that block, the values of the instance and bInited variables in the main memory will be set to the value from i-thread local memory. Both set operations are atomic.

7. Now consider the behavior of any other thread, let’s call it a w-thread, in minimum ITS semantics. That means, we can assume the order of executions for the w-thread as it specified in the Singleton code, but the shared variables can have “unexpected” values. That is what we will look at now.

Let’s use the following notations:

  •  M(bInited) is the copy of the bInited variable in the main memory
  •  I(bInited) is the copy of the bInited variable in the local i-thread memory
  •  W(bInited) is the copy of the bInited variable in the local w-thread memory

 

  •  M(instance) is the copy of the instance variable in the main memory
  •  I(instance) is the copy of the instance variable in the local i-thread memory
  •  W(instance) is the copy of the instance variable in the local w-thread memory
8. Let’s consider in turn following interesting cases for w-thread.

8.a. The w-thread waits on the synchronized block for i-thread to leave the block – piece of cake. First i-thread leaves the synchronized block, then java synchronizes i-thread local variables to the main memory,

          I(bInited) => M(bInited)                I(instance) => M(instance)

then on w-thread entry to the synchronized block java synchronizes the w-thread local variables from the main memory,

            M(bInited) => W(bInited)                M(instance) => W(instance)

and now the w-thread has a correct view of shared variables, same view as the i-thread has.

8.b. The w-thread is inside or before the FIRST CHECK operation when i-thread leaves the synchronized block.

Note, that W(bInited) and W(instance) are initialized from the main memory ether before or after the I(bInited)and I(instance) were synchronized to M(bInited)and M(instance), which happens after t-thread left the synchronized block. So each of W(bInited) and W(instance) can only have either initial value (as defined in the class Singleton) or the value produced by the i-thread, in any possible combination.

Then w-thread first checks the value of the variable W(bInited).

It value is false w-thread jumps to the synchronized block, essentially as in the case 7.a.

If  W(bInited)==true, then i-thread already has assigned I(bInited)=true and java already synchronized along the chain

I(bInited) => M(bInited) => W(bInited)

Therefore the i-thread already has initialized the Singleton object and at the very least the I(instance) is references that object.

Now next the w-thread checks the value of the W(instance) variable. If W(instance)==null then java not yet synchronizes along the chain

            I(instance) => M(instance) => W(instance)

but no worry, w-thread than only jumps on the entry of the synchronized block and discover the new value of the instance variable there, as in the 7.a case.

But if W(instance)=!null, then the only value that the W(instance)can only have is the value of the I(instance).  Therefore the w-thread will return the fully constructed instance of the Singleton.

9. So for any thread which obtains the instance variable through the getInstance() method it is guaranteed that the Singleton object has already been created and fully initialized by i-thread.

In other words, the only way how compiler/runtime optimization can break the gOracle pattern is by also potentially breaking the single thread execution of its code (assuming that we have minimum synchronization). This proves (for java) the statement B and illustrates the statement A. The defense rests its case.

Corollary: In any JDK 1.4 implementation provides the minimum ITS requirement, the gOracle pattern can’t produce there the phantom-object effect.

Let’s return to the question of how to find such an oracle for gOracle. What about some non-trivial mathematical statement, like:

  • the sum of every two sides of a triangle must be greater than or equal to the third side
  • any integer can be presented as a product of primes

Taking to the second statement, let’s implement oracle like this:

static boolean oracle(int hash) {

   Random rand = new Random(Date.getTime());

   int iNum = rand.nextInt() + hash;

   iNum = iNum % 100;   // optional line

   if( found iNum presentation as product of primes )

      return true

   else

      return false;

}

I hope you agree that the compiler designers are not Gods or Oracles yet and can’t teach compiler or runtime to recognize the usage of the Fundamental Theorem of Arithmetic [6] or Euclid Geometry Axioms in java code.  And then there is the Big Ferma Theorem.

 (*) I introduce the name “gOracle” for my implementation of the singleton pattern to express its Greek origin, the idea of “predicting the future” and how it was used by ancient Greeks, not to be confused with some product from the Oracle Corp.

References

1. Double-checked locking and the Singleton pattern, by peter Haggar

2. Double-checked locking: Clever, but broken, by Brian Goetz

3. Java theory and practice: Fixing the Java Memory Model by Brian Goetz

4. The "Double-Checked Locking is Broken" Declaration, by Jeremy Manson, Bill Pugh …

5. Java Language Specification, Third Edition

6. Fundamental theorem of arithmetic  

Rate this Article

Adoption
Style

This content is in the Threading topic

Related Topics:

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Community comments

  • Broken link

    by Daniele Bufarini,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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

    Back to top
  • Joshua Bloch claims that it works in Java 5.0+

    by Daniel Wiell,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    Joshua Bloch claims that it works in Java 5.0+

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

    Back to top
  • Re: Joshua Bloch claims that it works in Java 5.0+

    by Daniel Wiell,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Why bother? It's all too much

    by Lindsay Holman,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • link - this one works for me

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

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

    Back to top
  • Re: Joshua Bloch claims that it works in Java 5.0+

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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...

    Back to top
  • Re: Joshua Bloch claims that it works in Java 5.0+

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Link?

    by Thom Nichols,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Re: Link?

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Re: Why bother? It's all too much

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

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

    Back to top
  • Re: Why bother? It's all too much

    by Lindsay Holman,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Doesn't fix DCL

    by Oliver Ebert,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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).

    Back to top
  • Re: Doesn't fix DCL

    by Lukas Krecan,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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

    Back to top
  • Re: Doesn't fix DCL

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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

    Back to top
  • Re: Doesn't fix DCL

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Re: Doesn't fix DCL

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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).

    Back to top
  • Re: Doesn't fix DCL

    by Oliver Ebert,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.

    Back to top
  • Re: Doesn't fix DCL

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.>

    Back to top
  • Re: Doesn't fix DCL

    by Oliver Ebert,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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.


    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)
    >
    Yes, all that might be true, but that's not the point here.


    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>

    Back to top
  • Re: Doesn't fix DCL

    by Alexey Yakubovich,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    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

    Back to top

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

BT