int_leastN_t is all we need?

[Lauri Alanko]

I have been considering C's various integer types for a while,
and I'm having trouble seeing if they are all really justified.

In general, the most important thing when selecting an integer
type is to choose one that can represent the desired range of
values. It rarely hurts if the range is larger than desired, and
even then a judicious use of "& 0xfff..." will help. (This,
incidentally, is why I don't see why the exact-sized intN_t types
would ever be necessary.)

Classic (pre-C99) C offers a basic selection of integer types
based on the desired range: char, short and long are guaranteed
to have a minimum of 8, 16 and 32 bits, respectively. An
implementation then chooses a representation for each of these
types, based on the above range constraints and some reasonable
compromise between speed and size.

But sometimes the programmer wants to explicitly specify whether
speed or size is to be emphasized. Classic C already had one way
to do this in the form of int: int is like short except that it
may, at the implementation's discretion, be larger than short if
that makes it faster.

C99 then generalized these sorts of performance hints into the
int_fastN_t and int_leastN_t -types: specify the minimum required
range, and whether you want to emphasize speed or size, and the
implementation then gives you something appropriate for the given
specs.

But I'm beginning to wonder if the use of the int_fastN_t -types (or
even the classic short/int/long -types) is actually ever warranted.

I had a minor revelation when I realized that the size of an
integer type only really matters when the value is stored in
memory. In temporary values, local variables (whose address is
not taken) or parameters, the implementation is free to use
whatever representation it likes even for smaller types, e.g.
registers, or full words in stack.

So the only performance penalty from using int_leastN_t -types
seems to come when reading/writing a value from/to memory, when
it possibly gets possibly converted into another representation.
This can have a cost, to be sure, but I think it would be
negligible compared to the computation that is actually done with
that value. Not to mention that the saved space may actually
increase performance due to less cache pressure.

So here are my questions:

Are there any situations where the use of a int_fastN_t -type
could actually produce meaningfully faster code than would be
produced with the corresponding int_leastN_t -type, given a
reasonably sophisticated implementation?

Are there any situations where the use of an exact-sized intN_t
-type is warranted?

Comments much appreciated.

Cheers,


Lauri

 

[Eric Sosman]

I have been considering C's various integer types for a while,
and I'm having trouble seeing if they are all really justified.

You may not be alone. However, C is used on a wide variety
of platforms, including many whose characteristics are not known
to me. I imagine (without much foundation, to be sure) that some
of these types may be more important in embedded applications than
in contemporary hosted environments. YMMV.

So here are my questions:

Are there any situations where the use of a int_fastN_t -type
could actually produce meaningfully faster code than would be
produced with the corresponding int_leastN_t -type, given a
reasonably sophisticated implementation?

Sure. int_least24_t might be implemented by juggling three-
byte unaligned quantities to conserve storage, while int_fast24_t
just used a native 32-bit type without all the running around.

Are there any situations where the use of an exact-sized intN_t
-type is warranted?

Maybe not, since the behavior on overflow is no more defined
than for ints of other flavors. uintN_t types are warranted, I
think, even if only for convenience.

C99's rapidity of uptake suggests (to me, anyhow) that some of
its features' usefulness are not exactly axiomatic ... Perhaps we
should stop calling it "C99" and call it "C Vista" instead.

