Lazy Singleton Created Exactly Once

medium Multithreading and Concurrency

An expensive object must be created lazily (on the first request), and only once, even when n threads ask for it at the same moment. Every thread asks for the object once. Print created=C (how many times the object was really created) and then same=true if all n threads got the same object. A correct program prints created=1.

Constraints

1 <= n <= 20

Examples

Input

Output

created=1
same=true

Double-checked locking
volatile
Safe publication
Singleton

Solutions

Best approachTime O(n)Space O(n)

Without the lock, two threads can both see null and both create the object. The quick first check avoids the lock once the object exists; the second check inside the lock stops a second creation. volatile makes the finished object visible to all threads.

Same code works in Java810172125Basic features only, so nothing changes between versions.

JavaScript and TypeScript have no shared-memory threads here, so they follow the same steps in one thread.

/*
 * Problem : Count the creations.
 * Input   : n.
 * Output  : Two lines.
 * Approach: Double-checked locking
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: The shared object, and a counter that counts how often it was created.
        static final java.util.concurrent.atomic.AtomicInteger CREATED = new java.util.concurrent.atomic.AtomicInteger();

        static class Expensive {
            Expensive() {
                CREATED.incrementAndGet();
            }
        }

        // Step 2: Double-checked locking. "volatile" makes sure that other threads see a fully built object.
        static volatile Expensive instance;

        static Expensive get() {
            if (instance == null) {
                synchronized (Expensive.class) {
                    // Step 3: Check again inside the lock: another thread may have created it while we waited.
                    if (instance == null) {
                        instance = new Expensive();
                    }
                }
            }
            return instance;
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long n) {
        int count = (int) n;
        Expensive[] got = new Expensive[count];
        Thread[] threads = new Thread[count];
        for (int i = 0; i < n; i++) {
            final int at = i;
            threads[i] = new Thread(() -> got[at] = get());
            threads[i].start();
        }
        for (Thread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        boolean same = true;
        for (Expensive object : got) {
            same = same && object == got[0];
        }
        return new String[] {"created=" + CREATED.get(), "same=" + same};
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(String.join("\n", solve(n)));
    }
}

Hints (2)

Why check twice?
What does volatile add?