Efficiency: char array vs int array

Question

I am programming a game and want to represent a board using an array. I am looking for efficiency because I am going to do a lot of iterations. In this case, both the int array and the char array seem convenient for representing the board. Is there any difference in performance when performing operations in an int array and a char array?

I suspect that since each element of a char array is 1 byte in size, it may be slower due to a different representation in memory (consider a modern computer that has at least 32 bits for an int representation) ... Am Am ​​I right?

Thanks in advance.

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

Answer 1

What is CPU / s for?

Some CPUs cannot directly access anything smaller than “something,” and the compiler must generate a sequence of “load, change, and mask” instructions to access individual bytes. Using int should win for this case.

Some processors can access bytes without problems. In this case (if enough data is involved, which is important), the problem is likely to be related to cache size and / or memory bandwidth; and (at least for 80x86), I expect char win simply because more data will be packed into each cache line.

For what algorithm / s?

If you can throw SIMD, char can win. For example, with a 128-bit SIMD, you can process 16 bytes per instruction or 4 (32-bit) integers for each command, and char can be 4 times faster because of this.

The best advice would be to use something like:

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

Then you can view it and change it whenever you want.

Answer 2

char usually aligned by 1 byte, and int usually aligned by 4 bytes. Assuming you are working with a machine that follows this standard, both arrays will store their contents as contiguous blocks of memory (an int array is 4x the size of a char array). Thus, it is unlikely that any of them will differ from how they use a piece of allocated memory.

At the same time, even if the representation of the base memory was somehow different, I doubt that this will affect the throughput of your program.

Answer 3

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

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

See if there are obvious differences in the length of the generated code. This is not necessarily the whole story, as you need to understand how assembler evaluates differences. But this may give you a hint - it is possible that int and char will be almost the same.

Note that if you mix types, you will almost certainly get a bit slower code with char arrays. Therefore, if you store data in a char array, and then “process” it in some way using int types, you will probably get additional instructions every time a conversion between them is done. Try using -S.