(Or even "C Edsel," but I'm dating myself.

 

[Lauri Alanko]

Sure. int_least24_t might be implemented by juggling three-
byte unaligned quantities to conserve storage, while int_fast24_t
just used a native 32-bit type without all the running around.

That's not exactly a full answer. The question is, in what sort of a
situation does is the cost of this byte-juggling significant compared
to the cost of the computation that is done with the value?

Now that I think of it, vector operations seem like an obvious
candidate: if you read and write a huge amount of integers in an
array, and only do a single arithmetic operation on each of them, then
the conversion cost can indeed be significant. But in "normal"
programs with more indirections and tests, I suspect that even awkward
byte-juggling wouldn't matter very much.

Maybe not, since the behavior on overflow is no more defined
than for ints of other flavors. uintN_t types are warranted, I
think, even if only for convenience.

You mean the convenience of not having to insert the occational
"& 0xfff..."? That seems like a dubious justification.

Also, whenever an intN_t -type is present, it is guaranteed to have
the same size as the corresponding int_leastN_t -type. So you could as
well just have a compile-time check to see that int_leastN_t is
actually N bits wide. That would produce much neater compile errors
than encountering an unknown type.

C99's rapidity of uptake suggests (to me, anyhow) that some of
its features' usefulness are not exactly axiomatic ...

Funny. I find C99 invaluable. C is a horrible language, but C99 makes
it at least bearable while still remaining reasonably portable.

In any case, C99 is a resounding success when compared to R6RS:

http://lists.r6rs.org/pipermail/r6rs-discuss/2007-October/003351.html

Perhaps we
should stop calling it "C99" and call it "C Vista" instead.

(Or even "C Edsel," but I'm dating myself.

Or "New C". There is no dearth of failures in history...

Cheers,


Lauri

 

[Ian Collins]

You mean the convenience of not having to insert the occational
"& 0xfff..."? That seems like a dubious justification.

The uintN_t types are commonly used in embedded and driver land, or
anywhere else where a fixed sized entity is being represented.

 

[Lauri Alanko]

The uintN_t types are commonly used in embedded and driver land, or
anywhere else where a fixed sized entity is being represented.

Yes, but in such heavily platform-dependent contexts you also need to
know the sign representation and endianness of the types, and much
else besides. Why is it useful that the _standard_ define these types
partially, when you still need to rely on implementation-specific
details and the code isn't remotely portable in any case? Why couldn't
the types required for driver I/O be provided by a platform-specific
extension instead?


Lauri

 

[Eric Sosman]

That's not exactly a full answer. The question is, in what sort of a
situation does is the cost of this byte-juggling significant compared
to the cost of the computation that is done with the value?

Huh? Compare the cost of a plausible instruction sequence like

load r0,(ra)
inc r0
store r0,(ra)
vs.
load r0,(ra)
load r1,(ra+4)
load r2,r0
and r2,0xFFFF
sll r2,8
load r3,r1
srl r3,24
or r2,r3
inc r2
load r3,r2
sll r2,24
and r1,0xFFFFFF
or r1,r2
store r1,(ra+4)
srl r2,8
and r2,0xFFFF
and r0,0xFFFF0000
or r0,r1
store r0,(ra)

Instruction sets vary, of course, and the particulars of your favorite
will surely differ from this sketch. But go ahead: Try it on your
preferred CPU, and see how many more instructions you need to increment
a three-byte integer as compared to doing the same to an aligned
four-byte integer. For extra credit, do the exercise again starting
with the address of the integer's first byte (in the sketch above I've
assumed the shifts and masks are known at compile time; for an arbitrary
pointer this wouldn't be the case).

For extra extra credit, count up how many registers each sequence
dirties, hence how many are not available to hold other variables or
partial results of extended computations, and estimate the effect on
the compiler's ability to optimize large blocks of code.

[...] C is a horrible language, [...]

Ah. Hence your enthusiasm for discussing it. Roger and out.

 

[Ian Collins]

Yes, but in such heavily platform-dependent contexts you also need to
know the sign representation and endianness of the types, and much
else besides.

Endianness yes, but what else for an unsigned type?

Why is it useful that the _standard_ define these types
partially, when you still need to rely on implementation-specific
details and the code isn't remotely portable in any case?

What else could the standard mandate? As for portability, all the
embedded code I write has to work just as well on my Unix/Linux desktop
as is does on the 8-32bit targets.

Why couldn't
the types required for driver I/O be provided by a platform-specific
extension instead?

If nothing else to give a standard naming convention for fixed sized types.

 

[Richard Damon]

I have been considering C's various integer types for a while,
and I'm having trouble seeing if they are all really justified.

In general, the most important thing when selecting an integer
type is to choose one that can represent the desired range of
values. It rarely hurts if the range is larger than desired, and
even then a judicious use of "& 0xfff..." will help. (This,
incidentally, is why I don't see why the exact-sized intN_t types
would ever be necessary.)

Classic (pre-C99) C offers a basic selection of integer types
based on the desired range: char, short and long are guaranteed
to have a minimum of 8, 16 and 32 bits, respectively. An
implementation then chooses a representation for each of these
types, based on the above range constraints and some reasonable
compromise between speed and size.

But sometimes the programmer wants to explicitly specify whether
speed or size is to be emphasized. Classic C already had one way
to do this in the form of int: int is like short except that it
may, at the implementation's discretion, be larger than short if
that makes it faster.

C99 then generalized these sorts of performance hints into the
int_fastN_t and int_leastN_t -types: specify the minimum required
range, and whether you want to emphasize speed or size, and the
implementation then gives you something appropriate for the given
specs.

But I'm beginning to wonder if the use of the int_fastN_t -types (or
even the classic short/int/long -types) is actually ever warranted.

I had a minor revelation when I realized that the size of an
integer type only really matters when the value is stored in
memory. In temporary values, local variables (whose address is
not taken) or parameters, the implementation is free to use
whatever representation it likes even for smaller types, e.g.
registers, or full words in stack.

So the only performance penalty from using int_leastN_t -types
seems to come when reading/writing a value from/to memory, when
it possibly gets possibly converted into another representation.
This can have a cost, to be sure, but I think it would be
negligible compared to the computation that is actually done with
that value. Not to mention that the saved space may actually
increase performance due to less cache pressure.

Machines with word access may be subject to significant memory access
penalty, especially for writes (where it may need to actually read the
full word and mask and insert the value), if the leastN_t type is
smaller than a word.

So here are my questions:

Are there any situations where the use of a int_fastN_t -type
could actually produce meaningfully faster code than would be
produced with the corresponding int_leastN_t -type, given a
reasonably sophisticated implementation?

Are there any situations where the use of an exact-sized intN_t
-type is warranted?

Note that the presence of a intN_t does tell you more than it has N
bits, its presence also insures that the encoding is 2's complement, and
that there are no padding bits. Thus much bit fiddling that is
ill-defined for a plain int, is better defined for int16_t and uint16_t.

Comments much appreciated.

Cheers,


Lauri

Yes, for most code the exact type of integer won't make a significant
difference. There are a few cases where it does, and that is when you
need the extra types. I do sometimes wish that intN_t was actually want
we now have in int_leastN_t since, as you note, this is probably the
more common need, and then what is currently intN_t was named
int_exactN_t, making the use of the exact type more obvious, as the
times when you really do need them are sort of special and worth makeing
a note of. Alternatively, we could have int_leastN_t, int_fastN_t,
int_exactN_t all defined, and then intN_t could be defined as a general
purpose N bit integer, normally int_leastN_t unless that imposed a
"significant" overhead (like word addressed machines) in which case it
could be int_fastN_t.

 

[Lauri Alanko]

Huh? Compare the cost of a plausible instruction sequence like

load r0,(ra)
inc r0
store r0,(ra)

Right. My question was where these kinds of operations would be
prevalent enough to affect the performance of the entire program. But
I can think of a couple now: population count, heavy reference
counting, etc.

vs.

[big chunk of code]

The cost of the conversion was not under question, but thanks for the
concrete example. Presumably memory accesses are here considered so
expensive that reading and writing a byte at a time would be slower,
even with the masking and registers required by your solution?

srl r2,8
and r2,0xFFFF

Presumably these two should be just "srl r3,8"?

Instruction sets vary, of course, and the particulars of your favorite
will surely differ from this sketch. But go ahead: Try it on your
preferred CPU, and see how many more instructions you need to increment
a three-byte integer as compared to doing the same to an aligned
four-byte integer.

Well, simple operations like the increment can be implemented
specially:

addb $1, 2(%rdi)
jnc .Lend
addb $1, 1(%rdi)
jnc .Lend
incb (%rdi)
..Lend:

Pathological cases excepted, this should be as fast as a single byte
addition in memory, since usually the carry is not set and this is
predicted correctly.

[...] C is a horrible language, [...]

Ah. Hence your enthusiasm for discussing it. Roger and out.

Well, mostly all programming languages are horrible. That doesn't
prevent me from discussing them and using them, but also not from
dreaming of better alternatives. C is at least horrible only in the
relatively benign way of making everything utterly tedious. In the
sorts of contexts where the use of C is warranted, the only practical
alternative is C++. Choosing the lesser evil is a tough call.

Cheers,


Lauri

 

[Lauri Alanko]

The int_fast types have some justification for use as working
variables, in that I might want to store data in int_least8_t's and
then work on them in int_fast8_t's. Consider a compiler optimizing a
loop. Unless it can determine the loop bounds, it cannot expand the
type of the loop variable as it may have to simulate wraparound
(particularly for unsigned types).

Yes, that's a good example, although I'd guess that plain int would be
good enough everywhere except on eight-bit platforms.

But this actually demonstrates a problem with the integer types: the
range of a type is unknown, but fixed. if I have:

uint_least8_t x = 255;
x++;

Then I cannot know whether x will have the value of 0 or 256. But I am
guaranteed that incrementing a uint_least8_t value of 255 will
consistently either _always_ produce 0, or_always_ produce 256.

This kind of a guarantee doesn't seem very useful to the programmer,
yet that is precisely what prevents the efficient use of uint_least8_t
as a loop variable. The notion of "least size" pervades even local
variables, where "size" is often a meaningless concept since the
values are stored in registers.

What kinds of portable programs (that don't use <limits.h>) would
alter their meaning if the range of non-exact-sized integer types were
allowed to vary?


Lauri

 

[James Kuyper]

I have been considering C's various integer types for a while,
and I'm having trouble seeing if they are all really justified.

In general, the most important thing when selecting an integer
type is to choose one that can represent the desired range of
values. It rarely hurts if the range is larger than desired, and
even then a judicious use of "& 0xfff..." will help. (This,
incidentally, is why I don't see why the exact-sized intN_t types
would ever be necessary.)

When your code needs to implement an interface specification that stores
integers in exactly 16 consecutive bits, int_least16_t isn't necessarily
going to work. Nor is int_fast16_t.

....

So the only performance penalty from using int_leastN_t -types
seems to come when reading/writing a value from/to memory, when
it possibly gets possibly converted into another representation.
This can have a cost, to be sure, but I think it would be
negligible compared to the computation that is actually done with
that value.

That's possible, but not necessarily true. On platforms where it is
true, you can reasonably expect that implementations of C99 that care
about meeting their customer's needs will define int_fastN_t to be the
same as int_leastN_t. It's platforms where that's not true that the
distinction matters.

... Not to mention that the saved space may actually
increase performance due to less cache pressure.

I would hope that the decision made by the implementor as to which type
to designate as "fast" is influenced by all of the relevant speed
issues, included cache pressure.

So here are my questions:

Are there any situations where the use of a int_fastN_t -type
could actually produce meaningfully faster code than would be
produced with the corresponding int_leastN_t -type, given a
reasonably sophisticated implementation?

I'm not familiar with the details of a sufficiently wide variety of
platforms to be able to cite a particular one where this would be true,
but I would expect it to be commonplace. Some platforms have multiple
different register sizes, and specialized instructions for reading data
into and out of those registers. However, other platforms have only one
or two register sizes; for N smaller than the smallest register size,
int_leastN_t must be implemented by mask and shift operations that make
it inherently slower than int_fastN_t, which uses the smallest register
size.

Are there any situations where the use of an exact-sized intN_t
-type is warranted?

Certainly. Parsing external data formats specified in terms of precise
bit counts.

 

[ImpalerCore]

I have been considering C's various integer types for a while,
and I'm having trouble seeing if they are all really justified.

In general, the most important thing when selecting an integer
type is to choose one that can represent the desired range of
values. It rarely hurts if the range is larger than desired, and
even then a judicious use of "& 0xfff..." will help. (This,
incidentally, is why I don't see why the exact-sized intN_t types
would ever be necessary.)

Classic (pre-C99) C offers a basic selection of integer types
based on the desired range: char, short and long are guaranteed
to have a minimum of 8, 16 and 32 bits, respectively. An
implementation then chooses a representation for each of these
types, based on the above range constraints and some reasonable
compromise between speed and size.

But sometimes the programmer wants to explicitly specify whether
speed or size is to be emphasized. Classic C already had one way
to do this in the form of int: int is like short except that it
may, at the implementation's discretion, be larger than short if
that makes it faster.

C99 then generalized these sorts of performance hints into the
int_fastN_t and int_leastN_t -types: specify the minimum required
range, and whether you want to emphasize speed or size, and the
implementation then gives you something appropriate for the given
specs.

Unfortunately, the teaching literature has neglected discussion of the
majority of these types, which reinforces the perception that they are
mostly academic except in rare circumstances. They are often
interpreted as token types in the work environment I am in, and I've
never personally seen or used them.

But I'm beginning to wonder if the use of the int_fastN_t -types (or
even the classic short/int/long -types) is actually ever warranted.

I had a minor revelation when I realized that the size of an
integer type only really matters when the value is stored in
memory. In temporary values, local variables (whose address is
not taken) or parameters, the implementation is free to use
whatever representation it likes even for smaller types, e.g.
registers, or full words in stack.

So the only performance penalty from using int_leastN_t -types
seems to come when reading/writing a value from/to memory, when
it possibly gets possibly converted into another representation.
This can have a cost, to be sure, but I think it would be
negligible compared to the computation that is actually done with
that value. Not to mention that the saved space may actually
increase performance due to less cache pressure.

So here are my questions:

Are there any situations where the use of a int_fastN_t -type
could actually produce meaningfully faster code than would be
produced with the corresponding int_leastN_t -type, given a
reasonably sophisticated implementation?

Possibly, but I have no experience with such an environment.

Are there any situations where the use of an exact-sized intN_t
-type is warranted?

The area I use intN_t and uintN_t are in structure definitions.
Sometimes they are used to pack integer information into a smaller
chunk. Consider a simple gregorian year-month-day triple.

struct greg_date
{
int year;
int month;
int day;
};

vs

struct greg_date
{
int16_t year;
int8_t month;
int8_t day;
};

The decision of which structure definition to use depends on how one
wants to declare the function interface that uses them. If one
prefers to use an API that passes greg_date structs by value, then
packing the members into a 32-bit struct can be beneficial compared to
passing the 'int' version. You can assign '{ -1, -1, -1 }' to
represent an invalid date, maybe something like '{ INT16_MAX,
INT8_MAX, INT8_MAX }' to represent a positive infinity concept, and
one can define an API that can pass and return dates by value.

