CODEWITHSUNDEEP
c++
Martin
Martin

Reputation: 9369

Alternatives to array of chars

I would like to know what standard container could I use as an alternative to char board[8][8] from a performance point of view. The board needs to be accessed frequently for both reading and writing. up to 1 million of new board might be constructed during the algorithm. Only three possible values are allowed for each element: -1, 0, 1, so the total number of useful bits for a board actually is 128. I thought of a custom type built around std::bitset<128> with all the required (inline) operator[], ==, =, etc defined for accessing it as 2d array, but I am not sure this would speed up the access compared to the original char[8][8]. I also don't care about gains in memory usage, this is not a problem.

Upvotes: 0

Views: 1126

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 477348

I would use a std::array<signed char, 64> and access it as a[8 * i + j]*. No point going into sub-byte granularity, since those 64B will probably be in the same cache line anyway and you get quick access like that. You could even try an array of ints for comparison; it might be that word-sized access is even faster. Only profiling can tell.

*) Or even std::array<std::array<char>, 8>, 8>, as rightly commented. Same thing, essentially, though perhaps even easier to use.

Upvotes: 4

orlp
orlp

Reputation: 117771

If you do not care about memory usage, do not use a bitset. In fact, the fastest solution will probably be one that is the easiest to use for the hardware.

You will have to profile, but I suspect using a word-sized 1d array would be the fastest:

long board[64];

Obviously, board[x][y] becomes board[x * 8 + y];

If you want you can make a C++ class interface for this, make sure to have the functions inlined though.

Remember, always profile! There is a chance that a signed char is faster than a long, depending on the compiler and architecture.

Upvotes: 1

Related Questions