CODEWITHSUNDEEP
c++cmulticoredouble-checked-lockinglazy-initialization
Sebastian Mach
Sebastian Mach

Reputation: 39099

Triple checked locking?

So in the meanwhile we know that double-checked-locking as is does not work in C++, at least not in a portable manner.

I just realised I have a fragile implementation in a lazy-quadtree that I use for a terrain ray tracer. So I tried to find a way to still use lazy initialization in a safe manner, as I wouldn't like to quadruple memory usage and re-order large parts of implemented algorithms.

This traversal is inspired by the pattern on page 12 of C++ and the Perils of Double-Checked Locking, but tries to do it cheaper:

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            // get updated view
            #pragma flush childCreated[c]
            if (!childCreated[c]) { 
                ScopedLock sl (mutex[c]);
                if (!childCreated[c]) {
                    create (c);
                    #pragma flush childCreated[c]  
                    childCreated[c] = true;
                }
            }
        }
    }
}

It is assumed that #pragma flush would also serve as a hard sequence point where compilers and processors won't be allowed to re-order operations across them.

Which problems do you see?

edit: Version 2, trying to take into account Vlads answer (introduce third flush):

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            // get updated view
            #pragma flush childCreated[c]
            if (!childCreated[c]) { 
                ScopedLock sl (mutex[c]);
                #pragma flush childCreated[c]
                if (!childCreated[c]) {
                    create (c);
                    #pragma flush childCreated[c]
                    childCreated[c] = true;
                }
            }
        }
    }
}

edit: Version 3, I somehow find this pretty equivalent to Version 2, because I am not using the child itself but a primitive flag to check for validity, basically relying on a memory barrier between creating a child and writing to that flag.

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            ScopedLock sl (mutex[c]);
            #pragma flush childCreated[c]
            if (!childCreated[c]) {
                create (c);
                #pragma flush childCreated[c]
                childCreated[c] = true;
            }
        }
    }
}

Upvotes: 2

Views: 592

Answers (1)

Vlad
Vlad

Reputation: 35594

It seems that your pattern is not correct. Consider the case when thread #1 executes till after the first #pragma flush. Then the control switches to the thread #2, which goes on and creates a c, the control is taken back just before second #pragma flush. Now the first thread wakes up, and creates the child anew.

Edit: sorry, wrong: it will be unable to take the lock.

Edit 2: no, still correct, because the value will be not flushed in thread #1

Upvotes: 3

Related Questions