removing a loop cause it to go at half the speed?

[Rod Pemberton]

I was doing a simple test of the speed of a "maths" operation and when I
tested it I found that removing the loop that initialises the data array
for the operation caused the whole program to spend twice the time to
complete. If the loop is included it takes about 7.48 seconds to
complete, but when removed it takes about 11.48 seconds.

Does anybody have a suggestion as to why this is so and whether I can
trust the results of the code as it is below?

[...]
int total = 0;
int count = 65500;
signed int data[count];

<OT purpose=stop_wild_speculation>

It is because of the virtual memory system. When you initialize the
array beforehand, it forces the virtual memory system to materialize
memory for the pages appearing in the array. When you do not, this
materialization happens in the timed loop, and then of course it's
slower.

You should be able to confirm this by touching some but not all of the
pages beforehand and observing the resulting timings. Hint: page size
for i386 family processors is 4096 bytes. And you won't see it at all
using DJGPP, which is DOS-based and doesn't have a virtual memory
system.

FYI, DJGPP does use a virtual memory system by default. The primary DPMI
host for DJGPP uses hardware paging and has virtual memory support: CWSDPMI.
Also, when an DJGPP application is running in a Windows dosbox, it uses the
DPMI host and virtual memory of the OS. You can, of course, use other
non-paging DPMI hosts such as PMODEDJ (aka, PMODETSR). OpenWatcom, on the
other hand, supports many DPMI hosts and/or DOS extenders. The ones I'm
aware of are non-paging and have no virtual memory support.

</OT>

Rod Pemberton

 

[Keith Thompson]

A final note: if `data[]` is uninitialised, `total += data[c]` might
very easily overflow, if the pseudo-random values left lying around
inside [if that's what happened] were big enough. In which case, you
have another cause of undefined behaviour ...

I forgot to comment this.

The undefined behaviour here is if an overflow occurs and there is no
mechanism to handle that overflow, what happens with the OF bit then?
In my program that was of no concern, so the "undefined behaviour" is
irrelevant.

What the heck is an "OF" bit? If it's a condition code, it's
something specific to your system. We're talking about the C
programming language, not about whatever single specific
implementation of it you happen to be using.

If a signed integer arithmetic operation overflows, the C standard
says the behavior is undefined. That doesn't mean that it traps, it
means that the language standard does define the behavior. It can
wrap around, it can saturate, it can abort your program, it can yield
42, it can make demons fly out of your nose, or it can behave in some
manner that depends on the phase of the moon.

This program:

#include <limits.h>
int main(void)
{
int i = INT_MAX;
i = i + 1;
return 0;
}

exhibits undefined behavior. That is not a statement about what it
might do on your implementation, and any demonstration of what it
happens to do on your implementation does not affect the fact that it
invokes undefined behavior. Until and unless you understand that, you
don't really understand C.

 

[Keith Thompson]

That does not contradict what I am saying. These statements only
define what undefined behaviour is, in context of the standard and the
language, nothing more. It does not say using such a value must demand
undefined behaviour.

Undefined behavior is behavior that is not defined. It's entirely
consistent with doing exactly what you expected (whatever that might
be).

But there is an interesting point buried in all this.

The C99 standard's definition of undefined behavior does not mention
"indeterminately-valued objects".

For relative simplicity, I'm going to use unsigned short rather than
signed int.

int main(void)
{
unsigned short x; /* the value of x is indeterminate, C99 6.2.4p5 */
unsigned short y;
y = x; /* undefined behavior? */
return 0;
}

If unsigned short happens to have a trap representation, it's possible
that x has that trap representation; if so, the assignment definitely
produces undefined behavior.

But what if unsigned short has no trap representations and no padding
bits? It's sometimes possible to prove this:

#include <limits.h>
#include <stdio.h>
int main(void)
{
unsigned short x;
unsigned short y;
if ( CHAR_BIT == 8 &&
sizeof(unsigned short) == 2 &&
USHRT_MAX == 65535 )
{
printf("unsigned short has no padding bits\n");
y = x;
}
else {
printf("unsigned short may have padding bits\n");
}
return 0;
}

The test is not exhaustive; if it fails, unsigned short may or may not
have padding bits.

But if the test succeeds, and the program prints "unsigned short has
no padding bits", we *know* that there are no possible trap
representations for unsigned short (since the range of value uses all
the bits). Then the assignment "y = x;" does not, I believe, invoke
undefined behavior (in C99; it might in C90).

Some definitions:

undefined behavior

behavior, upon use of a nonportable or erroneous program construct or
of erroneous data, for which this International Standard imposes
no requirements

indeterminate value

either an unspecified value or a trap representation

unspecified value

valid value of the relevant type where this International Standard
imposes no requirements on which value is chosen in any instance
NOTE An unspecified value cannot be a trap representation.

And C99 6.2.6.1p5:

Certain object representations need not represent a value of the
object type. If the stored value of an object has such a
representation and is read by an lvalue expression that does not
have character type, the behavior is undefined. If such a
representation is produced by a side effect that modifies all or
any part of the object by an lvalue expression that does not have
character type, the behavior is undefined. Such a representation
is called a _trap representation_.

So, if my analysis is correct, it's safe to use the value of an
uninitialized object if the object's type has no trap representations.
But it's not safe (or at least not portable) to assume that a type has
no trap representations unless it's unsigned char. (You can prove, in
some cases, that an integer type has no trap representations, but it's
not likely to be worth the effort.)

