Wenn eine 32-Bit-Ganzzahl überläuft, können wir eine 40-Bit-Struktur anstelle einer 64-Bit-Struktur verwenden?

76

Wenn beispielsweise eine 32-Bit-Ganzzahl überläuft, können wir anstelle eines Upgrades intauf longeinen 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.

user1660982
quelle
5
Auch Speicher ist im Vergleich zu CPU-Zyklen sehr billig, um diese wertvollen Bytes zu speichern
Ed Heal
9
@ user1810087, Aniket ... woher weißt du, dass es unnötig ist? Oder dass es mehr Byte verbraucht als es speichert? Kennen Sie die Anforderungen und Einschränkungen? Vielleicht verarbeitet er TB von Daten, bei denen sich diese "wenigen Bytes" summieren?
Greenflow
24
@Aniket: Ich sehe einige Anwendungsfälle dafür, insbesondere wenn ich mit großen Datenmengen arbeite. Ich arbeite derzeit mit volumetrischen Simulationen in einem 1024 ^ 3-Würfel. Wir haben einen benutzerdefinierten 36-Bit-Datentyp implementiert, da dies den Unterschied ausmacht, ob unsere Anwendung mit 8 GB RAM verwendet werden kann oder nicht. Beispiel: 1024 ^ 3-Würfel mit 64 Bit = 8192 MB, 36 Bit = 4608 Bit. In diesem Fall spielt der kleine Code wirklich keine Rolle.
BDL
5
Es gibt einige Prozessoren, die Hardware-40-Bit-Ganzzahlen implementieren (EX: einige Texas Instruments-Prozessoren). Wenn Sie auf einem dieser Prozessoren laufen, würde ich sagen, ja, machen Sie weiter! Wenn Sie jedoch Hardware wie x86 verwenden, die nur 32- oder 64-Bit-Ganzzahlen enthält, überwiegen die Kosten wahrscheinlich die Vorteile der Verwendung von 40-Bit-Ganzzahlen.
Trevor Boyd Smith
24
@All: Wie wäre es, wenn Sie user1660982 entscheiden lassen, ob er es wirklich will oder nicht? Niemand hier kennt die Datenmenge oder ob Geschwindigkeit wichtig ist.
Deviantfan

Antworten:

82

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 varwird in der Tat eine Breite von 40 Bit auf Kosten von viel weniger 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).

Damon
quelle
1
Ich dachte das Gleiche, aber Bitfeldmitglieder mit mehr als 32 Bit sind eine gcc-Erweiterung und nicht Teil des C-Standards (versuchen Sie, Ihren Code mit zu kompilieren -Wpedantic).
Bitmaske
2
Interessant ... Clang groks es hier ganz gut (auch mit -Wpedantic). Wie mein GCC. War diese Beschränkung auf 32 Bit mit C ++ 11 möglicherweise gelockert?
Damon
2
Diese Antwort ist zwar nicht falsch, beantwortet die Frage jedoch nicht wirklich.
user694733
9
Außerdem werden Strukturen, die Bitfelder enthalten, mit der Strukturausrichtung aufgefüllt, die auf der Bitfeldzuweisungseinheit basiert. Wenn dies funktioniert, wird die Struktur sowieso auf 8 Byte aufgefüllt und Sie sparen keinen Platz.
Chris Dodd
3
Sie können das Packen von Bytes in den meisten Compilern erzwingen (dies ist ein Pragma, das von Compiler zu Compiler unterschiedlich ist), wodurch ein Array der Struktur entsprechend reduziert wird.
Joshua
54

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 )
}
runec
quelle
13
Ein Code-Snippet, das nach dem Auffüllen tatsächlich Speicherplatz spart, wird berücksichtigt! +1
Ben Voigt
1
Pro: Das spart tatsächlich Platz. Con: Dieser Code ist aufgrund der Indizierung wahrscheinlich SEHR langsam.
SamB
2
Es könnte sich lohnen, signed char hi[4];explizit zu verwenden; Plain charkann signiert oder nicht signiert sein.
Jonathan Leffler
4
Es könnte besser sein, uint_least32_tund int_least8_thier zu verwenden, als unsigned intund char. unsigned intmuss nur mindestens 16 Bit betragen. charwird immer mindestens 8 Bit sein, daher gibt es dort nicht so viele Probleme. Außerdem würde ich für den hiTeil 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!
Pete Becker
11
@SamB: Es ist nicht sofort klar, dass dies "SEHR" langsam sein wird. Die Sache ist, dass (vorausgesetzt, der Compiler ist so eingerichtet, dass er aggressiv optimiert - einschließlich Inlining - wie es für alles sein sollte, was "Milliarden" von Operationen betrifft!) Die gesamte Indizierung auf CPU-interne Operationen an Registern hinausläuft, die durchgeführt werden können in sehr wenigen Zyklen (dh schnell): normalerweise viel schneller als das Abrufen einer Cache-Zeile aus dem Speicher. Da wir jetzt insgesamt auf 35% weniger Speicher zugreifen als zuvor (aufgrund der Platzersparnis), können wir einen Nettogewinn erzielen. (Offensichtlich hängt dies von einer Menge ab - Messung empfohlen :))
psmears
25

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)

