Wie kann die Speicherauslastung eines Strukturtyps minimiert werden?

Question

für die Transpositionstabelle (in der Regel eine Hash-Tabelle) eines Connect Four Spiel, würde ich gerne den Speicher effizient nutzen (um die meisten möglichen Anzahl der Elemente zu speichern). Ein Tabellenelement hat speichern folgende Informationen:

• lock: unsigned 64-Bit-
• bewegen: [0..6] -> unsigned 3 Bit
• Punktzahl: [-2000..2000] - -> signierten 12-Bit-
• flag: VALID, UBOUND, LBOUND: -> unsigned 2 Bit
• Höhe: [-1..42]: -> signierten 7 Bit

Zuerst habe ich versucht folgende Datenstruktur, die 24 Bytes benötigt:

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

Nachdem die Elemente neu anordnen es 16 Bytes benötigt (fand ich die answer für dieses Verhalten):

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

Welche 16 Bytes benötigt auch:

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

Mein letzter Versuch war . Ist es möglich, die Struktur so zu ändern, dass sie nur 12 Bytes verwendet (auf einer 32-Bit-Architektur)? Warum macht der Compiler nicht meinen letzten Versuch 12 Bytes lang?

Danke!

Bearbeiten Die Eigenschaft lock ist eine eindeutige Element-ID zum Erkennen von Hash-Kollisionen.

Answer 1

Je nachdem, wie Sie Schlösser implementieren, kann es möglich sein, die Größe des Sperrfeldes zu reduzieren (Ich gehe davon aus das eine typischen SMP Sperre SMP-Maschine ist)

Eine Möglichkeit wäre, die Anzahl der zu reduzieren Schlösser.Das heißt, haben Sie eine separate, kleinere Array von Sperren, und sperren Sie ein Element von Ihrem Array-Element hier abgeleitet. Das heißt, wenn Sie auf das Transponierungstabellenelement t zugreifen, verwenden Sie die Sperre t % locktablesize. Die Sperrtabelle muss nicht annähernd so groß wie die Transponiertabelle sein.

Mit diesem Ansatz und Ihre TableEntry2 Bereich um und unter der Annahme Ihrer Sperrtabelle halb so groß wie die Umsetzungstabelle ist (was wahrscheinlich größer als nötig ist), die Sie 12 Byte get down ohne aufgrund Bitshift Operationen zu verlieren Leistung - Dieser Leistungsverlust kann sehr bedeutend sein, so dass es immer hilfreich ist, es zu vermeiden.

Answer 2

Sie können 12 Bytes erreichen von Nicht-Standard-Konstrukte wie Visual Studio mit #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; 
}; 

Hier sizeof(TableEntry3) ergibt 12 für mich.

Answer 3

Ja, da Sie nur 88 Bits an Informationen haben, ist es möglich, das in 96 Bits (12 Bytes) zu packen; aber brauchst du das wirklich? Beachten Sie im Extremfall, dass eine solche Komprimierung die Laufzeitleistung beeinträchtigen kann.

Wenn Sie Milliarden von diesen auf der Festplatte speichern, wäre die Berücksichtigung früherer kleinerer Effizienz sinnvoller, aber ist das hier der Fall? Haben Sie ein Problem bei der Speicherbenutzung gesehen? Wie viel Speicher benötigen Sie, derzeit mit 16-Byte-Objekten, und wie nahe ist Ihr geplanter Grenzwert? Der Versuch, die Verwendung des Laufzeitspeichers zu optimieren, ohne die letzten beiden Fragen zu beantworten, lautet premature.

Abgesehen davon, ich vermute, dass Ihr Compiler auffüllen am Ende der Struktur, so dass die __int64 immer auf einer 8-Byte-Grenze ausgerichtet ist. Betrachten Sie ein Array von diesen mit der Länge zwei: Bei einer Größe von 12 Byte könnte höchstens eines der __int64-Unterobjekte 8-Byte-ausgerichtet sein.