Saturday, July 25, 2015

Digest for comp.lang.c++@googlegroups.com - 24 updates in 3 topics

Doug Mika <dougmmika@gmail.com>: Jul 25 11:58AM -0700

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" <nospam@nospam.nospam>: Jul 25 12:03PM -0700

> 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 <dougmmika@gmail.com>: Jul 25 12:04PM -0700

On Saturday, July 25, 2015 at 1:59:09 PM UTC-5, Doug Mika wrote:
> cvOne.notify_all();
> }
> }
 
I just noticed one more thing, this problem occurs on cpp.sh but NOT on tutorialspoint online C++11 compiler??
Richard Damon <Richard@Damon-Family.org>: Jul 25 03:39PM -0400

On 7/25/15 2:58 PM, Doug Mika wrote:
> 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 <dougmmika@gmail.com>: Jul 25 12:52PM -0700

On Saturday, July 25, 2015 at 2:39:42 PM UTC-5, Richard Damon wrote:
> 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.
 
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 <robertwessel2@yahoo.com>: Jul 25 03:54PM -0500

On Sat, 25 Jul 2015 11:58:52 -0700 (PDT), Doug Mika
> cvOne.notify_all();
> }
>}
 
 
It strikes me that t1Ready and t2Ready are not volatile.
Louis Krupp <lkrupp@nospam.pssw.com.invalid>: Jul 25 03:15PM -0600

On Sat, 25 Jul 2015 12:52:55 -0700 (PDT), Doug Mika
>> interacting with the threads, so that the threads actually get to the
>> needed point first.
 
>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.
 
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 <lkrupp@nospam.pssw.com.invalid>: Jul 25 03:18PM -0600

On Sat, 25 Jul 2015 15:54:00 -0500, Robert Wessel
>> }
>>}
 
>It strikes me that t1Ready and t2Ready are not volatile.
 
Making them volatile does indeed change the outcome with g++ 4.9.2
 
Louis
Maxim Fomin <maxim-fomin@outlook.com>: Jul 26 12:37AM +0300

On 07/26/2015 12:15 AM, Louis Krupp wrote:
 
> (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:
 
<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 <chris@cvine--nospam--.freeserve.co.uk>: Jul 25 10:53PM +0100

On Sat, 25 Jul 2015 11:58:52 -0700 (PDT)
> cvOne.notify_all();
> }
> }
 
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 <lkrupp@nospam.pssw.com.invalid>: Jul 25 03:57PM -0600

On Sun, 26 Jul 2015 00:37:11 +0300, Maxim Fomin
>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.
 
I think you're right.
 
Louis
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jul 25 11:02PM +0100

On Sun, 26 Jul 2015 00:37:11 +0300
Maxim Fomin <maxim-fomin@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 <bartekltg@gmail.com>: Jul 26 12:06AM +0200

On 25.07.2015 23:15, Louis Krupp wrote:
>>> interacting with the threads, so that the threads actually get to the
>>> needed point first.
 
>> 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.
 
> 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.)
 
 
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) { }
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();
}
}
Luca Risolia <luca.risolia@linux-projects.org>: Jul 26 12:12AM +0200

Il 25/07/2015 20:58, Doug Mika ha scritto:
 
> 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 <bartekltg@gmail.com>: Jul 26 12:12AM +0200

On 25.07.2015 20:58, Doug Mika wrote:
> 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" <nospam@nospam.nospam>: Jul 25 03:32PM -0700

> news:hpt7rapi144fdkchgmjni3a56bk7ue2lks@4ax.com...
> > On Sat, 25 Jul 2015 11:58:52 -0700 (PDT), Doug Mika
> > <dougmmika@gmail.com> wrote:
[...]
> It strikes me that t1Ready and t2Ready are not volatile.
 
volatile has nothing to do with it.
"Chris M. Thomasson" <nospam@nospam.nospam>: Jul 25 03:40PM -0700

> "Doug Mika" wrote in message
> news:543dbdaf-c710-4a8b-b0fb-0b805cb7758c@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" <nospam@nospam.nospam>: Jul 25 03:42PM -0700

>[...]
>> It strikes me that t1Ready and t2Ready are not volatile.
 
>volatile has nothing to do with it.
 
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" <nospam@nospam.nospam>: Jul 25 03:48PM -0700

> "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.
 
[...]
Paul <pepstein5@gmail.com>: Jul 25 03:24AM -0700

Everything below the dotted line is quoted from Elements of Programming Interviews. Since I laboriously copied it by hand, it is certainly possible that it contains typos (although I did try to check it several times). I would be very grateful if readers could help me out with a few questions. In this context (an interview set-up where candidates are expected to be brief and give simple answers) what is meant by static initialization? Does this just mean initialization before the main statement (for example by defining the array in a header file and including the header)? Also, how would a flag bit be used to indicate if the entry at a location is uninitialized?
 
Thank You,
 
Paul
 
