Самый быстрый способ разбить 32-битное число на байты в C ++ - PullRequest
Новая
       22

Самый быстрый способ разбить 32-битное число на байты в C ++

3 голосов
/ 12 апреля 2009

Я пишу фрагмент кода, предназначенный для сжатия данных в структурах CLSID. Я храню их как сжатый поток из 128-битных целых чисел. Однако рассматриваемый код должен иметь возможность помещать недопустимые идентификаторы CLSID в поток. Чтобы сделать это, я оставил их как одну большую строку. На диске это будет выглядеть примерно так: 

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

Чтобы закодировать длину строки, мне нужно вывести 32-разрядное целое число, которое является длиной строки по одному байту за раз. Вот мой текущий код: 

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));

Этот код будет вызываться не часто, но на этапе декодирования потребуется аналогичная структура, которая вызывается много тысяч раз. Мне любопытно, если это самый эффективный метод или кто-то может придумать один лучше?

Спасибо всем!

Billy3

EDIT: Изучив некоторые ответы, я создал эту мини-тестовую программу, чтобы увидеть, какая из них была самой быстрой: 

// 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]);
}

Выполнение этого несколько раз приводит к: 

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

Похоже, что есть связь между назначенными сменами и объединением. Поскольку значение мне понадобится позже, объединение это! Спасибо!

Billy3

Ответы [ 7 ]

8 голосов
/ 12 апреля 2009

Это, вероятно, так же оптимизировано, как вы получите. Операции с битовым переворотом - одни из самых быстрых на процессоре.

Может быть быстрее >> 16, >> 24 вместо >> = 8 >> = 8 - вы сокращаете назначение.

Также я не думаю, что вам нужен & - так как вы преобразуете в BYTE (который должен быть 8-битным символом), он все равно будет соответствующим образом обрезан. (Это? Поправьте меня, если я ошибаюсь)

В целом, это действительно незначительные изменения. Профилируйте это, чтобы видеть, действительно ли это имеет значение: P

6 голосов
/ 12 апреля 2009

Просто используйте союз: 

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]);

ПРИМЕЧАНИЕ. В отличие от подхода со сдвигом битов в исходном вопросе, этот код производит вывод, зависящий от порядка байтов. Это имеет значение только в том случае, если выходные данные программы, запущенной на одном компьютере, будут считываться на компьютере с другим endianness - но так как, похоже, нет никакого измеримого увеличения скорости от использования этого метода, вы можете также использовать более переносимый подход с битовым сдвигом, на всякий случай.

2 голосов
/ 12 апреля 2009

Вы должны измерить, а не угадать какое-либо потенциальное улучшение, но я сначала подумал, что может быстрее сделать объединение следующим образом: 

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);

То, что может быть правильным порядком для откатов, но проверьте на всякий случай - это зависит от порядкового номера ЦП.

1 голос
/ 12 апреля 2009 
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]);

Существует еще более умный и быстрый способ! Давайте посмотрим, что делает этот код и как мы можем его улучшить.

Этот код сериализует целое число, один байт за раз. Для каждого байта он вызывает push_back, который проверяет свободное пространство во внутреннем векторном буфере. Если у нас нет места для другого байта, произойдет перераспределение памяти (подсказка, медленно!). Конечно, перераспределение происходит не часто (обычно перераспределение происходит путем удвоения существующего буфера). Затем новый байт копируется, а внутренний размер увеличивается на единицу.

vector <> имеет стандартное требование, согласно которому внутренний буфер должен быть непрерывным. вектор <> также может иметь операторы & () и оператор [] () .

Итак, вот лучший код, который вы можете придумать: 

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!

Приведенное выше приведение может быть выполнено за один раз с помощью оператора & compressBytes [0] , но это не будет быстрее. Это более читабельно.

ВНИМАНИЕ! Сериализация таким способом (или даже методом UNION) зависит от порядка байтов. То есть на процессоре Intel / AMD младший байт будет первым, а на старшей машине (PowerPC, Motorola ...) на первом месте будет старший. Если вы хотите быть нейтральным, вы должны использовать математический метод (сдвиги).

1 голос
/ 12 апреля 2009

Очень быстрый способ - просто обработать DWORD * (массив из одного элемента) как BYTE * (массив из 4 элементов). Код также намного более читабелен.

Предупреждение: я не скомпилировал это

Предупреждение: это делает ваш код зависимым от порядка байтов 

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]);
0 голосов
/ 06 января 2011

Возможно, можно получить 32-битный указатель на переменную, преобразовать его в указатель на символ и прочитать символ, затем добавить +1 к указателю и прочитать следующий символ ... просто теория :) Я не знаю, работает ли он

0 голосов
/ 12 апреля 2009

У вас есть , чтобы сделать это по одному байту за раз? Есть ли способ, которым вы могли бы просто memcpy () все 32 бита в потоке одним махом? Если у вас есть адрес буфера, который вы записываете в поток, можете ли вы просто скопировать в него?

...