Solving Lazy Initialization and double checked locking problem

[Vinay Aggarwal]

I have been thinking about the lazy initialization and double checked
locking problem. This problem is explain in detail here
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
I am not fully convinced that this problem cannot be
solved. I am going to propose a solution here. For the sake of
discussion I will post my solution here. It is possible that the
proposed solution does not work, feedback and comments are welcome.

Here is the original problem. We need to lazy initialize a non static
variable to an instance of a heavy object in a thread safe way. (It is
very easy to safely initialize a static variable). The most commonly
used code is as follows:
---------------------------------------------------------------------------
public class LazyInit
{
private HeavyObject heavyObject =
null;

public HeavyObject
getHeavyObject()
{
if (heavyObject ==
null)
{
synchronized(this)
{
if (heavyObject == null)
{
heavyObject = new HeavyObject();
}
}
}
return
heavyObject;
}
}

---------------------------------------------------------------------------

Unfortunately, this code is broken as described at
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html.
The problem arises from the fact that the optimising compilers can
reorder the constructor call and the assignment to the heavyObject
variable.

In my proposed solution, I am going to use polymorphism to appropriately
syncronize the initialization and after its safe initialization, replace
the implementation itself to be unsynchronized. Here is the code,
detailed description follows.

---------------------------------------------------------------------------
import java.util.*;

public class
LazyInit
// line 3
{
private static HeavyObjectInit heavyObjectInitStatic = new
HeavyObjectInit(); // line 5
private HeavyObjectInit heavyObjectInit = new
HeavyObjectInitSync(); // line 6
private volatile HeavyObject heavyObject =
null; // line 7

static class HeavyObjectInitSync extends
HeavyObjectInit // line 9
{
public HeavyObject getHeavyObject(LazyInit
lazyInit) // line 11
{
HeavyObject heavyObject =
getHeavyObjectInternal(lazyInit); // line 13
lazyInit.heavyObjectInit =
heavyObjectInitStatic; // line 14
return
heavyObject;
// line 15
}

private synchronized HeavyObject getHeavyObjectInternal(LazyInit
lazyInit) // line 18
{
if(lazyInit.heavyObject ==
null) // line 20
{
lazyInit.heavyObject = new
HeavyObject(); // line 22
}
return
lazyInit.heavyObject;
// line 24
}

}

static class
HeavyObjectInit
// line 29
{
public HeavyObject getHeavyObject(LazyInit
lazyInit) // line 31
{
return
lazyInit.heavyObject;
// line 33
}
}

public HeavyObject
getHeavyObject()
// line 37
{
return
heavyObjectInit.getHeavyObject(this);
// line 39
}
}

---------------------------------------------------------------------------

Explanation:
Lets assume this code is executing in a multi threading environment. Now
lets say a few threads enter LazyInit.getHeavyObject() at line 37
simultaneously. These threads will reach
heavyObjectInit.getHeavyObject() at line 39. Since heavyObjectInit is
initialized to HeavyObjectInitSync (at line 6), these threads will enter
getheavyObject() at line 11. At line 13, only one thread (lucky thread)
will be able to enter the syncronized method getHeavyObjectInternal
while rest of threads will be blocked at line 18. The lucky thread will
initialize the heavy object and return it. Since the thread is exiting a
syncronized method and the variable is volatile, the HeavyObject will be
fully initialized before the thread releases the lock. Now the lucky
thread will switch the implementation of heavyObjectInit to a non
syncronized initializer (line 14). Any threads reaching line 39 after
this will call the non syncronized version of getHeavyObject() at line
31. At the same time, all the threads blocked at line 18 will enter the
getHeavyObjectInternal() method one by one and return with the singleton
heavy object instance.

Thus initially a few threads will be synchronized till the lucky thread
switches the initializer. At this time the system will switch to non
syncronized implementation. Note that non syncronized implementation
(line 33) does not even incur the cost of null check as compared to the
original algorithm.

There are some intricacies that I have tried to explain in Q&A form.


Why is the instance of HeavyObjectInitSync nonstatic while instance of
HeavyObjectInit static?
If the HeavyObjectInitSync instance is made static, the syncronized
method will syncronize on the single instance of the class. Since all
instances of LazyInit will refer to single instance of
HeavyObjectInitSync, the call will be mutually exclusive across ALL
instances of LazyInit. Essentially if there are 1000 LazyInit objects
each one wanting to initialize HeavyObjects, these objects will get
initialized sequentially, thus slowing down the process. By making the
instance non static, different instances of LazyInit can initialize the
HeavyObject in parallel.
The HeavyObjectInit instance is static because we dont need one instance
of the HeavyObjectInit class with every instance of LazyInit. This
eliminates unnecessary object creation.

