Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C Programming Language

Enforce instruction ordering?


Hi!

Is there any way in C that one can guarantee that instructions are
executed in the same order as they are written in the program?

For example, say I have the following:

instruction1;
instruction2;
instruction3;

Is it possible to call some function/command to ensure that the
instructions are executed in this order?

dspfun said:

> Hi!

> Is there any way in C that one can guarantee that instructions are
> executed in the same order as they are written in the program?

> For example, say I have the following:

> instruction1;
> instruction2;
> instruction3;

> Is it possible to call some function/command to ensure that the
> instructions are executed in this order?

You don't need to. The semicolons mark "sequence points", which impose
the correct ordering.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

> > Is there any way in C that one can guarantee that instructions are
> > executed in the same order as they are written in the program?

> > For example, say I have the following:

> > instruction1;
> > instruction2;
> > instruction3;

> > Is it possible to call some function/command to ensure that the
> > instructions are executed in this order?

> You don't need to. The semicolons mark "sequence points", which impose
> the correct ordering.

Ok, great! Thanks for clear answer!

     Well, yes and no.  There are sequence points, to be sure,
but they exist only in the abstract machine.  When the abstract
machine reaches a sequence point, the state of the real machine
must agree with the abstract -- but only to the extent that a
conforming C program can detect the agreement (or lack thereof).
For example, if the three lines were

        x = sin(a) * cos(b) + cos(a) * sin(b);
        y = cos(a) * cos(b) - sin(a) * sin(b);
        z = atan2(y, x);

... a sufficiently clever compiler might generate just five
instead of nine function calls, rather obviously changing
the apparent order of operations.  We usually like it when the
compiler does this, and applaud it as "optimization."

     The compiler can do such things if a conforming program
can't tell they've been done, but this may still pose problems
for non-conforming programs.  If dspfun is trying to satisfy
some beyond-C-itself constraints (I/O registers? memory barriers?)
he'll need to rely on beyond-C-itself frameworks.

--
Eric Sosman
esos@acm-dot-org.invalid

Thanks for your answer! What would be some common examples of beyond-c-
itself constraints when this wouldn't necessarily be true (i.e. that
the semicolon doesn't necessarily guarantee in order execution)? You
mentioned I/O registers and memory barriers - how can they cause
unexpected reordering?

"dspfun" <dsp@hotmail.com> ha scritto nel messaggio
news:1180015356.066971.202030@q75g2000hsh.googlegroups.com...

If you declare a variable as volatile, it will have to be accessed
whenever the abstract machine does. HTH (but, without knowing what
you are trying to do, or trying to prevent from happening, it's
hard to guess).

But, if the compiler can prove there are no colliding side effects,
can't it rearrange them, or perhaps execute them in parallel?

Or does the sequence point require a strict ordering, regardless of
the possible optimization of rearranging?

For example:

    extern int foo;
    int a,b,c;

    a = foo+2;
    b = foo+1;
    c = foo;

What if it would be a speed improvement to do something like this
pseudo-code:

    load r1,foo
    stor r1,c     ' c = foo
    incr r1
    stor r1,b     ' b = foo+1
    incr r1
    stor r1,a     ' a = foo+2

Given the lack of "volatile", aren't the above sets of code equivalent?

Or perhaps a simple:

    a = foo;
    b = foo;

If the processor can execute "stor r1,a" and "stor r1,b" in parallel,
have you really "ensured that the instructions are executed in this
order"?

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody        | www.hvcomputer.com | #include              |
| kenbrody/at\spamcop.net | www.fptech.com     |    <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:ThisIsASpamT@gmail.com>

dspfun wrote On 05/24/07 10:02,:

>>Eric Sosman wrote (attribution restored):

>>     The compiler can do such things if a conforming program
>>can't tell they've been done, but this may still pose problems
>>for non-conforming programs.  If dspfun is trying to satisfy
>>some beyond-C-itself constraints (I/O registers? memory barriers?)
>>he'll need to rely on beyond-C-itself frameworks.

