Eric Sosman
5/20/2011 2:30:00 AM
On 5/19/2011 4:12 PM, dr.oktopus wrote:
> 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?
--
Eric Sosman
esosman@ieee-dot-org.invalid