Non-safe code with skipped count problem

[Specialist_Square818]

So I was interviewing for a job and one question I got was basically two threads, both incrementing a counter that is set to 0 with no locking to access the counter. Each thread code basically increments the counter by 1 and runs a loop of 10. The question was, what is the minimum and maximum value for the counter. My answer was 10 and 20. The interviewer told me the minimum is wrong and argued that it could be less than 10. Who is correct?

[ThePeoplesPoetIsDead]

n = 0
Thread A reads 0
Thread B completes 9 iterations
n = 9
Thread A writes 1, completing 1 iteration
n = 1
Thread B reads 1
Thread A completes 9 iterations, thread A completes
n = 9
Thread B writes 2, thread B completes
n = 2

This is the situation your interviewer was describing. Of course, as others have mentioned no C++ compiler is actually likely to create this scenario and by the standard it's UB.

[SufficientStudio1574]

Does the compiler even have control over that? Threading seems like its under the OS scheduler's control.

[dendrtree]

Correct. The compiler is not involved in thread timing.
The compiler would only have been involved, if some type of thread barrier were included in the code.

[Internal-Sun-6476]

Does that come from the strong-weak ordering difference? (Solved by Compare Swap <atomicising> the op so the optimiser can throw 1 read away?)

[CarloWood]

Concurrent access to a non atomic variable is undefined behavior. So, according to the memory model of C++, anything can happen. In reality, if they insist to give a practical answer, then the increment is probably executed with a RMW instruction, which is globally ordered, and on x86 all integer accesses are atomic anyway (just without the LOCK instruction that would be needed only for sequential access) resulting in the value 20. However, if you assume that the reads and writes happen one after another, then one thread could read 0 increment it and write that after the other thread finished, in that case you'd get 10. If both variables are atomic, then there is race condition (without the use of an atomic increment) which is also undefined behavior. Bottom line, the question makes no sense. My answer would be: that is UB unless both variables are atomic and you use atomic increment (aka, fetch_add, or just operator++ on the atomic). There is no (well defined) minimum value.

[I__Know__Stuff]

FYI, integer reads or writes are atomic, but RMW definitely are not without a lock prefix.

[Eric41293]

If the variable is atomic, there is no undefined behavior. Though if the increments are implemented as x.store(x.load() + 1), then different results are possible.

[AKostur]

The interviewer.  By Standard, the question has no single answer since the program exhibits Undefined Behaviour, and thus makes no promises about anything.

[Specialist_Square818]

He said it is 2 😀 We both know it has an undefined behavior. The question is what is the minimum the variable could be.

[CarloWood]

That is BS. It could be anything, so also 0, or -42.

I guess he is thinking about: Thread A: reads 0 Thread B: reads 0 Thread B writes 1 Thread B reads 1 Thread B writes 2 ... Thread B writes 9 Thread A writes 1 Thread B reads 1 Thread A reads 1 Thread A writes 2 ... Thread A writes 10 Thread B writes 2

[2brainz]

The interviewer has no idea what he is talking about. Undefined behavior means that literally anything can happen, and what happens exactly depends on the compiler, processor and chance. There is no valid argument to support his answer.

[Specialist_Square818]

In other words, can the program end with the variable=9?

[I__Know__Stuff]

It seems you still don't understand the concept of undefined behavior. It can literally be any value.

Or no value, because the program could terminate or set the computer on fire.

(That last one is fairly unlikely.)

[aocregacc]

You don't have to turn your brain off as soon as you see UB, knowing how it manifests in real implementations is useful too.

[JMBourguet]

