CODEWITHSUNDEEP
c++arraysoptimizationbooleanint
wrongusername
wrongusername

Reputation: 18918

Copying array of ints vs pointers to bools

I'm working on a program that requires an array to be copied many thousands/millions of times. Right now I have two ways of representing the data in the array:

An array of ints:

int someArray[8][8];

where someArray[a][b] can have a value of 0, 1, or 2, or

An array of pointers to booleans:

bool * someArray[8][8];

where someArray[a][b] can be 0 (null pointer), otherwise *someArray[a][b] can be true (corresponding to 1), or false (corresponding to 2).

Which array would be copied faster (and yes, if I made the pointers to booleans array, I would have to declare new bools every time I copy the array)?

Upvotes: 2

Views: 1951

Answers (7)

Kos
Kos

Reputation: 72271

Actually, both look more or less the same in terms of copying - an array of 32-bit ints vs an array of 32-bit pointers. If you compile as 64-bit, then the pointer would probably be bigger.

BTW, if you store pointers, you probably don't want to have a SEPARATE instance of "bool" for every field of that array, do you? That would be certainly much slower.

If you want a fast copy, reduce the size as much as possible, Either:

  • use char instead of int, or
  • devise a custom class with bit manipulations for this array. If you represent one value as two bits - a "null" bit and "value-if-not-null" bit, then you'd need 128 bits = 4 ints for this whole array of 64 values. This would certainly be copied very fast! But the access to any individual bit would be a bit more complex - just a few cycles more.

OK, you made me curious :) I rolled up something like this:

struct BitArray {
public:
    static const int DIMENSION = 8;

    enum BitValue {
        BitNull = -1,
        BitTrue = 1,
        BitFalse = 0
    };
    BitArray() {for (int i=0; i<DIMENSION; ++i) data[i] = 0;}
    BitValue get(int x, int y) {
        int k = x+y*DIMENSION; // [0 .. 64)
        int n = k/16;          // [0 .. 4)
        unsigned bit1 = 1 << ((k%16)*2);
        unsigned bit2 = 1 << ((k%16)*2+1);

        int isnull = data[n] & bit1;
        int value = data[n] & bit2;
        return static_cast<BitValue>( (!!isnull)*-1 + (!isnull)*!!value );
    }
    void set(int x, int y, BitValue value) {
        int k = x+y*DIMENSION; // [0 .. 64)
        int n = k/16;          // [0 .. 4)
        unsigned bit1 = 1 << ((k%16)*2);
        unsigned bit2 = 1 << ((k%16)*2+1);
        char v = static_cast<char>(value);

        // set nullbit to 1 if v== -1, else 0
        if (v == -1) {
            data[n] |= bit1;
        } else {
            data[n] &= ~bit1;
        }

        // set valuebit to 1 if v== 1, else 0
        if (v == 1) {
            data[n] |= bit2;
        } else {
            data[n] &= ~bit2;
        }
    }
private:
    unsigned data[DIMENSION*DIMENSION/16];
};

The size of this object for an 8x8 array is 16 bytes, which is a nice improvement compared to 64 bytes with the solution of char array[8][8] and 256 bytes of int array[8][8].

This is probably as low as one can go here without delving into greater magic.

Upvotes: 4

Karl Knechtel
Karl Knechtel

Reputation: 61526

"copying" this array with the pointers would require a deep copy, since otherwise changing the copy will affect the original, which is probably not what you want. This is going to slow things down immensely due to the memory allocation overhead.

You can get around this by using boost::optional to represent "optional" quantities - which is the only reason you're adding the level of indirection here. There are very few situations in modern C++ where a raw pointer is really the best thing to be using :) However, since you only need a char to store the values {0, 1, 2} anyway, that will probably be better in terms of space. I am pretty sure that sizeof(boost::optional<bool>) > 1, though I haven't tested it. I would be impressed if they specialized for this :)

You could even bit-pack an array of 2-bit quantities, or use two bit-packed boolean arrays (one "mask" and then another set of actual true-false values) - using std::bitset for example. That will certainly save space and reduce copying time, although it would probably increase access time (assuming you really do need to access one value at a time).

Upvotes: 0

Blastfurnace
Blastfurnace

Reputation: 18652

Without knowing too much about how you use the arrays, this is a possible solution:

typedef char Array[8][8];
Array someArray, otherArray;
memcpy(someArray, otherArray, sizeof(Array));

These arrays are only 64 bytes and should copy fairly fast. You can change the data type to int but that means copying at least 256 bytes.

Upvotes: 0

Y.H.
Y.H.

Reputation: 2847

I am not 100% sure, but I think they will take roughly the same time, though I prefer using stack allocation (since dynamic allocation might take some time looking for a free space).

Consider using short type instead of int since you do not need a wide range of numbers.

I think it might be better to use one dimension array if you really want maximum speed since using the for loops in the wrong order which the compiler use for storing multidimensional arrays (raw major or column major) could cause performance penalty!

Upvotes: 0

zvrba
zvrba

Reputation: 24546

I would say you need to redesign your program. Converting between int x[8][8] and bool *b[8][8] "millions" of times cannot be "right" however your definition of "right" is lax.

Upvotes: 1

fbrereto
fbrereto

Reputation: 35925

The answer to your question will be linked to the size of the data types. Typically bool is one byte while int is not. A pointer varies in length depending on the architecture, but these days is usually 32- or 64-bits.

Not taking caching or other processor-specific optimizations into consideration, the data type that is larger will take longer to copy.

Given that you have three possible states (0, 1, 2) and 64 entries you can represent your entire structure in 128 bits. Using some utility routines and two unsigned 64-bit integers you can efficiently copy your array around very quickly.

Upvotes: 0

Steve Townsend
Steve Townsend

Reputation: 54158

Which would copy faster is beside the point, The overhead of allocating and freeing entries, and dereferencing the pointer to retrieve each value, for your bool* approach will swamp the cost of copying.

If you just have 3 possible values, use an array of char and that will copy 4 times faster than int. OK, that's not a scientifically proven statement but the array will be 4 times smaller.

Upvotes: 5

Related Questions