CODEWITHSUNDEEP
c++multithreadingc++11atomic
MRB
MRB

Reputation: 3822

Lazy initialization in lock free code

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.

Upvotes: 2

Views: 694

Answers (2)

Fulvio Esposito
Fulvio Esposito

Reputation: 153

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.

Upvotes: 0

Useless
Useless

Reputation: 67772

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 ...

Upvotes: 1

Related Questions