Varints sind eine Methode zum Serialisieren von Ganzzahlen mit einem oder mehreren Bytes. Kleinere Zahlen benötigen weniger Bytes.

Für jedes Byte in einer Variable, mit Ausnahme des letzten Bytes, ist das höchstwertige Bit (msb) gesetzt. Dies zeigt an, dass weitere Bytes kommen werden. Die unteren 7 Bits jedes Bytes werden verwendet, um die Zweierkomplementdarstellung der Zahl in Gruppen von 7 Bits zu speichern, wobei die niedrigstwertige Gruppe zuerst ist.

Hier ist zum Beispiel die Nummer 1 - es ist ein einzelnes Byte, also ist die msb nicht gesetzt:

0000 0001

Und hier sind 300 - das ist etwas komplizierter:

1010 1100 0000 0010

Wie stellen Sie fest, dass dies 300 sind? Zuerst löschen Sie die msb von jedem Byte, da dies nur dazu dient, uns mitzuteilen, ob wir das Ende der Zahl erreicht haben (wie Sie sehen können, wird es im ersten Byte gesetzt, da mehr als ein Byte im varint vorhanden ist).

Vorteile

  • Wenn Sie viele kleine Zahlen haben, werden Sie wahrscheinlich im Durchschnitt weniger als 40 Bytes pro Ganzzahl verwenden. Möglicherweise viel weniger.
  • Sie können in Zukunft größere Zahlen (mit mehr als 40 Bit) speichern, ohne für die kleinen eine Strafe zahlen zu müssen

