speed of int vs bool for large matrix

[raj]

Hi,
I saw it mentioned that "int" is the fastest data-type for use in C
,that is data storage/retrieval would be the fastest if I use int among
the following 4 situations in a 32 bit machine with 4-byte ints:

int m[1000][1000];
bool m[1000][1000]; // assuming I use C++
char m[1000][1000];
unsigned char m[1000][1000];

I need to know if this statement is true. Also, if int is indeed the
fastest, in practice, how slower would the bool matrix be ? What if I
had to dynamically allocate all the 4 cases above - would the same
statements still hold?

Actually I need a large matrix for storing just a binary value (so
bool would be most appropriate) - but speed is my utmost concern, space
required comes next.

Some pointers ?

Thanks in advance.
Rajorshi

[pete]

raj wrote:

Hi,
I saw it mentioned that "int" is the fastest data-type for use in C I need to know if this statement is true.

It's almost true.
This is what the rules of C actually say:

N869
6.2.5 Types
[#5]
A ``plain'' int object has the natural size suggested by the
architecture of the execution environment (large enough to
contain any value in the range INT_MIN to INT_MAX as defined
in the header <limits.h>).

--
pete

[jacob navia]

raj wrote:

Hi,
I saw it mentioned that "int" is the fastest data-type for use in C
,that is data storage/retrieval would be the fastest if I use int among
the following 4 situations in a 32 bit machine with 4-byte ints:

int m[1000][1000];
bool m[1000][1000]; // assuming I use C++
char m[1000][1000];
unsigned char m[1000][1000];

I need to know if this statement is true. Also, if int is indeed the
fastest, in practice, how slower would the bool matrix be ? What if I
had to dynamically allocate all the 4 cases above - would the same
statements still hold?

Actually I need a large matrix for storing just a binary value (so
bool would be most appropriate) - but speed is my utmost concern, space
required comes next.

Some pointers ?

Thanks in advance.
Rajorshi

If you declare your table as a table of unsigned chars, memory
requitrements will be 1 000 000 bytes, in the other case will be
4 times as much (supposing a 32 bit machine), i.e. there is 4 times
as much data that will fit the Level 1 cache.

Input output requirements will be much more reduced and the
program will be surely much faster.

If you have a purely boolean matrix, I would use a packed
representation with 8 bits/byte, making your matrix just
125K, i.e. 8 times less than if you use the int data type.

Note that reducing space requirements increases speed, since
filling the cache from RAM introduces an enormous amount of wait
states. Memory access go through the bus at 300 MHZ, with a CPU
running at 3 000 MHZ, i.e. a memory access can be 10 times slower
when it doesn't hit the L1 cache.

Of course this analysis implies a sequential access to each
element of the matrix. In other cases where you just access
randomly elements of the matrix, an integer representation would
beat all others since you are NOT limited by I/O.

MAIN POINT
----------
Speculating about speed will never replace actual measurements.

1: Build a test matrix.
2: Simulate the access pattern of your application.
3: Time it using unsigned char, int.

Then you will know for sure.

jacob

[SM Ryan]

"raj" <ra******@fastm ail.fm> wrote:
# Hi,
# I saw it mentioned that "int" is the fastest data-type for use in C

That's wrong. The correct answer is MU. Suppose you're solving PDEs; the fastest
data type is float or double. You can do it in int, using various integers to
hold the exponents and fractions, but it's going to be a lot faster using what
is encoded in the hardware and math libraries. What is fastest depends on the
operations performed on what data in what order on what hardware with what caches
and what kind of virtual memory (if any) management. There's is no universally
correct answer.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Who's leading this mob?

[Keith Thompson]

jacob navia <ja***@jacob.re mcomp.fr> writes:

raj wrote:

I saw it mentioned that "int" is the fastest data-type for use in C
,that is data storage/retrieval would be the fastest if I use int among
the following 4 situations in a 32 bit machine with 4-byte ints:

int m[1000][1000];
bool m[1000][1000]; // assuming I use C++
char m[1000][1000];
unsigned char m[1000][1000];

I need to know if this statement is true. Also, if int is indeed the
fastest, in practice, how slower would the bool matrix be ? What if I
had to dynamically allocate all the 4 cases above - would the same
statements still hold?

Actually I need a large matrix for storing just a binary value (so
bool would be most appropriate) - but speed is my utmost concern, space
required comes next.

[...]
If you declare your table as a table of unsigned chars, memory
requitrements will be 1 000 000 bytes, in the other case will be
4 times as much (supposing a 32 bit machine), i.e. there is 4 times
as much data that will fit the Level 1 cache.
You're assuming there is a "Level 1 cache".
Input output requirements will be much more reduced and the
program will be surely much faster.
What input output requirements? The OP didn't indicate that the
matrix would be read from or written to an external file.
If you have a purely boolean matrix, I would use a packed
representation with 8 bits/byte, making your matrix just
125K, i.e. 8 times less than if you use the int data type.
Which will likely make access to individual elements slower.
Note that reducing space requirements increases speed, since
filling the cache from RAM introduces an enormous amount of wait
states. Memory access go through the bus at 300 MHZ, with a CPU
running at 3 000 MHZ, i.e. a memory access can be 10 times slower
when it doesn't hit the L1 cache.
That's all very system-specific.
Of course this analysis implies a sequential access to each
element of the matrix. In other cases where you just access
randomly elements of the matrix, an integer representation would
beat all others since you are NOT limited by I/O.

MAIN POINT
----------
Speculating about speed will never replace actual measurements.

1: Build a test matrix.
2: Simulate the access pattern of your application.
3: Time it using unsigned char, int.

Then you will know for sure.

You could have safely skipped everything before "MAIN POINT".

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Christian Bau]