In any case, using the value of an uninitialized object almost
certainly indicates a bug in your program, whether the behavior is
actually undefined or not.

 

[Chris Torek]

Can you then explain to me how it is that you think the behaviour of my
code can not be predicted?

Well, if you port it to a Burroughs A-machine, and the bit pattern
in the "int" array is a trapping floating-point value[%], the first
time you try to use the value you will get a trap and your program
will terminate.

Of course, this is "predicting" the behavior of your code, but I bet
this behavior does not match what *you* expected.

[% The A-series machines use floating-point for *everything*,
including integers. They just make sure that the value stored
in the floating-point variable is in fact an integer, by trapping
overflows and underflows, and truncating off the digits beyond
the decimal point in other cases.]

... I tested it by replacing the statement in
the loop with a guaranteed integer statement. So the undefined behaviour
argument has exploded in its own face. See code below.

The point of undefined behavior is twofold; see
<http://web.torek.net/torek/c/index.html>. Stepping outside
the C standard is not *bad* (but not *good* either). It is
just "undefined". If your implementation goes on to define the
behavior, great. But you are getting "implementation behavior",
not "C behavior". Just be aware of exactly what you are depending
on, and when it might (or definitely will not) stop working.

 

[Mark McIntyre]

sorry but using an uninitialised array does not cause undefined
behaviour.

Yes, it does. Quoting from the ISO Standard:
J.2 Undefined behavior
1 The behavior is undefined in the following circumstances:
- The value of an object with automatic storage duration is used while
it is indeterminate (6.2.4, 6.7.8, 6.8).

It only means the values of the array are not preset.

This is known as being "indeterminate"

An
array is just a sequence of memory positions, which have been used
previously by some other part of the program or the system, hence the
value it has is what was there before I allocated it.

And that value may be a trap representation, or not a number at all.
However its totally irrelevant since you are expressly forbidden from
doing this by hte ISO Standard.

If I had used the value in some expression,

You did - you read them.
Mark McIntyre

 

[Mark McIntyre]

Wrong, it does not cause undefined behaviour because the values used
does not require a specific set of values or a value range.

This is utterly irrelevant. The ISO standard expressly forbids you to
read uninitialised memory.

its just a
set of ints with a 32 bit value, nothing special about that. Its the
interpretation that matters not the value itself. And since my program
does not need to interpret the value there is no undefined behaviour.

It does, since it reads the value.

The reason it is stated that it causes undefined behaviour is because
the programmer has to decide what behaviour it should have in those
cases.

No!!! The programmer has no role, undefined behaviour is behaviour
that the ISO Standard says is undefined.
Mark McIntyre

 

[Richard Heathfield]

Rod Pemberton said:

Actually, I think Tom's interpretation for his implentation is correct.

His implementation is neither here nor there. The behaviour of the code is
undefined as far as the C language is concerned.

 

[Mark McIntyre]

Can you then explain to me how it is that you think the behaviour of my
code can not be predicted?

One of the values may be a trap representation, upon reading which
your operating system is obliged to abort the programme. Since you
don't know whats in the memory, you can't predict your programme's
behaviour and it will randomly crash in an unexplicable fashion.

I guarantee you that it will do it when you are trying to demonstrate
to a customer.

Are you actually telling me that just because
the array is uninitialised my program will fail/have undefined
behaviour, independent of how I use the array? lol

Yes. The only way you can use the array is by initialising it.

Before you answer, you should know that the reason for the problem is
that the rand() statement causes the compiler to output float operations
instead of integer operations.

