Самый быстрый способ написать бит-поток на современном оборудовании x86

Ответ 1

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

unsigned char* membuff; 
unsigned bit_pos; // current BIT position in the buffer, so it max size is 512Mb

// input bit buffer: we'll decode the byte address so that it even, and the DWORD from that address will surely have at least 17 free bits
inline unsigned int get_bits(unsigned int bit_cnt){ // bit_cnt MUST be in range 0..17
    unsigned int byte_offset = bit_pos >> 3;
    byte_offset &= ~1;  // rounding down by 2.
    unsigned int bits = *(unsigned int*)(membuff + byte_offset);
    bits >>= bit_pos & 0xF;
    bit_pos += bit_cnt;
    return bits & BIT_MASKS[bit_cnt];
};

// output buffer, the whole destination should be memset'ed to 0
inline unsigned int put_bits(unsigned int val, unsigned int bit_cnt){
    unsigned int byte_offset = bit_pos >> 3;
    byte_offset &= ~1;
    *(unsigned int*)(membuff + byte_offset) |= val << (bit_pos & 0xf);
    bit_pos += bit_cnt;
};

Ответ 2

Трудно ответить вообще, потому что это зависит от многих факторов, таких как распределение бит-размеров, которое вы читаете, шаблон вызова в клиентском коде, а также аппаратное обеспечение и компилятор. В общем, два возможных подхода для чтения (записи) из битового потока:

• Использование 32-битного или 64-битного буфера и условное чтение (запись) из базового массива, когда вам нужно больше бит. Этот подход использует ваш метод write_bits.
• Безусловное чтение (запись) из базового массива в каждом битовом потоке, чтение (запись), а затем перенос и маскирование результирующих значений.

Основные преимущества (1) включают:

• Только чтение из базового буфера минимально необходимое количество раз выравнивается.
• Быстрый путь (без чтения массива) выполняется несколько быстрее, поскольку ему не нужно выполнять чтение и соответствующую математику адресации.
• Метод, скорее всего, будет лучше, поскольку он не имеет чтения - если у вас есть несколько последовательных вызовов read_bits, например, компилятор может потенциально объединить много логики и создать действительно быстрый код.

Основное преимущество (2) состоит в том, что он полностью предсказуем - он не содержит непредсказуемых ветвей.

Просто потому, что есть только одно преимущество для (2), это не значит, что это хуже: это преимущество может легко сокрушить все остальное.

В частности, вы можете проанализировать вероятное поведение ветвления вашего алгоритма на основе двух факторов:

• Как часто битстеам нужно читать из базового буфера?
• Насколько предсказуемо количество вызовов перед чтением?

Например, если вы читаете 1 бит 50% времени и 2 бит 50% времени, вы будете делать 64 / 1.5 = ~42 чтение (если вы можете использовать 64-битный буфер), прежде чем требовать базового чтения. Это благоприятствует методу (1), поскольку считывание базовых данных является нечастым, даже если оно неверно предсказано. С другой стороны, если вы обычно читаете 20 бит, вы будете читать из базовых каждых нескольких вызовов. Вероятно, это благоприятствует подходу (2), если только шаблон базовых чтений не предсказуем. Например, если вы всегда читаете от 22 до 30 бит, вы, возможно, всегда будете принимать ровно три вызова, чтобы вывести буфер и прочитать базовый массив ¹. Таким образом, ветвь будет хорошо обоснована и (1) будет оставаться на месте.

Аналогично, это зависит от того, как вы называете эти методы, и как компилятор может встроить и упростить код. Особенно, если вы когда-либо повторяете методы с постоянным размером времени компиляции, возможно много упрощения. Мало что упрощение доступно, когда кодовое слово известно во время компиляции.

Наконец, вы сможете повысить производительность, предложив более сложный API. Это в основном относится к варианту реализации (1). Например, вы можете предложить вызов ensure_available(unsigned size), который гарантирует, что для чтения доступны как минимум size биты (обычно ограниченные размером буфера). Затем вы можете прочитать это количество бит, используя непроверенные вызовы, которые не проверяют размер буфера. Это может помочь вам сократить ошибочные прогнозы, заставив буфер заполняться предсказуемым графиком и позволяет писать более простые непроверенные методы.

¹ Это зависит от того, как именно написана ваша "прочитанная из базовой" процедура, так как здесь есть несколько вариантов: некоторые из них всегда заполняются до 64 бит, некоторые заполняют между 57 и 64- бит (т.е. чтение целого числа байтов), а некоторые могут заполнять между 32 или 33 и 64 битами (например, ваш пример, который читает 32-битные фрагменты).

Ответ 3

Вам, вероятно, придется подождать до 2013 года, чтобы заполучить настоящий HW, но новые инструкции "Haswell" приведут к соответствующим векторизованным сдвигам (т.е. способность сдвигать каждый векторный элемент на разные суммы, указанные в другом векторе) на x86/AVX. Не уверенный в деталях (много времени, чтобы понять их), но это, несомненно, обеспечит значительное улучшение производительности в коде построения потока бит.

Ответ 4

У меня нет времени написать его для вас (не слишком уверен, что ваш образец на самом деле достаточно для этого достаточно), но если вам нужно, я могу думать о

• с использованием таблиц перевода для различных смещений сдвига бит ввода/вывода; Эта оптимизация имела бы смысл для фиксированных единиц бит n (при n достаточно больших (8 бит?), Чтобы ожидать прироста производительности) По существу, вы сможете сделать

  destloc &= (lookuptable[bits_left_in_buffer][input_offset][codeword]);
  

отказ от ответственности: это очень неряшливый псевдокод, я просто надеюсь, что он передает мою идею таблицы поиска o предотвращает арифметику битрейта

• записать его в сборку (я знаю, что i386 имеет XLAT, но опять же хороший компилятор уже может использовать что-то вроде этого) ; Кроме того, XLAT кажется ограниченным 8 битами и регистром AL, поэтому он не очень универсален.

Update

Предупреждение. Обязательно используйте профилировщик и проверьте свою оптимизацию для правильности и скорости. Использование таблицы поиска может привести к снижению производительности в свете местоположения ссылки. Таким образом, вам может потребоваться изменить поток потокового потока на одном ядре (установить привязку потоков), чтобы получить преимущества, и вам, возможно, придется адаптировать размер таблицы поиска к кэшу L2 процессора.

Als, посмотрите SIMD, SSE4 или набор графических процессоров (CUDA), если вы знаете, что у вас будут определенные функции в вашем распоряжении.