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


Wenn zum Beispiel eine 32-Bit-Ganzzahl überläuft, anstatt zu aktualisieren int zu longKönnen wir einen 40-Bit-Typ verwenden, wenn wir nur innerhalb von 2 einen Bereich benötigen?40, so dass wir 24 (64-40) Bits für jede ganze Zahl speichern?

Wenn das so ist, wie?

Ich muss mit Milliarden umgehen und der Platz ist eine größere Einschränkung.


75
2017-12-30 12:22


Ursprung


Antworten:


Ja aber...

Es ist sicherlich möglich, aber es ist normalerweise unsinnig (für jedes Programm, das nicht verwendet Milliarden dieser Nummern):

#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
    uint64_t var : 40;
};

Hier, var wird tatsächlich eine Breite von 40 Bits auf Kosten von haben viel weniger effizienter Code generiert (es stellt sich heraus, dass "viel" sehr falsch ist - der gemessene Overhead beträgt nur 1-2%, siehe unten), und meistens ohne Erfolg. Sofern Sie keinen weiteren 24-Bit-Wert (oder einen 8- und 16-Bit-Wert) benötigen, den Sie in die gleiche Struktur packen möchten, verliert die Ausrichtung alles, was Sie möglicherweise erhalten.

In jedem Fall, außer wenn Sie Milliarden davon haben, wird der effektive Unterschied im Speicherverbrauch nicht bemerkbar sein (aber der zusätzliche Code, der benötigt wird, um das Bitfeld zu verwalten, wird auffallen!).

Hinweis:
Die Frage wurde inzwischen aktualisiert, um dies zu berücksichtigen Milliarden Da Zahlen vonnöten sind, kann dies durchaus sinnvoll sein, vorausgesetzt, Sie ergreifen Maßnahmen, um die durch Strukturanpassung und Auffüllung bedingten Gewinne nicht zu verlieren, dh entweder durch Speichern von etwas anderem in den verbleibenden 24 Bits oder durch Speichern Ihres 40-Bit Werte in Strukturen von jeweils 8 oder Vielfachen davon.
Speichern von drei Bytes eine Milliarde Mal Es lohnt sich, da es merklich weniger Speicherseiten benötigt und somit weniger Cache- und TLB-Fehler verursacht, und vor allem Seitenfehler (ein einzelner Seitenfehler, der Zehn-Millionen-Anweisungen wichtet).

Während das obige Snippet die verbleibenden 24 Bits nicht verwendet (es zeigt lediglich den Teil "40 Bits verwenden"), wird etwas Ähnliches wie folgt notwendig sein, um den Ansatz in einem Sinn des Bewahrens von Speicher nützlich zu machen - vorausgesetzt, dass Sie haben in der Tat andere "nützliche" Daten in die Löcher zu stecken:

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, so dass nichts verschwendet wird, wenn Sie z. ein Array von einer Milliarde solcher Strukturen (auch ohne compilerspezifische Erweiterungen). Wenn Sie keinen 8-Bit-Wert verwenden, können Sie auch einen 48-Bit- und einen 16-Bit-Wert verwenden (mit einem größeren Überlaufbereich).
Alternativ könnten 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 eine operator[] das stellt die lineare Array-Funktionalität wieder her und verbirgt die Strukturkomplexität).

Aktualisieren:
Schrieb eine schnelle Testsuite, um zu sehen, welchen Overhead die Bitfelder (und der Operator, der mit Bitfeldreferenzen überlädt) hätten. Gebuchter Code (wegen Länge) bei gcc.godbolt.deTestausgabe von meiner Win7-64 Maschine ist:

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 der Operator, der mit Bitfeldreferenz als Bequemlichkeitsfaktor überlädt, ist ziemlich drastisch (ungefähr 3x Zunahme), wenn er auf Cache-freundliche Weise linear Daten zugreift. Auf der anderen Seite ist es beim Direktzugriff kaum noch von Bedeutung.

Diese Timings legen nahe, dass die Verwendung von 64-Bit-Ganzzahlen besser wäre, da sie insgesamt zwar immer noch schneller sind als Bitfelder (obwohl mehr Speicher belegt wird), aber natürlich nicht die Kosten von Seitenfehlern mit viel größeren Datensätzen. Es könnte sehr anders aussehen, wenn du keinen physischen RAM mehr hast (ich habe das nicht getestet).


82
2017-12-30 12:32



Sie können 4 * 40bit-Ganzzahlen ganz einfach 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 wiederum wie folgt 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 )
}

53
2017-12-30 15:52



Sie könnten Variable-Length Encoding (VLE) in Betracht ziehen

