Double Checked Locking Solutions

Discussions

J2EE patterns: Double Checked Locking Solutions

  1. Double Checked Locking Solutions (10 messages)

    Background.

    http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

    Introduction.

    In a highly concurrent application much time can be spent in acquiring locks.

    Examples.

    In many cases objects which need to be created are only known at runtime.

    Case 1: You might want to store objects by name in a local cache. In a multithread environment it can be inefficient to synchronize on a local table which might store objects by name.

    Case 2: In some cases it might be necessary to initialize variables lazily at runtime. In a multithreaded environment this would need to be synchronized.

    Synchronization in a highly concurrent system can have a high cost in time. Removing non required synchronization can improve performance dramatically.

    The original idea, which is incorrect.

    public Object getObject() {
        if (object == null)
            synchronized(this) {
                if (object == null)
                    object = new String("my object");
                }
                return object;
            }
        }
    }


    Proposed Solutions and Patterns below


    import java.util.HashMap;
    import java.util.regex.Pattern;

    abstract class OncePer {
        public final Object getObject(String arg) throws Exception {
            System.out.println(Thread.currentThread() + " entering getObject(arg: " + arg + ")");
            Object obj = doGet(arg);
            if (obj == null) {
                obj = synchronizedGetObject(arg);
            }
            return obj;
        }
        
        protected final synchronized Object synchronizedGetObject(String arg) throws Exception {
            System.out.println(Thread.currentThread() + " entering synchronizedGetObject(arg: " + arg + ")");
            Object obj = doGet(arg);
            if (obj == null) {
                obj = doCreate(arg);
            }
            return obj;
        }
        
        protected abstract Object doGet(String arg) throws Exception;
        
        protected abstract Object doCreate(String arg) throws Exception;
    }

    abstract class Once1Get {
        private volatile boolean todo = true;
        
        private Object obj = null;
        
        public final Object getObject() throws Exception {
            System.out.println(Thread.currentThread() + " entering getObject");
            if (todo) {
                synchronized (this) {
                    if (todo) {
                        obj = doGet();
                        todo = false;
                    }
                }
            }
            return obj;
        }
        
        protected abstract Object doGet() throws Exception;
    }

    abstract class Once2Get extends Once2 {
        private Object obj = null;
        
        public final Object getObject() throws Exception {
            System.out.println(Thread.currentThread() + " entering getObject");
            boolean first = acquire();
            if (first) {
                try {
                    obj = doGet();
                    release();
                } catch (Exception e) {
                    e.printStackTrace();
                    release(false);
                    throw e;
                }
            }
            return obj;
        }
        
        protected abstract Object doGet() throws Exception;
    }

    abstract class Once2Block extends Once2 {
        public final void runBlock() throws Exception {
            System.out.println(Thread.currentThread() + " entering runBlock");
            boolean first = acquire();
            if (first) {
                try {
                    doRun();
                    release();
                } catch (Exception e) {
                    e.printStackTrace();
                    release(false);
                    throw e;
                }
            }
        }
        
        protected abstract void doRun() throws Exception;
    }

    class Once2 {
        private volatile boolean todo = true;
        private volatile boolean first = true;
        
        public final boolean acquire() throws InterruptedException {
            System.out.println(Thread.currentThread() + " entering acquire");
            if (todo) {
                synchronized (this) {
                    if (todo) {
                        for (;;) {
                            if (first) {
                                first = false;
                                return true;
                            } else {
                                wait();
                                if (!todo) {
                                    break;
                                }
                            }
                        }
                    }
                };
            }
            return false;
        }
        
        public final void release() {
            System.out.println(Thread.currentThread() + " entering release");
            release(true);
        }
        
        public final void release(boolean success) {
            System.out.println(Thread.currentThread() + " entering release(success:" + success + ")");
            if (success) {
                synchronized (this) {
                    todo = false;
                    notifyAll();
                }
            } else {
                synchronized (this) {
                    first = true;
                    notify();
                }
            }
        }
    }

    // Example test. Others removed due to length restrictions.

    public class Main {
        private Object oncePerObj = null;
        
        public static void main(String[] args) {
            Main main = new Main();
            main.testOncePer();
        }
        
        public void testOncePer() {
            System.out.println(Thread.currentThread() + " entering testOncePer");

            final OncePer once = new OncePer() {
                private HashMap table = new HashMap(); // This could be a WeakHashMap
                
                protected Object doGet(String arg) throws Exception {
                    System.out.println(Thread.currentThread() + " entering doGet(arg: " + arg + ")");
                    return table.get(arg);
                }
                
                protected Object doCreate(String arg) throws Exception {
                    System.out.println(Thread.currentThread() + " entering doCreate(arg: " + arg + ")");
                    Pattern pattern = Pattern.compile(arg);
                    table.put(arg, pattern);
                    return pattern;
                }
            };
            
            Thread th1 = new Thread(new Runnable() {
                public void run() {
                    System.out.println(Thread.currentThread() + " entering run");
                    try {
                        oncePerObj = (Pattern) once.getObject("[a-zA-Z0-9]+");
                        //test for matches
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            }, "th1");
            
            Thread th2 = new Thread(new Runnable() {
                public void run() {
                    System.out.println(Thread.currentThread() + " entering run");
                    try {
                        oncePerObj = (Pattern) once.getObject("[a-zA-Z0-9]+");
                        //test for matches
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            }, "th2");
            
            try {
                th1.start();
                th2.start();
                th1.join();
                th2.join();
                System.out.println(Thread.currentThread() + " oncePerObj: " + oncePerObj);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
  2. Jason,

    I will just quote one part from background link.

    "It doesn't work
    There are lots of reasons it doesn't work. The first couple of reasons we'll describe are more obvious. After understanding those, you may be tempted to try to devise a way to "fix" the double-checked locking idiom. Your fixes will not work: there are more subtle reasons why your fix won't work. Understand those reasons, come up with a better fix, and it still won't work, because there are even more subtle reasons.

    Lots of very smart people have spent lots of time looking at this. There is no way to make it work without requiring each thread that accesses the helper object to perform synchronization. "
  3. Ok, you have my time[ Go to top ]

    I spend some time looking at your code and foung one of the points which you missed. Look, this is your code:

        public final Object getObject() throws Exception {
            System.out.println(Thread.currentThread() + " entering getObject");
            if (todo) {
                synchronized (this) {
                    if (todo) {
                        obj = doGet();
                        todo = false;
                    }
                }
            }
            return obj;
        }

    According to Java memory model, it is correct for JIT compiler to assume, that this code is equal to:

        public final Object getObject() throws Exception {
            System.out.println(Thread.currentThread() + " entering getObject");
            if (todo) {
                synchronized (this) {
                    if (todo) {
                        todo = false;
                        obj = doGet();
                    }
                }
            }
            return obj;
        }

    It is first variant. We have NPE exception here :(

    Second variant is more complicated, and assuming that you read "A test case showing that it doesn't work" part from background link. The obj reference can be setted to uninitialized object and sync monitor frees. The second thread will have a link to uninitialized object. See example in backgroud link.

    One more point: variable "todo" is equal to "obj == null" in your code. Just by replacing it with this condition we have the same code, so we have the same problems.
  4. Ok, you have my time[ Go to top ]

    These are very good catches. I appreciate them very much. I do have one question though, as this is really the only one that needs to work and you did not comment on it.

    This is the correct way.

    private Object obj = null;

    public synchronized Object getObject() {
        if (obj == null) {
            obj = new Object(); // whatever you want here
        }
        return obj;
    }

    I really would like to know that a compiler can optimize this code to make it not work.

    public Object getObject() {
        if (obj == null) {
            obj = syncGetObject(name);
        }
        return obj;
    }

    This is the correct one.

    public synchronized Object syncGetObject(String name) {
        Object obj = null;
        if (obj == null) {
            // who knows maybe youd have to do
            // Object temp = new Object(); obj = temp;
            obj = new Object(); // whatever you want here
        }
        return obj;
    }

    or this

    public Object getObject(String name) {
        Object obj = hashmap.get(name); // if it is possible to get an exception here then catch it and use syncGet
        if (obj == null) {
            obj = syncGetObject(name);
        }
        return obj;
    }

    public synchronized Object syncGetObject(String name) {
        Object obj = hashmap.get(name);
        if (obj == null) {
            // who knows maybe youd have to do
            // Object temp = new Object(); obj = temp;
            obj = new Object(); // whatever you want here
            hashmap.put(name, obj);
        }
        return obj;
    }

    These are based on my first example, the OncePer


    This double checked locking is really a critical optimization to be had, especially the one using a map

    Thanks
  5. Voliate pre-1.5[ Go to top ]

    Just a note. Volatile does not guarantee what it should (and what you expect) in pre-1.5 jvms. For this reason (among others) these are all suspect on a pre-1.5 JVM.
  6. flushing[ Go to top ]

    I really would like to know that a compiler can optimize this code to make it not work.

    I's the same as the dobule-checked locking version. The Object reference could be non-null before it is fully created. When the thread looks at that check for null, it will skip over the synchronization and return the malformed Object.

    1.5 contains a number of concurrent collections and you can get these for 1.4 also. You may want to look into those.
  7. Thank you for your reply. I am quite familiar with the concurrent classes even prior to their inclusion in java5.

    Now is it not possible to force the correct state somehow?

    private Object obj = null;

    public Object getObject() {
        // avoid partially initialized object
        // if obj is 64 bit reference, i.e.,
        // obj != null but not fulled initialized
        if (obj == null || !obj.isInitted()) {
            syncGetObject();
        }
        return obj;
    }

    // Are we saying that a compiler is going to wait to construct the member fields in Object until after the setInitted method is called as an optimization and get a divide by zero exception? See below.

    public synchronized Object syncGetObject() {
        if (obj == null) {
            obj = new Object(); // whatever you want here
            obj.setInitted(); // assume the method exists
        }
        return obj;
    }

    class Object {
        private volatile int initted = 0;

        private XXX myfield = null;

        public Object() {
            myfield = new XXX();
            initted = 0;
        }

        public void setInitted() {
            initted = 1;
            1/initted; // potential divide by zero
        }

        public boolean isInitted() { return initted == 1; }
    }

    or this (This is the one I want most to work)

    private HashMap hashmap = new HashMap();

    public Object getObject(String name) {
        Object obj = hashmap.get(name); // if it is possible to get an exception here then catch it and use syncGet
        if (obj == null) {
            obj = syncGetObject(name);
        }
        return obj;
    }

    // Are we saying the object will be placed into the hashmap in position before its member fields are initialized and therefore the hashmap.get above returns a non null unitialized object?

    public synchronized Object syncGetObject(String name) {
        Object obj = hashmap.get(name);
        if (obj == null) {
            obj = new Object(); // whatever you want here
            hashmap.put(name, obj);
        }
        return obj;
    }

    I'd like to think that there is a solution, or that in some case the compiler cannot do the optimization.
  8. I'd like to think that there is a solution, or that in some case the compiler cannot do the optimization.

    I'm not really an expert on how the VM may optimize these things or when the cache must be flushed. Personally, I don't think it's worth worrying about.

    For you specific problem (the map) you can use a concurrent Map or you can use two layer locking where whole method is only locked for a moment to determine whether the key is set. If not, it creates the key.

    Then, after leaving the critical section, it locks on the key and loads the value if necessary. This removes a lot of contention which is the real problem. Synchronization is not that expensive in itself.
  9. Well thanks for your comments.

    A coworker suggested using copy on write, but the source for CopyOnWriteArrayList uses synchronization in its reads.

    As you hinted i did take a look at the ConcurrentHashMap, the source! It turns out i don't think i was very far off, and this probably is the best bet.

    With notes like these it seems likely that even they are just hoping for the best.

    /**
     * ConcurrentHashMap list entry. Note that this is never exported
     * out as a user-visible Map.Entry.
     *
     * Because the value field is volatile, not final, it is legal wrt
     * the Java Memory Model for an unsynchronized reader to see null
     * instead of initial value when read via a data race. Although a
     * reordering leading to this is not likely to ever actually
     * occur, the Segment.readValueUnderLock method is used as a
     * backup in case a null (pre-initialized) value is ever seen in
     * an unsynchronized access method.
     */


         * Read operations can thus proceed without locking, but rely
         * on selected uses of volatiles to ensure that completed
         * write operations performed by other threads are
         * noticed. For most purposes, the "count" field, tracking the
         * number of elements, serves as that volatile variable
         * ensuring visibility. This is convenient because this field
         * needs to be read in many read operations anyway:
         *
         * - All (unsynchronized) read operations must first read the
         * "count" field, and should not look at table entries if
         * it is 0.
         *
         * - All (synchronized) write operations should write to
         * the "count" field after structurally changing any bin.


        /**
         * Reads value field of an entry under lock. Called if value
         * field ever appears to be null. This is possible only if a
         * compiler happens to reorder a HashEntry initialization with
         * its table assignment, which is legal under memory model
         * but is not known to ever occur.
         */
        V readValueUnderLock(HashEntry<K,V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }
        
        /* Specialized implementations of map methods */
        
        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }


    I suppose it may be time to look at the java5 memory model in further detail.

    Here seems to be a good starting point.

    http://www.cs.umd.edu/~pugh/java/memoryModel/

    Thanks
  10. Apparently the double checked locking is fixed in the new memory model. What is suggested below however leads me to question the performance improvement gained through something like ConcurrentHashMap which uses a volatile check in place of synchronization. Also it appears that there are new semantics for volatile and final fields in an object and elsewhere which ensure proper ordering when used. Read this it is very interesting.

    From http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

    Many people assumed that the use of the volatile keyword would eliminate the problems that arise when trying to use the double-checked-locking pattern. In JVMs prior to 1.5, volatile would not ensure that it worked (your mileage may vary). Under the new memory model, making the instance field volatile will "fix" the problems with double-checked locking, because then there will be a happens-before relationship between the initialization of the Something by the constructing thread and the return of its value by the thread that reads it.

    However, for fans of double-checked locking (and we really hope there are none left), the news is still not good. The whole point of double-checked locking was to avoid the performance overhead of synchronization. Not only has brief synchronization gotten a LOT less expensive since the Java 1.0 days, but under the new memory model, the performance cost of using volatile goes up, almost to the level of the cost of synchronization. So there's still no good reason to use double-checked-locking.


    Also it appears that the original dl.util.concurrent.ConcurrentHashMap may be open to reordering and looks to have a questionable check against null, but don't take my word for it.
  11. This thread is old by now, but hope it's still active because question about "Not only has brief synchronization gotten a LOT less expensive since the Java 1.0 days, but under the new memory model, the performance cost of using volatile goes up, almost to the level of the cost of synchronization". Do you have URL or doc etc for benchmarks showing that?