CODEWITHSUNDEEP
c++multithreadingc++11atomiccompare-and-swap
David
David

Reputation: 28178

C++11 Lock free update 2 variables atomically

I'd like to update atomicX when a thread finds a new minimum to change it to. When it does set the new minimum, I would also like to change a variable y, atomically. Is there a way to do this without locks?

Example of a thread function executing on many threads at once:

uint64_t x = atomicX;
int y = g();

for(int newX = 0; newX < x; ++newX)
{
    if(f(newX))
    {
        while(newX < x && !atomicX.compare_exchange_strong(x, newX));
        // also set atomicY to y if the exchange happened above
        break;
    }

    x = atomicX;
}

I can do it with locks as so:

int y = g();

for(uint64_t newX = 0; newX < atomicX; ++newX)
{
    if(f(newX))
    {
        mutex.lock();
        if(newX < atomicX)
        {
            atomicX = newX;
            atomicY = y; // atomicY no longer needs to be atomic
        }
        mutex.unlock()
        break;
    }
}

I'm also open to any cleaner structuring of this, or another way to do it all together. I don't like that I have to have the same newX < x condition twice, or that I have to break the loop.

Upvotes: 4

Views: 1778

Answers (1)

Useless
Useless

Reputation: 67822

There's a fairly simply and likely-to-be-portable-enough solution, which is to use a pointer and CAS that:

struct XY {
  uint64_t x;
  uint32_t y;
};
std::atomic<XY *> globalXY;

Then the tricky bit becomes figuring out how to allocate and release these objects without excessive cost or ABA problems.

For clarity, the code would end up something like this:

XY *newXY = somehow_allocate_objects();
XY *oldXY = globalXY;
int oldX = oldXY->x;
newXY->y = g();

for(int newX = 0; newX < oldX; ++newX) {
    if(f(newX)) {
        // prepare newXY before swapping
        newXY->x = newX;
        while(newX < oldX && !globalXY.compare_exchange_strong(oldXY, newXY)) {
            // oldXY was updated, reload oldX
            oldX = oldXY->x;
        }
        // globalXY->x,y both updated by pointer CAS
        break;
    }
    oldXY = globalXY;
    oldX = oldXY->x;
}

For reference, the eventual conclusion was that these threads were long-lived, so statically allocating a single XY instance for each thread was sufficient.

Upvotes: 1

Related Questions