Оптимизация XOR `char` с старшим байтом` int` - PullRequest
Новая
       51

Оптимизация XOR `char` с старшим байтом` int`

0 голосов
/ 10 марта 2019

Пусть у нас есть int i и char c.

При использовании i ^= c компилятор будет XOR c с младшим байтом i и переведет код в один процессоринструкция.

Когда нам нужно XOR c с старшим байтом i, мы можем сделать что-то вроде этого: 

i ^= c << ((sizeof(i) - sizeof(c)) * 8)

, но компилятор сгенерирует две инструкции: XORи BIT-SHIFT.

Есть ли способ XOR char с старшим байтом int, который будет переведен в однопроцессорную инструкцию в C ++?

Ответы [ 3 ]

1 голос
/ 10 марта 2019

Если вы уверены в порядке байтов системы, например, установив __BYTE_ORDER__ или эквивалентный макрос в своей системе, вы можете сделать что-то вроде этого: 

#if // Somehow determing if little endian, so biggest byte at the end
    *(&reinterpret_cast<char&>(i) + sizeof i - 1) ^= c
#else
    // Is big endian, biggest byte at the beginning
    reinterpret_cast<char&>(i) ^= c
#endif
0 голосов
/ 17 мая 2019

Компиляторы действительно умны в отношении таких простых арифметических и побитовых операций.Они не делают этого просто потому, что они не могут , поскольку на этих архитектурах нет таких инструкций.Не стоит тратить драгоценное пространство кода операции на редко используемые операции, подобные этой.В любом случае, большинство операций выполняются во всем регистре, и работа только над частью регистра очень неэффективна для ЦП, потому что блоки выполнения с ненадлежащим порядком или переименования регистров должны будут работать намного усерднее.По этой причине инструкции x86-64 для 32-битных регистров обнуляют верхнюю часть полного 64-битного регистра или почему изменение младшей части регистра в x86 (например, AL или AX) может бытьмедленнее, чем изменение всего RAX.INC также может быть медленнее, чем ADD 1 из-за частичного обновления флага

Тем не менее, существуют архитектуры, которые могут комбинировать SHIFT и XOR вединственная инструкция, как ARM, потому что разработчики ARM потратили большую часть кодирования команд на предикацию и смену, торгуя за меньшее количество регистров.Но опять же ваша предпосылка неверна, потому что тот факт, что что-то может быть выполнено в одной инструкции, не означает, что это будет быстрее .Современные процессоры очень сложны, потому что каждая инструкция имеет различную задержку, пропускную способность и количество портов выполнения.Например, если ЦП может выполнять 4 пары SHIFT-затем-XOR параллельно, тогда очевидно, что он будет быстрее, чем другой ЦП, который может последовательно выполнять 4 отдельные инструкции SHIFT-XOR, при условии, что тактовый цикл равен

Это очень типичная XY проблема , потому что то, что вы думали, является просто неправильным способом.Для операций, которые нужно выполнять тысячи, миллионы и более раз, это работа GPU или SIMD блока

Например, это то, что Clangкомпилятор создает цикл XORing старшего байта i с c на процессоре x86 с AVX-512 

    vpslld  zmm0, zmm0, 24
    vpslld  zmm1, zmm1, 24
    vpslld  zmm2, zmm2, 24
    vpslld  zmm3, zmm3, 24
    vpxord  zmm0, zmm0, zmmword ptr [rdi + 4*rdx]
    vpxord  zmm1, zmm1, zmmword ptr [rdi + 4*rdx + 64]
    vpxord  zmm2, zmm2, zmmword ptr [rdi + 4*rdx + 128]
    vpxord  zmm3, zmm3, zmmword ptr [rdi + 4*rdx + 192]

Делая это, он достигает 16 SHIFT-и-XOR только с 2 инструкциями.Представь, как быстро это.Вот почему все высокопроизводительные архитектуры имеют своего рода SIMD, который легче выполнять быстро, а не бесполезную инструкцию SHIFT-XOR.Даже на ARM с SHIFT-XOR с одной инструкцией компилятор будет достаточно умен, чтобы знать, что SIMD быстрее, чем серия eor rX, rX, rY, lsl #24

    shl     v3.4s, v3.4s, 24
    shl     v2.4s, v2.4s, 24
    shl     v1.4s, v1.4s, 24
    shl     v0.4s, v0.4s, 24
    eor     v3.16b, v3.16b, v7.16b
    eor     v2.16b, v2.16b, v6.16b
    eor     v1.16b, v1.16b, v4.16b
    eor     v0.16b, v0.16b, v5.16b

Вот демонстрация для приведенных выше фрагментов

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

0 голосов
/ 11 марта 2019

Не думайте, что компилятор сгенерирует сдвиг с приведенным выше кодом.Большинство современных компиляторов умнее этого:

https://godbolt.org/z/b6l8qk

...