473,246 Members | 1,667 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,246 software developers and data experts.

Solving Lazy Initialization and double checked locking problem


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/mem...edLocking.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/mem...edLocking.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 /
Jul 17 '05 #1
2 3986
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/...urrent/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.

"Vinay Aggarwal" <vi******@h-o-t-m-a-i-l.com> wrote in message
news:Xw*****************@twister.austin.rr.com...

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/mem...edLocking.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/mem...edLocking.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 /

Jul 17 '05 #2
On Fri, 28 Nov 2003 18:32:23 +0000, Vinay Aggarwal wrote:

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/mem...edLocking.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/mem...edLocking.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;
}
}
}
Jul 17 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
by: Siemel Naran | last post by:
What is a good idiom for handling a lazy object? I see 2 good possibilities. Any more, any comments? Which way do people here use? (1) class Thing { public: Thing(double x, double y) :...
7
by: Drew McCormack | last post by:
I have a C++ template class which contains a static variable whose construction registers the class with a map. Something like this: template <typename T> class M { static Registrar<M>...
4
by: Bret Pehrson | last post by:
I just stumbled across the following problem: //.h class Masses { static double mass1; static double mass2; static double mass3; };
16
by: Martin Jørgensen | last post by:
Hi, I've made a program from numerical recipes. Looks like I'm not allowed to distribute the source code from numerical recipes but it shouldn't even be necessary to do that. My problem is...
3
by: JohnQ | last post by:
SomeObject* instance() // flawed way { static SomeObject* instance = NULL; LockThing(); // locking even when not required if(instance == NULL) // instance may still be NULL when another thread...
3
by: Steve Folly | last post by:
Hi, I had a problem in my code recently which turned out to be the 'the "static initialization order fiasco"' problem (<http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.12>) The FAQ...
8
by: claudiu | last post by:
Hi, I have a question on the double checked locking. The classic implementation (shamelessly copied from Scott Meyers' and Andrei Alexandrescu's article) class Singleton { public: static...
0
by: George2 | last post by:
Hello gurus, For the wellknown Double-Checked Locking pattern, http://www.ddj.com/184405726?pgno=1 Step 1: Allocate memory to hold a Singleton object. Step 2: Construct a Singleton object...
9
by: Rohit | last post by:
I am trying to initialize an array whose initializers depend on value of Enums. I take enum and then decide the initializer value, so that even if enum value changes because of addition to list...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.