Optimizing C

[Keith Thompson]

Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
but KT pointed out that maximum unsigned int might still be 32767
due to padding bits.

Not quite. The standard guarantees that UINT_MAX is at least 65535.

 

[Richard G. Riley]

Not quite. The standard guarantees that UINT_MAX is at least 65535.

whoops, sorry : brain off there.

 

[Richard Heathfield]

Richard G. Riley said:

whoops, sorry : brain off there.

It seems you have discovered the ability to apologise for your mistakes. I
suggest you develop that skill further.

 

[Dag-Erling =?iso-8859-1?Q?Sm=F8rgrav?=]

But any techniques for doing the standard bit fiddles without
occurring extra unnecessary cpu bandwidth would be nice. By standard
bit fiddles I mean : shift & rotate, anding, oring, shift til bit
found etc. The operations will be occurring on sequences of
words and the smallest word will be the standard CPU word size (32
bits). By sequences of words : I might, for example, be locating
the first non zero bit from the left in sequence of 64 words.

Slightly off-topic, POSIX has ffs(), which returns the index of the
first non-zero bit in an int. Compare each int with zero, in
sequence, and sic ffs() at the first non-zero one. Presumably, your
implementation will translate the call to ffs() into the most
efficient instruction sequence for your platform; on some systems, it
maps to a single CPU instruction.

As for regular "shift & rotate, anding, oring", if your implementation
does not translate the equivalent C operators into efficient machine
code, you'd better find another one that does.

DES

 

[Michael Mair]

It's guaranteed that, for any integer type, all-bits-zero is a
representation of the value 0. (Neither the C90 nor the C99 standard
says this, but n1124 does; this change was made in TC2 in response to
DR #263. I've never heard of an implementation that doesn't have this
property anyway, and I'd be comfortable depending on it.) For
one's-complement and sign-magnitude representations, there are two
distinct representations of zero (+0 and -0), but you can avoid that
by using an unsigned type. But unsigned types *can* have padding
bits, so even if buf==0, you might still have missed a 1 bit.

Could you please explain this? If I have calculated (or even knw..) that the
underlying word size is 32 bit and I use an unsigned int to represent
this in C, then how do padding bits make any difference? Isnt the
variable guarenteed to go from 0 to 2^32-1?

No, it isn't. The guaranteed range of unsigned int is 0 to 32768.
But, for example, an implementation could legally have:
CHAR_BIT == 8
sizeof(unsigned int) == 4
INT_MAX == 32767
An unsigned int then has 32 bits: 16 value bits and 16 padding bits.

For details, see section 6.2.6.2 of the C99 standard.

Wow. That would break a lot of code. Assumimg some situation like
that, is their a constant "MAX BITS FOR ULONG" or "MAX WORD SIZE IN BITS"? e.g
to get a platform independant assurance of the number of bits one can
use in a single HW word? Having said that, in my sample code in the
initial reply to Eric, I would only need to recalculate my "start
mask" from 0x80000000 to "whatever" when I calculate "usable bits per
HW word" in program init. Since the overhead of doing that calc is
almost less than zero compared to cother computation, I could do that.

If you intend "fast and portable", then consider doing the
following:

That is the best. My initial requirements are slightly smaller : fast
on x86 as I originally specified and "works elsewhere when it might be
needed the day hell freezes over" .-; Having said that, I have taken
Thomsons comments to heart about word padding for some reason : I see
no real overhead (when keeping everything in C) to ensure platform
compatability in the C level. It will be, I admit, the first code I
ever wrote where a machine word can potentially hold less values than
its size indicates : unless of course I do come across an unforseen
performance hit in which case bye bye good practice.

Build a "guaranteedly portable" version of your intended to be fast
stuff.
Then start documenting your assumptions for your "fast header": Add a
source file which is not linked with the rest of the code but fails
compilation (during preprocessing or actual compiling) if one of
these assumptions is violated.
Say you have determined that sizeof(int)*CHAR_BIT is 32 Bits, then
0xFFFFFFFF - INT_MAX should be 0. In other words, neither
char inttestl[0x7FFFFFFF - (long)INT_MAX + 1L];

Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
but KT pointed out that maximum unsigned int might still be 32767
due to padding bits..I asked for an easy way to determine "usable bit
size" but got no reply so I guess its just some code to do at
init. Not too far up on the priority list I must admit though.

Apart from the one excess "unsigned": My point here is that
you well may assume no padding, 2s complement and everything
that makes life easy as long as you can guarantee that your
code will not compile if these assumptions are invalid.
Writing code to cater for every possible situation the standard
permits may be a noble goal to aim at but will definitely not
_help_ you with the "fast" part (*).
Thus the portable version to have in your hand for testing the
fast version and for having fallback code. If you program it at
the same time as the rest, you do not waste much time -- but
it will save you much time if you need it (and don't have to
remember what all of this was supposed to do); and maybe even
earlier, when testing the fast version against the bulletproof
version...
____
(*) It is possible that it won't hinder you either.


Cheers
Michael