How to enforce execution order?

Hi there,

i have a sequence like the following:

const char *a = "foo";
char b[10];

for ( i = 1; i < strlen(a); i++)
{
b[i] = a[i];
}
b[0] = a[0];

I guess, an optimizing compiler might mixup the execution order of this
code snipped. How can I enforce, that the copying of the char at
position 0 is done after the loop?

I work in a multithreaded environment, and Semaphores, Mutex etc. are
not suitable for the current situation.

-Sacha

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

"Sacha Schär" <sacha.schaer@unibas.ch> wrote in message
news:43df394f$1_3@news.bluewin.ch...[color=blue]
> Hi there,
>
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

volatile const char *a = "foo";

BTW why are you using C-style strings instead of std::string?


-Mike

re: How to enforce execution order?

Sacha Schär wrote:[color=blue]
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

Turn off optimizations for this particular piece of code. Consult with
your compiler manual on how to do that.
[color=blue]
> I work in a multithreaded environment, and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]

And it's not relevant to the newsgroups you posted to, anyway. There are
no such things like "Semaphores" or "Mutex" in C++.

V

re: How to enforce execution order?

This is just a guess.. how about an inline function?

void inline copyFirstElem(const char *a, char *b)
{
b[0] = a[0]
}

{Please do not top post. -mod/fg}

Sacha Schär wrote:[color=blue]
> Hi there,
>
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?
>
> I work in a multithreaded environment, and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär wrote:
[color=blue]
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped.[/color]

Sure, it can do whatever it wants, as far as the final effect is the same.
[color=blue]
> How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

It does not make any difference. After all, you want to copy some bytes
somewhere, right?
[color=blue]
> I work in a multithreaded environment[/color]

So you don't want to *just* copy some bytes somewhere, you want to make
some more complicated logic on top of it.
If a and b are shared objects, then you have to use proper tools to make
the threads properly collaborate. It's not only about order, but also
about visibility.
[color=blue]
> and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]

Why? Without proper synchronization tools, there is nothing you can do
to *enforce* any particular ordering of events in the multithreaded
application.


--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär schrieb:
<snip>[color=blue]
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

switch off all optimizations?

to be honest, you'd have to fool the compiler's optimization by using
some value that could be computed only at the end of the loop i.e.

int i;
for ( i = 0 ; i < strlen(a); i++ )
{ b[i] = a[i]; }

// this is not portable at the moment
// i think there is a macro CHAR_BYTES that should replace the "8"
// and the mask must be fixed
b[0] = ((unsigned int)i<<8|(unsigned int)(a[0]))&0xff;

however, even with this the compiler might be clever enough to get it out.

the most secure way would be to reimplement the loop using assembler.

greetings from dresden
andré

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

On 2006-01-31 17:55, Sacha Schär wrote:[color=blue]
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?
>
> I work in a multithreaded environment, and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]

The reordering of accesses by the compiler can be prevented by
performing the relevant accesses through volatile-qualified lvalues.
But in a multithreaded environment this isn't good enough, because the
hardware can reorder accesses as well, in addition to the compiler.
To prevent such reordering at the hardware level, you need to issue
a memory barrier instruction, either directly or by employing some
synchronization primitive. How you can do this is compiler- and/or
OS-dependent.

-- Niklas Matthies

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär wrote:
[color=blue]
> i have a sequence like the following:[/color]
[color=blue]
> const char *a = "foo";
> char b[10];[/color]
[color=blue]
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];[/color]
[color=blue]
> I guess, an optimizing compiler might mixup the execution
> order of this code snipped. How can I enforce, that the
> copying of the char at position 0 is done after the loop?[/color]

In what sense? The standard requires that the observable
behavior be as if the assignment at position 0 occured after the
loop. But since there is no observable behavior in the above, a
compiler can pretty much do what it wants. Because there is no
observable behavior, of course, you can't tell what it does,
either.
[color=blue]
> I work in a multithreaded environment, and Semaphores, Mutex
> etc. are not suitable for the current situation.[/color]

If other threads can access b, then you cannot avoid some sort
of synchronization primitive. Posix offers mutex, and a few
others; Windows, and many Unix platforms, also have lower level
primitives. But without some primitive, there is no guarantee
concerning the order of the writes as seen in another thread.
(And it's not just a problem of the compiler. Modern hardware
does considerable reordering itself. The primitives will use
special hardware instructions to inhibit the reordering. And
typically, there is no way to get the compiler to emit these
instructions; it must be done in assembler.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär wrote:[color=blue]
> const char *a = "foo";
> char b[10];
> for ( i = 1; i < strlen(a); i++)
> b[i] = a[i];
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped.[/color]
Yes, as long as the observable behaviour does not change.
[color=blue]
> How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]
Make 'b' volatile "volatile char b[10]".
[color=blue]
> I work in a multithreaded environment, and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]
You should also consider CPU cache coherency. For example, another thread may run on
another CPU and it's cache may contain different values in 'b' than the cache of the CPU
running your main thread. You may also need a memory barrier here.

It would help you you explained the problem you are trying to solve.

Also, it is not efficient to call strlen in each iteration, it would be a way faster to
calculate it once and use that value (although sometimes a good compiler may be able to
optimise that call away if it can prove that 'a' and 'b' do not overlap).

--

