C ++ не является языком ассемблера, и компилятор может скомпилировать вашу текущую функцию в asms без ветвей, если она хочет . (Разыменование указателя на структуру для загрузки одного члена подразумевает, что весь объект структуры присутствует и, таким образом, может быть умозрительно прочитан без риска сбоя, даже если абстрактная машина C ++ не коснулась бы членов y или z.) Какой компилятор (ы) для какая архитектура (ы) вас больше всего волнует?
Вы пробовали компилировать с оптимизацией по профилю, чтобы компилятор мог видеть, что ветви непредсказуемы? Это может привести к тому, что он преобразует if() в cmov без ответвлений или что-то еще, в зависимости от целевого ISA. (Создайте свои случайные данные с помощью rand() & 0x7 или чего-то еще, чтобы объекты нередко имели равные x и y и фактически достигли случая z.)
Возможно используйте SIMD, чтобы найти первый несовпадающий элемент, затем верните diff этого элемента . Например, в x86 SIMD есть операция movemask, которая может превратить результат сравнения векторов в целочисленную битовую маску, которую мы можем использовать с командой битового сканирования, чтобы найти первый или последний установленный бит.
(Это зависит от возможность безопасно читать 16 байтов из вашей 12-байтовой структуры, предполагая x86. Это имеет место до тех пор, пока ваш массив не заканчивается последним элементом в конце страницы, а следующая страница не отображается. Безопасно ли читать после конца буфера на одной и той же странице на x86 и x64? обычно да, и широко используется для эффективной реализации strlen и аналогичных функций.)
(ARM NEON не имеет удобной маски перемещения, поэтому для ARM / AArch64 может быть лучше перетасовать данные в пределах вектора SIMD, чтобы получить результат, если SIMD вообще выиграл.Это может быть не с предикативными инструкциями сравнения ARM, или с более ограниченными условными инструкциями AArch64, которые по-прежнему лучше, чем x86 CMOV.)
SIMD может дать мы имеем хорошую пропускную способность, но, вероятно, низкую задержку по сравнению с версией @ Scheff arithmeti без ответвлений c в комментариях , особенно в широком конвейере, таком как современная x86, который может выполнять большую часть независимой работы параллельно (например, превращать отдельные результаты сравнения в булевы целые числа). Высокая задержка может быть не идеальной в QSort, где вы ожидаете, что ошибочные прогнозы ветвления не будут редкостью; Перекрывающиеся независимые сравнения с выполнением вне порядка работают только тогда, когда ветви предсказаны правильно.
Чтобы получить + / 0 / - результат из двух значений int, вы можете привести к int64_t и вычесть. Это исключает возможность переполнения со знаком и эффективно для 64-битных ISA. (Или, если он может быть встроенным, в идеале может компилироваться только в 32-разрядное сравнение со знаком вместо фактического вычитания. 32-разрядное вычитание могло бы иметь переполнение со знаком, которое является UB, и потеряло бы результат при переносе). Если вам не нужно нормализовать до +1 / 0 / -1, сделайте это.
Я использовал анонимную структуру внутри объединения с массивом для расширения @ удобной среды тестирования Scheff ( с исправлением ) без изменения всего с a->x на a->vals.x.
#include <stdint.h>
#include <immintrin.h>
union Obj {
struct { // extension: anonymous struct
int x;
int y;
int z;
};
int elems[3];
};
// a better check would be on value ranges; sizeof can include padding
static_assert( sizeof(int64_t) > sizeof(int), "we need int smaller than int64_t");
int64_t compare_x86(const Obj *a, const Obj *b)
{
__m128i va = _mm_loadu_si128((const __m128i*)a); // assume over-read is safe, last array object isn't at the end of a page.
__m128i vb = _mm_loadu_si128((const __m128i*)b);
__m128i veq = _mm_cmpeq_epi32(va,vb);
unsigned eqmsk = _mm_movemask_ps(_mm_castsi128_ps(veq));
eqmsk |= 1<<2; // set elems[2]'s bit so we'll return that (non)diff if they're all equal
unsigned firstdiff = __builtin_ctz(eqmsk); // GNU C extension: count trailing zeros
// sign-extend to 64-bit first so overflow is impossible, giving a +, 0, or - result
return a->elems[firstdiff] - (int64_t)b->elems[firstdiff];
}
На Godbolt с GCC9.3 -O3 -march=skylake -fno-tree-vectorize для x86-64 , он компилируется в этот ассемблер для не встроенного случая:
compare_x86(Obj const*rdi, Obj const*rsi):
vmovdqu xmm1, XMMWORD PTR [rsi]
vpcmpeqd xmm0, xmm1, XMMWORD PTR [rdi]
vmovmskps edx, xmm0 # edx = bitmask of the vector compare result
or edx, 4
tzcnt edx, edx # rdx = index of lowest set bit
mov edx, edx # stupid compiler, already zero-extended to 64-bit
movsx rax, DWORD PTR [rdi+rdx*4] # 32->64 sign extending load
movsx rdx, DWORD PTR [rsi+rdx*4]
sub rax, rdx # return value in RAX
ret
Критический путь задержки проходит через загрузки SIMD + сравнивает через маску перемещения обратно в целое число, or ( 1 цикл), tzcnt / bsf (3 цикла на Intel), затем еще одна задержка L1d при нагрузке при нагрузке movsx (5 циклов). (цифры от https://agner.org/optimize/ https://uops.info/. См. также { ссылка }). Адреса скалярной загрузки не известны до окончания tzcnt, поэтому здесь очень мало ILP. Современный x86 может делать 2 загрузки за такт, поэтому мы пользуемся этим. Однако он может частично перекрывать независимые сравнения, а общее число мопов низкое, поэтому узкое место в полосе пропускания внешнего интерфейса не так уж и плохо.
Не выровненные загрузки SIMD не налагают штраф на процессоры Intel, если они не пересекают границу строки кэша. Тогда задержка составляет дополнительные 10 циклов или около того. Или хуже, если они пересекают границу 4k, особенно на Intel до того, как Skylake сделал разделение страниц намного дешевле. Для случайных 4-байтовых выровненных адресов объектов есть 3 из 16 начальных позиций, которые приводят к разделенной загрузке строк кэша (для строк кэша 64B). Это дополнительно увеличивает среднюю задержку от готовности входных адресов к готовому результату сравнения и не может перекрываться с какой-либо работой.
Без -march=skylake G CC используется отдельная movdqu невыровненная загрузка и rep bsf, что соответствует инструкции tzcnt. Процессоры без BMI1 будут декодировать его как обычный bsf. (Они отличаются только при нулевом входном сигнале; мы убеждаемся, что этого не происходит. bsf медленный на AMD, такая же скорость, как tzcnt на Intel.)
Использование эталонного теста @ Scheff (что считается результаты) на Godbolt, это несколько быстрее, чем простая скалярная версия "арифметика c", когда вы отключаете автоматическую векторизацию. (G CC может автоматически c арифметическая c версия.) Результаты синхронизации несовместимы между запусками, поскольку тестовый набор слишком мал и серверы AWS, на которых работает обозреватель компилятора, могут иметь разные частоты процессора хотя они все Skylake-avx512. Но в пределах одного прогона, чередуя между этим и arith, результат, подобный этому, типичен:
compare_x86() 5. try: 28 mus (<: 3843, >: 3775)
compareArithm() 5. try: 59 mus (<: 4992, >: 5007)
compare_x86() 6. try: 39 mus (<: 3843, >: 3775)
compareArithm() 6. try: 64 mus (<: 4992, >: 5007)
compare_x86() 7. try: 27 mus (<: 3843, >: 3775)
compareArithm() 7. try: 64 mus (<: 4992, >: 5007)
Но помните, это всего лишь , складывающее , <0 и >0 return значения, и, таким образом, ограничено пропускной способностью, а не задержкой. Новое сравнение может начаться без какой-либо зависимости данных или управляющей зависимости от предыдущего результата сравнения.
Хмм, я мог бы использовать pmovmskb, чтобы получить старший бит каждого байта вместо каждого двойного слова с версия ps, но C делает неудобным использование байтового смещения в массиве int вместо смещения элемента. В asm вы бы tzcnt или BSF, а затем movsx rax, [rdi + rdx]. Это может сэкономить цикл задержки в обходе между SIMD-целым числом pcmpeqd и SIMD-FP movmskps. Но чтобы получить это от компилятора, вам, возможно, придется привести к char* для добавления указателя, а затем обратно к int*.
Сначала я подумал об использовании _mm_cmpgt_epi32(va,vb), чтобы получить вектор 0 / -1 сравнивает результаты со знаком «больше-чем», но потом я понял, что индексирование исходных структур будет так же просто, как преобразование нужного элемента или его части в целое число -1 / +1.
Если вы хотите, чтобы в особом случае был случай всех равных, вместо этого вы могли бы установить бит # 3 (|= 1<<3), затем выполнить переход в этом редком случае, но все равно делать все остальное без ветвлений.
eqmsk |= 1<<3; // set the 4th bit so there's a non-zero bit to find
unsigned firstdiff = __builtin_ctz(eqmsk);
if (firstdiff >= 3) // handle this rare(?) case with a branch
return 0;
... something with (a < b) * 2 - 1
Смешанная стратегия ветвления:
Если редко x s равны, возможно, рассмотрим
if (a->x != b->x)
return a->x - (int_fast64_t)b->x;
else {
8-byte branchless SIMD?
or maybe just 2 element branchless scalar
}
IDK, если вообще стоит делать SIMD только для еще 2 элементов. Вероятно, нет.
Или, возможно, рассмотрите возможность выполнения безветвления для x и y, а разветвление для y компонентов равно скалярному пропуску z? Если ваши объекты являются случайными в большей части диапазона int, то будет редко, когда вы найдете два, которые отличаются только последним компонентом.
Я думаю, что хорошие алгоритмы сортировки делают меньше сравнений, избегая избыточные сравнения, вероятно, создают больше энтропии в шаблоне результатов и, вероятно, также увеличивают количество сравнений, выполненных с элементами, которые «близки» друг к другу в конечном порядке сортировки. Таким образом, QSort может делать больше сравнений, которые должны проверять y-элементы, если есть много элементов с равным x.