Lazy initialization in lock free code

Question

Suppose i have an atomic pointer:

std::atomic<void*> mItems;

and in a function when one thread need to access that, it first check it, and if it is null, thread will allocate memory for it:

void* lItems = std::atomic_load_explicit(&mItems, memory_order_relaxed);
if(lItems == nullptr)
{
    void* lAllocation = malloc(...);

    if(!std::atomic_compare_exchange_strong_explicit(
        &mItems, 
        &lItems, 
        lAllocation, 
        memory_order_relaxed, 
        memory_order_relaxed))
    {
        free(lAllocation);
    }
}
    ...

But if N thread run this method concurrency and see mItems equal to null then all of them will allocate memory and N - 1 of them will free agian.

How i can write similar method with better approach.

Punch "double checked locking" into your favorite search engine. — David Schwartz
– David Schwartz, Commented Oct 8, 2013 at 10:07
Surprise! This is a solved problem en.cppreference.com/w/cpp/thread/call_once — R. Martinho Fernandes
– R. Martinho Fernandes, Commented Oct 8, 2013 at 10:12
@R.MartinhoFernandes: I doubt that call_once is lock-free, though. — Kerrek SB
– Kerrek SB, Commented Oct 8, 2013 at 10:24
@KerrekSB why wouldn't it? (IOW is this problem unsolvable?) — R. Martinho Fernandes
– R. Martinho Fernandes, Commented Oct 8, 2013 at 10:25

Useless · Accepted Answer · 2013-10-08 11:32:22Z

1

I guess you can make the pointer your mutex, using some well-known value (say, the address of a global) as a flag that some other thread is already doing the allocation.

So, your values are: NULL -> magic "allocation in progress" pointer -> real allocation.

The code would do something like:

load address: it will have one of the following values:
1. NULL: CAS with magic value
  - did CAS succeed? If yes, we're doing the allocation and everyone knows it
    - do the allocation, store the new address, we're done (shouldn't have to CAS it since we already guaranteed exclusion with the first CAS)
  - no, then someone else is doing the allocation, go back to 1
2. address not NULL, but the magic value
  - so someone is already doing the allocation - just wait until it changes, and use the eventual value
3. neither NULL nor magic, so it's already a real allocated value - just use it

This way only one thread does the allocation, but your other N-1 threads may be busy waiting. Whether this is really better will vary ...

answered Oct 8, 2013 at 11:32

Useless

68.5k6 gold badges100 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MRB Over a year ago

Thanks, this approach was in my mind too. but this is similar to once_flag. i only search for better approach although all of these are acceptable, but +1 for your answer.

Useless Over a year ago

The difference is you don't have a separate flag: you do a single load and, only in the corner case, CAS a single word. You incur no cache or other overhead in the usual fast case.

Fulvio Esposito · Accepted Answer · 2013-10-08 14:41:50Z

0

As I get it, you need that structure as soon as the first thread execute your function, so how about move the allocation before starting any thread? I mean, rearrange the code so that your function is called with the atomic pointer as a parameter, and the structure is allocated before any of the threads calling your function are spawned (you can also avoid creating any thread if the allocation fails)

something like:

std::atomic<void*> mItems;
void func_that_uses_mItems();

int main()
{
    mItems = init_struct();
    std::thread t1 { &func_that_uses_mItems };
    std::thread t2 { &func_that_uses_mItems };


    // ... join with or detach threads ...

    return( 0 );
}

If the allocation fails an exception is thrown and no thread is started.

edited Oct 8, 2013 at 14:41

answered Oct 8, 2013 at 14:33

Fulvio Esposito

1536 bronze badges

1 Comment

MRB Over a year ago

Well, the problem is that i don't want do this. suppose i have an array of items and each of them point to an array of other items and i want initialize them only if some body access them.

Collectives™ on Stack Overflow

Lazy initialization in lock free code

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related