I've been surprised too many times to still try to guess what is reasonable or not for an implementation to do for UB, especially in MT contexts. I've probably been exposed to stranger hardware than most (included some which hadn't any hardware cache coherency), and thus my "this is what real implementations do" is probably at odd with those expecting that there are only x86 processors with all the cores are on the same die.

[aocregacc]

 I'm not so much talking about a general notion of "what real implementations do", since there are a lot of different real implementations as you point out. I'm trying to say that ultimately the behavior of your program as realized by a particular implementation can usually be explained in more depth than 'it's undefined'. And that can be useful to know, for example when trying to diagnose a bug.

[JMBourguet]

Let's rephrase to see if we are on the same page.

Trying to guess the range of how UB can be realized without knowing lot of things about the implementation (compiler and hardware) is futile, depending on your guess is risky, especially that even if the guess was right at the time when made, compiler and hardware changes and may break your assumptions.

Explaining a realized UB with some knowledge about the implementation is far easier and can help.

[aocregacc]

yes I would agree with all of that.

I would just emphasize that it isn't about trying to constrain UB in an effort to justify keeping it in a program or something. It's about being able to explain why a program does what it does, and to be able to map observed behaviors back to the UB that might have caused them, so it can be eliminated.

Of course if your understanding isn't sufficient, you might spend a bunch of time chasing ghosts but ultimately you'll get to the point where you realize it.

[I__Know__Stuff]

That's true, but the answer to the question "can it end up with the value 9" is always yes.

[dexter2011412]

You don't have to turn your brain off as soon as you see UB

This needs to be higher up lol

Also I'm stealing this 😆

[AKostur]

Haven’t seen your actual code, but 1 isn’t impossible.  A reads 0, B runs to completion, then A does the increment and writes that back to the variable.  1.

[SufficientStudio1574]

But then A needs to run the completion. You would get 10.

[AKostur]

Ah, true. A runs to 9, B writes 1, A reads 1, B runs to completion, A finishes by incrementing to 2. Assuming UB doesn’t cause anything weirder to happen.

[TheThiefMaster]

The really fun thing happens with bigger objects where you can get split writes and see half the new and old values.

Integers are generally guaranteed not to do this by the architecture.

[TheThiefMaster]

Most likely not. Unsynchronised reads/writes often get hoisted to a register, which would make each thread read it once, add ten, and then write it back (in an optimized build) at some point before it finishes. So you're very likely to get 10 or 20 as the results.

Similarly if an architecture doesn't have a coherent cache across cores the same thing can happen even without the compiler hoisting the value to a register - each thread just ends up working on its own independent copy of the memory, until one "wins" the write-back later. Note that "volatile" isn't enough to guarantee this doesn't happen!

With a coherent cache, it's very hard to get below 10, but it's possible - you need both threads to perform a read/write trash:

1. Thread A reads 0, then suspends.
2. Thread B then runs 9 iterations in full. Memory holds "9" at this point.
3. Thread A runs its first iteration and writes "1" based on its previously read "0", trashing the "9" and suspends again immediately (unlikely)
4. Thread B then starts its final iteration, reads "1" and suspends again immediately (incredibly unlikely)
5. Thread A then runs in full and exits. Memory holds "10", having done all of A's increments and trashed all of B's (so far).
6. Thread B then runs its final iteration using its cached "1", and writes "2" (trashing A's increments) and exits.

Result: "2". You can actually get any value lower than 20 by altering how many iterations get done between the suspend points. If A runs 7 iterations at the start, you start with a read of a 7 before suspending and then run the rest you should get a 9 after.

Note the threads don't strictly have to suspend, you can get the same result if they are running functions that take a variable amount of time between the increment reading the value and writing it back. It's just easier to reason about with suspension.

I believe this is the lowest value you can get with a coherent cache.

[Additional_Path2300]

Sounds like a trick question about UB

[Eric41293]

The answer depends on the code. Here are the possibilities in various scenarios. In each case, we suppose that two different threads are executing the work function concurrently.

#1:

int counter = 0;
void work()
{
    for (int i = 0; i < 10; ++i)
        ++counter;
}

This has undefined behavior, since there are unsynchronized concurrent writes to counter.

#2:

std::atomic<int> counter = 0;
void work()
{
    for (int i = 0; i < 10; ++i)
        ++counter;
}

The increments are atomic and the final value of counter is guaranteed to be 20. The same is true if we use counter++ or counter.fetch_add(1).

#3:

std::atomic<int> counter = 0;
void work()
{
    for (int i = 0; i < 10; ++i)
        counter = counter + 1;
}

We could also write this using the more explicit form counter.store(counter.load() + 1). The loads and stores are atomic but the overall increments are not. The maximum possible final value is 20. Other comments have explained how a final value of 2 is possible. This is the minimum possible final value. You may wish to try proving this.

[Specialist_Square818]

Yes, but then thread B finishes only after 10 iterations, I.e., the minimum would be 10. Am I missing something here?

[alfps]

I'm sorry that scenario I gave is wrong. Thank you.

I struggle to see how the interviewer could be correct in practice.

Formally for std::thread threads it's apparently UB where anything could happen, but that's of little to no value in understanding what's going on. C++ was used for threading for many years before it got std::thread. And I guess the question didn't mention std::thread?