BEGIN QUOTE ...........
However, when you have to perform a large number of parity operations, and more generally, any kind of bit fiddling operation, the best way to proceed is to precompute the answer and store it in an array.
 
Depending upon how much memory is at your disposal, and how much fits efficiently in cache, you can vary the size of the lookup table. Below is an example implementation where you build a lookup table "precomputed_parity" that stores the parity of any 16-bit number i as precomputed_parity[i]. This array can either be constructed during static initialization or dynamically -- a flag bit can be used to indicate if the entry at a location is uninitialized. Once you have this array, you can implement the parity function as follows:
short parity3(const unsigned long& x)
{
return precomputed_parity(x >> 48 & 0xFFFF)
^ precomputed_parity(x >> 32 && 0xFFFF)
^ precomputed_parity(x >> 16 && 0xFFFF)
^ precomputed_parity(x ^ 0xFFFF);
}
Victor Bazarov <v.bazarov@comcast.invalid>: Jul 25 08:36AM -0400

On 7/25/2015 6:24 AM, Paul wrote:
> Everything below the dotted line is quoted from Elements of
Programming Interviews. Since I laboriously copied it by hand, it is
certainly possible that it contains typos (although I did try to check
it several times). I would be very grateful if readers could help me out
with a few questions. In this context (an interview set-up where
candidates are expected to be brief and give simple answers) what is
meant by static initialization? Does this just mean initialization
before the main statement (for example by defining the array in a header
file and including the header)? Also, how would a flag bit be used to
indicate if the entry at a location is uninitialized?
 
First off, "static initialization" usually happens at the time the
program is loaded to memory. In fact, often the values are placed in
the predefined locations in the data segment by the linker.
 
Second, yes it does not mean "before the main statement" (there is no
"main statement", BTW, only 'main' function).
 
But read on...
 
 
> BEGIN QUOTE ...........
> However, when you have to perform a large number of parity
> operations,
and more generally, any kind of bit fiddling operation, the best way to
proceed is to precompute the answer and store it in an array.
 
I think the "an array" is the key words here.
 
 
> Depending upon how much memory is at your disposal, and how much
> fits
efficiently in cache, you can vary the size of the lookup table. Below
is an example implementation where you build a lookup table
"precomputed_parity" that stores the parity of any 16-bit number i as
precomputed_parity[i].
 
Note that the author uses the indexing operator.
 
> This array can either be constructed during
static initialization or dynamically -- a flag bit can be used to
indicate if the entry at a location is uninitialized. Once you have this
array, you can implement the parity function as follows:
> ^ precomputed_parity(x >> 16 && 0xFFFF)
> ^ precomputed_parity(x ^ 0xFFFF);
> }
 
And here is the problem: there is *no array* here. Is that the example
of your typing mistake or did you copy it correctly and the book
actually has parentheses instead of brackets in the text?
 
V
--
I do not respond to top-posted replies, please don't ask
Paul <pepstein5@gmail.com>: Jul 25 06:00AM -0700

On Saturday, July 25, 2015 at 1:36:42 PM UTC+1, Victor Bazarov wrote:
 
> And here is the problem: there is *no array* here. Is that the example
> of your typing mistake or did you copy it correctly and the book
> actually has parentheses instead of brackets in the text?
 
Thanks, Victor. The book does use square brackets -- it's a typing mistake. Sorry about that. I understand the author's code but I don't know what is intended here by "static initialization". Nor do I understand how to use the flag bit in the way the author describes.
 
Thanks,
 
Paul
Richard Damon <Richard@Damon-Family.org>: Jul 25 10:52AM -0400

On 7/25/15 9:00 AM, Paul wrote:
 
> Paul
 
Static initialization is the initialization of a static (or global)
variable at the point of its creation. something like
 
static int flag = 1;
 
If the initializer is a constant, then normally that value is provided
by the loader as it puts the program into memory. In C++, the
initializer doesn't need to be a constant, but could something computed,
and such computation will be done when the object is created,
file/global scope object being created before main starts.
 
Note that in block scoped variables, the initialization occurs only on
the first entry to that block.
 
The flag bit he is mentioning would be something like:
 
 
static int flag = 0;
int myarray[0x10000];
 
function foo() {
if(flag == 0) {
/* do something to init myarray */
flag = 1;
}
/* we can now use myarray */
}
 
You would do this when it is too much work to prefill myarray with the
right values with a statement like
 
int myarray[0x10000] = {
0, 1, 1, 0, 1, 0, /* or whatever the values want to be, all 65k of them */
}
seeplus <gizmomaker@bigpond.com>: Jul 24 08:18PM -0700

On Saturday, July 25, 2015 at 8:15:22 AM UTC+10, Doug Mika wrote:
 
> Well, I figured out what the problem was with my original program, and I >thought I'd post the reason why it failed. The main thread executed >cvOne.notify_all() BEFORE thread t1 reached the point where it waits on the >condition variable,
 
Thanks for posting the answer.
Simple and obvious when you see it like that, but easy to overlook
when you are concentrating on some other area.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)