Schnellste Methode zum Aufteilen einer 32-Bit-Zahl in Bytes in C++

Question

Ich schreibe einen Code, der für die Datenkomprimierung von CLSID-Strukturen konzipiert ist.Ich speichere sie als komprimierten Stream von 128-Bit-Ganzzahlen.Der betreffende Code muss jedoch in der Lage sein, ungültige CLSIDs in den Stream einzufügen.Um dies zu erreichen, habe ich sie als eine große Schnur belassen.Auf der Festplatte würde es etwa so aussehen:

+--------------------------+-----------------+------------------------+
|                          |                 |                        |
| Length of Invalid String | Invalid String  | Compressed Data Stream |
|                          |                 |                        |
+--------------------------+-----------------+------------------------+

Um die Länge der Zeichenfolge zu kodieren, muss ich die 32-Bit-Ganzzahl, die der Länge der Zeichenfolge entspricht, Byte für Byte ausgeben.Hier ist mein aktueller Code:

std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
compressedBytes.push_back((BYTE)  invalidLength        & 0x000000FF);
compressedBytes.push_back((BYTE) (invalidLength >>= 8) & 0x000000FF));
compressedBytes.push_back((BYTE) (invalidLength >>= 8) & 0x000000FF));
compressedBytes.push_back((BYTE) (invalidLength >>= 8));

Dieser Code wird nicht oft aufgerufen, aber in der Dekodierungsphase muss eine ähnliche Struktur vorhanden sein, die viele tausend Male aufgerufen wird.Ich bin gespannt, ob dies die effizienteste Methode ist oder ob jemand eine bessere finden kann?

Vielen Dank an alle!

Billy3

BEARBEITEN:Nachdem ich einige der Antworten durchgesehen hatte, habe ich dieses Mini-Testprogramm erstellt, um herauszufinden, welches am schnellsten war:

// temp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <windows.h>
#include <ctime>
#include <iostream>
#include <vector>

void testAssignedShifts();
void testRawShifts();
void testUnion();

int _tmain(int argc, _TCHAR* argv[])
{
    std::clock_t startTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testAssignedShifts();
    }
    std::clock_t assignedShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testRawShifts();
    }
    std::clock_t rawShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testUnion();
    }
    std::clock_t unionFinishedTime = std::clock();
    std::printf(
        "Execution time for assigned shifts: %08u clocks\n"
        "Execution time for raw shifts:      %08u clocks\n"
        "Execution time for union:           %08u clocks\n\n",
        assignedShiftsFinishedTime - startTime,
        rawShiftsFinishedTime - assignedShiftsFinishedTime,
        unionFinishedTime - rawShiftsFinishedTime);
    startTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testAssignedShifts();
    }
    assignedShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testRawShifts();
    }
    rawShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testUnion();
    }
    unionFinishedTime = std::clock();
    std::printf(
        "Execution time for assigned shifts: %08u clocks\n"
        "Execution time for raw shifts:      %08u clocks\n"
        "Execution time for union:           %08u clocks\n\n"
        "Finished. Terminate!\n\n",
        assignedShiftsFinishedTime - startTime,
        rawShiftsFinishedTime - assignedShiftsFinishedTime,
        unionFinishedTime - rawShiftsFinishedTime);

    system("pause");
    return 0;
}

void testAssignedShifts()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    DWORD invalidLength = (DWORD) invalidClsids.length();
    compressedBytes.push_back((BYTE)  invalidLength);
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
}
void testRawShifts()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    DWORD invalidLength = (DWORD) invalidClsids.length();
    compressedBytes.push_back((BYTE) invalidLength);
    compressedBytes.push_back((BYTE) (invalidLength >>  8));
    compressedBytes.push_back((BYTE) (invalidLength >>  16));
    compressedBytes.push_back((BYTE) (invalidLength >>  24));
}

typedef union _choice
{
    DWORD dwordVal;
    BYTE bytes[4];
} choice;