Nachteile

  • Sie zahlen ein zusätzliches Bit für jeweils 7 signifikante Bits Ihrer Zahlen. Das bedeutet, dass eine Zahl mit 40 signifikanten Bits 6 Bytes benötigt. Wenn die meisten Ihrer Zahlen 40 signifikante Bits haben, sind Sie mit einem Bitfeldansatz besser dran.
  • Sie verlieren die Möglichkeit, aufgrund des Index leicht zu einer Zahl zu springen (Sie müssen alle vorherigen Elemente in einem Array zumindest teilweise analysieren, um auf die aktuelle zuzugreifen.
  • Sie benötigen eine Art Dekodierung, bevor Sie etwas Nützliches mit den Zahlen tun können (obwohl dies auch für andere Ansätze wie Bitfelder gilt).
Sam
quelle
Sie können die kleinste Einheit auf 16 oder 32 Bit ändern, um viel Speicherplatz zu sparen, wenn die meisten Werte mehr als 1 Byte
betragen,
3
Wenn die Zahlen, die OP zu speichern versucht, gleichmäßig verteilt sind, gibt es viel mehr große Zahlen als kleine, und die Codierung mit variabler Länge ist kontraproduktiv.
Russell Borogove
21

(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

Stefan Atev
quelle
In Übereinstimmung mit @Andreas ist dies mit vorhersehbarem Codegen unkompliziert, im Gegensatz zu den Antworten, die Bitfelder verwenden oder auf compilerspezifischem Packen beruhen. Hier ist eine constexpr-ified C ++ 17-Implementierung.
ildjarn
16

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".

Barak Manos
quelle
@barakmanos: Bist du sicher, dass deine neue Version besser ist?
Ben Voigt
@ BenVoigt: Auf VC2013 ist dies der Fall. Was ich nicht 100% sicher bin, ist, ob dies gemäß dem Sprachstandard geschieht oder ob es vom Compiler abhängig ist. Wenn letzteres der Fall ist, #pragma packsollte a "den Rest der Arbeit" erledigen. Übrigens gibt es hier andere Probleme, wie zum Beispiel CHAR_BITtheoretisch mehr als 8 oder sizeof(short)theoretisch 1 (z. B. CHAR_BIT16). Ich zog es vor, die Antwort einfach und leicht lesbar zu halten, anstatt auf all diese Eckfälle hinzuweisen.
Barak Manos
1
@MarcGlisse und mit 64 meinst du 8, weil sizeofBytes zählt.
user253751
1
@Inverse: Danke, aber Ihre Bearbeitung des ersten Teils machte die Eröffnungserklärung des zweiten Teils sinnlos . Außerdem (und noch schlimmer) war es falsch - 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).
Barak Manos
@immibis Nein, ich meinte wirklich 64, aber dieser Kommentar wurde vor der Bearbeitung gepostet (siehe den Verlauf, wenn Sie sehen möchten, worum es ging).
Marc Glisse
9

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 longim 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 longund 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 longund 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.

Grantly
quelle
6

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.

Superkatze
quelle
Beachten Sie, dass divmod-3 wahrscheinlich tatsächlich durch Multiplikation erfolgen würde.
SamB
@SamB: Normalerweise wird dies am besten mit einer Art Multiplikation durchgeführt, aber das kann zwischen den Implementierungen variieren. Auf so etwas wie einem Cortex-M0 wäre ein Divmod3 einer beliebigen 32-Bit-Nummer etwas teuer, und es wäre kein Problem, vollständig getrennte Abrufe für die 32-Bit-Teile und 40-Bit-Teile einer Nummer durchzuführen.
Supercat
6

Ich werde das annehmen

  1. das ist C und
  2. Sie benötigen ein einzelnes großes Array mit 40-Bit-Zahlen und
  3. Sie befinden sich auf einer Maschine, die Little-Endian ist, und
  4. Ihre Maschine ist intelligent genug, um die Ausrichtung zu handhaben
  5. Sie haben die Größe als die Anzahl der benötigten 40-Bit-Zahlen definiert

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);
}
cmm
quelle
4
Beachten Sie, dass Code undefiniertes Verhalten enthält 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 darf movaps.
Maciej Piechotka
1
Wahrscheinlich die einfachste Lösung von allen!
Anatolyg
Sicher, das sieht in C mit all dem Typ-Casting irgendwie hässlich aus, aber der resultierende Maschinencode wird einfach und schnell sein. Ihre Shift-Version von get ist höchstwahrscheinlich schneller, da sie nicht verzweigt. Es könnte weiter optimiert werden, indem aus 3 Bytes vor der Zahl gelesen wird, wodurch die Linksverschiebung gespart wird.
aaaaaaaaaaa
1
Sie können es dem Compiler überlassen, auf diese Weise eine effiziente Zeichenerweiterung durchzuführen . Dies sollte jedoch sorgfältig getestet werden, da ein nicht ausgerichteter Zugriff sehr kostspielig sein kann. Das separate Speichern des 5. Bytes wie in einigen anderen Lösungen könnte besser sein
phuclv
1
Sie können memcpydamit 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 verwendet char 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)
Peter Cordes
5

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;
}
Prost und hth. - Alf
quelle
Ich denke, Sie nehmen die Ergänzung von 2 für die Zeichenerweiterung an. Es denkt, es bricht mit dem Vorzeichen / der Größe, könnte aber mit dem Komplement von 1 funktionieren. Wie auch immer, für das 2er-Komplement wäre es wahrscheinlich einfacher und effizienter, den Compiler zu bitten, das letzte Byte für Sie auf 64 Bit vorzeichenweise zu erweitern, dann ODER in der unteren Hälfte. (Dann könnten x86-Compiler eine movsxByte-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.
Peter Cordes
@PeterCordes: Danke, da ist eine nicht erwähnte Annahme der Zweierkomplementform drin, ja. Ich weiß nicht, warum ich mich darauf verlassen habe. Rätselhaft.
Prost und hth. - Alf
Ich würde nicht auf Effizienz verzichten, nur um es auf Plattformen portierbar zu machen, auf denen niemand es jemals verwenden wird. Verwenden static_assertSie jedoch nach Möglichkeit die Semantik, auf die Sie sich verlassen.
Peter Cordes
5

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 memcpyKonvertierung 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:

  • Fehlerbehandlung (Malloc kann fehlschlagen!)
  • Kopierkonstruktor (z. B. durch Kopieren von Daten, Hinzufügen von Referenzzählungen oder durch Privatisieren des Kopierkonstruktors)
  • Konstruktor verschieben
  • const Überladungen
  • STL-kompatible Iteratoren
  • Bound-Checks für Indizes (im Debug-Build)
  • Bereichsprüfungen auf Werte (im Debug-Build)
  • behauptet für die impliziten Annahmen (Little-Endianness)
  • Wie es ist, Itemhat Referenzsemantik, nicht Wertesemantik, was für ungewöhnlich ist operator[]; Sie könnten das wahrscheinlich mit einigen cleveren Konvertierungstricks vom Typ C ++ umgehen

All 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.

Niki
quelle
@anatolyg: Ich habe versucht, Ihre Punkte in Anmerkung 2 zusammenzufassen. Sie können gerne zu dieser Liste hinzufügen ;-)
Niki
3

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.

Hans Klünder
quelle
40 * 64 = 2560 Bit können auf 1 cm (40,64) = 320 Bit pro "Block" reduziert werden, d. H. 5 64bit-ints
deviantfan
3
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 a long long.
cmaster
3
Hängt davon ab. Ein std :: vector für 100000000 Ganzzahlen ist in Ordnung. Wenn wir kleine Blöcke wie in einer anderen Antwort entwerfen wollen, wäre std :: vector Platzverschwendung.
Hans Klünder
3

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:

Ein Speicherort ist entweder ein Objekt vom Skalartyp oder eine maximale Folge benachbarter Bitfelder, die alle eine Breite ungleich Null haben.

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.

  • Verwenden Sie keine Bitfelder, es sei denn, Sie sind bereit, deren Kosten zu bezahlen. Wenn Sie beispielsweise ein Array von Bitfeldern haben und es für die Verarbeitung auf mehrere Threads aufteilen möchten, stecken Sie fest. Nach den Regeln von C ++ 11 bilden alle Bitfelder einen Speicherort und können daher jeweils nur von einem Thread aufgerufen werden (dies liegt daran, dass die Methode zum Packen der Bitfelder implementierungsdefiniert ist, sodass C ++ 11 dies nicht kann Hilfe bei der Verteilung auf nicht implementierungsdefinierte Weise)
  • Verwenden Sie keine Struktur, die eine 32-Bit-Ganzzahl und ein Zeichen enthält, um 40 Bytes zu erstellen. Die meisten Prozessoren erzwingen die Ausrichtung und Sie speichern kein einzelnes Byte.
  • Verwenden Sie homogene Datenstrukturen, z. B. ein Array von Zeichen oder ein Array von 64-Bit-Ganzzahlen. Es ist viel einfacher, die richtige Ausrichtung zu erreichen. (Und Sie behalten auch die Kontrolle über die Verpackung, was bedeutet, dass Sie ein Array zur Berechnung auf mehrere Threads aufteilen können, wenn Sie vorsichtig sind.)
  • Entwerfen Sie separate Lösungen für 32-Bit- und 64-Bit-Prozessoren, wenn Sie beide Plattformen unterstützen müssen. Da Sie etwas sehr Niedriges tun und sehr schlecht unterstützt werden, müssen Sie jeden Algorithmus individuell an seine Speicherarchitektur anpassen.
  • Denken Sie daran, dass sich die Multiplikation von 40-Bit-Zahlen von der Multiplikation von 64-Bit-Erweiterungen von 40-Bit-Zahlen unterscheidet, die auf 40 Bit reduziert wurden. Genau wie beim Umgang mit der x87-FPU müssen Sie sich daran erinnern, dass das Marshalling Ihrer Daten zwischen Bitgrößen Ihr Ergebnis verändert.
Cort Ammon
quelle
Wenn Ihre Nummern zusammenhängend sind (z. B. 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).
Peter Cordes
Eine Pack / Unpack-Strategie, die einen Zweig umfasst, ist möglich, aber kaum erwähnenswert, es sei denn, Sie erhalten manuell Super-Low-Level- uintptr_tund Ausrichtungsprüfungen / breite Lasten ( wie Sie es in asm in Betracht ziehen könnten ). Oder haben Sie darüber gesprochen, dies zusätzlich zu tun uint64_t []und mit einem ifherauszufinden, ob Sie nur eine Ladung benötigen? Das klingt nach einer schlechten Idee, anstatt nur Shifts zu verwenden, um uint64_t zu / von uint32_tund zu teilen und zusammenzuführen uint8_t, und memcpy oder eine Struktur zu verwenden, um sie für die Ausrichtung zu gruppieren.
Peter Cordes
Gemäß ISO C ++ 11 können Sie "einen Speicherort" durch ein Bitfeld mit einer Breite von Null abgrenzen. Ich bin nicht sicher, ob der Standard impliziert, dass ein Array von 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 dies int end:0zu gewährleisten ( Modulo-Compiler-Fehler ! und stackoverflow.com/questions/47008183/… )
Peter Cordes
3

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.

GuyB
quelle
2

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:

array8 [i] = x >> 32; array32 [i] = x;

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.

gnasher729
quelle
Würde dies nicht schreckliche Dinge für den Cache tun?
SamB