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

Question

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

Какой самый быстрый способ упаковать два байта в один? У меня есть большой массив байтов. Каждый байт представляет число не больше 15 (4-битное число). Из-за этого я мог упаковать два байта в один, поместив первый байт в верхний полубайт, а последний в нижний полубайт.

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

3

assembly byte-shifting c++

Решение

Другие решения

Сначала я подхожу к этому на C или C ++, измеряю, а затем прибегаю к сборке, только если производительность неприемлема. В С:

void packarray(unsigned char *buff, int len)
{
unsigned char *packed;
unsigned char byte;
assert(len >= 2);  /* len must be at least 2 bytes */
assert((len & 1) != 1);   /* len must be an even number */
for (packed = buff; len>0; len-=2) {
byte= *buff++;
*packed++ = (byte << 4) | *buff++;
}
}

Предупреждение: непроверенный код

0

Источник

Accepted Answer

Очевидно, что если ваш массив большой, потребуется некоторое время — вам нужно пройти через все это.

Первое, что я хотел бы сделать, это создать таблицу поиска из двух байтов в один, поэтому вам не нужно сдвигать и / или брать следующие два байта, искать их смещение и получать результирующий байт.

Эта таблица поиска должна иметь 2 ^ 12 записей (вам нужно всего 4 байта из старшего байта) и хорошо вписываться в кэш L1 вашего ЦП. Это может быть быстрее, чем сдвиг и / или.

С другой стороны, если вы загружаете 8 байтов за раз (на 64-битном процессоре, поскольку они все в настоящее время), вы можете превратить его в 4 байта и сохранить их. Вы сможете распараллелить это (разделите массив на 4 части, и каждое ядро будет обрабатывать одну часть).

Если бы были инструкции, которые берут байты 0, 2, 4 и 6 из 64-битного регистра и помещают их в 32-битный регистр, все будет сделано.

ОБНОВИТЬ:
Вы упомянули в вопросе у вас есть несколько миллионов байтов. В этом случае не беспокойтесь. Разница между высокооптимизированной сборкой и наивной реализацией в C не окупится. Просто загрузите данные по два байта за раз, сдвиг и / или два куска в один байт и сохраните в целевом массиве. Обработка 1 МБ данных должна быть мгновенной.

4