It's possible that the performance of an API that uses the 'int'
version of greg_date with pass-by-value semantics may be faster that
the packed struct with int8_t types. Unfortunately I do not have the
time to experiment and measure performance differences between using
the 'int' version of greg_date with either pass-by-value or pass-by-
reference semantics compared to the packed version using intN_t types
and pass-by-value.

The point is that it can be appealing to use data types conformed to
the maximum bit requirements of the elements they represent. This is
particularly true in my work with avionics bus-traffic that have
protocols with hard-defined bit-requirements on integer widths in
their specification.

Comments much appreciated.

Best regards,
John D.

 

[ImpalerCore]

Yes, that's a good example, although I'd guess that plain int would be
good enough everywhere except on eight-bit platforms.

But this actually demonstrates a problem with the integer types: the
range of a type is unknown, but fixed. if I have:

uint_least8_t x = 255;
x++;

Then I cannot know whether x will have the value of 0 or 256. But I am
guaranteed that incrementing a uint_least8_t value of 255 will
consistently either _always_ produce 0, or_always_ produce 256.

Sure you can. Isn't that what UINT_LEAST8_MAX is for?

uint_least8_t x = 255;
x++;

if ( UINT_LEAST8_MAX > 255 )
{
if ( x == 256 ) {
printf( "expected\n" );
} else {
printf( "not expected\n" );
}
}
else if ( UINT_LEAST8_MAX == 255 )
{
if ( x == 0 ) {
printf( "expected\n" );
} else {
printf( "not expected\n" );
}
}
else {
printf( "not expected\n" );
}

[snip]