Vermutlich haben Sie viele dieser Zahlen irgendwo gespeichert (im RAM, auf der Festplatte, senden Sie sie über das Netzwerk, usw.), und nehmen Sie sie dann nacheinander und machen Sie etwas Verarbeitung.

Ein Ansatz wäre zu kodieren sie verwenden VLE. Von Google's Protobuf Dokumentation (CreativeCommons-Lizenz)

Varints sind eine Methode zum Serialisieren von ganzen Zahlen   ein oder mehrere Bytes. Kleinere Zahlen nehmen eine kleinere Anzahl von Bytes.

Jedes Byte in einer Variablen, außer dem letzten Byte, hat die signifikanteste   Bit (msb) gesetzt - dies zeigt an, dass weitere Bytes kommen.   Die unteren 7 Bits jedes Bytes werden verwendet, um das Zweierkomplement zu speichern   Darstellung der Zahl in Gruppen von 7 Bits, am wenigsten signifikant   Gruppe zuerst.

Also, hier ist zum Beispiel die Nummer 1 - es ist ein einzelnes Byte, also die MSB   ist nicht festgelegt:

0000 0001

Und hier sind 300 - das ist ein bisschen komplizierter:

1010 1100 0000 0010

Wie finden Sie heraus, dass das 300 ist? Zuerst legst du die MSB ab   jedes Byte, da dies nur da ist, um uns zu sagen, ob wir das erreicht haben   Ende der Zahl (wie Sie sehen können, ist es im ersten Byte als dort gesetzt   ist mehr als ein Byte in der Varint)

Pros

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

Nachteile

  • Sie zahlen ein zusätzliches Bit für jede 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 besser mit einem Bitfeld-Ansatz.
  • Sie werden die Fähigkeit verlieren, einfach zu einer Zahl zu springen, die ihrem Index entspricht (Sie müssen alle vorherigen Elemente in einem Array zumindest teilweise analysieren, um auf das aktuelle zuzugreifen.
  • Sie werden eine Art von Decodierung benötigen, bevor Sie etwas Nützliches mit den Zahlen machen (obwohl das auch für andere Ansätze gilt, wie Bitfelder).

25
2017-12-30 20:29



(Edit: Vor allem - was Sie wollen ist möglich, und macht in einigen Fällen Sinn; Ich musste ähnliche Dinge tun, wenn ich etwas für die Netflix-Herausforderung zu tun versuchte und nur 1 GB Speicher hatte; Zweitens - es ist wahrscheinlich am besten ein Char-Array für den 40-Bit-Speicher zu verwenden, um Ausrichtungsprobleme zu vermeiden und die Notwendigkeit, sich mit Pragma-Packs zu befassen Drittens: Dieser Entwurf geht davon aus, dass Sie mit 64-Bit-Arithmetik für Zwischenergebnisse nur für große bin Array-Speicher, den Sie Int40 verwenden würden; Viertens: Ich bekomme nicht alle Vorschläge, dass dies eine schlechte Idee ist, lesen Sie einfach, was Leute durchgehen, um Mesh-Datenstrukturen zu verpacken, und dies sieht im Vergleich wie ein Kinderspiel aus).

Was Sie wollen, ist eine Struktur, die nur zum Speichern von Daten als 40-Bit-Ints verwendet wird, aber implizit in Int64_t für Arithmetik konvertiert. Der einzige Trick besteht darin, die Zeichenerweiterung von 40 auf 64 Bit richtig zu machen. Wenn Sie mit nicht signierten Ints zufrieden sind, kann der Code noch einfacher sein. Dies sollte Ihnen den Einstieg ermöglichen.

#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


19
2017-12-30 16:44



Sie können eine Bit-Feld-Struktur verwenden, aber es wird Ihnen keinen Speicher sparen:

struct my_struct
{
    unsigned long long a : 40;
    unsigned long long b : 24;
};

Sie können ein beliebiges Vielfaches von 8 solcher 40-Bit Variablen in eine Struktur quetschen:

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.

Also wird die Speicheroptimierung für die Laufzeit-Performance "getauscht".


16
2017-12-30 12:32



Wie die Kommentare zeigen, ist dies eine ziemliche Aufgabe.

Wahrscheinlich ein unnötiger Ärger es sei denn Sie möchten viel RAM sparen - dann macht es viel mehr Sinn. (RAM-Speicher wäre die Summe der Bits, die über Millionen gespeichert wurden long Werte im RAM gespeichert)

Ich würde in Betracht ziehen, ein Array von 5 Bytes / Char (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, um sie zu speichern.

Um die Werte zu verwenden, verschieben Sie die Bits wieder nach a long und Sie können den Wert verwenden.

Dann ist Ihr RAM und Dateispeicher des Werts 40 Bits (5 Bytes), ABER Sie müssen Datenausrichtung berücksichtigen, wenn Sie vorhaben, ein zu verwenden struct um die 5 Bytes zu halten. Lassen Sie mich wissen, wenn Sie die Auswirkungen auf die Bitverschiebung und die Datenausrichtung näher ausführen möchten.

Ähnlich könnten Sie das 64-Bit verwenden long, und verbergen andere Werte (3 Zeichen vielleicht) in den restlichen 24 Bits, die Sie nicht verwenden möchten. Erneut - Verwenden der Bitverschiebung zum Hinzufügen und Entfernen der 24-Bit-Werte.


8
2017-12-30 12:36



Eine andere Variante, die hilfreich sein könnte, wäre eine Struktur zu verwenden:

typedef struct TRIPLE_40 {
  uint32_t low[3];
  uint8_t hi[3];
  uint8_t padding;
};

Solch eine Struktur würde 16 Bytes benötigen und würde, wenn 16 Bytes ausgerichtet würden, vollständig in eine einzelne Cachezeile passen. Während das Identifizieren, welcher der Teile der zu verwendenden Struktur teurer sein kann, als es der Fall wäre, wenn die Struktur vier statt drei Elemente enthält, kann der Zugriff auf eine Cachezeile viel billiger sein als der Zugriff auf zwei. Wenn die Leistung wichtig ist, sollte man einige Benchmarks verwenden, da einige Maschinen eine divmod-3-Operation billig ausführen können und hohe Kosten pro Cache-Zeilen-Abruf haben, während andere billigeren Speicherzugriff und teureren divmod-3 haben könnten.


6
2017-12-31 05:28



Ich nehme das an

  1. das ist C, und
  2. Sie benötigen ein einzelnes, großes Array von 40-Bit-Nummern und
  3. Sie sind 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 Anzahl der 40-Bit-Nummern definiert, die Sie benötigen

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, mit zwei Schichten umzugehen.

__int64 get_huge(unsigned index)
{
    return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24);
}

6
2017-12-30 21:58



Für den Fall, dass einige Milliarden 40-Bit-Ganzzahlen mit Vorzeichen gespeichert werden und 8-Bit-Bytes vorausgesetzt werden, können Sie 8 40-Bit-Ganzzahlen mit Vorzeichen in eine Struktur packen (im folgenden Code verwenden Sie dazu ein Array von Bytes), und Da diese Struktur normalerweise ausgerichtet ist, können Sie dann ein logisches Array solcher gepackten Gruppen erstellen und eine gewöhnliche sequentielle Indizierung für Folgendes 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;
}