> Thanks for your answer! What would be some common examples of beyond-c-
> itself constraints when this wouldn't necessarily be true (i.e. that
> the semicolon doesn't necessarily guarantee in order execution)? You
> mentioned I/O registers and memory barriers - how can they cause
> unexpected reordering?

    It's not that these things cause reordering, but
that reordering can affect the outcome in ways the
compiler may not be aware of.  For example, if you
want to use a lock of some kind to coordinate access
to a shared variable in a multi-threaded program, you
might write code like

        for (i = 0;  i < 100;  ++i) {
            acquire_lock();
            x[i] *= shared_flag ? shared_value1 : shared_value2;
            release_lock();
            ...
        }

... the idea being to ensure that the shared_xxx variables
are not used by one thread while another is changing them.

    Unfortunately, C-itself doesn't know anything about
threads or shared variables or locks, and doesn't realize
that the shared_xxx values should only be accessed while
the lock is held.  The compiler may see an opportunity to
get rid of 99 conditionals, and reorganize the code as if
you had written

        temp = shared_flag ? shared_value1 : shared_value2;
        for (i = 0;  i < 100;  ++i) {
            acquire_lock();
            x[i] *= temp;
            release_lock();
            ...
        }

... and this violates the one-at-a-time requirement.  It's
not really the compiler's "fault;" it's just that the compiler
is unaware of the unstated relationship between the lock and
the shared_xxx variables.  A deaf man is not at fault for
failing to perceive a difference between Beethoven and Bono.

    (By the way: The `volatile' keyword is not an effective
cure for the problem here.  It solves the reordering issue
but leaves others unaddressed; visit comp.programming.threads
for more information on this topic, or on this off-topic.)

    Anyhow, your interest in enforcing instruction ordering
made me suspect that you might be facing a situation of this
general kind.  Ordinarily, C programmers do not (and should
not) worry about the instructions the compiler generates to
carry out their wishes; they just want the program to do its
job in the most expeditious manner possible.  Richard's
answer ("That's what sequence points are for") is fine for
the people who just need the program to run, but doesn't help
those who need it to run in a particular prescribed fashion
that isn't expressible in C as such.  I suspected you might
be one of those and so threw out a caution flag.

--
Eric.Sos@sun.com

Kenneth Brody said:

> Richard Heathfield wrote:

>> The semicolons mark "sequence points", which
>> impose the correct ordering.

> But, if the compiler can prove there are no colliding side effects,
> can't it rearrange them, or perhaps execute them in parallel?

If the compiler can prove that the strictly conforming program can't
tell the difference, it can do what it likes, and the strictly
conforming program - oddly enough - can't tell the difference, so it
doesn't actually matter.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

dspfun <dsp@hotmail.com> writes:
> Is there any way in C that one can guarantee that instructions are
> executed in the same order as they are written in the program?

> For example, say I have the following:

> instruction1;
> instruction2;
> instruction3;

> Is it possible to call some function/command to ensure that the
> instructions are executed in this order?

What instructions?

C statements don't specify CPU instructions; they specify computations
or actions to be performed.  The compiler is free to generate whatever
instructions will do the job, and to rearrange them within the
constraints imposed by the standard.

The assumption is that the programmer cares about what the program
does, not about what CPU instrutions it executes to do it.  99% of the
time, that's a valid assumption (and programmers who care about
specific instructions for some reason can always use assembly
language).

To be able to answer your question, it would be helpful if you could
answer a couple of questions.  Why do you care?  And what problem are
you trying to solve?

--
Keith Thompson (The_Other_Keith) k@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

x=sin(a+b); y=cos(a+b);
z=atg(cos()/sin())=atg(1/tg())

>    z = atan2(y, x);

>... a sufficiently clever compiler might generate just five

for me computer has not to be clever
double   t0, t1;
double   a, b, x, y;
........
        x = (t0=sin(a))*(t1=cos(b)) + (t3=cos(a))*(t4=sin(b));
        y = t3*t1 - t0*t4;
        z = atan2(y, x);
or
  t0=sin(a); t1=cos(b); t3=cos(a); t4=sin(b);
  z = atan2(t3*t1 - t0*t4, t0*t1 + t3*t4);

the only problem here seems to be "a" and "b" are "good" double
and t0*t1 + t3*t4!=0 [sin(a+b)!=0 => a+b!=kPi]

but this should be better
if((t=sin(a+b))!=0.0)
     z = atan2(cos(a+b), t );
else exit(-1);

or z= (t=sin(a+b))!=0.0 ? atan2(cos(a+b), t): 1.0/+0.0;
don't know what can happen for sin(a+b)==0

3 only calls
possibly the result can be done only use "a" and "b" so 0 calls
but i not try

"a\\/b" <a@f.g> writes:
> On Thu, 24 May 2007 08:38:23 -0400, Eric Sosman wrote:

> >[an example of how an optimising compiler might transform a
> > sequence of expressions including]

> >       x = sin(a) * cos(b) + cos(a) * sin(b);
> >       y = cos(a) * cos(b) - sin(a) * sin(b);
> >       z = atan2(y, x);

> x=sin(a+b); y=cos(a+b);
> z=atg(cos()/sin())=atg(1/tg())

If I may, I would like to comment a bit on this simplification.

Granted, you did later make the assertion that `a' and `b' be `good'.
However, trignonometric identities that are valid in the real numbers
fail, sometimes spectacularly, when applied to floating point numbers
as implemented in computer systems.  For instance, what happens in the
above transformation if

    (a > DBL_MAX / 2.0) && (b > DBL_MAX / 2.0)

?

Also, while your expression for `z' is enticing at first sight, I
would nevertheless use atan2() as the latter is designed to avoid
divide-by-zero problems.

Best regards,
--
Brd Skaflestad                         <Bard.Skafles@math.ntnu.no>

On May 25, 1:45 am, Richard Heathfield <r@see.sig.invalid> wrote:

> >> The semicolons mark "sequence points", which
> >> impose the correct ordering.
> If the compiler can prove that the strictly conforming program
> can't tell the difference, it can do what it likes, and the
> strictly conforming program - oddly enough - can't tell
> the difference, so it doesn't actually matter.

Sometimes it is hardware, not compiler which
reorders transparently.

I hope readers don't object to off-topic, but
"interesting", anecdotes.  Here's one ...

There was once a computer with a "write buffer".
When ordered to write some data, D2, at an address, A2,
it saved these in a buffer and actually wrote D1 at A1.
Later, when ordered to write D3 at A3 it saved these
in the buffer and actually wrote D2 at A2.  On a read
operation, requested address was compared with write
buffer address so that buffered data could be sent
when required.

This peculiar design arose because of MOS ram
timing spec: system time from write data available at
chip to time read data from *next* cycle must be
valid exceeded chip spec.

The first prototype was a hand-soldered card
with a soldering error, such that the current
address was substituted for the correct buffered
address.  The interesting thing was that *the IBM
memory diagnostics correctly with this bug*!
(This was a Brand-X memory attachment to 370/168.
Of course the IBM diagnostics did not know about
the write buffer, and of course system diagnostics
failed readily.  Still it was peculiar that the
"comprehensive" memory diagnostics all passed --
this meant they all had a trivial form like
Write at A; Read at A with no intervening write;
or else wrote exact same data at all locations.)

> "Usenet is a strange place" - dmr

Some computer systems were pretty strange too.
Especially ones with broken wires....

jamesdowallen at gmail

     Then the sines and cosines of a and b cannot be computed
with any accuracy anyhow.  Garbage in, garbage out.

     No compiler for any general-purpose programming language
that I've ever run into has done transformations of this kind,
and if I ever did run into one I doubt I'd like it.  As you
say, identities that hold for the real numbers quite frequently
do not hold for floating-point numbers, a small subset of the
rationals.  Even as simple an identity as 1+x-1==x does not
always hold (c.f. the definition of DBL_EPSILON).

     My point was not about finding the fastest possible or
best possible or cleverest possible way to compute a value,
but about the ways typical compilers may try to improve on
a computation already expressed.  Many improvements involve
relocating parts of the computation, substituting additions
for multiplications, and doing even weirder things.  These
transformations do violence to the "instruction ordering,"
which is ordinarily not a concern for a C programmer but may
be important for the C-as-a-component-of-something-else
programmer.

--
Eric Sosman
esos@acm-dot-org.invalid

Thanks for your answer! The reason I care is that I have a sequence of
registers in on-chip memory controllers and off-chip memory that must
be configured in chronological order. If the sequence of writes and
reads can be changed then the configuration will have undefined
behaviour. That's why I want to make sure things are written and read
in the order I have written the program.

BRs!

dspfun wrote On 05/25/07 09:12,:

    What you need is `volatile'.  There are a lot of
implementation-defined aspects to `volatile' so you'll
need to check your compiler's documentation, but this
is one of the purposes it exists for.

    (Think of the time, words, and electrons that might
have been saved if you'd divulged this information about
your problem when you first posed it twenty-six hours
ago ...  It is easy to get caught up in tactical issues
and ask questions solely about them, forgetting that the
people you're asking don't know the strategic context in
which the tactical questions arise.  Next time, try to
convey a little more of the context.)

--
Eric.Sos@sun.com

In alt.folklore.computers James Dow Allen <jdallen2@yahoo.com> wrote:

Which is one reason I wrote an article about 30 years ago telling
exactly *why* any decent "memory test" should use random data, or at
least algorithmic data, while bit-tests (supposedly the best tests
around at that time) would pass most failing memory.

I had plenty of real-time data to prove my point.
I never had memory that failed *any* type of pattern-test pass a random
memory test; while most memory that failed the random-pattern tests
would *pass* almost all pattern, bit, and shift tests.

Still don't trust any "memory test" that doesn't include random data
over large blocks of memory, with no repeats in the test area.

Damned few indeed still meet that criterium.
;-{

>> "Usenet is a strange place" - dmr

>Some computer systems were pretty strange too.
>Especially ones with broken wires....

>jamesdowallen at gmail

--
    _____
     /  '               /
  ,-/-, __  __.  ____  /_
 (_/   / (_(_/|_/ / <_/ <_
On Fri, 25 May 2007 14:58:00 -0500, Frank McCoy <mcc@millcomm.com>
wrote:

<snip>

>Still don't trust any "memory test" that doesn't include random data
>over large blocks of memory, with no repeats in the test area.

>Damned few indeed still meet that criterium.
>;-{

Ever tried: http://www.memtest86.com/  ?

I have been using it for some years now, and it seems to do ok.
--
ArarghMail705 at [drop the 'http://www.' from ->] http://www.arargh.com
BCET Basic Compiler Page: http://www.arargh.com/basic/index.html

To reply by email, remove the extra stuff from the reply address.

In alt.folklore.computers ArarghMail705NOS@NOT.AT.Arargh.com wrote:
>On Fri, 25 May 2007 14:58:00 -0500, Frank McCoy <mcc@millcomm.com>
>wrote:

><snip>

>>Still don't trust any "memory test" that doesn't include random data
>>over large blocks of memory, with no repeats in the test area.

>>Damned few indeed still meet that criterium.
>>;-{

>Ever tried: http://www.memtest86.com/  ?

>I have been using it for some years now, and it seems to do ok.

Yes, I tried it, and it actually found some memory errors for me.
It has a random-data pattern test in it; but I'm not sure if it meets my
criteria or not.  I *suspect* not; because of the way the data is
presented on the screen.  That doesn't mean it isn't.  I'd have to see
more information about the way the actual random-data is generated.  My
*fears* are that they just generate a random 32-bit pattern ... and
duplicate that same 32-bits throughout memory, which is *NOT* what I
mean by random pattern testing though to a person not familiar with what
I mean, it *sounds* like the same thing, but is nowhere near the same.

--
    _____
     /  '               /
  ,-/-, __  __.  ____  /_
 (_/   / (_(_/|_/ / <_/ <_

On Fri, 25 May 2007 18:34:45 -0500, Frank McCoy <mcc@millcomm.com>
wrote:

New version back in Jan, 2007.

The source is available: memtest86-3.3.tar.gz is the latest version.  

 . . .

Just looked at it.  At least 1 test calls the rand routine for each
memory word in 'test.c'.  I suppose another question is how good is
the random number generator (in random.c).  It's a PRNG, and I don't
know its period.
--
ArarghMail705 at [drop the 'http://www.' from ->] http://www.arargh.com
BCET Basic Compiler Page: http://www.arargh.com/basic/index.html

To reply by email, remove the extra stuff from the reply address.

ArarghMail705NOS@NOT.AT.Arargh.com wrote:

... snip about memtest86 ...

> New version back in Jan, 2007.

> The source is available: memtest86-3.3.tar.gz is the latest version.

>  . . .

> Just looked at it.  At least 1 test calls the rand routine for each
> memory word in 'test.c'.  I suppose another question is how good is
> the random number generator (in random.c).  It's a PRNG, and I don't
> know its period.

Then you should be able to replace it if you wish.  The cokusmt
module (not mine) is included in hashlib.h, and is supposedly
excellent.  See:

  <http://cbfalconer.home.att.net/download/>

The interface is simple.  Seed it with something, saving the seed
value, set the memory, reseed with the same value, and run
comparisons.  Correct the 32 bit values modulo WHATEVER+1.  Whether
or not it works when longs are bigger than 32 bits is unknown to
me.

--
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

On Fri, 25 May 2007 21:08:59 -0400, CBFalconer <cbfalco@yahoo.com>
wrote:

Replacing the PRNG might be a good idea.  memtest86 is supposed to be
able to test up to 2 gig of memory, so for a GOOD random test, the
period of the PRNG needs to be larger than 2 gig.  IMO.

 . . .

Just took another look at 'random.c'  I can't tell from the way it's
coded just what the period might be.
--
ArarghMail705 at [drop the 'http://www.' from ->] http://www.arargh.com
BCET Basic Compiler Page: http://www.arargh.com/basic/index.html

To reply by email, remove the extra stuff from the reply address.

ArarghMail705NOS@NOT.AT.Arargh.com writes:
> Replacing the PRNG might be a good idea.  memtest86 is supposed to
> be able to test up to 2 gig of memory, so for a GOOD random test,
> the period of the PRNG needs to be larger than 2 gig.  IMO.

Shirley it would still be "good" provided the period and 2G were
relatively prime, even if the period was smaller?

(This isn't topical in either clc or afc; followups set to
comp.programming, in the absence of any better idea.  Followers-up are
of course free to ignore this suggestion.)

mlp

Um ... That sounds good.
If the source is available like you say, I *really* should look it over
and see if I can figure decent improvements to same, considering my past
background in the subject; especially in random-number generators used
to test memory.  My suspicions would be (from what you describe) that
the test in question probably takes about three times as long (or even
far more) than necessary, because of it calling the routine in random.c.

*Far* faster, and just as good a test would be a pseudo-random
shift-register test based on a good ECC algorithm, that is rolled into
the code loop instead of being a function-call.  For best "randomality",
doing the generation a prime number of times (3 to 7) gives
astonishingly good "randomness" as far as memory patterns are concerned.

There are other methods of doing even better; but (of course) they are
also much slower.

The key, of course, is it being a psuedo-random pattern that can be
recovered from the starting word; and if the test is run several times,
a different start used on each iteration.

Still, it's nice to know they probably *do* meet my basic criteria of a
good memory test.

Thanks.

--
    _____
     /  '               /
  ,-/-, __  __.  ____  /_
 (_/   / (_(_/|_/ / <_/ <_

No ... at *least* 2 gig; but not necessarily longer.
Explaining why this is so, would take considerable time.
Running it with several different starting seeds though, is a good idea
... *if* you have the time to spare.

> . . .

>Just took another look at 'random.c'  I can't tell from the way it's
>coded just what the period might be.

It's difficult to tell with most generators.
Rather like "The Halting Problem" with computers.
Sometimes you either have to *know* from the design, or just run tests
to see.

Generally (but not always) shift-register generators that use
exclusive-ors of the last two bits and at least one from the first
three, tend to be size-limited; taking the full word-size shifted.

But, not always.  I've seen a 32-bit shift that repeated in only 65K
iterations.

--
    _____
     /  '               /
  ,-/-, __  __.  ____  /_
 (_/   / (_(_/|_/ / <_/ <_

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc