9

I am programming a game and want to represent a board using an array. I am looking for efficiency since I am going to do many iterations. In this case, both an int array or a char array seem convenient for the board representation. Is there any difference in terms of efficiency when doing operations in an int array and a char array?

I suspect that since every element of the char array has size of 1 byte it may be slower because of a different representation in memory (consider a modern computer which has at least 32 bits for int representation)... Am I right?

Thanks in advance.

EDIT: I am going to generate game trees, that's why efficiency is so important and small differences in time consumption can make a huge difference.

Alex Lockwood
  • 83,063
  • 39
  • 206
  • 250
PALEN
  • 2,784
  • 2
  • 23
  • 24
  • I can't think of any reason `char` would be slower. If anything, possibly depending on what operations you're doing, it may be faster. On embedded targets with 8-bit architecture, `int` operations would be slower. – jedwards May 20 '12 at 02:04
  • Maybe, but a `char` array occupies less memory, that may make it faster than an `int` array, if it has enough elements. – Daniel Fischer May 20 '12 at 02:04

3 Answers3

8

For which CPU/s?

Some CPUs can't directly access anything smaller than "something", and the compiler needs to generate a "load, shift and mask" sequence of instructions to access individual bytes. Using int should win for this case.

Some CPUs can access bytes without problems. In this case (if enough data is involved that it matters) the problem is likely to be cache size and/or memory bandwidth; and (at least for 80x86) I'd expect char would win simply because more data is packed into each cache line.

For which algorithm/s?

If you can throw SIMD at it, char is likely to win. For example, with 128-bit SIMD you can process 16 bytes per instruction or 4 (32-bit) integers per instruction and char might be 4 times faster because of this alone.

The best advice would be to use something like:

#ifdef USE_INT
    typedef int thingy
#else
    typedef unsigned char thingy
#endif

Then you can profile it and change it whenever you like.

Brendan
  • 35,656
  • 2
  • 39
  • 66
5

chars are generally 1-byte aligned and ints are generally 4-byte aligned. Assuming you are working with a machine that follows this standard, both arrays will store their content as contiguous blocks of memory (the int array being 4x the size of the char array). Thus, it is unlikely that either one will be any different in terms of how they utilize a chunk of allocated memory.

That being said, even if the underlying memory representation was any different, I doubt it would impact your program's throughput.

Alex Lockwood
  • 83,063
  • 39
  • 206
  • 250
  • I agree with the first sentence, but wouldn't this imply that the int representation (on a 32-bit machine) would take 4x the memory? Yes, the blocks will be contiguous, but not the same size. – jedwards May 20 '12 at 02:08
  • I updated my answer to clarify this point (I assumed the reader would pick up on this, but maybe I should have been more explicit). – Alex Lockwood May 20 '12 at 02:10
  • I think the sentence that got me was "it is unlikely that either one will be any different in terms of total memory utilization." -- It terms of total memory utilization, they will be different, one 4x the size of the other. – jedwards May 20 '12 at 02:14
  • Ahh, OK I see now. Sorry, I was trying to describe how the variables utilize the chunk of allocated memory returned by the call to `malloc`. i.e. "assuming the machine follows this standard (and assuming you are using a reasonable implementation of `malloc`), there will almost certainly be no internal fragmentation". Something like that at least, sorry for the confusion. – Alex Lockwood May 20 '12 at 02:20
  • If one uses the same number of array elements for both types, the char array will use 1/4 the space. On some processors, using char array would be slightly faster; on others, int array would be slightly faster. If one uses the same number of bytes for both types (meaning one uses 1/4 the number of elements for the int array), operations which do not require packing and unpacking will likely take the same amount of time per array element with either type (meaning that the 'int' could be four times as fast). – supercat May 20 '12 at 02:33
4

Try it and see. Use the -S flag to gcc to get the assembler code:

gcc -Wall -S code.c -o code.s

See if there are any obvious differences in the length of the code generated. This is not necessarily the whole story as you need to understand the assembler to judge differences. But it might give you a hint - probably that int and char will be much the same.

Note that if you mix types, you will almost certainly get slightly slower code with char arrays. So if you store data in the char array and then 'process' it somehow using int types you will probably get an extra instruction each time a conversion is made between the two. Try it with -S.

William Morris
  • 3,554
  • 2
  • 23
  • 24
  • +1! That will be the definite proof that confirms the assertions. Both great answers, it's a shame I can just pick one. – PALEN May 20 '12 at 04:44