Why is HeavyObjectInitSync class static?
This class can be static or non-static. It is a matter of personal
choice. It should work both ways. I wanted to be consistent with
HeavyObjectInit class.

I have a code sample that shows how different threads will execute.
Download it here http://24.167.121.42/LazyInit.java

The output of this program demonstrates
1. Different threads entering one instance of LazyInit get blocked till
the HeavyObject is initialized.
2. Different threads entering different instances of LazyInit can
initialize the heavy object simultaneously.
3. The HeaveyObject is initialized only once per instance of LazyInit.
4. After the initialization is complete, any other threads entering that
instance of LazyInit do not syncronize anymore.


Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

 

[=?iso885915?q?Roger_Lindsj=F6?=]

I have been thinking about the lazy initialization and double checked
locking problem. This problem is explain in detail here
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html I
am not fully convinced that this problem cannot be solved. I am going to
propose a solution here. For the sake of discussion I will post my
solution here. It is possible that the proposed solution does not work,
feedback and comments are welcome.

Sorry, but I don't think it works.

Since the thread is exiting a
syncronized method and the variable is volatile, the HeavyObject will be
fully initialized before the thread releases the lock. Now the lucky
thread will switch the implementation of heavyObjectInit to a non
syncronized initializer (line 14). Any threads reaching line 39 after
this will call the non syncronized version of getHeavyObject() at line
31. At the same time, all the threads blocked at line 18 will enter the
getHeavyObjectInternal() method one by one and return with the singleton
heavy object instance.

Here I think it goes wrong. The JIT should be free to reassign the
instructions as long as it does not change the execution of the current
thread according to the specs. This would allow it to:

lazyInit.heavyObjectInit = heavyObjectInitStatic; // line 14

before line 13 since this does not change anything for the executing
thread. However, now another thread can enter LazyInit.getHeavyObject()
and get the non synchronized implementation with an uninitialized object
before the first thread has had a chance to fully create the heavy
object.

So the second thread could return a null object or a not fully
initialized object.

BTW, comp.lang.java does not exist.

//Roger Lindsjö

 

[Vinay Aggarwal]

Hey Roger,

That was a nice catch. I missed that one.

Now lets follow this logic. The compiler can only reorder the statements
if it does not change anything for the currently executing thread.
So can we create a side effect?

What if I change the inner class to something as follows.


static class HeavyObjectInitSync extends
HeavyObjectInit // line 9
{
public volatile int i=0;
public HeavyObject getHeavyObject(LazyInit
lazyInit) // line 11
{
HeavyObject heavyObject =
getHeavyObjectInternal(lazyInit); // line 13
if(i>0)
lazyInit.heavyObjectInit =
heavyObjectInitStatic; // line 14
return
heavyObject;
// line 15
}

private synchronized HeavyObject getHeavyObjectInternal(LazyInit
lazyInit) // line 18
{
if(lazyInit.heavyObject ==
null) // line 20
{
lazyInit.heavyObject = new
HeavyObject(); // line 22
}
i++;
return
lazyInit.heavyObject;
// line 24
}
}

Now the compiler is bound to keep them in straight order. What do you
think?

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

 

[pete kirkham]

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.


Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Vinay Aggarwal]

Hey Pete,

I do agree with you on some points and disagree on others. You are
correct that mostly this problem doesn't bother us in real world.
Syncronizing the whole method usually is good enough. However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.
I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved. Not only that, I also
believe that this pattern can be used to solve other problems as
well. For example, you mentioned that releasing the singletons is
an issue for some cases. My solution can possibly be extended to
solve such problems.

This whole exercise could be just theoretical. Its out there
in case somebody wants to use it. If there are efforts to change
memory models and threading specifications to solve this problem,
my solution probably interests somebody.

Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

DCL is not much of a problem in the real world. AFAIK no-one has ever
given an example of a profiled application on a modern JVM where the
additional overhead of a synchronized call makes enough of a difference
to use complex DCL alternatives. Show me some code that
does something useful and has at least a 10% improvement in speed in its
critical path by making a faster synchronization mechanism for singletons.

The common solutions to lazy creation are to use class/instance
synchronization (singletons and per-instance resources):

[static] HeavyObject heavyObject;
public [static] synchronized getHeavyObject () {
if (heavyObject==null) {
heavyObject = new HeavyObject();
}
return heavyObject;
}

or the first-call synchronization implicit in class loading (singletons
only):

class HeavyObjectGuardian {
static HeavyObject heavyObject = new HeavyObject();
}