In article <ch********@odb k17.prod.google .com>,
"raj" <ra******@fastm ail.fm> wrote:

Hi,
I saw it mentioned that "int" is the fastest data-type for use in C
,that is data storage/retrieval would be the fastest if I use int among
the following 4 situations in a 32 bit machine with 4-byte ints:

int m[1000][1000];
bool m[1000][1000]; // assuming I use C++
char m[1000][1000];
unsigned char m[1000][1000];

I need to know if this statement is true. Also, if int is indeed the
fastest, in practice, how slower would the bool matrix be ? What if I
had to dynamically allocate all the 4 cases above - would the same
statements still hold?

Actually I need a large matrix for storing just a binary value (so
bool would be most appropriate) - but speed is my utmost concern, space
required comes next.

Why don't you just try it out. Write four functions, one with each kind
of matrix, and then set every element to zero, then to one, and repeat
this thousand times. Measure the time. Observe the difference.

[jacob navia]

Keith Thompson wrote:

jacob navia <ja***@jacob.re mcomp.fr> writes:

If you declare your table as a table of unsigned chars, memory
requitremen ts will be 1 000 000 bytes, in the other case will be
4 times as much (supposing a 32 bit machine), i.e. there is 4 times
as much data that will fit the Level 1 cache.

You're assuming there is a "Level 1 cache".

I am assuming of course a modern CPU, either a PPC, x86 or similar.
Please lets be realistic: handling 1-4MB matrices in a DSP
with 4K of RAM would be ridiculous...

Input output requirements will be much more reduced and the
program will be surely much faster.

What input output requirements? The OP didn't indicate that the
matrix would be read from or written to an external file.

Input output to/from the CPU of course!
I am not speaking about file I/O but RAM I/O.

If you have a purely boolean matrix, I would use a packed
representatio n with 8 bits/byte, making your matrix just
125K, i.e. 8 times less than if you use the int data type.

Which will likely make access to individual elements slower.

No, this is my point. If you have to read from RAM 8 times less
data, each read producing at least 10-20 wait states, the few
more instructions to access the individual bits would be
compensated by the smaller I/O.

Note that reducing space requirements increases speed, since
filling the cache from RAM introduces an enormous amount of wait
states. Memory access go through the bus at 300 MHZ, with a CPU
running at 3 000 MHZ, i.e. a memory access can be 10 times slower
when it doesn't hit the L1 cache.

That's all very system-specific.

Not really. As the CPUs of modern micro computers go to
ever higher clock speeds, memory doesn't catch up at all,
and I/O from RAM becomes the limiting factor.

Of course this analysis implies a sequential access to each
element of the matrix. In other cases where you just access
randomly elements of the matrix, an integer representation would
beat all others since you are NOT limited by I/O.

MAIN POINT
----------
Speculating about speed will never replace actual measurements.

1: Build a test matrix.
2: Simulate the access pattern of your application.
3: Time it using unsigned char, int.

Then you will know for sure.

You could have safely skipped everything before "MAIN POINT".

No, I wanted to describe alternatives and leave the OP the choice
but of an informed choice.

[Derrick Coetzee]

raj wrote:

int m[1000][1000];
bool m[1000][1000]; // assuming I use C++
char m[1000][1000];
unsigned char m[1000][1000];

Like many people, you make the mistake of assuming that bools occupy a
single bit (also note that C99 includes a bool type much like the C++
one.) There is a difficult-to-predict performance tradeoff here that
will vary from machine to machine. Here's a comparison of the advantages
and disadvantages:

int m[1000][1000];

This stores a single value in each word, consuming at least one million
words. Random access requires only the address calculation plus a single
read/write operation on most machines, with no need for bit operations.
That makes this alternative good for random access on machines with weak
bit-level capabilities. If the array is going to be traversed
sequentially on a machine with a data cache though, it will produce many
more cache misses than other approaches.

char m[1000][1000];

This stores a single value in each byte, so that you only need about
million bytes. If you traverse the array in order on a machine with a
data cache, you'll get a lot less cache misses with this version, and on
byte-addressable machines with instructions to fetch bytes, no bit
operations are needed on top of address calculation. On word-addressable
machines with no special instructions for loading bytes, however, this
may turn out to compile into something as slow as the bit array below.
It also still takes 8 times as much space as the bit array, and has
about 8 times as many cache misses when traversed in order on machines
with data caches.

