Very peculiar problem

[Doug Mika]

Ok, this has happened to me once when I was programming in java, and it makes completely no sense to me. In the program below I use two threads to add the even fibanacci numbers below 4 000 000. The program is a little awkwerd because of all the cout's but the problem is this, if you REM (or delete) the line "cout<<".";" in the while statement in main() the program doesn't work, however, if you print all those anoying dots to the screen the program works. WHY?

#include <iostream>
#include <thread>
#include <functional>
#include <mutex>
#include <condition_variable>
#include <chrono>

using namespace std;

void functionOne();
void functionTwo();

mutex mtx;
condition_variable cvOne, cvTwo;
long t1Value=1, t2Value=2, sum=0;
bool t1Ready=false, t2Ready=false;

int main()
{
cout<<"Solution: "<<endl;
thread t1(functionOne);
thread t2(functionTwo);
//cout<<"main thread going to sleep"<<endl;
while (!t1Ready||!t2Ready) {
cout<<"."; //IF YOU DELETE THIS cout, THE PROGRAM DOESN'T WORK!!
}
unique_lock<std::mutex> lck(mtx);
cvOne.notify_all();
cout<<"Notified cvOne"<<endl;
lck.unlock();
cout<<" t1="<<t1Value<<endl;
cout<<" t2="<<t2Value<<endl;
t1.join();
t2.join();
cout<<"End:"<<endl;
cout<<" sum="<<sum<<endl;

return 0;
}

void functionOne(){
cout<<"Inside functionOne"<<endl;
unique_lock<std::mutex> lck(mtx);
t1Ready=true;
while(t1Value<4000000){
cout<<"t1: inside while\n";
cvOne.wait(lck);
cout<<"t1 is adding"<<endl;
if(t1Value%2==0) sum+=t1Value;
t1Value+=t2Value;
cvTwo.notify_all();
}
}

void functionTwo(){
cout<<"Inside functionTwo"<<endl;
unique_lock<std::mutex> lck(mtx);
t2Ready=true;
while(t2Value<4000000){
cout<<"t2: inside while\n";
cvTwo.wait(lck);
cout<<"t2 is adding"<<endl;
if(t2Value%2==0) sum+=t2Value;
t2Value+=t1Value;
cvOne.notify_all();
}
}

[Chris M. Thomasson]

> "Doug Mika" wrote in message
> news:543dbdaf-c710-4a8b...@googlegroups.com...

> ____________________________________

> unique_lock<std::mutex> lck(mtx);
> cvOne.notify_all();
> cout<<"Notified cvOne"<<endl;
> lck.unlock();

> ____________________________________

I still need to take at look at the whole, however, you seem to be notifying
a condition without
any mutations to any condition. In other words, you seem to be blindly
broadcasting without
any change in the state. Keep in mind that condvar signals do not maintain
their own state
like an event. They depend on the user defined state.

FWIW, check this out:

http://www.1024cores.net/home/relacy-race-detector

I might be able to help you out a bit.

[Doug Mika]

I just noticed one more thing, this problem occurs on cpp.sh but NOT on tutorialspoint online C++11 compiler??

[Richard Damon]

On 7/25/15 2:58 PM, Doug Mika wrote:
> Ok, this has happened to me once when I was programming in java, and
> it makes completely no sense to me. In the program below I use two
> threads to add the even fibanacci numbers below 4 000 000. The
> program is a little awkwerd because of all the cout's but the problem
> is this, if you REM (or delete) the line "cout<<".";" in the while
> statement in main() the program doesn't work, however, if you print
> all those anoying dots to the screen the program works. WHY?
>

I haven't really looked at your code in detail, but this sort of issue
sounds like something similar to a race condition. IT means that likely
the program doesn't have defined behavior even with the print, it just
make the undefined behavior much more likely to be appearing to work. It
probably slows done the main thread between testing the flags and
interacting with the threads, so that the threads actually get to the
needed point first.

[Doug Mika]

For those curious, I'd recommend trying to run the code in cpp.sh. After I ran it there, I must say I'm convinced they have a buggy compiler...I know, that's a strong statement - but try it.

[Robert Wessel]

It strikes me that t1Ready and t2Ready are not volatile.

[Louis Krupp]

The scary thing is that you might be right.

I tried your program with g++ version 4.9.2. With no optimization, it
worked without the cout in question. At optimization level 1,
however, the while (!t1Ready||!t2Ready) loop never terminated.

