Memory read visibility ordering vs write order using double-checked locking

Question

I have the following function which is intended to "memoize" argument-less functions. Meaning to only call the function once, and then return the same result all other times.

private static Func<T> Memoize<T>(Func<T> func)
{
    var lockObject = new object();
    var value = default(T);
    var inited = false;

    return () => {
        if (inited)
            return value;

        lock (lockObject) {
            if (!inited) {
                value = func();
                inited = true;
            }
        }

        return value;
    };
}

Can I be certain that if a thread reads "inited == true" outside the lock, it will then read the "value" which was written before "inited" was set to true?

Note: Double-checked locking in .NET covers the fact the it should work and this question mainly to check if my implementation is correct and maybe get better alternatives.

Answer 1

No, because inited is not volatile. volatile gives you the memory release and acquire fences you need in order to establish the correct happens-before relationship.

If there's no release fence before inited is set to true, then the value may not be completely written by the time another thread reads inited and sees it as true, which could result in a half-constructed object being returned. Similarly, if there's a release fence but no corresponding acquire fence before reading inited in the first check, it's possible that the object is fully constructed, but that the CPU core that saw inited as true hasn't yet seen the memory effects of value being written (cache coherency does not necessarily mandate that the effects of consecutive writes are seen in order on other cores). This would again potentially result in a half-constructed object being returned.

This is, by the way, an instance of the already very well-documented double-checked locking pattern.

Instead of using a lambda that captures local variables (which will make the compiler generate an implicit class to hold the closed-over variables in non-volatile fields), I suggest explicitly creating your own class with a volatile filed for value.

private class Memoized<T>
{
    public T value;
    public volatile bool inited;
}

private static Func<T> Memoize<T>(Func<T> func)
{
    var memoized = new Memoized<T>();

    return () => {
        if (memoized.inited)
            return memoized.value;

        lock (memoized) {
            if (!memoized.inited) {
                memoized.value = func();
                memoized.inited = true;
            }
        }

        return memoized.value;
    };
}

Of course, as others have mentioned Lazy<T> exists for this very purpose. Use it instead of rolling your own, but it's always a good idea to know the theory behind how something works.

Answer 2

I think you would be better off using the standard Lazy<T> class to implement the functionality you need, as in:

private static Func<T> Memoize<T>(Func<T> func)
{
    var lazyValue = new Lazy<T>(func, isThreadSafe: true);
    return () => lazyValue.Value;
}

Answer 3

No, that code is not safe. The compiler is free to reorder the writes to value and inited; so is the memory system. This means that another thread might see inited set to true whilst value is still at its default.

This pattern is called double-checked locking, and is discussed by Albahari under Lazy Initialization. The recommended solution is to use the built-in Lazy<T> class. An equivalent implementation would be the following:

private static Func<T> Memoize<T>(Func<T> func)
{
    var lazy = new Lazy<T>(func);
    return () => lazy.Value;
}