#define INT_BITS (sizeof(int)*8)
#define CEIL_DIV(x,y) ((x+y-1)/y)
int m[1000][CEIL_DIV(1000,I NT_BITS)];
#define M_GET(r,c) (m[(r)][(c)/INT_BITS] & (1 << ((c) % INT_BITS)))
#define M_SET(r,c) (m[(r)][(c)/INT_BITS] |= (1 << ((c) % INT_BITS)))
#define M_CLEAR(r,c) (m[(r)][(c)/INT_BITS] &= ~(1 << ((c) % INT_BITS)))

This creates an array of bits and some macros for accessing it. Although
the division and modulus operations will probably compile to bit
operations, each random access to a non-constant index pair will require
on most machines at least two ANDs and two shifts that the word version
doesn't. Accesses to fixed or partially fixed indexes are faster, since
it can precompute the index and bit mask (shown here for an INT_BITS of 32):

M_GET(40,65)
(m[(40)][(65)/INT_BITS] & (1 << ((65) % INT_BITS)))
m[40][65/32] & (1 << (65 % 32))
m[40][2] & (1 << 1)
m[40][2] & 2

Sequential access actually can yield very good performance, since you
can do that with a loop like this:

unsigned int current_word, i, j, mask;
for(i=0; i<1000; i++) {
for(j=0; j<CEIL_DIV(1000 , INT_BITS); j++) {
current_word = m[i][j];
for(mask = 1; mask != 0; mask <<= 1) {
int current_bit = current_word & mask; /*get current bit*/
current_word |= mask; /* set the current bit */
current_word &= ~mask; /* clear the current bit */
}
m[i][j] = current_word;
}
}

This amounts to two bit operations and 2/INT_BITS word accesses per
element on average, which is not only often faster than two word
accesses but cache misses on machines with caches are reduced by about
INT_BIT times.

Even if you only do random access, considering that you reduce your
space requirements by INT_BIT times, a few extra cycles per access is
justified in many applications.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.

[Randy Howard]

In article <ch**********@n ews-reader5.wanadoo .fr>, ja***@jacob.rem comp.fr
says...

I am assuming of course a modern CPU, either a PPC, x86 or similar.
Intel is STILL selling Celerons. *sigh*
No, this is my point. If you have to read from RAM 8 times less
data, each read producing at least 10-20 wait states, the few
more instructions to access the individual bits would be
compensated by the smaller I/O.

I don't know that's a given. Hypertransport 4-way Opteron boxes
can move almost 8GB/s to/from memory with current DDR modules when
spinning through 64GB of total memory, using 4GB block move/compares.

I'm not at all sure that 8GB/s (being close to 4X what a Xeon 4-way can
do) is going to care much for typical application read/write sizes
whether you use char's, int's, etc. As usual, it depends on the
specifics, the hardware, etc. There is no general rule for this sort of
thing that isn't so general as to be practically worthless. Measure,
then you'll know.

--
Randy Howard
To reply, remove FOOBAR.

[Keith Thompson]

jacob navia <ja***@jacob.re mcomp.fr> writes:

Keith Thompson wrote:

jacob navia <ja***@jacob.re mcomp.fr> writes:

If you declare your table as a table of unsigned chars, memory
requitrements will be 1 000 000 bytes, in the other case will be
4 times as much (supposing a 32 bit machine), i.e. there is 4 times
as much data that will fit the Level 1 cache.

You're assuming there is a "Level 1 cache".

I am assuming of course a modern CPU, either a PPC, x86 or similar.
Please lets be realistic: handling 1-4MB matrices in a DSP
with 4K of RAM would be ridiculous...

Input output requirements will be much more reduced and the
program will be surely much faster.

What input output requirements? The OP didn't indicate that the
matrix would be read from or written to an external file.

Input output to/from the CPU of course!
I am not speaking about file I/O but RAM I/O.

Hmm. I don't think that's what most people mean by "I/O".

If you have a purely boolean matrix, I would use a packed
representati on with 8 bits/byte, making your matrix just
125K, i.e. 8 times less than if you use the int data type.

Which will likely make access to individual elements slower.

No, this is my point. If you have to read from RAM 8 times less
data, each read producing at least 10-20 wait states, the few
more instructions to access the individual bits would be
compensated by the smaller I/O.

If the matrix is read randomly, the code will still have to read
memory for each access, *plus* the overhead of extracting the desired
bit (and similarly for write access).

[...]

MAIN POINT
----------
Speculatin g about speed will never replace actual measurements.

1: Build a test matrix.
2: Simulate the access pattern of your application.
3: Time it using unsigned char, int.

Then you will know for sure.

You could have safely skipped everything before "MAIN POINT".

No, I wanted to describe alternatives and leave the OP the choice
but of an informed choice.

I may have been slightly too harsh. My real complaint is that you
didn't qualify your statements. The amount of cache, if any, is still
system-specific, even if it happens that most modern systems have at
least some particular amount. If you had made that clearer, I
wouldn't have minded as much.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.