word size and gcc builtins usage

[dr.oktopus]

Hello,
simple question: what is the most appropriate type for implement a bit
array type for
operations like anding, oring, etc..
simple answer: well, it should be the word size of the microprocessor
you are using.
More exactly, it should be the largest word the os allow you. So, if
you are running
x86 linux on a 64-bit microprocessor, it is 32 bit. But how detect it?
Looking around
seems no obvious answer exists. Most code I've seen get it from a
configuration file.
This is from libSDL:

#ifdef SDL_HAS_64BIT_TYPE
typedef int64_t Sint64;

SDL_HAS_64BIT_TYPE is defined in different headers for different
platforms.
I would like to know if there is any chance to get info on 64 bit type
availability.

Moreover, I need to define a macro based on this type, that use a gcc
builtin (in my case one of __builtin_clz, __builtin_clzl,
__builtin_clzll)
of the appropriate size, or a custom function if no builtin is
available on
that platform (or version of the compiler).
Can you point me any link about correct usage of gcc builtins?

 

[Ian Collins]

Hello,
simple question: what is the most appropriate type for implement a bit
array type for
operations like anding, oring, etc..
simple answer: well, it should be the word size of the microprocessor
you are using.
More exactly, it should be the largest word the os allow you. So, if
you are running
x86 linux on a 64-bit microprocessor, it is 32 bit. But how detect it?

Why 32 bit? unsigned long is 64 bit on that platform.

Using size_t probably meets your requirements.

 

[Joel C. Salomon]

simple question: what is the most appropriate type for implement a bit
array type for operations like anding, oring, etc..
simple answer: well, it should be the word size of the microprocessor
you are using. More exactly, it should be the largest word the os
allow you.

Look in your compiler's manual for <stdint.h>.

Do you want the *largest* size available, or the most efficient one?
The largest is `uintmax_t`; the fastest will likely be `unsigned int`,
but if you need at least some specific number of bits, `uint_fast32_t`
or `uint_fast64_t` will work. So will `uint_least32_t` and
`uint_least64_t`, but the `...fast...` versions might well be faster.

So, if you are running x86 linux on a 64-bit microprocessor, it is 32
bit. But how detect it? Looking around seems no obvious answer exists.
Most code I've seen get it from a configuration file.

This is from libSDL:

#ifdef SDL_HAS_64BIT_TYPE
typedef int64_t  Sint64;

Sounds like you mean "64-bit" rather than "32 bit"; in either case, C
mandates an integer type with at least 64 bits; see above.

If you want to know if a type with exactly 64 bits is available --
i.e., `uint64_t` or `int64_t` -- you can do something like this:

#ifdef UNINT64_MAX
typedef uint64_t  bitmask;
#else
#error "No 64-bit type!"
#endif

--Joel

 

[Seebs]

Hello,
simple question: what is the most appropriate type for implement a bit
array type for
operations like anding, oring, etc..
simple answer: well, it should be the word size of the microprocessor
you are using.
Maybe.

More exactly, it should be the largest word the os allow you.

This may well not be.

So, if
you are running
x86 linux on a 64-bit microprocessor, it is 32 bit. But how detect it?

This seems backwards, because on a 64-bit processor, you probably do
have a 64-bit type available.

I would like to know if there is any chance to get info on 64 bit type
availability.

In C99, the answer is always yes, however, the existence of a 64-bit type
doesn't mean it's an *efficient* type. 64-bit types were widely available
on 32-bit hardware long ago.

Moreover, I need to define a macro based on this type, that use a gcc
builtin (in my case one of __builtin_clz, __builtin_clzl,
__builtin_clzll)
of the appropriate size, or a custom function if no builtin is
available on
that platform (or version of the compiler).

Why do you need to use a gcc builtin?

Can you point me any link about correct usage of gcc builtins?

I can point you at one thing:

Use int.

If you don't know, use int. The only time you should use an integer type
other than int is when you're sure that int isn't big enough, but for a bit
array, it doesn't matter; you'll likely have more than one object. At that
point, int is going to be the right type, because it's the type the processor
is happiest with. Specifically, for bit operations, "unsigned int".

There are machines where a 64-bit type exists, but where "unsigned int" will
be noticably faster...

-s

 

[Keith Thompson]

In C99, the answer is always yes, however, the existence of a 64-bit type
doesn't mean it's an *efficient* type. 64-bit types were widely available
on 32-bit hardware long ago.

[...]

In C99, there is always a type that's *at least* 64 bits.

I seriously doubt that any C99 implementation exists that doesn't have
an integer type that's exactly 64 bits, but it's theoretically possible.
Some future system might provide hardware operations only for 128-bit
quantities, and make all predefined integer types (perhaps except for
the char tyeps) 128 bits.

 

[Seebs]

In C99, the answer is always yes, however, the existence of a 64-bit type
doesn't mean it's an *efficient* type. 64-bit types were widely available
on 32-bit hardware long ago. [...]

In C99, there is always a type that's *at least* 64 bits.

Good catch.

-s

 

[robertwessel2]

Look in your compiler's manual for <stdint.h>.

