Массив пар 3-х битных элементов

Question

Из-за ограничений памяти я должен хранить несколько пар значений в массиве с 6 бит / пара (3 бита / значение). Проблема возникает, когда я хочу получить доступ к этому массиву как обычный, основанный на индексе пары. Массив выглядит так

|--byte 0 | --byte 1 | --byte 2  
|00000011 | 11112222 | 22333333   ...  and so on, the pattern repeats.  
|------|-------|--------|------|  
 pair 0  pair 1  pair 2  pair 3 

 => 4 pairs / 3 bytes

Вы можете видеть, что иногда (для индексов, кратных 1 и 2) требуется 2 байта для извлечения значений.
Я сделал функцию, которая с учетом индекса возвращает первое значение из пары (3 бита) и другое (также 3 бита).

void GetPair(char *array, int index, int &value1, int &value2) {
    int groupIndex = index >> 2; // Divide by 4 to get the index of the group of 3 bytes (with 4 pairs)
    // We use 16 bits starting with the first byte from the group for indexes divisible by 0 and 1,  
    // 16 bits starting with the second byte when divisible by 2 and 3
    short int value = *(short int *)(array + groupIndex + ((index & 0x02) >> 1));

    switch(index & 0x03) { // index % 4
        case 0: { 
            // extract first 3 bits
            value1 = (value & 0xE000) >> 13;
            // extract the next 3 bits
            value2 = (value & 0x1C00) >> 10;
            break;
        }
        case 1: {
            value1 = (value & 0x380) >> 7;
            value2 = (value & 0x70) >> 4;
            break;
        }
        case 2: {
            value1 = (value & 0xE00) >> 9;
            value2 = (value & 0x1C0) >> 6;
            break;
        }
        case 3: {
            value1 = (value & 0x38) >> 2;
            value2 = value & 0x7;
            break;
        }
}

Теперь мой вопрос: Есть ли более быстрый способ извлечь эти значения?

Я сделал тест, и при использовании 2 байтов / пара (1 байт / значение) требуется около 6 секунд для доступа ко всем парам (всего 53) 100 миллионов раз. При использовании компактного массива это занимает около 22 секунд :( (возможно, потому что ему нужно вычислить все эти маски и битовые сдвиги).
Я пытался объяснить как можно яснее ... простите, если нет.

Answer 1

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

Вы можете исключить оператор switch, используя таблицу поиска, чтобы найти правильные значения shift и mask.

short int shift1[4] = { 13, 7, 9, 2 };
short int shift2[4] = { 10, 4, 6, 0 };
short int mask1[4] = { 0xe000, 0x0380, 0x0e00, 0x38 };
short int mask2[4] = { 0x1c00, 0x0700, 0x1c, 0x07 };

int index = value % 4; /* you're not saving any time by using bitwise AND but you are making your code less readable */
value1 = (value & mask1[index]) >> shift1;
value2 = (value & mask2[index]) >> shift2;

Идея состоит в том, что вы устраняете любые ветвления. Однако каждый путь настолько короток, что может не иметь значения. В моем тестировании (gcc на PowerPC) разницы почти не было. Однако пропускная способность памяти на этом компьютере достаточно мала, поэтому обе версии работают быстрее, чем просто прямой доступ к массиву и 1 байт на значение.

Answer 2

Как насчет этого? Это исключает доступ к памяти для масок и значений сдвига. (Конечно, (непереносимое) предположение состоит в том, что char является 8-битным, а short - 16-битным. Также предполагается, что индекс * 6 не переполняется int.)

void GetPair(char *array, int index, int &value1, int &value2)
{
   unsigned shift = 10 - index * 6 % 8;
   unsigned short data = (*(unsigned short *)(array + index * 6 / 8) >> shift) & 0x3f;
   value2 = data & 7;
   value1 = data >> 3;
}

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

Answer 3

Современные архитектуры даже не обращаются к отдельным байтам; они адресуют 4-байтовые слова и извлекают часть, которую вы запросили. Так что на стандартном оборудовании вы можете увидеть улучшение, используя 4 байта на пару и извлекая части самостоятельно. 4 байта на запись тоже могут быть быстрее, но стоимость загрузки второго слова, вероятно, больше, чем стоимость маскировки и сдвига. А может и нет; современные процессоры странные. Заполни профиль и посмотри!