(You didn't mention what you meant when you said the program "didn't
work." This is an important detail.)

With no optimization, this is the generated assembler for the loop:

.L48:
movzbl t1Ready(%rip), %eax
xorl $1, %eax
testb %al, %al
jne .L48
movzbl t2Ready(%rip), %eax
xorl $1, %eax
testb %al, %al
jne .L48

At optimization level 1, this is generated:

movzbl t1Ready(%rip), %eax
movzbl t2Ready(%rip), %edx
.L103:
testb %al, %al
je .L103
testb %dl, %dl
je .L103

The values of t1Ready and t2Ready are stored in registers which will
never change, so the loop goes on forever.

The cout changes the generated code a lot, and the possibly buggy
optimization isn't done.

Louis

[Louis Krupp]

Making them volatile does indeed change the outcome with g++ 4.9.2

Louis

[Maxim Fomin]

<disasm skipped>
>
> Louis
>

Why this means that compiler is buggy? I can observe same behavior with
MSVC and gcc: in optimization ('release') mode the execution stops.

My guess is that due to 'as if' permission 'abstract machine' optimizes
check away if the while statement is empty (note, it seems that adding
any non-optimized call, such as printf() or srand() makes the program work).

It seems the right way is to qualify objects as volatile, as suggested
previously.

[Chris Vine]

It may not represent the cause of what you are seeing (TL;DR) (your code
may well have other problems), but your code is broken for at least one
reason. Condition variables in C++11 (and POSIX) cannot be used without
a condition because they can have spurious wake-ups. You cannot use
them like event objects - the clue is in the name.

See in particular the documentation on condition_variable::wait() in
§30.5.1 of C++11: "The function will unblock when signaled by a call to
notify_one() or a call to notify_all(), _or spuriously_" (my
emphasis). All condition variables should be used in a while loop with
an associated condition. (The version of condition_variable::wait()
which takes a predicate will do that for your automatically.)


Chris

[Louis Krupp]

I think you're right.

Louis

[Chris Vine]

On Sun, 26 Jul 2015 00:37:11 +0300

Maxim Fomin <maxim...@outlook.com> wrote:
[snip]

> It seems the right way is to qualify objects as volatile, as
> suggested previously.

That may work in practice on x86/64, where on int-sized variables
volatile has a similar effect to relaxed atomics, but it is not
guaranteed by the standard. To avoid tearing you need to use atomics
with at least relaxed memory ordering. To provide memory visibilty and
ordering you need acquire/release semantics on an atomic variable.

In Java volatile does provide acquire/release semantics as a matter of
language requirement. In C/C++ it does not.

However, I have pointed out elsewhere that apart from that the OP is
misusing condition variables.

Chris

[bartekltg]

You, OP, I, most people known bool is atomic variable and
can be uset to interthread communication.
But compiler doesn't known we want use it to interthread
communication;-)

During strone age it was patched by using volatile. But it worked
only on _some_ platforms and compilers. Do not use volatile in
that way!

"This makes volatile objects suitable for communication with a signal
handler, but not with another thread of execution, see
std::memory_order)."
http://en.cppreference.com/w/cpp/language/cv
http://en.cppreference.com/w/cpp/atomic/memory_order


Now, with c++11, just add:
#include <atomic>
change type:
atomic_bool t1Ready{false}, t2Ready{false};


Works both on gcc and... cpp.sh (why?! :)


Using methods 'store' and "load" you can tweak
memory order, but default is good and "=" is
equiwalent to strore and using as bool is (casting)
is equivalent to load.



code:

#include <iostream>
#include <thread>
#include <functional>
#include <mutex>
#include <condition_variable>
#include <chrono>

#include <atomic>

using namespace std;

void functionOne();
void functionTwo();

mutex mtx;
condition_variable cvOne, cvTwo;
long t1Value=1, t2Value=2, sum=0;

atomic_bool t1Ready{false}, t2Ready{false};

int main()
{
cout<<"Solution: "<<endl;
thread t1(functionOne);
thread t2(functionTwo);
//cout<<"main thread going to sleep"<<endl;
while (!t1Ready||!t2Ready) { }

[Luca Risolia]

Il 25/07/2015 20:58, Doug Mika ha scritto:

> //cout<<"main thread going to sleep"<<endl;
> while (!t1Ready||!t2Ready) {
> cout<<"."; //IF YOU DELETE THIS cout, THE PROGRAM DOESN'T WORK!!
> }

The standard requires that the observable behaviour *inside a thread* of
the generated code must be correct:

"An implementation is free to disregard any requirement of this
International Standard as long as the result is *as if* the requirement
had been obeyed, as far as can be determined from the observable
behaviour of the program. For instance, an implementation need not
evaluate part of an expression if it can deduce that its value is not
used and that no side effects affecting the observable behaviour of
program are produced"

I suggest that you look better at how you declared/used t1Ready and t2Ready.

[bartekltg]

On 25.07.2015 20:58, Doug Mika wrote:
> Ok, this has happened to me once when I was programming in java, and
> it makes completely no sense to me. In the program below I use two
> threads to add the even fibanacci numbers below 4 000 000. The
> program is a little awkwerd because of all the cout's but the problem
> is this, if you REM (or delete) the line "cout<<".";" in the while
> statement in main() the program doesn't work, however, if you print
> all those anoying dots to the screen the program works. WHY?
>

add:
#include <atomic>

change the type:

bool t1Ready{false}, t2Ready{false};

->

atomic_bool t1Ready{false}, t2Ready{false};

Works both in gcc and cpp.sh

Do not use volatile, it will backfire someday:)

More deep inside this thread.

bartekltg

[Chris M. Thomasson]

> "Robert Wessel" wrote in message
> news:hpt7rapi144fdkchg...@4ax.com...