Do you want the *largest* size available, or the most efficient one?
The largest is `uintmax_t`; the fastest will likely be `unsigned int`,
but if you need at least some specific number of bits, `uint_fast32_t`
or `uint_fast64_t` will work.  So will `uint_least32_t` and
`uint_least64_t`, but the `...fast...` versions might well be faster.

I think the only answer is that you simply can't tell in advance.
Consider an implementation of C on an 8-bit microprocessor. The
fastest type is almost certainly going to be a char, and not int
(shifting and masking a 16 bit quantity may well be very expensive on
such a beast). And even for CPUs with int sized words, it may be that
a longer or shorter int may be more efficient for a bit array even if
the word sized int is the "fastest" general purpose type. Consider
x86-64 - if you need to use masks to access the bits, you can't code
them as immediates if you use 64 bit ints (whether that results in
sufficient performance impairment to suggest 32 bit ints instead is a
different issue). Or assuming the opposite, many 64 implementations
define int as 32 bits, regardless of performance. And, of course, all
that can change between versions of the implementation (new CPU
microarchitecture, new compiler release, different compiler flags...).

So the only "real" solution is a configuration file. And perhaps to
default to int if the configuration file doesn't specify anything
better. And to check (*first*) if this optimization is going to
actually matter.

 

[Eric Sosman]

Hello,
simple question: what is the most appropriate type for implement a bit
array type for
operations like anding, oring, etc..
simple answer: well, it should be the word size of the microprocessor
you are using.
More exactly, it should be the largest word the os allow you.

It's not so simple a question, because there are at least three
scenarios with three different goals you might seek:

1) The bit array is long (> ~256 bits, say) and the dominant
operations are wholesale ANDs, ORs, and XORs of entire arrays. You
want to minimize the "hardware ops" for a full-array operation, so
you'd like to choose the widest type whose operations are "fast."
That is, if the implementation offers a 32-bit "native" type and a
64-bit "composed" type, you might do better with 32 bits even though
it's not the widest available.

2) The dominant operations are setting, clearing, flipping, and
testing individual bits by number. You don't much care about the
element width (you will index your way directly to the one you want),
so you'd like to choose the fastest type regardless of the width.

3) The bit array is of a known fixed length, small enough that
you can hope to fit the whole thing into a single unit and avoid all
that clumsy looping. In this case you want the fastest type that's
at least wide enough.

Note that in scenarios (1) and (2) for sure, and possibly in (3),
memory latency may well drown operation counts.

So, if
you are running
x86 linux on a 64-bit microprocessor, it is 32 bit.

That seems a peculiar conclusion. Of course, "64-bit processor"
is not rigidly defined, and the 32-bit choice might in fact be best
for some systems that claim the title. Unlikely, but possible.

But how detect it?
Looking around
seems no obvious answer exists. Most code I've seen get it from a
configuration file.

That's probably best. You'll need to run timing tests of whatever
scenario is important to you, and make a choice based on the results
(and realize that the results and the choice may change on the next
machine you use).

I would like to know if there is any chance to get info on 64 bit type
availability.

#if __STDC_VERSION__ >= 199001L
#include <stdint.h>
typedef uint64_t BitVecElement; // other choices possible
#else
#include <limits.h>
#if ((((UINT_MAX >> 15) >> 15) >> 15) >> 15) >= 16
typedef unsigned int BitVecElement;
#elif ((ULONG_MAX >> 30) >> 30) >= 16
typedef unsigned long BitVecElement;
#else
#error "This CPU is narrow-minded"
#endif
#endif

However, this says absolutely nothing about the speeds of the various
choices. A C99 implementation *must* offer a type of at least 64 bits,
even if it must generate subroutine calls for all operations on it.

Moreover, I need to define a macro based on this type, that use a gcc
builtin [...]
Can you point me any link about correct usage of gcc builtins?

How about the gcc INFO documents?

 

[dr.oktopus]

     It's not so simple a question, because there are at least three
scenarios with three different goals you might seek:

     1) The bit array is long (> ~256 bits, say) and the dominant
operations are wholesale ANDs, ORs, and XORs of entire arrays.  You
want to minimize the "hardware ops" for a full-array operation, so
you'd like to choose the widest type whose operations are "fast."
That is, if the implementation offers a 32-bit "native" type and a
64-bit "composed" type, you might do better with 32 bits even though
it's not the widest available.

This should be my case. The type should be the largest that allow you
to work fast with and/or/xor operations. A type simulated by the
compiler
as 64 should be avoided, like you say

What I meant here, and say wrong (sorry I wrote in a few minutes),
it is that running a 32 bit os on a 64 bit processor doesn't allow
you to use 64 bit registers, so largest type is still 32 bit.

     How about the gcc INFO documents?

I looked at them (maybe I have to re-read it?). I miss how to check if
a builtin I like to use is available. perhaps try to #ifdef it?

 

[Jorgen Grahn]

Why 32 bit? unsigned long is 64 bit on that platform.

"x86" implies 32-bit -- the one you're thinking of is "x86_64" AKA
"amd64". Not sure why he mentioned 64-bit; it's irrelevant if you
run in 32-bit mode.

/Jorgen