Любой возможный код, который может переворачивать бит / целое число /bool между 0 и 1 в одной инструкции CPU
Может ли одна инструкция x86 переключать логическое значение между "0" и "1"?
Я думал о следующих путях, но все они приводят к двум инструкциям с флагом -O3 для gcc.
status =! status;
status = 1 - status;
status = status == 0 ? 1: 0;
int flip[2] = {1, 0};
status = flip[status];
Есть ли более быстрый способ сделать это?
Вот что я попробовал: https://godbolt.org/g/A3qNUw
Что мне нужно, так это функция, которая переключает ввод и возвращает, написанные способом, который компилируется в одну инструкцию. Что-то похожее на эту функцию:
int addOne(int n) { return n+1; }
lea eax, [rdi+1] # return n+1 in a single instruction
ret
3 ответа
Чтобы перевернуть немного в целое число, используйте xor как это: foo ^= 1 ,
gcc знает эту оптимизацию уже для bool, так что вы можете return !status; как нормальный человек без потери эффективности. GCC компилирует status ^= 1 к инструкции XOR, а также. На самом деле все ваши идеи, кроме поиска по таблице, компилируются в один xor инструкция с bool ввод / возвращаемое значение.
Проверьте это на проводнике компилятора Godbolt с gcc -O3, с выходными панелями asm для bool а также int,
MYTYPE func4(MYTYPE status) {
status ^=1;
return status;
}
# same code for bool or int
mov eax, edi
xor eax, 1
ret
против
MYTYPE func1(MYTYPE status) {
status = !status;
return status;
}
# with -DMYTYPE=bool
mov eax, edi
xor eax, 1
ret
# with int
xor eax, eax
test edi, edi
sete al
ret
Почему bool отличный от int?
X86-64 System V ABI требует, чтобы вызывающие абоненты передавали bool передать значение 0 или 1, а не просто любое ненулевое целое число. Таким образом, компилятор может предположить, что о вводе.
Но с int foo выражение C !foo требует "логического" значения. !foo имеет тип _Bool / (иначе bool если ты #include <stdbool.h>) и преобразование его обратно в целое число должно привести к значению 0 или 1. Если компилятор не знает, что foo должно быть 0 или же 1 не может оптимизировать !foo в foo^=1 и не могу этого понять foo ^= 1 переворачивает значение между правдой / ложью. (В смысле if(foo) средства if(foo != 0) в с).
Вот почему вы получаете test/setcc (расширенный ноль в 32-битный int от xor обнуление регистра перед test).
Связано: логические значения как 8-битные в компиляторах. Операции на них неэффективны?, Вещи как (bool1 && bool2) ? x : y не всегда компилируется так эффективно, как вы можете надеяться. Компиляторы довольно хороши, но в них есть ошибки по пропущенной оптимизации.
Как насчет этого дополнительного mov инструкция?
Он пропадет при вставке, если компилятору не нужно / не нужно сохранять старое значение без переворачивания на потом. Но в автономной функции первый аргумент edi и возвращаемое значение должно быть в eax (в соглашении о вызовах System V x86-64).
Крошечные функции, подобные этой, являются близким приближением к тому, что вы можете получить как часть большой функции (если этот переход не может быть оптимизирован для чего-то другого), но необходимость результата в другом регистре является смешивающим фактором.
В x86 нет целочисленной инструкции copy-and-xor, поэтому для автономной функции потребуется как минимум mov скопировать из проходящего через arg регистра в eax,
lea Это особенность: это одна из немногих целочисленных инструкций ALU, которые могут записать результат в другой регистр, вместо того, чтобы уничтожить его ввод. lea это инструкция копирования-и-сдвига / добавления, но в x86 нет инструкции copy-and-xor. Многие наборы команд RISC имеют 3-операндные инструкции, например, MIPS может xor $t1, $t2, $t3,
AVX представил неразрушающие версии векторных инструкций (сохраняя много movdqa / movups копирование регистров в большом количестве кода), но для целых чисел есть только несколько новых инструкций, которые делают разные вещи. rorx eax, ecx, 16 например делает eax = rotate_right(ecx, 16) и использует ту же кодировку VEX, которую используют неразрушающие инструкции AVX.
Из этого запуска кода Godbolt (этот код в основном содержит несколько опций, которые я пробовал) кажется, что XORing дает одно утверждение, которое может это сделать:-(Как вы сказали, переключение - это то, что вы ищете)
status ^= 1;
сводится к одной инструкции (это было с -O0)
xor DWORD PTR [rbp-4], 1
С -O3 Вы можете увидеть все методы, которые вы упомянули использовать xor Если это в частности mov eax, edi/xor eax, 1,
И это гарантирует переключение состояния туда-сюда из 0 в 1 и наоборот. (Потому что xor утверждение - что есть в большинстве архитектур и полезно во многих случаях).
Я позволил другой вариант доступа к памяти провалиться - потому что арифметика указателя и разыменование адреса не будет быстрее, чем эти (иметь возможный доступ к памяти).
Я предложил один из способов сделать это на основе небольшого возни с Годболтом. Что вы можете сделать здесь - сравнить различные способы сделать это, а затем получить результат, который вы получаете. Предположительно, результат вы получите XORне будет так плохо на архитектуре вашей машины.
Интересно, что Питер Кордес в примере показал, что это будет справедливо и для логических выражений.
С этим примером ясно, что компилятор оптимизирует к кешированию неоптимизированного кода с 1 версия. Это один из способов поддержки того факта, что ксоринг даст лучший результат в случае нормальной операции int. С логическими значениями при компиляции с использованием -O3 все показанные выше mov eax, edi/xor eax, 1,
Если вы дошли до попытки микрооптимизации логических операций, вы либо преждевременно оптимизируете, либо выполняете много операций с большим количеством логических данных. Для первого - ответ не; для последнего вы можете задавать не тот вопрос. Если реальный вопрос заключается в том, как оптимизировать (много) операций с (большими) булевыми данными, ответ заключается в использовании альтернативного представления, основанного на "флагах" (иначе говоря, используйте лучший алгоритм). Это позволит вам переносить и легко помещать больше данных в кэш и одновременно выполнять несколько операций и тестов.
Почему / как это лучше?
кэш
Рассмотрим систему, в которой размер строки кэша составляет 64 байта. 64 _Bool поместится в строку кеша данных, тогда как в 8 раз больше. Скорее всего, у вас также будет меньший код инструкции - от 1 дополнительной инструкции до 32х меньше. Это может иметь большое значение в тесных петлях.
операции
Большинство операций включают одну или две (обычно очень быстрые) операции и один тест независимо от того, сколько флагов вы тестируете. Поскольку это может включать в себя несколько значений одновременно, каждая операция может выполнять (обычно в 32 или 64 раза) больше работы.
разветвление
Поскольку несколько операций и тестов могут быть выполнены одновременно, то, что было бы до 32 (или 64) возможных ветвей, может быть уменьшено до одного. Это может уменьшить ошибочные прогнозы отрасли.
читабельность
Используя хорошо названную константу маски, сложный вложенный if-else-if-else блок может быть уменьшен до одной читаемой строки.
портативность
_Bool не был доступен в ранних версиях C и C++ использует различные механизмы для логического; однако флаги будут работать в более старых версиях C и совместимы с C++
Вот практический пример того, как установить маску с флагами:
int isconsonant(int c){
const unsigned consonant_mask = (1<<('b'-'a'))|
(1<<('c'-'a'))|(1<<('d'-'a'))|(1<<('f'-'a'))|(1<<('g'-'a'))|
(1<<('h'-'a'))|(1<<('j'-'a'))|(1<<('k'-'a'))|(1<<('l'-'a'))|
(1<<('m'-'a'))|(1<<('n'-'a'))|(1<<('p'-'a'))|(1<<('q'-'a'))|
(1<<('r'-'a'))|(1<<('s'-'a'))|(1<<('t'-'a'))|(1<<('v'-'a'))|
(1<<('w'-'a'))|(1<<('x'-'a'))|(1<<('y'-'a'))|(1<<('z'-'a'));
unsigned x = (c|32)-'a'; // ~ tolower
/* if 1<<x is in range of int32 set mask to position relative to `a`
* as in the mask above otherwise it is set to 0 */
int ret = (x<32)<<(x&31);
return ret & consonant_mask;
}
//compiles to 7 operations to check for 52 different values
isconsonant:
or edi, 32 # tmp95,
xor eax, eax # tmp97
lea ecx, [rdi-97] # x,
cmp ecx, 31 # x,
setbe al #, tmp97
sal eax, cl # ret, x
and eax, 66043630 # tmp96,
ret
Эту концепцию можно использовать для одновременной работы с имитированным массивом логических значений, используя что-то вроде:
//inline these if your compiler doesn't automatically
_Bool isSpecificMaskSet(uint32_t x, uint32_t m){
return x==m; //returns 1 if all bits in m are exactly the same as x
}
_Bool isLimitedMaskSet(uint32_t x, uint32_t m, uint32_t v){
return (x&m) == v;
//returns 1 if all bits set in v are set in x
//bits not set in m are ignored
}
_Bool isNoMaskBitSet(uint32_t x, uint32_t m){
return (x&m) == 0; //returns 1 if no bits set in m are set in x
}
_Bool areAllMaskBitsSet(uint32_t x, uint32_t m){
return (x&m) == m; //returns 1 if all bits set in m are set in x
}
uint32_t setMaskBits(uint32_t x, uint32_t m){
return x|m; //returns x with mask bits set in m
}
uint32_t toggleMaskBits(uint32_t x, uint32_t m){
return x^m; //returns x with the bits in m toggled
}
uint32_t clearMaskBits(uint32_t x, uint32_t m){
return x&~m; //returns x with all bits set in m cleared
}
uint32_t getMaskBits(uint32_t x, uint32_t m){
return x&m; //returns mask bits set in x
}
uint32_t getMaskBitsNotSet(uint32_t x, uint32_t m){
return (x&m)^m; //returns mask bits not set in x
}