5
2018-01-01 00:47



Wenn Sie Milliarden von Zahlen verarbeiten müssen, würde ich versuchen, sie zu verschleiern Arrays von 40-Bit-Nummern anstelle von Single 40-Bit-Nummern. Auf diese Weise können Sie verschiedene Arrayimplementierungen testen (z. B. eine Implementierung, die Daten im laufenden Betrieb komprimiert, oder möglicherweise eine, die weniger verwendete Daten auf der Festplatte speichert.), Ohne den restlichen Code 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);
    }
};

Beachten Sie das memcpyDie Umwandlung von 40 Bit zu 64 Bit ist im Grunde undefiniertes Verhalten, da sie Little-Endianz annimmt. Es sollte jedoch auf x86-Plattformen funktionieren.

Hinweis 2: Offensichtlich handelt es sich hierbei um einen Proof-of-Concept-Code, nicht um einen produktionsfertigen Code. Um es in realen Projekten zu verwenden, müssten Sie (unter anderem) hinzufügen:

  • Fehlerbehandlung (malloc kann fehlschlagen!)
  • Kopieren des Konstruktors (z. B. durch Kopieren von Daten, Hinzufügen einer Referenzzählung oder durch Freigeben des Kopierkonstruktors)
  • Konstruktor verschieben
  • const Überlastungen
  • STL-kompatible Iteratoren
  • Grenzen prüft auf Indizes (im Debug-Build)
  • Bereich prüft auf Werte (im Debug-Build)
  • behauptet für die impliziten Annahmen (Little-Endianess)
  • Wie es ist, Item hat Referenzsemantik, nicht Wert Semantik, die für ungewöhnlich ist operator[]; Sie könnten das wahrscheinlich mit einigen cleveren C ++ - Konvertierungstricks umgehen

All diese Dinge sollten für einen C ++ - Programmierer einfach sein, aber sie würden den Beispielcode viel länger machen, ohne ihn klarer zu machen, also habe ich beschlossen, sie wegzulassen.


5
2017-12-30 20:59