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.

Why are you not using the built-in [`Lazy` class](https://msdn.microsoft.com/en-us/library/dd642331%28v=vs.110%29.aspx)? — Alex, Apr 27 '15 at 17:14
With your code it may happen that func() is evaluated twice if Memoize() is called before the first func() returned. — DrKoch, Apr 27 '15 at 17:15
This isn't a duplicate. The problem is the same, but the solution is different (this isn't a singleton!). — Cameron, Apr 27 '15 at 17:15
This particular [answer](http://stackoverflow.com/a/394932/477420) in the duplicate says "ok", but indeed you should consider using existing `Lazy` to do so. — Alexei Levenkov, Apr 27 '15 at 17:16
@DrKoch: No, that can't happen. For that to happen, `inited` would have to be seen to be false *inside* the lock by two separate threads, which is clearly impossible (unless `func` throws). — Cameron, Apr 27 '15 at 17:17
@Cameron the question I've picked is not about singleton either - double-check locking is the pattern used in both questions... I'm willing to re-open this question if someone can update it to clarify why it is not related to double-checked locking. — Alexei Levenkov, Apr 27 '15 at 17:18
@Alexei: True, however I feel the use of the pattern here is specific enough to warrant its own question (applying the answers in that question to this one requires a not-insignificant leap). — Cameron, Apr 27 '15 at 17:20
I've reopened. The other question asked whether the double-checking locking pattern in .NET is broken (it isn't); this question asks whether its code implements it correctly. Related, but not duplicate. — Douglas, Apr 27 '15 at 17:21
@Douglas - good point... strange that no one tried to implement that before :) — Alexei Levenkov, Apr 27 '15 at 17:23
NotNull, please see if my edit aligns with your goals about the question. — Alexei Levenkov, Apr 27 '15 at 17:25
@AlexeiLevenkov My goal was indeed to get feedback on the implementation. — NotNull, Apr 27 '15 at 17:28
@AlexeiLevenkov: This question introduces new considerations that weren't applicable to the general scenario. Since the variables need to be declared as locals (rather than fields), they can't take advantage of the volatile keyword. — Douglas, Apr 27 '15 at 17:30

Cameron · Accepted Answer · 2015-04-27T17:39:51.767

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.

I will just replace it with an instance of Lazy: `private static Func Memoize(Func func) { var lazy = new Lazy(func); return () => lazy.Value; }` That should do what I wanted. Nice to know that getting these things right can be tricky! — NotNull, Apr 27 '15 at 17:20
@NotNull, about it being tricky to get right: change `new Lazy(func)` to `new Lazy(func, true)`. Not **needed**, but documents explicitly what it does. — Alex, Apr 27 '15 at 17:23

Alex · Answer 2 · 2015-04-27T17:28:24.650

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;
}

edited Apr 27 '15 at 17:28

answered Apr 27 '15 at 17:23

Alex

13,024
33
62

It seems that the default constructor (without the boolean) will be thread safe as well. According to the docs: "The thread safety mode of a Lazy instance that is initialized with this constructor is LazyThreadSafetyMode.ExecutionAndPublication." – NotNull Apr 27 '15 at 17:38
@NotNull yes, but using it explicitly in this case makes for good documentation of that line – Alex Apr 27 '15 at 17:39

score 1 · Answer 3 · answered Apr 27 '15 at 17:20

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;
}

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

3 Answers3