void testUnion()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    choice invalidLength;
    invalidLength.dwordVal = (DWORD) invalidClsids.length();
    compressedBytes.push_back(invalidLength.bytes[0]);
    compressedBytes.push_back(invalidLength.bytes[1]);
    compressedBytes.push_back(invalidLength.bytes[2]);
    compressedBytes.push_back(invalidLength.bytes[3]);
}

Wenn Sie dies ein paar Mal ausführen, ergibt sich Folgendes:

Execution time for assigned shifts: 00012484 clocks
Execution time for raw shifts:      00012578 clocks
Execution time for union:           00013172 clocks

Execution time for assigned shifts: 00012594 clocks
Execution time for raw shifts:      00013140 clocks
Execution time for union:           00012782 clocks

Execution time for assigned shifts: 00012500 clocks
Execution time for raw shifts:      00012515 clocks
Execution time for union:           00012531 clocks

Execution time for assigned shifts: 00012391 clocks
Execution time for raw shifts:      00012469 clocks
Execution time for union:           00012500 clocks

Execution time for assigned shifts: 00012500 clocks
Execution time for raw shifts:      00012562 clocks
Execution time for union:           00012422 clocks

Execution time for assigned shifts: 00012484 clocks
Execution time for raw shifts:      00012407 clocks
Execution time for union:           00012468 clocks

Scheint ein Gleichstand zwischen den zugewiesenen Schichten und der Gewerkschaft zu sein.Da ich den Wert später brauchen werde, ist es Union!Danke!

Billy3

Answer 1

Verwenden Sie einfach eine Gewerkschaft:

assert(sizeof (DWORD) == sizeof (BYTE[4]));   // Sanity check

union either {
    DWORD dw;
    struct {
         BYTE b[4];
    } bytes;
};

either invalidLength;
invalidLength.dw = (DWORD) invalidClsids.length();
compressedBytes.push_back(either.bytes.b[0]);
compressedBytes.push_back(either.bytes.b[1]);
compressedBytes.push_back(either.bytes.b[2]);
compressedBytes.push_back(either.bytes.b[3]);

NOTIZ:Im Gegensatz zum Bit-Shifting-Ansatz in der ursprünglichen Frage erzeugt dieser Code eine Endian-abhängige Ausgabe. Dies ist nur dann von Bedeutung, wenn die Ausgabe eines Programms, das auf einem Computer läuft, auf einem Computer mit anderer Endianness gelesen wird – aber da es durch die Verwendung dieser Methode offenbar keine messbare Geschwindigkeitssteigerung zu geben scheint, können Sie genauso gut den portableren Bit-Shifting-Ansatz verwenden , nur für den Fall.

Answer 2

Dies ist wahrscheinlich so optimiert, wie Sie es bekommen werden.Bit-Twiddling-Operationen gehören zu den schnellsten, die auf dem Prozessor verfügbar sind.

Es kann schneller sein, >> 16, >> 24 statt >>= 8 >>= 8 – Sie reduzieren eine Aufgabe.

Ich glaube auch nicht, dass Sie das & brauchen, da Sie in ein BYTE umwandeln (was sollen ein 8-Bit-Zeichen sein), wird es ohnehin entsprechend gekürzt.(Ist es?korrigiere mich, wenn ich falsch liege)

Insgesamt handelt es sich jedoch um wirklich geringfügige Änderungen.Profilieren Sie es, um zu sehen, ob es tatsächlich einen Unterschied macht :P

Answer 3

Sie sollten mögliche Verbesserungen eher messen als vermuten, aber mein erster Gedanke ist, dass sie es sind Mai Gehen Sie wie folgt vor, um eine Vereinigung schneller durchzuführen:

typedef union {
    DWORD d;
    struct {
        BYTE b0;
        BYTE b1;
        BYTE b2;
        BYTE b3;
    } b;
} DWB;

std::vector<BYTE> compBytes;
DWB invLen;
invLen.d = (DWORD) invalidClsids.length();
compBytes.push_back(invalidLength.b.b3);
compBytes.push_back(invalidLength.b.b2);
compBytes.push_back(invalidLength.b.b1);
compBytes.push_back(invalidLength.b.b0);

