Быстрый поиск и замена клев в int [c;microoptimisation]

Question

Это вариант Быстрый поиск некоторых кусков в два дюйма с одинаковым смещением (C, микрооптимизация) вопрос с другой задачей:

Задача состоит в том, чтобы найти предопределенный полубайт в int32 и заменить его другим полубайтом. Например, клев для поиска 0x5; клев на 0xe:

int:   0x3d542753 (input)
           ^   ^
output:0x3dE427E3 (output int)

Может быть другая пара клев для поиска и клев для замены (известная во время компиляции).

Я проверил свою программу, эта часть - одна из самых популярных (доказано gprof, 75% времени работает); и это называется очень-очень много раз (доказано gcov). Фактически это 3-й или 4-й цикл вложенных циклов, с оценкой числа прогонов (n ^ 3) * (2 ^ n) , для n = 18..24.

Мой текущий код работает медленно (я переписываю его как функцию, но это код из цикла):

static inline uint32_t nibble_replace (uint32_t A) __attribute__((always_inline))
{
  int i;
  uint32_t mask = 0xf;
  uint32_t search = 0x5;
  uint32_t replace = 0xe;
  for(i=0;i<8;i++) {
    if( (A&mask) == search ) 
        A = (A & (~mask) )   // clean i-th nibble
           | replace;        // and replace
    mask <<= 4; search <<= 4; replace <<= 4;
  }
  return A;
}

Можно ли переписать эту функцию и макрос параллельно, используя некоторую магию битовой логики? Магия - это что-то вроде (t-0x11111111)&(~t)-0x88888888 и, возможно, ее можно использовать с SSE *. Проверьте принятый ответ на связанный вопрос, чтобы почувствовать необходимую магию.

Мой компилятор - gcc452, а процессор - Intel Core2 Solo в 32-битном режиме (x86) или (в ближайшем будущем) в 64-битном режиме (x86-64).

Answer 1

Это казалось забавным вопросом, поэтому я написал решение, не глядя на другие ответы.В моей системе это примерно в 4,9 раза быстрее.В моей системе это также немного быстрее, чем решение DigitalRoss (~ 25% быстрее).

static inline uint32_t nibble_replace_2(uint32_t x)
{
    uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111;
    uint32_t y = (~(ONES * SEARCH)) ^ x;
    y &= y >> 2;
    y &= y >> 1;
    y &= ONES;
    y *= 15; /* This is faster than y |= y << 1; y |= y << 2; */
    return x ^ (((SEARCH ^ REPLACE) * ONES) & y);
}

Я бы объяснил, как это работает, но ... думаю, объяснение этого портит удовольствие.

Примечание по SIMD: Такие вещи очень и очень легко векторизовать.Вам даже не нужно знать, как использовать SSE или MMX.Вот как я его векторизовал:

static void nibble_replace_n(uint32_t *restrict p, uint32_t n)
{
    uint32_t i;
    for (i = 0; i < n; ++i) {
        uint32_t x = p[i];
        uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111;
        uint32_t y = (~(ONES * SEARCH)) ^ x;
        y &= y >> 2;
        y &= y >> 1;
        y &= ONES;
        y *= 15;
        p[i] = x ^ (((SEARCH ^ REPLACE) * ONES) & y);
    }
}

Используя GCC, эта функция автоматически преобразуется в код SSE на -O3, при условии правильного использования флага -march.Вы можете передать -ftree-vectorizer-verbose=2 в GCC и попросить распечатать, какие петли векторизованы, например:

$ gcc -std=gnu99 -march=native -O3 -Wall -Wextra -o opt opt.c
opt.c:66: note: LOOP VECTORIZED.

Автоматическая векторизация дала мне дополнительный прирост скорости примерно на 64%, а у меня даже не былочтобы добраться до руководства по процессору.

Редактировать: Я заметил дополнительное ускорение на 48%, изменив типы в версии с автоматическим вектором с uint32_t на uint16_t.Это увеличивает общее ускорение до 12 раз по сравнению с оригиналом.Изменение на uint8_t приводит к сбою векторизации.Я подозреваю, что есть некоторая существенная дополнительная скорость, которая может быть найдена при ручной сборке, если это так важно.

Редактировать 2: Изменено *= 7 на *= 15, это аннулирует тесты скорости.

Редактировать 3: Вот ретроспективное изменение:

static inline uint32_t nibble_replace_2(uint32_t x)
{
    uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111;
    uint32_t y = (~(ONES * SEARCH)) ^ x;
    y &= y >> 2;
    y &= y >> 1;
    y &= ONES;
    return x ^ (y * (SEARCH ^ REPLACE));
}