CODEWITHSUNDEEP
c++c
eejakobowski
eejakobowski

Reputation: 117

Is there a computationally efficient way to store values smaller than a byte in multidimensional arrays in C/C++?

My current project involves working with arrays of 5+ dimensions, but the individual elements of the array do not need to have 256 possible values. I was wondering if I could save on memory space by using a custom data type with, for example, only 4 or 6 bits to represent the value of an element, and if these memory savings would come at some significant performance cost.

Upvotes: 2

Views: 214

Answers (1)

Petr Skocik
Petr Skocik

Reputation: 60137

Multidimensional arrays in C are really basically arrays of arrays. (It can't be any other way as RAM is inherently linear). You can emulate them on linear arrays in terms of pointer arithmetic:

#undef NDEBUG
#include <assert.h>
#include <stdint.h>
int main()
{
    typedef uint32_t TYPE;
    enum{A=3,B=4,C=5};
    TYPE a[A][B][C];

    assert((char*)&a[1][2][3] == ((char*)&a) + \
          3*sizeof(TYPE) + 2 *C*sizeof(TYPE) + 1 *B*C*sizeof(TYPE));
}

Computers don't let you address sub-char types but it's not difficult to imagine a sub-char type.

The above char offset calculation for addressing a[1][2][3] could be rewriten like

char_ix = (3*sizeof(TYPE)*CHAR_BIT + 2 *C*sizeof(TYPE)*CHAR_BIT + 1 *B*C*sizeof(TYPE)*CHAR_BIT)/CHAR_BIT;

and if instead of chars (8-bits) you wanted to address e.g., 4-bits, you'd change it to 

char_ix_of_4_bit = 
     (3*sizeof(TYPE)*CHAR_BIT/2 + 
      2 *C*sizeof(TYPE)*CHAR_BIT/2 + 
      1 *B*C*sizeof(TYPE)*CHAR_BIT/2) \
     / CHAR_BIT; //2 4-bits per octet

char_ix_of_4_bit_remainder = 
     (3*sizeof(TYPE)*CHAR_BIT/2 + 
      2 *C*sizeof(TYPE)*CHAR_BIT/2 + 
      1 *B*C*sizeof(TYPE)*CHAR_BIT/2) \
     % CHAR_BIT; //2 4-bits per octet

The 4 bit value at the destination would then be

((unsigned char*)&a)[char_ix_of_4_bit] >> (4*char_ix_of_4_bit_remainder)

Similar for other bit groups.

In short, you can think of multidimensional bit arrays, reimagine them as linear bit arrays and then use regular indexing and bit shifting to address the appropriate bit group or individual bits (IIRC, C++'s std::bitset/std::vector<bool> hide the last part under bit indexing with an overloaded [] operator, but it's not hard to do it manually (which is what you'll need to do in pure C anyway, as pure C doesn't have operator overloading).

Bit ops are said to be slower and generate larger code than operations with whole types, but this might be well be offset by better cache locality, which using sub-char bit arrays might buy you depending on your data (you'd better have lots of data if you're attempting to do this).

Upvotes: 4

Related Questions