How to minimize the memory usage of a struct-type?

for the transposition table (generally a hash table) of a Connect Four game, I would like to use the memory efficiently (to store the most possible number of elements). One table element has to store following information:

• lock: unsigned 64 bit
• move: [0..6] --> unsigned 3 bit
• score: [-2000..2000] --> signed 12 bit
• flag: VALID, UBOUND, LBOUND: --> unsigned 2开发者_运维技巧 bit
• height: [-1..42]: --> signed 7 bit

First I tried following data structure, which needs 24 Bytes:

struct TableEntry1
{
    unsigned __int64 lock;
    unsigned char move;
    short score;
    enum { VALID, UBOUND, LBOUND } flag;
    char height;
};

After rearranging the elements it needs 16 Bytes (I found the answer for this behavior):

struct TableEntry2
{
    unsigned __int64 lock;
    enum { VALID, UBOUND, LBOUND } flag;
    short score;
    char height;
    unsigned char move;
};

My last try was:

struct TableEntry3
{
    unsigned __int64 lock;
    unsigned int move:3;
    int score:12;
    enum { VALID, UBOUND, LBOUND } flag:2;
    int height:7;
};

Which also needs 16 Bytes. Is it possible to change the structure so that it only uses 12 Bytes (on a 32 bit-architecture)? Why the compiler doesn't make my last try 12 bytes long?

Thanks!

Edit The property lock is a unique element id to detect hash collisions.

Yes, since you only have 88 bits of information it is possible to pack that into 96 bits (12 bytes); however, do you really need that? In the extreme case, remember that such packing can degrade runtime performance.

If you were storing gazillions of these to disk, considering tiny efficiencies earlier would make more sense, but is that the case here? Have you seen a problem in memory use? How much memory do you need, currently with 16 byte objects, and how close is that to your planned limit? Trying to optimize runtime memory use without answering these last two questions is premature.

That aside, I suspect your compiler is padding at the end of the struct so the __int64 is always aligned on an 8-byte boundary. Consider an array of these with length two: with a 12 byte size, at most one of the __int64 sub-objects could be 8-byte aligned.

You can reach 12 bytes by using non-standard constructs such as Visual Studio #pragma pack :

#pragma pack(1)
struct TableEntry3
{
    unsigned __int64 lock;
    unsigned int move:3;
    int score:12;
    enum { VALID, UBOUND, LBOUND } flag:2;
    int height:7;
};

Here, sizeof(TableEntry3) yields 12 for me.

Depending on how you implement locks, it may be possible to reduce the size of your lock field (I'm assuming this is a typical SMP lock SMP machine)

One option would be to reduce the number of locks. That is, have a seperate, smaller array of locks, and lock an element derived from your array element here. That is, if you're accessing transposition table element t, use lock t % locktablesize. The lock table doesn't have to be nearly as big as the transposition table.

Using this approach, and your TableEntry2 field order, and assuming your lock table is half the size of the transposition table (which is probably bigger than necessary) you get down to 12 bytes without losing performance due to bitshift operations - this performance loss can be quite significant, so it's always helpful to be able to avoid it.