public static getHeavyObject () {
return HeavyObjectGuardian.heavyObject;
}

Edge cases exist where the singleton needs to be released, but your
example doesn't help that in its current form - that would require safe
setting of the heavyObjectInit field, and so you're back to square one
synchronizing that.

On a single or dual processor machine with a recent JVM, a synchronized
method call is only very slightly slower than an non-synchronized call -
DCL was an artifact to get round the slow synchronization in early JVMs.

Speed was the only reason to use DCL in the first place. DCL compromised
deterministic thread safety with probabalistic thread safety (there are
no recorded examples of it failing, but it is theoretically possible) in
order to gain a speed advantage by not using synchronization, as
synchronization was costly at the time.

Therefore alternatives to DCL must be deterministically thread safe (you
can still use DCL if you only need probable safety - if a plane journey
were as safe as a DCL access, then you could travel every day for a
million years and never crash), and either faster or simpler than the
two patterns above to be worthwhile. Those two examples are thread safe,
so execution speed is the *only* criteria to judge a different thread
safe pattern against them.

Plot a graph showing how much faster your method is on single, dual and
multiple processors architectures when compared to the two normal
solutions above, and explain why the additional complexity is worth the
effort in a typical application, where method invocation overhead is a
very minor cost. Without profiling your pattern in a realistic
sscenario, there is nothing to judge its merit, and the simplist
solution wins.

Pete

 

[Chris Uppal]

[snipped]

strange echo in here...

;-)

-- chris

 

[pete kirkham]

However I cannot
say that every application in the world will be better off with
syncronizing the get method. It may be true, it may not. I will
let individual application authors decide what they want to use.

Choice is good, but you have to take into account the reason why method
synchronization isn't used - speed. Synchronizing the method is
deterministically safe, and of minimal complexity.

Unless you do give data showing that your solution is faster, there
there is nothing on which to base that choice.

I believe there are applications where reliability and responsiveness
is much more important than solution complexity. For example
stock trading applications or infrastructure pieces like EJB
containers.

Yes. Therefore to encourage people to look at your solution, show that
in your experience it gives an improvement- profile it under load. You
can't expect people to change their architectures based on a theory that
even the creator doesn't know if it will give any benefit.

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons.

I've seen several, including the use of TLS. None I've tried actually
give an improvement.

Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

No, the whole DCL debate is based on an optimisation applied because it
was commonly believed it would be significantly faster, and adopted
without realising that it breaks safety.

If you give an optimisation, intended to improve speed, and don't give
any figures to back it, then there is no basis for anyone using it. If
you test it on various specific archititectures, then the number will be
valid for those architectures. At the very least, you'll get an idea if
you're going in the right direction.

If it was you that came up with the jet engine, when the world is full
of propeller driven planes, then you have to get something in the air
and flying faster before you can say it's better. Before you take your
idea that far, you have to run one on a bench so you know it's giving
enough thrust (by noting the highest mark the strain gauges reach,
converting that to a equivalent nozzle thrust, then subtracting the
momentum thrust that the mass of air hitting the intake at speed causes-
the benchmark only gives an idea, not what you get in practise) that you
think it's worth making a flying prototype.

There is no theoretic solution to this problem- this sort of
optimisation is engineering not science- the effect is more governed by
the system's environment (how efficiently the JVM implements
synchronization) than any theory you care to apply to it (assuming
you're not modelling the whole JVM and processor architecture as a timed
transition state machine).

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved.

The problem DCL was designed to solve was to provide a solution to
preventing access to a lazily initialised singleton when it is in an
inconsistant state, in a environment with at least two threads, that is
less time costly than synchronizing the whole method.

Therefore, any proposed alternative to DCL that doen't mention the
results of profiling it under load isn't addressing the DCL problem,
only providing another singleton pattern. As close to minimal complexity
threadsafe singleton patterns exist, there doesn't seem to be much point
in creating new ones, but it's your time to spend.

This whole exercise could be just theoretical.

DCL is a pattern to solve an engineering problem which manifested
strongly in the early JVMs, and weakly in later ones. If you are
proposing an alternative to DCL, it is not a theoretical exercise, but
an engineering one.


Pete

 

[Chris Smith]

Now the compiler is bound to keep them in straight order. What do you
think?

I'm not Roger, but it's still broken. The 'volatile' keyword only
constrains memory order with respect to the variable it's applied to.
Worrying about the compiler reordering instructions is only half of the
problem. You still have the problem whereby memory visibility is
undefined from a separate thread, so that the change to the reference
heavyObjectInit is visible to thread B before the changes to the fields
of the new HeavyObject are visible, despite the efforts made to
propogate changes to the integer 'i' in a globally consistent order.

