Эмуляция переменной бит-сдвига с использованием только постоянных сдвигов?

Ответ 1

Здесь вы идете...

Я решил попробовать это, так как Майк Актон утверждал, что это будет быстрее, чем использование микрокодированного сдвига CELL/PS3 на его сайте CellPerformance, где он предлагает избегайте косвенного сдвига. Тем не менее, во всех моих тестах использование микрокодированной версии было не только быстрее, чем полная родовая замена без замены для непрямого сдвига, тем меньше памяти для кода (1 инструкция).

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

template <typename T> FORCEINLINE T VariableShiftLeft(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=(nVal&bMask1) + nVal;   //nVal=((nVal<<1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal<<(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal<<(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal<<(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal<<(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}
template <typename T> FORCEINLINE T VariableShiftRight(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=((nVal>>1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal>>(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal>>(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal>>(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal>>(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}

EDIT: Примечание по isel() Я видел ваш isel() код на вашем сайте.

// if a >= 0, return x, else y
int isel( int a, int x, int y )
{
    int mask = a >> 31; // arithmetic shift right, splat out the sign bit
    // mask is 0xFFFFFFFF if (a < 0) and 0x00 otherwise.
    return x + ((y - x) & mask);
};

FWIW, если вы переписываете свой isel(), чтобы сделать маску и дополнение к маске, она будет быстрее на вашей цели PowerPC, поскольку компилятор достаточно умен, чтобы создать код операции andc. Он имеет такое же количество кодов операций, но в кодах операций есть меньше зависимых от результата к вводу-регистру. Две операции маски могут также выдаваться параллельно на суперскалярном процессоре. Это может быть 2-3 цикла быстрее, если все выстроено правильно. Вам просто нужно изменить возврат к этому для версий PowerPC:

return (x & (~mask)) + (y & mask);

Ответ 2

Как насчет этого:

if (y & 16) x <<= 16;
if (y & 8) x <<= 8;
if (y & 4) x <<= 4;
if (y & 2) x <<= 2;
if (y & 1) x <<= 1;

вероятно, потребуется больше времени для выполнения, но проще чередовать, если у вас есть другой код для перехода между ними.

Ответ 3

Предположим, что ваш максимальный сдвиг равен 31. Таким образом, величина сдвига является 5-битным числом. Поскольку сдвиг является кумулятивным, мы можем разбить его на пять постоянных сдвигов. Очевидная версия использует ветвление, но вы исключили это.

Пусть N будет числом от 1 до 5. Вы хотите сдвинуть x на 2 ^N, если бит, значение которого равно 2 ^N установлен в y, в противном случае сохраните x без изменений. Вот один из способов сделать это:

#define SHIFT(N) x = isel(((y >> N) & 1) - 1, x << (1 << N), x);

Макрос назначает x либо x << 2ᴺ либо x, в зависимости от того, установлен N- ^й бит в y или нет.

И тогда водитель:

SHIFT(1); SHIFT(2); SHIFT(3); SHIFT(4); SHIFT(5)

Обратите внимание, что N является макропеременной и становится постоянной.

Не знаю, будет ли это на самом деле быстрее, чем переменная смещение. Если это так, то возникает вопрос, почему микрокод не запустит это вместо этого...

Ответ 4

Это ломает голову. Я теперь отбросил полдюжины идей. Все они используют понятие о том, что добавление вещи к себе сдвигается влево 1, делая то же самое с сдвигами результатов слева 4 и так далее. Если вы сохраняете все частичные результаты для сдвига влево 0, 1, 2, 4, 8 и 16, то, тестируя биты 0-4 переменной сдвига, вы можете получить начальный сдвиг. Теперь сделайте это снова, один раз для каждого 1 бит в переменной сдвига. Честно говоря, вы можете отправить процессор на кофе.

Единственное место, где я искал бы реальную помощь, - это Хэнк Уоррен Hacker Delight (что является единственной полезной частью этого ответа).

Ответ 5

Как насчет этого:

int[] multiplicands = { 1, 2, 4, 8, 16, 32, ... etc ...};

int ShiftByVar( int x, int y )
{
    //return x << y;
    return x * multiplicands[y];
}

Ответ 6

Здесь есть несколько хороших вещей, связанных с манипуляцией черными магами: Расширенная манипуляция бит fu (блог Christer Ericson)

Не знаю, применимо ли какое-либо из них, но если есть способ, вероятно, есть какие-то намеки на этот путь где-то там.

Ответ 7

Если число смен можно рассчитать заранее, у меня есть две идеи, которые могут сработать

• Использование самоизменяющегося кода

  Просто измените величину смены непосредственно в инструкции. Альтернативно генерировать код динамически для функций с переменным сдвигом

• Если возможно, сгруппируйте значения с одним и тем же количеством сдвигов и выполните операцию одновременно, используя указатель устройства или функции Duff, чтобы минимизировать ошибочное прогнозирование ветвлений.

  // shift by constant functions
  typedef int (*shiftFunc)(int);    // the shift function
  #define SHL(n) int shl##n(int x) { return x << (n); }
  SHL(1)
  SHL(2)
  SHL(3)
  ...
  shiftFunc shiftLeft[] = { shl1, shl2, shl3... };
  
  int arr[MAX];       // all the values that need to be shifted with the same amount
  shiftFunc shl = shiftLeft[3]; // when you want to shift by 3
  for (int i = 0; i < MAX; i++)
      arr[i] = shl(arr[i]);
  

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

  Редактировать: Как прокомментировано, к сожалению, нет никакого предсказания ветвления при переходе, чтобы зарегистрироваться вообще, поэтому единственный способ, которым это могло бы работать, - генерировать код, как я сказал выше, или использовать SIMD

Если диапазон значений невелик, справочная таблица является еще одним возможным решением

#define S(x, n) ((x) + 0) << (n), ((x) + 1) << (n), ((x) + 2) << (n), ((x) + 3) << (n), \
                ((x) + 4) << (n), ((x) + 5) << (n), ((x) + 6) << (n), ((x) + 7 << (n)
#define S2(x, n)    S((x + 0)*8, n), S((x + 1)*8, n), S((x + 2)*8, n), S((x + 3)*8, n), \
                    S((x + 4)*8, n), S((x + 5)*8, n), S((x + 6)*8, n), S((x + 7)*8, n)
uint8_t shl[256][8] = {
    { S2(0U, 0), S2(8U, 0), S2(16U, 0), S2(24U, 0) },
    { S2(0U, 1), S2(8U, 1), S2(16U, 1), S2(24U, 1) },
    ...
    { S2(0U, 7), S2(8U, 7), S2(16U, 7), S2(24U, 7) },
}

Теперь x << n - это просто shl[x][n] где x - это uint8_t. Таблица стоит 2 КБ (8 × 256 B) памяти. Однако для 16-битных значений вам понадобится таблица размером 1 МБ (16 × 64 КБ), которая все еще может быть жизнеспособной, и вы можете сделать 32-битный сдвиг, комбинируя два 16-битных сдвига вместе

Ответ 8

Здесь что-то, что тривиально невозможно:

int result= value;

int shift_accumulator= value;

for (int i= 0; i<5; ++i)
{
    result += shift_accumulator & (-(k & 1)); // replace with isel if appropriate
    shift_accumulator += shift_accumulator;
    k >>= 1;
}