Asp Forum - int_leastN_t is all we need?

Lauri Alanko

9/8/2011 2:12:00 AM

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

16 Answers

Eric Sosman

9/8/2011 3:11:00 AM

On 9/7/2011 10:12 PM, Lauri Alanko wrote:
> 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. ;)

--
Eric Sosman
esosman@ieee-dot-org.invalid

Lauri Alanko

9/8/2011 4:04:00 AM

In article <j49br0$f52$1@dont-email.me>,
Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
> On 9/7/2011 10:12 PM, Lauri Alanko wrote:
> > 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.

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.

> > 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.

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/0...

> 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

9/8/2011 4:12:00 AM

On 09/ 8/11 04:03 PM, Lauri Alanko wrote:
> Eric Sosman<esosman@ieee-dot-org.invalid> wrote:
>> On 9/7/2011 10:12 PM, Lauri Alanko wrote:
>
>>> 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.
>
> 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.

--
Ian Collins

Lauri Alanko

9/8/2011 4:22:00 AM

In article <9cqtl5Fke5U1@mid.individual.net>,
Ian Collins <ian-news@hotmail.com> wrote:
> 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

9/8/2011 4:28:00 AM

On 9/8/2011 12:03 AM, Lauri Alanko wrote:
> In article<j49br0$f52$1@dont-email.me>,
> Eric Sosman<esosman@ieee-dot-org.invalid> wrote:
>> On 9/7/2011 10:12 PM, Lauri Alanko wrote:
>>> 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.
>
> 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.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Ian Collins

9/8/2011 4:37:00 AM

On 09/ 8/11 04:22 PM, Lauri Alanko wrote:
> In article<9cqtl5Fke5U1@mid.individual.net>,
> Ian Collins<ian-news@hotmail.com> wrote:
>> 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.

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.

--
Ian Collins

Richard Damon

9/8/2011 5:33:00 AM

On 9/7/11 10:12 PM, Lauri Alanko wrote:
> 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.

robertwessel2@yahoo.com

9/8/2011 7:17:00 AM

On Thu, 8 Sep 2011 02:12:14 +0000 (UTC), Lauri Alanko <la@iki.fi>
wrote:

>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.

I'd comment that given the utterly trivial cost to support those types
(a few typedefs and macros in stdint.h and inttypes.h, and literally
nothing else), not all that much justification is needed. And being
able to select the smallest and fastest types of a certain minimum
size makes a certain amount of sense.

But in general all of these should be used sparingly, although the
justification for the int_least types is easiest.

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). I might know that the expansion is
safe, and can communicate that by using an int_fast type for the loop
variable. For example:

void f(uint_least8_t a, uint_least8_t b)
{
uint_least8_t q;

for(q=a; q!=b; q++)
...
}

in that case, the compiler is obligated to preserve the wrap-around
semantics of unsigneds, unless it can prove that a will be less than
or equal to b on input. OTOH, if *I* know that, I can effectively
tell the compiler by declaring q as a uint_fast8_t. And then, on the
assumption that the selected type is actually faster (consider the
overhead on byte operations on the original Alpha, for example), there
may be an advantage.

And yes, the conversions can be non-trivial, so they may be justified
for storage as well.

Lauri Alanko

9/8/2011 11:24:00 AM

In article <j49gab$3hi$1@dont-email.me>,
Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
> On 9/8/2011 12:03 AM, Lauri Alanko wrote:
> > 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)

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

9/8/2011 11:53:00 AM

In article <8spg671kp4q4ihkto9ucbafr23dstp2ond@4ax.com>,
Robert Wessel <robertwessel2@yahoo.com> wrote:
> 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

comp.lang.c

int_leastN_t is all we need?

Lauri Alanko

Eric Sosman

Lauri Alanko

Ian Collins

Lauri Alanko

Eric Sosman

Ian Collins

Richard Damon

robertwessel2@yahoo.com

Lauri Alanko

Lauri Alanko

x Login to ForumsZone