In order for this to work properly, the reference 'heavyObjectInit'
itself of LazyInit would have to be volatile, along with the entirety of
the state of the HeavyObject class (and recursively, any other objects
it keeps references to -- whether direct or indirect). That might be
possible if HeavyObject consists entirely of a primitives, but is likely
to be impossible in most real-world situations.

Frankly, you aren't going to find a general solution that doesn't
involve synchronizing on every object retrieval.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Chris Smith]

My solution does seems complicated than DCL but well its the only
deterministic alternative to method syncronization for instance based
singletons. Individual application authors have to decide for
themselves about how much do they stand to gain with different
implementations. The performance can have huge variation depending on
the application architecture. Hence any numbers I provide are
probably not useful in real world.

This would all be interesting if your solution were deterministic.
Unfortunately, it's not. Unfortunately as well, Pete's talk about DCL's
brokenness being practically a non-issue and merely theoretical is also
far from the case. DCL is specifically quite broken on machines where
memory reordering optimizations are done in the hardware (e.g., Alpha),
and on NUMA platforms with substantially different propogation times for
memory access to different segments of memory (a very interesting area
that encompasses a lot of high-performance distributed computing
applications). If you plan on running your software on these platforms,
treating DCL problems as something that won't happen just because you
don't see it on you x86 PC is sorta like assuming that elephants don't
exist because you haven't seen one in your back yard.

If you're searching for a solution, you need to remember that
introducing new memory ordering issues won't help things, and that
pushing memory reordering/timing problems behind method dispatch (even
polymorphic method dispatch) still won't solve the simple fact that they
are still there.

One of my motives of solving the problem was just to take a shot at
a problem that experts say cannot be solved.

I agree that this is quite fun. I recall I spent a year in the eighth
grade trying to come up with a solution for trisecting an angle with a
straight-edge and a compass. Nevertheless, you should realize that
experts have a good reason for saying that things can't be done... and
when you're working with a deterministic mathematical model as you are
in software, a sound argument that something's impossible doesn't go
away just because you try hard. At a minimum, you should understand the
ground rules and the cause of the problem's difficulty.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Chris Smith]

No, the whole DCL debate is based on an optimisation applied because it
was commonly believed it would be significantly faster, and adopted
without realising that it breaks safety.

I don't think it's that simple. You can't universally assert that DCL
is "safe" or "unsafe". You can only say that relative to some specific
processing model for multithreaded applications. On several modern
models (e.g., POSIX and the Java platform), DCL doesn't work. DCL was
widely adopted, though, before these models ever came into being. DCL
works on most machines, and when targeting a platform or set of
platforms where it works, you can't fault a programmer for using it.

In the end, it's impossible to write software that will work properly
after any given arbitrary change in the behavior of the language, and
the change made to recent threading models (versus some of the older
models which tended to be based on simple hardware characteristics on a
given platform) to accomodate Alpha and other memory reordering
processors and distributed systems is such a case.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Anton Spaans]

Hi Vinay,

Unless 'synchronized' blocks cause unacceptable performance issues, just use
them.
Otherwise, take a look at this:


http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.h
tml

We use it in our software, for lazy caching of certain objects (using
ConcurrentReaderHashMap).
It works great! And the use of this package is free. No license needed.

-- Anton.

 

[David]

I have been thinking about the lazy initialization and double checked
locking problem. This problem is explain in detail here
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
I am not fully convinced that this problem cannot be
solved. I am going to propose a solution here. For the sake of
discussion I will post my solution here. It is possible that the
proposed solution does not work, feedback and comments are welcome.

I know this thread is getting old but I had an interview with someone who
claims to have solved the DCL paradox. When I look at this I cannot help
but think that if it were that simple many people would have solved it by
now.> Here is the original problem. We need to lazy initialize a non static

variable to an instance of a heavy object in a thread safe way. (It is
very easy to safely initialize a static variable). The most commonly
used code is as follows:
---------------------------------------------------------------------------
public class LazyInit
{
private HeavyObject heavyObject =
null;

public HeavyObject
getHeavyObject()
{
if (heavyObject ==
null)
{
synchronized(this)
{
if (heavyObject == null)
{
heavyObject = new HeavyObject();
}
}
}
return
heavyObject;
}
}

---------------------------------------------------------------------------

Unfortunately, this code is broken as described at
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html.
The problem arises from the fact that the optimising compilers can
reorder the constructor call and the assignment to the heavyObject
variable.

