About sickness it might prove true, given the fact my girlfriend asked to check if I got HIV(!) because I tend to be sort of ill lately. Anyways - what's done is done.
Wikipedia has a quite bad article on that - mostly focused on Java. Yet, it missed probably the most influential resource (IR). Looking at the notes I was surprised it actually has no article about Brian Goetz. His blog, if you need anything about concurrent programming, this is the guy. He speaks the truth. Upon reflection I checked Wikipedia once more and found out that Singleton article covered it way better.
So if you have already visited the most influential resource you know that the double lock (check) idiom is about. Actually, I am sure, you knew it before hand, nonetheless.
Basically the double lock checking idiom attempts to avoid locking (and the overhead attached to) by issuing some non-sync version. The paper (or the IR) explains why it's broken and actually it was one of the reasons (but not the main) java memory model (JMM) to be revised. JMM was revised since it was broken (similar to the idiom), if my memory serves me right (which might not be case if the starting lines hold true) Bill Pugh (the author of SkipList) was the first to point the flaws.
Without beating the dead horse again and explaining why it was so damn broken here I offer the 'modern' Java ways to implement it.
- Forget about it and don't lazy initialize: e.g.
private static final Singleton singleton=new Singleton()
public static Singleton getSingleton(){
return singleton;
}
Pros: very easy to implemented 100% thread safe, 100% no overhead, completely inlineable.
Cons: no lazy initialization. The class initialization is explained here at point "2.17.5 Detailed Initialization Procedure". Basically an invisible lock ensures the class is initialized only once and no other threads will see out-of-order writes or anything (there is memory fence after initialization completes). Cannot deal with exceptions (explained b).
- Use another class helper. Or Bill Pugh's way.
public class Singleton{
private Singleton(){
}
private static class Helper{
private static final Singleton singleton=new Singleton();
}
public static Singleton getSingleton(){
return Helper.singleton;
}
}
Pros: 100% thread safe, 100% no overhead, true lazy initialization, not difficult to implement, completely inlineable
Cons: extra class, the classes take space in the perm-gen, which is not the heap and it's limited... and something I have never seen mentioned, it may pose some security risk. Yes, that's correct it might be unsafe under some conditions - but not thread unsafe :). Extra cons: can't deal with exceptions.
First: How this idiom works: it relies that class initialization (clinit method) might be called at most once. This method is called when any operation is required by the class, invoking 'new', any field access, any static method. So the only field 'singleton' that Helper has is initialized during the first call of 'getInstance()'.
As you might see, nothing, really nothing comprises the security. The class Helper is a private one and it's inaccessible outside Singleton (actually outside the package of Singleton, but that's not an issue). So no other premature initialization may occur. Almost. If the class can be loaded via Class.forName(String, true, classLoader) [or simply Class.forName(String)] the clinit method will be called. There is no restriction to the loading classes and calling clinit even if the class is utterly hidden. Simple code like Class.forName("Singleton$Helper") actually creates the instance. Remember how you used to initialize the databases drivers once, yes in such way. How this poses a risk: well the code might be called from any untrusted codebase or thread as long as the classloader can discover Singleton. That alone may fail Singleton creation, if the calling context is expected to bear some special privileges. Even getInstance might check the SecurityManager and allow access only when the needed priviliges are met. Worst of all happens if the initialization fails with ExceptionInInitializerError - the Singleton will never be initialized at all... I hope you got the idea, if not post a comment. Here is a bit more about:
Exception handling
Even though, it looks it doesn't belong here exception handling might become a problem with idioms above. The greatest issues is that Singleton constructor may not throw any exception. If it contains a checked one the code simply can not compile which is ok. If it is unchecked it's actually worst: the first attempt to create will end up via ExceptionInInitializerError and any further calls will result in NoClassDefFoundError. It's not possible to recover from the situation at all (sun.misc.Unsafe hacks don't count).
To me this is the biggest flaw of otherwise a very elegant pattern (Pugh's one). Basically there is a single change to initialize the Singleton and if it fails, it fails forever... or at least until all the classes are unloaded and their respective classloader too and another attempt is establish to initialize everything. A process also known as redeploy.
- Back to basics
So if we need an exception handling, security checking we are left dry with the simple a synchronization option
public class Singleton{
private Singleton() throws IOException{
//perform some IO
}
private static final Object lock=new Object();
private static Singleton singleton;//not final
private static Singleton createSingleton() throws IOException{
Singleton s = new Singleton();
//extra init, if needed
return s;
}
public static Singleton getSingleton() throws IOException{
synchronized(lock){
Singleton s = singleton;
if (s == null){
singleton = s = createSingleton();
}
return s;
}
}
}
Pros: 100% thread safe, true lazy initialization, exception handling, not very difficult to implement
Cons: A fully blown sync with all the memory barriers required. The slowest approach.
The old, old simple sync and no tricks. Rock solid if it comes to thread safety but that's all. Ok, plus the exception handling. Not much remarks here.
- Java 5+ and the JMM
Java 5 finally offered a better memory model and way stricter volatiles. Before that moment regular (non-volatile) writes could be reordered with volatile ones - quite horrid to ensure any success one would need to declare everything volatile. Since I always target Java 6+ we simply move to the code:
public class Singleton{
private Singleton() throws IOException{
//perform some IO
}
private static final Object lock=new Object();
private static volatile Singleton singleton;//notice volatile here
private static Singleton tryCreateSingleton() throws IOException{
synchronized(lock){
if (singleton == null){
singleton = new Singleton();
//extra init, if needed
}
}
return singleton;
}
public static Singleton getSingleton() throws IOException{
Singleton s = singleton;
if (s == null){
//check under lock; move creation logic to a separate method to allow inlining of getSingleton()
s = tryCreateSingleton();
}
return s;
}
}
}
Pros: 100% thread safe, true lazy initialization, exception handling
Cons: A memory fence for the volatile.
Looks much better, virtually lock free aside the first time. Yet, still we got a memory fence. On multi-core that memory fence can reduce the performance. Hey, look from the bright side: it's better than full sync, we can handle exceptions and we don't take space in the perm-gen, and we don't involve extra class loading IO operation.
- Thread Local Storage
...Or bestsss' favorite. It was first proposed by Alexader Terekhov. Here is the deal: if after the 1st successful attempt to obtain a singleton a cached reference is held by the current thread, no further memory fences will be needed since the cache reference is accessible iff by a single thread. Every thread keeps such a reference - an absolutely negligible memory issue. Thread local storage can be implemented in a couple of ways: ThreadLocal and custom thread. Presently a ThreadLocal entries are implemented via subclass of WeakReference which holds the real value and weak ref to the ThreadLocal (so if the ThreadLocal is GC'd the value can lost but that happens only if the table is full), plus an array for the Entries in the ThreadLocalMap that is held by Thread. Quite effective implementation of linear probing hash table (non-tree hash map).
the code:
public class Singleton{
private Singleton() throws IOException{
//perform some IO
}
private static final Object lock=new Object();
private static volatile Singleton singleton;//notice volatile here
private static final ThreadLocal<Singleton> instances = new ThreadLocal<Singleton>();//every thread keeps its own ref here
private static Singleton tryCreateSingleton() throws IOException{
synchronized(lock){
if (singleton == null){
singleton = new Singleton();
//extra init, if needed
}
}
return singleton;
}
private static Singleton doGetSingleton() throws IOException{
Singleton s = singleton;
if (s == null){
s = tryCreateSingleton();
}
instances.set(s);//store for the current thread
return s;
}
public static Singleton getSingleton() throws IOException{
Singleton s = instances.get();//take from the current thread cache
if (s == null){
s = doGetSingleton();
}
return s;
}
}
Pros: thread safe, true lazy initialization, exception handling, no memory fence
Cons: Quite difficult to implement, one extra weak reference per thread, more expensive than Pugh's.
The solution is quite elegant and allows exception handling. Most important: it doesn't issue a memory fence which is a very good news. Can it be improved: yes, slightly.
However right now it's quite late in the night and I have to stop but...
(to be continued - asm of the examples and micro benchmark tests)
Posts