Valentin Samko - http://www.valentinsamko.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

"Sacha Schär" <sacha.schaer@unibas.ch> skrev i meddelandet
news:43df394f$1_3@news.bluewin.ch...[color=blue]
> Hi there,
>
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of
> this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

Why would you?

An optimizing compiler can do anything it likes, as long as you can't
tell the difference. That is called the "as-if" rule. The code must be
executed as-if it is done exactly in the order you write it.

Can you tell the difference?


Bo Persson




[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär wrote:[color=blue]
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

Put it in an _asm block.
Or put an empty _asm block between the loop and the last line.
Or turn off optimization.

Or, document the problem and report it to the compiler...
if you can tell the difference in a conforming program, then the
compiler is broken.
[color=blue]
> I work in a multithreaded environment, and Semaphores, Mutex etc. are
> not suitable for the current situation.[/color]

In a multithreaded environment, strike the bit about a conforming
program,
because the standard doesn't currently address multiple threads.
But still, if the semaphore or whatever works properly, it ought to
guard the order of your program's execution.
Check your compiler's documentation!


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Sacha Schär <sacha.schaer@unibas.ch> wrote:[color=blue]
> i have a sequence like the following:
>
> const char *a = "foo";
> char b[10];
>
> for ( i = 1; i < strlen(a); i++)
> {
> b[i] = a[i];
> }
> b[0] = a[0];
>
> I guess, an optimizing compiler might mixup the execution order of this
> code snipped. How can I enforce, that the copying of the char at
> position 0 is done after the loop?[/color]

Why do you need this? It might not be enough to ensure that "b[0] =
a[0]" happens at the end since the compiler might not even write the
data to memory but keep it in registers up to a point.

You can use a compiler barrier before the last assignment (and maybe
one more after it if you want to ensure that the data was really
written to memory). In general, any function call (which is not
inlined) is a compiler barrier. Otherwise, it depends on the
compiler. For gcc, an empty asm directive would do the job:

asm volatile ("" : : : "memory");

It might help if you detail the problem you are seeing a bit more.

--
Catalin

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

André Kempe wrote:[color=blue]
> Sacha Schär schrieb:
> <snip>[color=green]
> > for ( i = 1; i < strlen(a); i++)
> > {
> > b[i] = a[i];
> > }
> > b[0] = a[0];[/color][/color]
[color=blue][color=green]
> > I guess, an optimizing compiler might mixup the execution
> > order of this code snipped. How can I enforce, that the
> > copying of the char at position 0 is done after the loop?[/color][/color]
[color=blue]
> switch off all optimizations?[/color]

[...][color=blue]
> the most secure way would be to reimplement the loop using
> assembler.[/color]

Note that even then, unless you use special instructions to
ensure otherwise, another thread may see the writes in a
different order.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

Catalin Marinas wrote:[color=blue]
> Sacha Schär <sacha.schaer@unibas.ch> wrote:[color=green]
> > i have a sequence like the following:[/color][/color]
[color=blue][color=green]
> > const char *a = "foo";
> > char b[10];[/color][/color]
[color=blue][color=green]
> > for ( i = 1; i < strlen(a); i++)
> > {
> > b[i] = a[i];
> > }
> > b[0] = a[0];[/color][/color]
[color=blue][color=green]
> > I guess, an optimizing compiler might mixup the execution
> > order of this code snipped. How can I enforce, that the
> > copying of the char at position 0 is done after the loop?[/color][/color]
[color=blue]
> Why do you need this? It might not be enough to ensure that
> "b[0] = a[0]" happens at the end since the compiler might not
> even write the data to memory but keep it in registers up to a
> point.[/color]
[color=blue]
> You can use a compiler barrier before the last assignment (and
> maybe one more after it if you want to ensure that the data
> was really written to memory). In general, any function call
> (which is not inlined) is a compiler barrier. Otherwise, it
> depends on the compiler. For gcc, an empty asm directive would
> do the job:[/color]
[color=blue]
> asm volatile ("" : : : "memory");[/color]

Not on a Sparc. You'd have to put a membar instruction in the
asm directive.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

re: How to enforce execution order?

"kanze" <kanze@gabi-soft.fr> wrote:[color=blue]
> Catalin Marinas wrote:[color=green]
>> You can use a compiler barrier before the last assignment (and
>> maybe one more after it if you want to ensure that the data
>> was really written to memory). In general, any function call
>> (which is not inlined) is a compiler barrier. Otherwise, it
>> depends on the compiler. For gcc, an empty asm directive would
>> do the job:[/color]
>[color=green]
>> asm volatile ("" : : : "memory");[/color]
>
> Not on a Sparc. You'd have to put a membar instruction in the
> asm directive.[/color]

I was only talking about the compiler barrier, not the hardware
one. If you are not on an SMP system or the memory location doesn't
need to be accessed by something other than the CPU itself, an empty
asm instruction is enough. This is because even if the value didn't
get to memory (weakly ordered memory or write buffers), the CPU should
be smart enough to get it from the write buffers if it is read by
itself. The only use of this is probably for the code that breaks the
strict aliasing rules.

On SMP or if the location is shared with a device, indeed you would
need a hardware memory barrier as well (and maybe cache flushing). My
experience is mainly with ARM processors but I don't think it is too
different on Sparc (I might be wrong though).

--
Catalin

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]