Das Mai Seien Sie die richtige Reihenfolge für die Pushbacks, aber überprüfen Sie sie nur für den Fall – es hängt von der Endian-Qualität der CPU ab.

Answer 4

Eine wirklich schnelle Möglichkeit besteht darin, ein DWORD* (Einzelelement-Array) einfach als BYTE* (4-Element-Array) zu behandeln.Der Code ist auch viel besser lesbar.

Warnung:Ich habe das nicht zusammengestellt

Warnung:Dadurch ist Ihr Code von der Bytereihenfolge abhängig

std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
BYTE* lengthParts = &invalidLength;
static const int kLenghtPartsLength = sizeof(DWORD) / sizeof(BYTE);
for(int i = 0; i < kLenghtPartsLength; ++i)
    compressedBytes.push_back(lengthParts[i]);

Answer 5

compressedBytes.push_back(either.bytes.b[0]);
compressedBytes.push_back(either.bytes.b[1]);
compressedBytes.push_back(either.bytes.b[2]);
compressedBytes.push_back(either.bytes.b[3]);

Es gibt eine noch intelligentere und Schneller Weg!Sehen wir uns an, was dieser Code bewirkt und wie wir ihn verbessern können.

Dieser Code serialisiert die Ganzzahl Byte für Byte.Für jedes Byte wird push_back aufgerufen, wodurch der freie Speicherplatz im internen Vektorpuffer überprüft wird.Wenn wir keinen Platz für ein weiteres Byte haben, erfolgt eine Neuzuweisung des Speichers (Hinweis: langsam!).Zugegeben, die Neuzuweisung wird nicht häufig vorkommen (Neuzuweisungen erfolgen normalerweise durch Verdoppelung des vorhandenen Puffers).Anschließend wird das neue Byte kopiert und die interne Größe um eins erhöht.

Für vector<> gibt es eine Standardanforderung, die vorschreibt, dass der interne Puffer zusammenhängend sein muss.vector<> hat zufällig auch eine Operator& () Und Operator[] ().

Hier ist also der beste Code, den Sie finden können:

std::string invalidClsids("This is a test string");
std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
compressedBytes.resize(sizeof(DWORD)); // You probably want to make this much larger, to avoid resizing later.
// compressedBytes is as large as the length we want to serialize.
BYTE* p = &compressedBytes[0]; // This is valid code and designed by the standard for such cases. p points to a buffer that is at least as large as a DWORD.
*((DWORD*)p) = invalidLength;  // Copy all bytes in one go!

Der obige Gips kann in einem Arbeitsgang mit dem durchgeführt werden &compressedBytes[0] Aussage, aber es wird nicht schneller sein.Das ist besser lesbar.

NOTIZ!Die Serialisierung auf diese Weise (oder sogar mit der UNION-Methode) ist Endian-abhängig.Das heißt, auf einem Intel/AMD-Prozessor kommt das niedrigstwertige Byte zuerst, während auf einem Big-Endian-Rechner (PowerPC, Motorola...) das höchstwertige Byte zuerst kommt.Wenn Sie neutral sein wollen, Sie muss Verwenden Sie eine mathematische Methode (Schichten).

Answer 6

Tust du haben um es byteweise zu tun?Gibt es eine Möglichkeit, mit memcpy() einfach die gesamten 32 Bit auf einen Schlag in den Stream zu übertragen?Wenn Sie die Adresse des Puffers haben, den Sie in den Stream schreiben, können Sie ihn einfach dorthin kopieren?

Answer 7

Vielleicht ist es möglich, einen 32-Bit-Variablenzeiger zu erhalten, ihn in einen char-Zeiger umzuwandeln und char zu lesen, dann +1 zum Zeiger hinzuzufügen und das nächste Zeichen zu lesen ..Nur Theorie :) Ich weiß nicht, ob es funktioniert