Очень быстрый способ проверить бит набора в C

Я использую какой-то BitStream в своем коде, который имеет функцию read_bit(). Эта функция называется очень часто (более одного миллиарда раз в одном потоке). Это то, что структура BITSTREAM выглядит следующим образом:Очень быстрый способ проверить бит набора в C

typedef struct BitStream { 
    unsigned char* data; 
    unsigned int size; 
    unsigned int currentByte; 
    unsigned char buffer; 
    unsigned char bitsInBuffer; 
} BitStream;

И read_bit() -функции определяется следующим образом:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) { 
    unsigned int byte = bitPos/8; 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mask = 128 >> (bitPos & 7); 
    if (mask & byteVal) { 
     return 1; 
    } else { 
     return 0; 
    } 
}

Теперь я узнал, путем проб и ошибок, что линия unsigned char mask = 128 >> (bitPos & 7); очень медленный. Есть ли способ ускорить проверку? Я уже пытался использовать массив, который индексирует 8 различных возможных масок, но это происходит не быстрее (я думаю, из-за доступа к памяти).

EDIT: Я пробовал много ответов за прошедшую неделю и выполнил множество тестов, но улучшения производительности не было. В итоге мне удалось добиться улучшения за 10 секунд, изменив порядок бит в потоке битов. Таким образом, вместо того, чтобы использовать маску 128 >> (bitPos & 7), я использовал функцию:

unsigned char bitstream_read_bit_2(BitStream* stream, const unsigned long long bitPos) { 
    unsigned int byte = (unsigned int) (bitPos/8); 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mod = bitPos & 7; 
    return (byteVal & (1 << mod)) >> mod; 
}

я, очевидно, также изменили соответствующую запись-функцию.

источник

2016-10-22 Pieter Verschaffelt

Как медленно в данный момент? Насколько «медленный» (но более быстрый, чем текущий) приемлем?Сколько памяти вы можете выделить для этого? Можете ли вы включить разборку текущей реализации? – Amit

Конкретная линия использует около 10 секунд из общего числа 28 секунд. По крайней мере, это возможно, чтобы заставить его работать за 5 секунд (или меньше). Я могу выделить для этого довольно немного памяти (не менее 10 МБ). Я скоро отправлю разборку. Заранее благодарю –

Замените '128 >> (bitPos & 7)' на массив статических масок. –

Вот как я изначально оптимизирован код:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) 
{ 
    return !!(stream->data[(bitPos/8)] & (128 >> (bitPos % 8))); 
}

Но сам вызов функции накладных расходов, скорее всего, больше инструкций, чем код немного щипание внутри него. Так что если вы действительно хотите, чтобы оптимизировать его еще дальше, давайте воспользоваться встраиванием и просто преобразовать его в макрос:

#define bitstream_read_bit(stream, bitPos) (!!((stream)->data[((bitPos)/8)] & (128 >> ((bitPos) % 8))))

источник

2016-10-22 17:49:13 selbie

Выполняете ли вы какие-либо проблемы с производительностью, используя '%'? – Mike

Это не имеет значения. Накладные расходы функции намного больше, чем затраты на неэффективную работу по настройке битов. Но это не значит, что мы не можем объединить оба наших решения вместе. – selbie

Или воспользоваться встроенной функцией, префикс функции с помощью 'static inline'? –

Очевидное первое улучшением является сдвиг загруженного значения вместо маски:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) { 
    unsigned int byte = bitPos/8; 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char maskVal = byteVal >> (bitPos & 7); 
    return maskVal & 1; 
}

Это устраняет необходимость в условном (Нет if или ! или ?:).

Если вы можете изменить struct, я бы рекомендовал доступ к более крупных единиц, чем байт:

#include <stddef.h> 
#include <limits.h> 
#include <stdbool.h> 

typedef struct WBitStream 
{ 
    size_t *data; 
    size_t size; 
} WBitStream; 

bool Wbitstream_read_bit(WBitStream* stream, size_t bitPos) 
{ 
    size_t location = bitPos/(sizeof(size_t)*CHAR_BIT); 
    size_t locval = stream->data[location]; 
    size_t maskval = locval >> (bitPos & (sizeof(size_t)*CHAR_BIT-1)); 
    return maskval & 1; 
}

В некоторых процессорах (в частности, общий x86), маска переключающего-сумма является NOP, так как команда нативного сдвига процессора учитывает только младшие бит суммы сдвига в любом случае. По крайней мере, gcc знает об этом.

источник

2016-10-22 18:35:56 EOF

Я испытал на optimzed макросъемки по сравнению с вашим начальным исходным кодом:

static unsigned char tMask[8] = { 128, 64, 32, 16, 8, 4, 2, 1 }; 

#define BITSTREAM_READ_BIT1(stream, bitPos) (((128 >> (bitPos & 7)) & stream->data[bitPos >> 3])!=0) 
#define BITSTREAM_READ_BIT2(stream, bitPos) (((tMask[(bitPos & 7)]) & stream->data[bitPos >> 3])!=0)

Замена маски вычисления по маске в массиве не увеличивает производительность. Основной разрыв между функцией и макросом (в 6 раз быстрее на моем компьютере с 80 000 000 вызовов).

И статическое встроенное использование находится недалеко от макроса.

источник

2016-10-22 18:47:08

Очень быстрый способ проверить бит набора в C

ответ

Смежные вопросы