> > On Sat, 25 Jul 2015 11:58:52 -0700 (PDT), Doug Mika
> > <doug...@gmail.com> wrote:

[...]

> It strikes me that t1Ready and t2Ready are not volatile.

volatile has nothing to do with it.

[Chris M. Thomasson]

> "Doug Mika" wrote in message
> news:543dbdaf-c710-4a8b...@googlegroups.com...

You have a big problem here:

> while (!t1Ready||!t2Ready) {
> cout<<"."; //IF YOU DELETE THIS cout, THE PROGRAM DOESN'T WORK!!
> }

Personally, I would not use volatile to fix it. Use relaxed atomic loads and
stores instead.

[Chris M. Thomasson]

>"Chris M. Thomasson" wrote in message
>news:mp12qd$6k5$1...@speranza.aioe.org...

Well, it has something to do with it. Sorry.

IMVHO, I would advise the OP to rigorously learn ho to use condvars, then
get all fancy
with fine grain atomics...

;^)

[Chris M. Thomasson]

> "bartekltg" wrote in message news:mp11k8$o59$1...@node2.news.atman.pl...
[...]

> Do not use volatile, it will backfire someday:)

:^)

For use in threading, it can actually backfire to the point where it blows
the damn car up.

Ouch.

[...]

[Marcel Mueller]

On 25.07.15 20.58, Doug Mika wrote:
> #include <iostream>
> #include <thread>
> #include <functional>
> #include <mutex>
> #include <condition_variable>
> #include <chrono>
>
> using namespace std;
>
> void functionOne();
> void functionTwo();
>
> mutex mtx;
> condition_variable cvOne, cvTwo;
> long t1Value=1, t2Value=2, sum=0;
> bool t1Ready=false, t2Ready=false;
>
> int main()
> {
> cout<<"Solution: "<<endl;
> thread t1(functionOne);
> thread t2(functionTwo);
> //cout<<"main thread going to sleep"<<endl;
> while (!t1Ready||!t2Ready) {
> cout<<"."; //IF YOU DELETE THIS cout, THE PROGRAM DOESN'T WORK!!

Indeed. Your booleans are not declared to be changed asynchronously. So
the compiler may optimize away the entire loop and check the condition
only once. And even if the compiler will not do this kind of
optimization you are missing a memory barrier, i.e. the CPU cache of the
executing thread might return out-dated values.

This changes by the call to cout<<. First of all any function call might
change any static variable unless it is an inline function and the
compiler knows its code. So calling a function from another object
module implicitly acts like volatile here.

Secondly the iostreams are thread-safe (nowadays guaranteed), i.e.
writing to the same stream from different threads is defined behavior in
the way that it will not turn the stream into an inconsistent state and
no output is lost. (Note that the order of the output is still undefined.)
However, this thread safety is usually implemented by a mutex. So each
call to operator<< acquires and releases a mutex at least once. The
mutex operations in turn imply a full memory barrier. So the CPU cache
is also synchronized. That't the reason why it works.

This is also why others recommended atomic_bool.

volatile in contrast is /not sufficient/ as it solves the optimization
problem but not the memory fence for cache coherence. Although on
typical hardware the caches become synchronized somewhat later. So your
detection is usually only delayed undefinedly.

But besides all the discussion above I would reject this code as soon as
I see it anywhere because of the busy loop that constantly eats CPU
cycles without any reasonable result. A wait() is missing in this loop.
I would not even accept this for educational purposes unless the task is
to demonstrate what happens because of the wrong code.


Marcel

[Bo Persson]

This is very much like using volatile - not sufficent. :-)

Modern compilers are smart enough to inline functions from other
modules, so they surely can see the code there as well.

So the "trick" here is that cout either contains some synchronization,
or makes operating system calls, which compilers cannot see through (yet).

>
> volatile in contrast is /not sufficient/ as it solves the optimization
> problem but not the memory fence for cache coherence. Although on
> typical hardware the caches become synchronized somewhat later. So your
> detection is usually only delayed undefinedly.

Bo Persson

[Marcel Mueller]

Full ack!

In C++ (unlike C#) volatile does not force acquire / release semantics
an read / write access to volatile fields. So it is of very limited use.

The only use I remember is to declare class instances as volatile, but
only for the purpose to invoke other thread-safe member function
overloads. This can be very useful for strongly thread safe, reference
counted smart pointers or string classes.


Marcel

[Wouter van Ooijen]

> In C++ (unlike C#) volatile does not force acquire / release semantics
> an read / write access to volatile fields. So it is of very limited use.
>
> The only use I remember is to declare class instances as volatile, but
> only for the purpose to invoke other thread-safe member function
> overloads.

You are under-appreciating voltaile! *Everything* you do in an
application is ultimately communicated to the outside world by
manipulating volatile variables that represent hardware registers that
are somehow electrically coupled to I/O hardware. Without volatile your
application would be totally deaf-mute.

Wouter

[Luca Risolia]

volatile and atomic<> are orthogonal. For example, it would not be
unreasonable to use them together in device drivers that need to access
special I/O memory concurrently:

volatile atomic<int> val; // atomic, no reorderings, no optimizations.