Как минимизировать использование памяти struct-type?

Question

для таблицы транспонирования (обычно хеш-таблицы) игры Connect Four, я хотел бы эффективно использовать память (для хранения максимально возможного количества элементов).Один элемент таблицы должен хранить следующую информацию:

• блокировка: 64-битный без знака
• перемещение: [0..6] -> 3-битный без знака
• счет: [-2000..2000] -> подписанный 12-битный
• флаг: VALID, UBOUND, LBOUND: -> беззнаковый 2-битный
• высота: [-1..42]:-> подписанный 7 бит

Сначала я попробовал следующую структуру данных, для которой требуется 24 байта:

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

После перестановки элементов требуется 16 байтов (я обнаружил ответ за это поведение):

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

Моя последняя попытка была:

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

Для чего также необходимо 16 байтов.Можно ли изменить структуру так, чтобы она использовала только 12 байтов (на 32-битной архитектуре)?Почему компилятор не делает мою последнюю попытку длиной 12 байт?

Спасибо!

Редактировать Свойство lock является уникальным идентификатором элемента для обнаружения коллизий хешей.

Answer 1

Да, поскольку у вас есть только 88 бит информации, ее можно упаковать в 96 бит (12 байтов); однако вам это действительно нужно? В крайнем случае, помните, что такая упаковка может ухудшить производительность во время выполнения.

Если бы вы хранили эти миллиарды из них на диске, более ранние соображения имели бы смысл, если учесть малую эффективность, но так ли это здесь? Вы видели проблему с использованием памяти? Сколько памяти вам нужно, в настоящее время с 16-байтовыми объектами, и насколько близко это к запланированному пределу? Попытка оптимизировать использование оперативной памяти, не отвечая на эти два последних вопроса, является преждевременной .

Кроме того, я подозреваю, что ваш компилятор дополняет конец структуры, поэтому __int64 всегда выравнивается по 8-байтовой границе. Рассмотрим их массив длиной два: с 12-байтовым размером максимум один из подобъектов __int64 может быть выровнен на 8 байт.

Answer 2

Вы можете достичь 12 байтов, используя нестандартные конструкции, такие как 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;
};

Здесь sizeof(TableEntry3) дает 12 для меня.

Answer 3

В зависимости от того, как вы реализуете блокировки, может быть возможно уменьшить размер вашего поля блокировки (я предполагаю, что это типичная машина SMP с блокировкой SMP)

Один из вариантов - уменьшить количество блокировок. То есть, иметь отдельный , меньший массив блокировок и заблокировать элемент, полученный из вашего элемента массива, здесь. То есть, если вы обращаетесь к элементу таблицы транспонирования t, используйте блокировку t % locktablesize. Стол блокировки не должен быть почти таким же большим, как стол транспонирования.

Используя этот подход, и ваш TableEntry2 порядок полей, и предполагая, что ваша таблица блокировок вдвое меньше таблицы транспонирования (которая, вероятно, больше, чем необходимо), вы получите 12 байтов без потери производительности из-за операции битового сдвига - эта потеря производительности может быть весьма значительной, поэтому всегда полезно ее избежать.