Wenn beispielsweise eine 32-Bit-Ganzzahl überläuft, können wir anstelle eines Upgrades int
auf long
einen 40-Bit-Typ verwenden, wenn wir nur einen Bereich innerhalb von 2 bis 40 benötigen , sodass wir für jeden 24 (64-40) Bit speichern ganze Zahl?
Wenn das so ist, wie?
Ich muss mich mit Milliarden auseinandersetzen und Platz ist eine größere Einschränkung.
c++
c
memory-management
integer-overflow
user1660982
quelle
quelle
Antworten:
Ja aber...
Es ist sicherlich möglich , aber normalerweise unsinnig (für jedes Programm, das nicht Milliarden dieser Zahlen verwendet):
#include <stdint.h> // don't want to rely on something like long long struct bad_idea { uint64_t var : 40; };
Hier
var
wird in der Tat eine Breite von 40 Bit auf Kosten vonvielweniger effizientem Code generiert (es stellt sich heraus, dass "viel" sehr viel falsch ist - der gemessene Overhead beträgt nur 1-2%, siehe Timings unten) und normalerweise ohne Erfolg. Sofern Sie keinen weiteren 24-Bit-Wert (oder einen 8- und 16-Bit-Wert) benötigen, den Sie in dieselbe Struktur packen möchten, verfällt bei der Ausrichtung alles, was Sie möglicherweise gewinnen.In jedem Fall wird der effektive Unterschied im Speicherverbrauch nicht spürbar sein, es sei denn, Sie haben Milliarden davon (aber der zusätzliche Code, der zur Verwaltung des Bitfelds benötigt wird, wird spürbar sein!).
Hinweis:
Die Frage wurde in der Zwischenzeit aktualisiert, um zu berücksichtigen, dass tatsächlich Milliarden von Zahlen benötigt werden. Dies kann daher sinnvoll sein, vorausgesetzt, Sie ergreifen Maßnahmen, um die Gewinne aufgrund von Strukturausrichtung und Polsterung nicht zu verlieren indem Sie etwas anderes in den verbleibenden 24 Bit speichern oder indem Sie Ihre 40-Bit-Werte in Strukturen von jeweils 8 oder mehreren davon speichern).
Das milliardenfache Speichern von drei Bytes lohnt sich, da dadurch deutlich weniger Speicherseiten benötigt werden und somit weniger Cache- und TLB-Fehler und vor allem Seitenfehler (ein einzelner Seitenfehler mit einer Gewichtung von mehreren zehn Millionen Anweisungen) verursacht werden.
Während das obige Snippet die verbleibenden 24 Bit nicht verwendet (es zeigt lediglich den Teil "40 Bit verwenden"), ist etwas Ähnliches wie das Folgende erforderlich, um den Ansatz wirklich nützlich zu machen, um Speicher zu erhalten - vorausgesetzt, dass Sie haben in der Tat andere "nützliche" Daten, die Sie in die Löcher stecken müssen:
struct using_gaps { uint64_t var : 40; uint64_t useful_uint16 : 16; uint64_t char_or_bool : 8; };
Strukturgröße und Ausrichtung entsprechen einer 64-Bit-Ganzzahl, sodass nichts verschwendet wird, wenn Sie beispielsweise ein Array von einer Milliarde solcher Strukturen erstellen (auch ohne Verwendung von compilerspezifischen Erweiterungen). Wenn Sie keinen 8-Bit-Wert verwenden können, können Sie auch einen 48-Bit- und einen 16-Bit-Wert verwenden (was einen größeren Überlaufspielraum ergibt).
Alternativ können Sie auf Kosten der Benutzerfreundlichkeit 8 40-Bit-Werte in eine Struktur einfügen (das kleinste gemeinsame Vielfache von 40 und 64 ist 320 = 8 * 40). Natürlich wird dann Ihr Code, der auf Elemente im Array von Strukturen zugreift, viel komplizierter (obwohl man wahrscheinlich einen implementieren könnte
operator[]
, der die Funktionalität des linearen Arrays wiederherstellt und die Komplexität der Struktur verbirgt).Update:
Schrieb eine schnelle Testsuite, um zu sehen, welchen Overhead die Bitfelder (und die Überladung des Operators mit Bitfeldreferenzen) haben würden. Der auf gcc.godbolt.org veröffentlichte Code (aufgrund der Länge) lautet : Die Testausgabe von meinem Win7-64-Computer lautet:
Running test for array size = 1048576 what alloc seq(w) seq(r) rand(w) rand(r) free ----------------------------------------------------------- uint32_t 0 2 1 35 35 1 uint64_t 0 3 3 35 35 1 bad40_t 0 5 3 35 35 1 packed40_t 0 7 4 48 49 1 Running test for array size = 16777216 what alloc seq(w) seq(r) rand(w) rand(r) free ----------------------------------------------------------- uint32_t 0 38 14 560 555 8 uint64_t 0 81 22 565 554 17 bad40_t 0 85 25 565 561 16 packed40_t 0 151 75 765 774 16 Running test for array size = 134217728 what alloc seq(w) seq(r) rand(w) rand(r) free ----------------------------------------------------------- uint32_t 0 312 100 4480 4441 65 uint64_t 0 648 172 4482 4490 130 bad40_t 0 682 193 4573 4492 130 packed40_t 0 1164 552 6181 6176 130
Was man sehen kann, ist, dass der zusätzliche Overhead von Bitfeldern vernachlässigbar ist, aber das Überladen des Operators mit Bitfeldreferenz als Annehmlichkeitssache ist ziemlich drastisch (etwa 3-fache Zunahme), wenn auf Daten auf cachefreundliche Weise linear zugegriffen wird. Auf der anderen Seite spielt es beim Direktzugriff kaum eine Rolle.
Diese Timings legen nahe, dass die einfache Verwendung von 64-Bit-Ganzzahlen besser wäre, da sie insgesamt immer noch schneller sind als Bitfelder (obwohl mehr Speicher berührt wird), aber natürlich berücksichtigen sie nicht die Kosten für Seitenfehler bei viel größeren Datensätzen. Es könnte ganz anders aussehen, wenn Ihnen der physische Arbeitsspeicher ausgeht (das habe ich nicht getestet).
quelle
-Wpedantic
).Sie können 4 * 40-Bit-Ganzzahlen ganz effektiv in eine 160-Bit-Struktur wie folgt packen:
struct Val4 { char hi[4]; unsigned int low[4]; } long getLong( const Val4 &pack, int ix ) { int hi= pack.hi[ix]; // preserve sign into 32 bit return long( (((unsigned long)hi) << 32) + (unsigned long)pack.low[i]); } void setLong( Val4 &pack, int ix, long val ) { pack.low[ix]= (unsigned)val; pack.hi[ix]= (char)(val>>32); }
Diese können wieder so verwendet werden:
Val4[SIZE] vals; long getLong( int ix ) { return getLong( vals[ix>>2], ix&0x3 ) } void setLong( int ix, long val ) { setLong( vals[ix>>2], ix&0x3, val ) }
quelle
signed char hi[4];
explizit zu verwenden; Plainchar
kann signiert oder nicht signiert sein.uint_least32_t
undint_least8_t
hier zu verwenden, alsunsigned int
undchar
.unsigned int
muss nur mindestens 16 Bit betragen.char
wird immer mindestens 8 Bit sein, daher gibt es dort nicht so viele Probleme. Außerdem würde ich für denhi
Teil des Werts die Multiplikation anstelle der Bitverschiebung verwenden . Das ist gut definiert, und der Compiler kann die Bitverschiebung ersetzen, wenn dies angemessen ist. Ansonsten gute Idee!Möglicherweise möchten Sie die Codierung mit variabler Länge (VLE) in Betracht ziehen.
Vermutlich haben Sie viele dieser Nummern irgendwo gespeichert (im RAM, auf der Festplatte, senden Sie sie über das Netzwerk usw.), und nehmen Sie sie dann einzeln und führen Sie eine Verarbeitung durch.
Ein Ansatz wäre, sie mit VLE zu codieren . Aus der Protobuf- Dokumentation von Google (CreativeCommons-Lizenz)
Vorteile
Nachteile
quelle
(Bearbeiten: Erstens - was Sie wollen, ist möglich und in einigen Fällen sinnvoll; ich musste ähnliche Dinge tun, als ich versuchte, etwas für die Netflix-Herausforderung zu tun, und hatte nur 1 GB Speicher; zweitens - es ist wahrscheinlich das Beste Um ein char-Array für den 40-Bit-Speicher zu verwenden, um Ausrichtungsprobleme und die Notwendigkeit zu vermeiden, sich mit Pragmas zum Packen von Strukturen herumzuschlagen. Drittens: Bei diesem Entwurf wird davon ausgegangen, dass Sie mit 64-Bit-Arithmetik für Zwischenergebnisse einverstanden sind. Dies gilt nur für große Array-Speicher, den Sie mit Int40 verwenden würden; Viertens: Ich verstehe nicht alle Vorschläge, dass dies eine schlechte Idee ist. Lesen Sie einfach nach, was die Leute durchmachen, um Mesh-Datenstrukturen zu packen, und das sieht im Vergleich dazu wie ein Kinderspiel aus.
Was Sie wollen, ist eine Struktur, die nur zum Speichern von Daten als 40-Bit-Ints verwendet wird, aber implizit für die Arithmetik in int64_t konvertiert wird. Der einzige Trick besteht darin, die Vorzeichenerweiterung von 40 auf 64 Bit richtig durchzuführen. Wenn Sie mit vorzeichenlosen Ints gut zurechtkommen, kann der Code noch einfacher sein. Dies sollte Ihnen den Einstieg erleichtern.
#include <cstdint> #include <iostream> // Only intended for storage, automatically promotes to 64-bit for evaluation struct Int40 { Int40(int64_t x) { set(static_cast<uint64_t>(x)); } // implicit constructor operator int64_t() const { return get(); } // implicit conversion to 64-bit private: void set(uint64_t x) { setb<0>(x); setb<1>(x); setb<2>(x); setb<3>(x); setb<4>(x); }; int64_t get() const { return static_cast<int64_t>(getb<0>() | getb<1>() | getb<2>() | getb<3>() | getb<4>() | signx()); }; uint64_t signx() const { return (data[4] >> 7) * (uint64_t(((1 << 25) - 1)) << 39); }; template <int idx> uint64_t getb() const { return static_cast<uint64_t>(data[idx]) << (8 * idx); } template <int idx> void setb(uint64_t x) { data[idx] = (x >> (8 * idx)) & 0xFF; } unsigned char data[5]; }; int main() { Int40 a = -1; Int40 b = -2; Int40 c = 1 << 16; std::cout << "sizeof(Int40) = " << sizeof(Int40) << std::endl; std::cout << a << "+" << b << "=" << (a+b) << std::endl; std::cout << c << "*" << c << "=" << (c*c) << std::endl; }
Hier ist der Link, um es live zu versuchen: http://rextester.com/QWKQU25252
quelle
constexpr
-ified C ++ 17-Implementierung.Sie können eine Bitfeldstruktur verwenden, die Ihnen jedoch keinen Speicher spart:
struct my_struct { unsigned long long a : 40; unsigned long long b : 24; };
Sie können ein beliebiges Vielfaches von 8 solchen 40-Bit-Variablen in einer Struktur zusammenfassen:
struct bits_16_16_8 { unsigned short x : 16; unsigned short y : 16; unsigned short z : 8; }; struct bits_8_16_16 { unsigned short x : 8; unsigned short y : 16; unsigned short z : 16; }; struct my_struct { struct bits_16_16_8 a1; struct bits_8_16_16 a2; struct bits_16_16_8 a3; struct bits_8_16_16 a4; struct bits_16_16_8 a5; struct bits_8_16_16 a6; struct bits_16_16_8 a7; struct bits_8_16_16 a8; };
Dies spart Ihnen etwas Speicher (im Vergleich zur Verwendung von 8 "Standard" 64-Bit-Variablen), aber Sie müssen jede Operation (und insbesondere arithmetische) für jede dieser Variablen in mehrere Operationen aufteilen.
Die Speicheroptimierung wird also gegen Laufzeitleistung "eingetauscht".
quelle
#pragma pack
sollte a "den Rest der Arbeit" erledigen. Übrigens gibt es hier andere Probleme, wie zum BeispielCHAR_BIT
theoretisch mehr als 8 odersizeof(short)
theoretisch 1 (z. B.CHAR_BIT
16). Ich zog es vor, die Antwort einfach und leicht lesbar zu halten, anstatt auf all diese Eckfälle hinzuweisen.sizeof
Bytes zählt.sizeof(my_struct)
nicht 5 Bytes auf jedem Compiler (oder möglicherweise auf jedem Compiler). In jedem Fall können Sie kein Array dieser Strukturen instanziieren, die 5 Bytes pro Eintrag widerspiegeln würden. Bitte überprüfen Sie Ihre Änderungen, bevor Sie sie festschreiben (insbesondere in Antworten anderer Benutzer).Wie aus den Kommentaren hervorgeht, ist dies eine ziemliche Aufgabe.
Wahrscheinlich ein unnötiger Aufwand, wenn Sie nicht viel RAM sparen möchten - dann ist es viel sinnvoller. (RAM-Einsparung wäre die Gesamtsumme der Bits, die über Millionen von
long
im RAM gespeicherten Werten gespeichert wurden.)Ich würde in Betracht ziehen, ein Array von 5 Bytes / Zeichen (5 * 8 Bits = 40 Bits) zu verwenden. Dann müssen Sie Bits von Ihrem (übergelaufenen int - daher a
long
) Wert in das Array von Bytes verschieben, um sie zu speichern.Um die Werte zu verwenden, verschieben Sie die Bits wieder in a
long
und Sie können den Wert verwenden.Dann beträgt Ihr RAM- und Dateispeicher des Werts 40 Bit (5 Byte), ABER Sie müssen die Datenausrichtung berücksichtigen, wenn Sie a verwenden möchten
struct
, um die 5 Bytes zu speichern . Lassen Sie mich wissen, wenn Sie näher auf diese Auswirkungen der Bitverschiebung und Datenausrichtung eingehen müssen.In ähnlicher Weise können Sie das 64-Bit verwenden
long
und andere Werte (möglicherweise 3 Zeichen) in den verbleibenden 24 Bit verbergen , die Sie nicht verwenden möchten. Wieder - Verwenden der Bitverschiebung zum Hinzufügen und Entfernen der 24-Bit-Werte.quelle
Eine andere Variante, die hilfreich sein könnte, wäre die Verwendung einer Struktur:
typedef struct TRIPLE_40 { uint32_t low[3]; uint8_t hi[3]; uint8_t padding; };
Eine solche Struktur würde 16 Bytes benötigen und, wenn sie mit 16 Bytes ausgerichtet wäre, vollständig in eine einzelne Cache-Zeile passen. Während das Identifizieren, welcher der zu verwendenden Teile der Struktur teurer sein kann, als wenn die Struktur vier statt drei Elemente enthalten würde, kann der Zugriff auf eine Cache-Zeile viel billiger sein als der Zugriff auf zwei. Wenn die Leistung wichtig ist, sollten einige Benchmarks verwendet werden, da einige Computer eine Divmod-3-Operation kostengünstig ausführen und hohe Kosten pro Cache-Zeilenabruf verursachen, während andere möglicherweise einen günstigeren Speicherzugriff und teureres Divmod-3 haben.
quelle
Ich werde das annehmen
unsigned char hugearray[5*size+3]; // +3 avoids overfetch of last element __int64 get_huge(unsigned index) { __int64 t; t = *(__int64 *)(&hugearray[index*5]); if (t & 0x0000008000000000LL) t |= 0xffffff0000000000LL; else t &= 0x000000ffffffffffLL; return t; } void set_huge(unsigned index, __int64 value) { unsigned char *p = &hugearray[index*5]; *(long *)p = value; p[4] = (value >> 32); }
Es kann schneller sein, das Get mit zwei Schichten zu handhaben.
__int64 get_huge(unsigned index) { return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24); }
quelle
unsigned char
, für das keine korrekte Ausrichtung garantiert werden kann__int64
. Auf einigen Plattformen wie x86-64 hat dies wahrscheinlich keine großen Auswirkungen auf den nicht optimierten Build (erwartete Leistungseinbußen), auf anderen ist dies jedoch problematisch - wie z. B. ARM. Bei optimierten Builds sind alle Wetten deaktiviert, da der Compiler beispielsweise Code mit erstellen darfmovaps
.memcpy
damit nicht ausgerichtete Ladevorgänge / Speicher portabel ausdrücken , ohne dass Verstöße gegen das strikte Aliasing wie diese Zeigerumwandlung auftreten. Moderne Compiler, die auf x86 (oder andere Plattformen mit effizienten nicht ausgerichteten Lasten) abzielen, verwenden einfach eine nicht ausgerichtete Last oder einen nicht ausgerichteten Speicher. Hier ist zum Beispiel ( godbolt.org/g/3BFhWf ) eine gehackte Version von Damons 40-Bit-Ganzzahl-C ++ - Klasse, die a verwendetchar value[5]
und mit gcc für x86-64 auf dieselbe Weise kompiliert wie diese. (Wenn Sie die Version verwenden, die überliest, anstatt separate Ladevorgänge durchzuführen, aber das ist auch ziemlich gut)Wenn Sie einige Milliarden von 40-Bit-Ganzzahlen mit Vorzeichen speichern und 8-Bit-Bytes annehmen möchten, können Sie 8 40-Bit-Ganzzahlen mit Vorzeichen in eine Struktur packen (im folgenden Code mit einem Array von Bytes) und Da diese Struktur normalerweise ausgerichtet ist, können Sie ein logisches Array solcher gepackter Gruppen erstellen und eine normale sequentielle Indizierung davon bereitstellen:
#include <limits.h> // CHAR_BIT #include <stdint.h> // int64_t #include <stdlib.h> // div, div_t, ptrdiff_t #include <vector> // std::vector #define STATIC_ASSERT( e ) static_assert( e, #e ) namespace cppx { using Byte = unsigned char; using Index = ptrdiff_t; using Size = Index; // For non-negative values: auto roundup_div( const int64_t a, const int64_t b ) -> int64_t { return (a + b - 1)/b; } } // namespace cppx namespace int40 { using cppx::Byte; using cppx::Index; using cppx::Size; using cppx::roundup_div; using std::vector; STATIC_ASSERT( CHAR_BIT == 8 ); STATIC_ASSERT( sizeof( int64_t ) == 8 ); const int bits_per_value = 40; const int bytes_per_value = bits_per_value/8; struct Packed_values { enum{ n = sizeof( int64_t ) }; Byte bytes[n*bytes_per_value]; auto value( const int i ) const -> int64_t { int64_t result = 0; for( int j = bytes_per_value - 1; j >= 0; --j ) { result = (result << 8) | bytes[i*bytes_per_value + j]; } const int64_t first_negative = int64_t( 1 ) << (bits_per_value - 1); if( result >= first_negative ) { result = (int64_t( -1 ) << bits_per_value) | result; } return result; } void set_value( const int i, int64_t value ) { for( int j = 0; j < bytes_per_value; ++j ) { bytes[i*bytes_per_value + j] = value & 0xFF; value >>= 8; } } }; STATIC_ASSERT( sizeof( Packed_values ) == bytes_per_value*Packed_values::n ); class Packed_vector { private: Size size_; vector<Packed_values> data_; public: auto size() const -> Size { return size_; } auto value( const Index i ) const -> int64_t { const auto where = div( i, Packed_values::n ); return data_[where.quot].value( where.rem ); } void set_value( const Index i, const int64_t value ) { const auto where = div( i, Packed_values::n ); data_[where.quot].set_value( where.rem, value ); } Packed_vector( const Size size ) : size_( size ) , data_( roundup_div( size, Packed_values::n ) ) {} }; } // namespace int40 #include <iostream> auto main() -> int { using namespace std; cout << "Size of struct is " << sizeof( int40::Packed_values ) << endl; int40::Packed_vector values( 25 ); for( int i = 0; i < values.size(); ++i ) { values.set_value( i, i - 10 ); } for( int i = 0; i < values.size(); ++i ) { cout << values.value( i ) << " "; } cout << endl; }
quelle
movsx
Byte-Last, eine Verschiebung und dann ein ODER in den niedrigen 32-Bit-Werten verwenden. Die meisten anderen Architekturen haben auch vorzeichenverlängernde enge Lasten.) Sie sind bereits auf das implementierungsdefinierte Verhalten beim Verschieben negativer Zahlen nach angewiesen Tun Sie, was Sie wollen.static_assert
Sie jedoch nach Möglichkeit die Semantik, auf die Sie sich verlassen.Wenn Sie mit Milliarden von Ganzzahlen umgehen müssen, würde ich versuchen, Arrays mit 40-Bit-Zahlen anstelle einzelner 40-Bit-Zahlen zu kapseln . Auf diese Weise können Sie verschiedene Array-Implementierungen testen (z. B. eine Implementierung, die Daten im laufenden Betrieb komprimiert, oder eine, die weniger verwendete Daten auf der Festplatte speichert), ohne den Rest Ihres Codes zu ändern.
Hier ist eine Beispielimplementierung ( http://rextester.com/SVITH57679 ):
class Int64Array { char* buffer; public: static const int BYTE_PER_ITEM = 5; Int64Array(size_t s) { buffer=(char*)malloc(s*BYTE_PER_ITEM); } ~Int64Array() { free(buffer); } class Item { char* dataPtr; public: Item(char* dataPtr) : dataPtr(dataPtr){} inline operator int64_t() { int64_t value=0; memcpy(&value, dataPtr, BYTE_PER_ITEM); // Assumes little endian byte order! return value; } inline Item& operator = (int64_t value) { memcpy(dataPtr, &value, BYTE_PER_ITEM); // Assumes little endian byte order! return *this; } }; inline Item operator[](size_t index) { return Item(buffer+index*BYTE_PER_ITEM); } };
Hinweis: Die
memcpy
Konvertierung von 40-Bit in 64-Bit ist im Grunde genommen ein undefiniertes Verhalten, da sie von einer geringen Endianness ausgeht. Es sollte jedoch auf x86-Plattformen funktionieren.Hinweis 2: Dies ist offensichtlich ein Proof-of-Concept-Code, kein produktionsbereiter Code. Um es in realen Projekten zu verwenden, müssten Sie (unter anderem) hinzufügen:
Item
hat Referenzsemantik, nicht Wertesemantik, was für ungewöhnlich istoperator[]
; Sie könnten das wahrscheinlich mit einigen cleveren Konvertierungstricks vom Typ C ++ umgehenAll dies sollte für einen C ++ - Programmierer unkompliziert sein, aber sie würden den Beispielcode viel länger machen, ohne ihn klarer zu machen, deshalb habe ich beschlossen, sie wegzulassen.
quelle
Ja, das können Sie, und es spart Platz für große Mengen von Zahlen
Sie benötigen eine Klasse, die einen std :: -Vektor eines vorzeichenlosen Integer-Typs enthält.
Sie benötigen Mitgliedsfunktionen, um eine Ganzzahl zu speichern und abzurufen. Wenn Sie beispielsweise 64 Ganzzahlen mit jeweils 40 Bit speichern möchten, verwenden Sie einen Vektor mit 40 Ganzzahlen mit jeweils 64 Bit. Dann benötigen Sie eine Methode, die eine Ganzzahl mit Index in [0,64] speichert, und eine Methode, um eine solche Ganzzahl abzurufen.
Diese Methoden führen einige Verschiebungsoperationen und auch einige binäre | aus und & .
Ich füge hier noch keine weiteren Details hinzu, da Ihre Frage nicht sehr spezifisch ist. Wissen Sie, wie viele Ganzzahlen Sie speichern möchten? Kennen Sie es während der Kompilierungszeit? Wissen Sie es, wenn das Programm startet? Wie sollen die ganzen Zahlen organisiert sein? Wie ein Array? Wie eine Karte? Sie sollten dies alles wissen, bevor Sie versuchen, die Ganzzahlen in weniger Speicher zu komprimieren.
quelle
std::vector<>
ist definitiv nicht der richtige Weg: Es hat eine Grundfläche von mindestens drei Zeigern, dh 96 oder 192 Bit, je nach Architektur. Das ist viel schlimmer als die 64 Bits von along long
.Hier gibt es einige Antworten zur Implementierung, daher möchte ich über Architektur sprechen.
Normalerweise erweitern wir 32-Bit-Werte auf 64-Bit-Werte, um ein Überlaufen zu vermeiden, da unsere Architekturen für die Verarbeitung von 64-Bit-Werten ausgelegt sind.
Die meisten Architekturen sind für die Verwendung mit ganzen Zahlen ausgelegt, deren Größe eine Potenz von 2 ist, da dies die Hardware erheblich vereinfacht. Aufgaben wie das Zwischenspeichern sind auf diese Weise viel einfacher: Es gibt eine große Anzahl von Divisionen und Moduloperationen, die durch Bitmaskierung und Verschiebungen ersetzt werden können, wenn Sie sich an Potenzen von 2 halten.
Als Beispiel dafür, wie wichtig dies ist, definiert die C ++ 11-Spezifikation Multithreading-Race-Cases basierend auf "Speicherorten". Ein Speicherort ist in 1.7.3 definiert:
Mit anderen Worten, wenn Sie die Bitfelder von C ++ verwenden, müssen Sie das gesamte Multithreading sorgfältig durchführen. Zwei benachbarte Bitfelder müssen als derselbe Speicherort behandelt werden, auch wenn Sie möchten, dass Berechnungen über mehrere Threads verteilt werden können. Dies ist für C ++ sehr ungewöhnlich und kann zu Frustrationen bei Entwicklern führen, wenn Sie sich darüber Sorgen machen müssen.
Die meisten Prozessoren verfügen über eine Speicherarchitektur, die jeweils 32-Bit- oder 64-Bit-Speicherblöcke abruft. Die Verwendung von 40-Bit-Werten führt daher zu einer überraschenden Anzahl zusätzlicher Speicherzugriffe, was sich erheblich auf die Laufzeit auswirkt. Berücksichtigen Sie die Ausrichtungsprobleme:
40-bit word to access: 32-bit accesses 64bit-accesses word 0: [0,40) 2 1 word 1: [40,80) 2 2 word 2: [80,120) 2 2 word 3: [120,160) 2 2 word 4: [160,200) 2 2 word 5: [200,240) 2 2 word 6: [240,280) 2 2 word 7: [280,320) 2 1
Bei einer 64-Bit-Architektur ist eines von vier Wörtern "normale Geschwindigkeit". Für den Rest müssen doppelt so viele Daten abgerufen werden. Wenn Sie viele Cache-Fehler erhalten, kann dies die Leistung beeinträchtigen. Selbst wenn Sie Cache-Treffer erhalten, müssen Sie die Daten entpacken und in ein 64-Bit-Register umpacken, um sie zu verwenden (was möglicherweise sogar einen schwer vorhersehbaren Zweig mit sich bringt).
Es ist durchaus möglich, dass dies die Kosten wert ist
Es gibt Situationen, in denen diese Strafen akzeptabel sind. Wenn Sie über eine große Menge speicherresidenter Daten verfügen, die gut indiziert sind, sind die Speichereinsparungen möglicherweise die Leistungseinbußen wert. Wenn Sie für jeden Wert umfangreiche Berechnungen durchführen, sind die Kosten möglicherweise minimal. In diesem Fall können Sie eine der oben genannten Lösungen implementieren. Hier sind jedoch einige Empfehlungen.
quelle
struct { char val[5]; };
mit memcpy), befinden sich die mehreren Ladevorgänge oder Speicher in derselben Cache-Zeile. Das ist billig (wenn Sie zuvor keinen Engpass bei den Anweisungen oder beim L1D-Durchsatz hatten) und verursacht keine zusätzlichen Cache-Fehler, verhindert jedoch die automatische Vektorisierung, sodass Sie möglicherweise nicht einmal mit dem Speicher für den sequentiellen Zugriff Schritt halten. (In der Regel wird erwartet, dass es auf Zielen, die nicht ausgerichtete Ladevorgänge unterstützen, zu einer 32-Bit- + einer 8-Bit-Last kompiliert wird. die Strafe ist höher).uintptr_t
und Ausrichtungsprüfungen / breite Lasten ( wie Sie es in asm in Betracht ziehen könnten ). Oder haben Sie darüber gesprochen, dies zusätzlich zu tunuint64_t []
und mit einemif
herauszufinden, ob Sie nur eine Ladung benötigen? Das klingt nach einer schlechten Idee, anstatt nur Shifts zu verwenden, um uint64_t zu / vonuint32_t
und zu teilen und zusammenzuführenuint8_t
, und memcpy oder eine Struktur zu verwenden, um sie für die Ausrichtung zu gruppieren.struct __attribute__((packed)) { unsigned long long v:40; };
wirklich ein einziger riesiger Speicherort wäre. Aber selbst wenn Strukturgrenzen keine Speicherortgrenzen sind, können Sie eine verwenden, um diesint end:0
zu gewährleisten ( Modulo-Compiler-Fehler ! und stackoverflow.com/questions/47008183/… )Dies erfordert ein verlustfreies Streaming im Speicher. Wenn es sich um eine Big-Data-Anwendung handelt, sind dichte Packtricks bestenfalls taktische Lösungen für das, was eine recht anständige Unterstützung auf Middleware- oder Systemebene zu erfordern scheint. Sie müssten gründlich getestet werden, um sicherzustellen, dass alle Bits unversehrt wiederhergestellt werden können. Die Auswirkungen auf die Leistung sind nicht trivial und sehr hardwareabhängig, da die CPU-Caching-Architektur gestört wird (z. B. Cache-Zeilen gegenüber der Packungsstruktur). Jemand erwähnte komplexe Vernetzungsstrukturen: Diese werden häufig so optimiert, dass sie mit bestimmten Caching-Architekturen zusammenarbeiten.
Aus den Anforderungen geht nicht hervor, ob das OP einen wahlfreien Zugriff benötigt. Angesichts der Größe der Daten ist es wahrscheinlicher, dass nur lokaler Zugriff auf relativ kleine Blöcke erforderlich ist, die zum Abrufen hierarchisch organisiert sind. Sogar die Hardware tut dies bei großen Speichergrößen (NUMA). Wie verlustfreie Filmformate zeigen, sollte es möglich sein, wahlfreien Zugriff in Blöcken ("Frames") zu erhalten, ohne dass der gesamte Datensatz in den Hot-Memory (aus dem komprimierten In-Memory-Backing-Speicher) geladen werden muss.
Ich kenne ein schnelles Datenbanksystem (kdb von KX Systems, um nur eines zu nennen, aber ich weiß, dass es andere gibt), das extrem große Datenmengen verarbeiten kann, indem scheinbar große Datenmengen aus dem Hintergrundspeicher scheinbar speicherabgebildet werden. Es besteht die Möglichkeit, die Daten im laufenden Betrieb transparent zu komprimieren und zu erweitern.
quelle
Wenn Sie wirklich ein Array von 40-Bit-Ganzzahlen wollen (was Sie natürlich nicht haben können), würde ich einfach ein Array von 32-Bit- und ein Array von 8-Bit-Ganzzahlen kombinieren.
So lesen Sie einen Wert x am Index i:
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
So schreiben Sie einen Wert x in den Index i:
Offensichtlich gut in eine Klasse eingekapselt, mit Inline-Funktionen für maximale Geschwindigkeit.
Es gibt eine Situation, in der dies nicht optimal ist, und in der Sie wirklich zufällig auf viele Elemente zugreifen, sodass jeder Zugriff auf ein int-Array einen Cache-Fehler darstellt. Hier erhalten Sie jedes Mal zwei Cache-Fehler. Um dies zu vermeiden, definieren Sie eine 32-Byte-Struktur, die ein Array von sechs uint32_t, ein Array von sechs uint8_t und zwei nicht verwendete Bytes enthält (41 2/3 Bits pro Nummer). Der Code für den Zugriff auf ein Element ist etwas komplizierter, aber beide Komponenten des Elements befinden sich in derselben Cache-Zeile.
quelle