In my proposed solution, I am going to use polymorphism to appropriately
syncronize the initialization and after its safe initialization, replace
the implementation itself to be unsynchronized. Here is the code,
detailed description follows.

---------------------------------------------------------------------------
import java.util.*;

public class
LazyInit
// line 3
{
private static HeavyObjectInit heavyObjectInitStatic = new
HeavyObjectInit(); // line 5
private HeavyObjectInit heavyObjectInit = new
HeavyObjectInitSync(); // line 6
private volatile HeavyObject heavyObject =
null; // line 7

static class HeavyObjectInitSync extends
HeavyObjectInit // line 9
{
public HeavyObject getHeavyObject(LazyInit
lazyInit) // line 11
{
HeavyObject heavyObject =
getHeavyObjectInternal(lazyInit); // line 13
lazyInit.heavyObjectInit =
heavyObjectInitStatic; // line 14
return
heavyObject;
// line 15
}

private synchronized HeavyObject getHeavyObjectInternal(LazyInit
lazyInit) // line 18
{
if(lazyInit.heavyObject ==
null) // line 20
{
lazyInit.heavyObject = new
HeavyObject(); // line 22
}
return
lazyInit.heavyObject;
// line 24
}

}

static class
HeavyObjectInit
// line 29
{
public HeavyObject getHeavyObject(LazyInit
lazyInit) // line 31
{
return
lazyInit.heavyObject;
// line 33
}
}

public HeavyObject
getHeavyObject()
// line 37
{
return
heavyObjectInit.getHeavyObject(this);
// line 39
}
}

---------------------------------------------------------------------------

Explanation:
Lets assume this code is executing in a multi threading environment. Now
lets say a few threads enter LazyInit.getHeavyObject() at line 37
simultaneously. These threads will reach
heavyObjectInit.getHeavyObject() at line 39. Since heavyObjectInit is
initialized to HeavyObjectInitSync (at line 6), these threads will enter
getheavyObject() at line 11. At line 13, only one thread (lucky thread)
will be able to enter the syncronized method getHeavyObjectInternal
while rest of threads will be blocked at line 18. The lucky thread will
initialize the heavy object and return it. Since the thread is exiting a
syncronized method and the variable is volatile, the HeavyObject will be
fully initialized before the thread releases the lock. Now the lucky
thread will switch the implementation of heavyObjectInit to a non
syncronized initializer (line 14). Any threads reaching line 39 after
this will call the non syncronized version of getHeavyObject() at line
31. At the same time, all the threads blocked at line 18 will enter the
getHeavyObjectInternal() method one by one and return with the singleton
heavy object instance.

Thus initially a few threads will be synchronized till the lucky thread
switches the initializer. At this time the system will switch to non
syncronized implementation. Note that non syncronized implementation
(line 33) does not even incur the cost of null check as compared to the
original algorithm.

There are some intricacies that I have tried to explain in Q&A form.


Why is the instance of HeavyObjectInitSync nonstatic while instance of
HeavyObjectInit static?
If the HeavyObjectInitSync instance is made static, the syncronized
method will syncronize on the single instance of the class. Since all
instances of LazyInit will refer to single instance of
HeavyObjectInitSync, the call will be mutually exclusive across ALL
instances of LazyInit. Essentially if there are 1000 LazyInit objects
each one wanting to initialize HeavyObjects, these objects will get
initialized sequentially, thus slowing down the process. By making the
instance non static, different instances of LazyInit can initialize the
HeavyObject in parallel.
The HeavyObjectInit instance is static because we dont need one instance
of the HeavyObjectInit class with every instance of LazyInit. This
eliminates unnecessary object creation.

Why is HeavyObjectInitSync class static?
This class can be static or non-static. It is a matter of personal
choice. It should work both ways. I wanted to be consistent with
HeavyObjectInit class.

I have a code sample that shows how different threads will execute.
Download it here http://24.167.121.42/LazyInit.java

The output of this program demonstrates
1. Different threads entering one instance of LazyInit get blocked till
the HeavyObject is initialized.
2. Different threads entering different instances of LazyInit can
initialize the heavy object simultaneously.
3. The HeaveyObject is initialized only once per instance of LazyInit.
4. After the initialization is complete, any other threads entering that
instance of LazyInit do not syncronize anymore.


Vinay Aggarwal
CTO Techlobby
vinay at t e c h l o b b y dot com
h t t p : / / w w w. t e c h l o b b y . c o m /

public class Singleton {
private static Singleton _instance;

public Singleton getInstance() {
if(_instance == null ) {
_instance = createInstance();
}

return _instance;
}

private synchronized Singleton createInstance() {
if(_instance == null) {
return new Singleton;
}
}
}