Whats this got to do with the price of fish? Just because you found
another bug, doesn't mean this one goes away.

"Officer, I hear you telling me its illegal to run a red light, but
now I'm keeping to the speed limit, your argument abour red lights has
exploded in its face. So there"


Mark McIntyre

 

[Mark McIntyre]

I think there is no point continuing the discussion.

There certainly isn't. You evidently aren't prepared to learn even
from some of the most experienced C programmers around.

But if you consider the pragmatics of it, in addition to the
literal meaning, which you should when you are programming, then you are
wrong.

No, he's still right, we're still right.

However you won't see that because you're totally convinced that your
own tiny corner of the galaxy is the only inhabitable world and life
*cannot* exist elsewhere.
Mark McIntyre

 

[Mark McIntyre]

No I don't think that. But undefined behaviour in my book is behaviour
not defined, if you tell the computer to do something then its defined.

Bullshit. Lets say you tell the computer to write to byte data[c] on
your hard disk. Is that a defined operation? No.

The compiler controls the undefined behaviour so, therefore its not
undefined anymore, portability or not.

Absolute caeculum tauri.

Lets just agree that we to some extent disagree,

The only thing we can agree on is that you are too arrogant to be
taught, it seems.
Mark McIntyre

 

[Mark McIntyre]

The undefined behaviour here is if an overflow occurs and there is no
mechanism to handle that overflow, what happens with the OF bit then?

what OF bit? Who says there is one?

In my program that was of no concern, so the "undefined behaviour" is
irrelevant.

So if the setting of the OF bit causes your processor to abort your
programme, thats of no concern? You really /are/ a chump.
Mark McIntyre

 

[Mark McIntyre]

Actually, I think Tom's interpretation for his implentation is correct.
Take another look:


The construct and data aren't errnoneous for his implementation. But, may
be elsewhere.

The words "for your implementation" do not appear in your quote.

They aren't indeterminately-valued for his implementation.

Again, irrelevant.

Therefore, valid for his implementation. Maybe UB elsewhere.

Doesn't work like that. UB is what is not defined in the standard, not
what is not defined for a specific implementation.
Mark McIntyre

 

[Keith Thompson]

Yes, it does. Quoting from the ISO Standard:
J.2 Undefined behavior
1 The behavior is undefined in the following circumstances:
- The value of an object with automatic storage duration is used while
it is indeterminate (6.2.4, 6.7.8, 6.8).

Now this is interesting. Appendix J is informative, not normative,
so the fact that accessing an indeterminate object invokes undefined
behavior should be stated normatively elsewhere -- but I can't find it.

Sections 6.2.4 ("Storage duration of objects"), 6.7.8,
("Initialization"), and 6.8 ("Statements and blocks") all say that
says that the initial value of an automatic object is indeterminate,
but they don't say anything about attempting to access that value.

If the statement in J.2 is to be taken literally, then in this
program:

int main(void)
{
unsigned char x;
unsigned char y;
y = x;
return 0;
}

the assignment invokes undefined behavior. Clearly, the value of x is
indeterminate. Since an indeterminate value is either an unspecified
value or a trap representation, and since unsigned char has no trap
representations, it must be an unspecified value. By definition, an
"unspecified value" is a "valid value of the relevant type".

What normative text in the standard says that this is undefined
behavior? (There would have to be an explicit statement; the behavior
of the assignment is specified in 6.5.16.1.)

 

[David Holland]

> > <OT purpose=stop_wild_speculation>
> > It is because of the virtual memory system. When you initialize the
> > array beforehand, it forces the virtual memory system to materialize
> > memory for the pages appearing in the array. When you do not, this
> > materialization happens in the timed loop, and then of course it's
> > slower.
> > [...]

>
> FYI, DJGPP does use a virtual memory system by default. [...]

Huh. Neat. Does it defer materialization of untouched pages until
they're used? I imagine it probably does.

Anyhow, I withdraw this explanation, now that I've read the code more
carefully. Materializing 64 pages is a negligible cost compared to 3
billion or so loop cycles, and I should have noticed this before
opening my mouth. (Likewise, initial cache warmth is irrelevant
because the loop touches the array 50,000 times, of which 49,999 occur
with warm cache either way.)

On my platform I can get a 20% speed improvement by inserting twelve
nop instructions. I'm going to assume the OP's results are purely a
matter of whether the loop code ends up cache-aligned or not.

 

[Chris Torek]

The point of undefined behavior is twofold; see
<http://web.torek.net/torek/c/index.html>. ...

Oops, I meant to point directly to
<http://web.torek.net/torek/c/compiler.html> (specifically, the
last section on "debugging and undefined behavior").

 

[Dik T. Winter]

> > . . .
> > A final note: if `data[]` is uninitialised, `total += data[c]` might
> > very easily overflow . . .

>
> At last, someone has picked up on what I posted very early in
> this thread. Overflow interrupts need to be serviced, and this
> consumes extra TIME which, depending on the implementation,
> may be charged to the process in which they occurred.

It is pretty unlikely that the processor traps on integer overflow. It has
been a long time ago that I actually did see one.

 

[Dik T. Winter]

> Before you answer, you should know that the reason for the problem is
> that the rand() statement causes the compiler to output float operations
> instead of integer operations.

If it is a sane compiler it will only use float operations in the
initialisation part (which you do not time). If it generates float
instructions for the statement;
total += data[c];
you better throw away the compiler because the answer will be incorrect.
Moreover, those float instructions would greatly increase the execution
time. I see the same timing enigma, and in my case it looks as follows
(with five tries):
w/loop w/o loop
#1 12.235 10.100
#2 12.231 8.735
#3 12.232 10.571
#4 12.234 12.232
#5 12.235 10.322
(using float operations it increases to 53.109 seconds...)

But I now see a difference in the compilation. With the initialisation
the timed loop is (under -O3 and gcc 4.0.2) compiled in 10 instructions,
without the initialisation there are only 8 instructions. In the first
case the loop counters (%ecx and %edx) are initialised at 0, incremented
and the result is compared to the final value. In the second case they
are initialised to the final value, decremented (and the compare is
implicit). Moreover, I do not know whether the instructions time the same.
And I have no idea where that difference comes from. Seems to me more
something for the gcc oriented newsgroups. But look at the instructions
following the first call to gettimeofday.

 

[ena8t8si]

Now this is interesting. Appendix J is informative, not normative,
so the fact that accessing an indeterminate object invokes undefined
behavior should be stated normatively elsewhere -- but I can't find it.

Sections 6.2.4 ("Storage duration of objects"), 6.7.8,
("Initialization"), and 6.8 ("Statements and blocks") all say that
says that the initial value of an automatic object is indeterminate,
but they don't say anything about attempting to access that value.

If the statement in J.2 is to be taken literally, then in this
program:

int main(void)
{
unsigned char x;
unsigned char y;
y = x;
return 0;
}

the assignment invokes undefined behavior. Clearly, the value of x is
indeterminate. Since an indeterminate value is either an unspecified
value or a trap representation, and since unsigned char has no trap
representations, it must be an unspecified value. By definition, an
"unspecified value" is a "valid value of the relevant type".

What normative text in the standard says that this is undefined
behavior? (There would have to be an explicit statement; the behavior
of the assignment is specified in 6.5.16.1.)

Appendix J just has it wrong in this case (probably for historical
reasons). Accessing an uninitialized local is undefined behavior
only if the indeterminate value can be a trap representation.

 

[Richard Bos]

Actually, I think Tom's interpretation for his implentation is correct.

Possibly (though - how are we to know without having access to the
machine?) but for comp.lang.c it isn't.

Therefore, not undefined for his implementation, but may be UB elsewhere.

His code exhibited undefined behaviour in C. It may not exhibit UB in
Zog-C-for-the-Orange-Q30-series-with-Q33-specific-extensions, but that
is not important in this newsgroup.

The key is that his code is correct for his environment.

The key is that C is on topic in comp.lang.c, and his environment is
not.

Richard

 

[arnold]

However you won't see that because you're totally convinced that your
own tiny corner of the galaxy is the only inhabitable world and life
*cannot* exist elsewhere.

Did you ever hear of conviction? I think you are being a bit harsh here.
If he has been programming for a while with the belief that what he is
saying is true, then to him that is true. And thats the position he will
defend in the discussion. You cant blame him for that, except for
perhaps not picking up on what you guys are trying to say faster or
being a bit stubborn. It seems to me that he during the discussion,
slowly realised that he had misunderstood it, but still wasnt sure. That
I understand, because you guys dont allways make it easy to understand
what it is you are actually saying. (I just experienced that earlier
today on this group, with the "i++ * i++" discussion), so you could
perhaps look a bit at why the person do not get what you are saying and
perhaps make an explanation more suited to the understanding of the person.

arnold