(Предполагается, что это "точечный продукт" двух векторов над полем Z/2Z, aka. GF (2).)
Ответ 3
Это может показаться немного суровым, но я считаю, что это нужно сказать. Пожалуйста, не принимайте это лично; Я не имею в виду это как оскорбление, тем более, что вы уже признались, что "знаете, что нет собрания". Но если вы думаете, что код такой:
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
будет избить то, что генерирует компилятор C, тогда у вас действительно нет бизнеса, использующего встроенную сборку. Только в этих 5 строках кода я вижу две инструкции, которые выглядят крайне неоптимальными. Его можно было бы оптимизировать, просто слегка переписав его:
xor eax, eax
test ecx, ecx ; logically, should use RCX, but see below for behavior of PF
jnp jmp_over
mov eax, 1 ; or possibly even "inc eax"; would need to verify
jmp_over:
ret
Или, если у вас есть случайные входные значения, которые могут скрыть предиктор ветвления (т.е. не существует предсказуемого паттерна для четности входных значений) то было бы быстрее удалить ветку, записав ее как:
xor eax, eax
test ecx, ecx
setp al
ret
Или, может быть, эквивалент (который будет быстрее для некоторых процессоров, но не обязательно всех):
xor eax, eax
test ecx, ecx
mov ecx, 1
cmovp eax, ecx
ret
И это только улучшения, которые я мог видеть с головы до ног, учитывая мои существующие знания о ISA x86 и предыдущих тестах, которые я провел. Но чтобы кто-нибудь не обманул, это, несомненно, не самый быстрый код, потому что (заимствование у Майкла Абраша) "нет такого понятия, как самый быстрый код" - кто-то практически может сделать это быстрее.
Есть достаточно проблем с использованием встроенной сборки, когда вы являетесь экспертным программистом на ассемблере и мастером, когда дело доходит до тонкостей ISA x86. Оптимизаторы в наши дни довольно хороши, и это означает, что для истинного гуру достаточно получить лучший код (хотя, конечно, не невозможно). Он также заслуживает надежных тестов, которые подтвердят ваши предположения и подтвердят, что оптимизированная встроенная сборка выполняется быстрее. Никогда не обязуйтесь использовать встроенную сборку, чтобы перехитрить оптимизатор компилятора, не выполняя хороший тест. Я не вижу никаких доказательств в вашем вопросе, что вы сделали что-то подобное. Я размышляю здесь, но похоже, что вы видели, что код был написан в сборке и предположил, что это будет быстрее. Это редко бывает. Компиляторы C в конечном итоге также испускают код языка ассемблера, и это часто более оптимально, чем то, что мы, люди, способны производить, учитывая ограниченное количество времени и ресурсов, гораздо менее ограниченный опыт.
В этом конкретном случае существует мнение, что встроенная сборка будет быстрее, чем вывод компилятора C, поскольку компилятор C не сможет разумно использовать встроенный флаг четности x86 (PF) в свою пользу, И вы можете быть правы, но это довольно шаткий предположение, далеко не универсализуемое. Как я уже сказал, оптимизация компиляторов в наши дни довольно умна, и они оптимизируются для конкретной архитектуры (при условии, что вы указываете правильные параметры), поэтому меня совершенно не удивит, что оптимизатор испустит код, который использовал PF. Вы должны посмотреть на разборку, чтобы убедиться в этом.
В качестве примера того, что я имею в виду, рассмотрим высокоспециализированную инструкцию BSWAP, которую предоставляет x86. Вы могли бы наивно думать, что встроенная сборка должна была бы использовать ее, но это не так. Следующий код C компилируется в инструкцию BSWAP практически для всех основных компиляторов:
uint32 SwapBytes(uint32 x)
{
return ((x << 24) & 0xff000000 ) |
((x << 8) & 0x00ff0000 ) |
((x >> 8) & 0x0000ff00 ) |
((x >> 24) & 0x000000ff );
}
Производительность будет эквивалентной, если не лучше, потому что оптимизатор имеет больше знаний о том, что делает код. Фактически, основным преимуществом этой формы над встроенной сборкой является то, что компилятор может выполнять постоянную сворачивание с помощью этого кода (т.е. При вызове с постоянной времени компиляции). Кроме того, код более читабельен (по крайней мере, программисту C), гораздо меньше подвержен ошибкам и значительно проще в обслуживании, чем если бы вы использовали встроенную сборку. О, и я упоминал об этом достаточно портативно, если вы когда-либо хотели настроить таргетинг на архитектуру, отличную от x86?
Я знаю, что я это делаю, и хочу, чтобы вы поняли, что я говорю об этом как о ком-то, кому нравится писать высоконастраиваемый ассемблерный код, который превосходит оптимизатор компилятора в производительности. Но каждый раз, когда я это делаю, это просто: вызов, который приходит с жертвами. Это не панацея, и вам нужно не забывать проверять свои предположения, в том числе:
- Является ли этот код на самом деле узким местом в моем приложении, так что оптимизация его даже может сделать какую-либо заметную разницу?
- Оптимизатор действительно испускает субоптимальные инструкции машинного языка для кода, который я написал?
- Неужели я ошибаюсь в том, что я наивно считаю субоптимальным? Может быть, оптимизатор знает больше, чем я о целевой архитектуре, и то, что выглядит как медленный или субоптимальный код, на самом деле быстрее. (Помните, что меньше кода не обязательно быстрее.)
- Я тестировал ли я его в значимом, реальном мире, и доказал, что код, сгенерированный компилятором, медленный и что моя встроенная сборка выполняется быстрее?
- Невозможно ли я настроить код C, чтобы убедить оптимизатора испускать лучший машинный код, близкий, равный или даже превосходящий производительность моей встроенной сборки?
В попытке ответить на некоторые из этих вопросов я настроил небольшой ориентир. (Используя MSVC, потому что это то, что мне удобно, если вы нацеливаетесь на GCC, лучше всего использовать этот компилятор, но мы все равно можем получить общую идею. Я использую и рекомендую Библиотека сравнения Google.) И я сразу столкнулся с проблемами. См., Я сначала запускаю свои тесты в режиме "отладки", с утверждениями, скомпилированными в том, что проверка того, что мой "измененный" / "оптимизированный" код фактически дает те же результаты для всех тестовых случаев, что и исходный код (который, как известно, работает/правильно). В этом случае сразу же уволилось утверждение. Оказывается, что процедура CheckParity, написанная на ассемблере, не возвращает идентичные результаты в процедуру parity64, написанную на C! Ой-ой. Ну, это еще одна пуля, которую нам нужно добавить в список выше:
- Обеспечил ли я, чтобы мой "оптимизированный" код возвращал правильные результаты?
Это особенно важно, потому что легко сделать что-то быстрее, если вы также ошибаетесь.:-) Я шучу, но не полностью, потому что я делал это много раз в поисках более быстрого кода.
Я считаю, что Майкл Петч уже указал причину расхождения: в реализации x86 флаг четности (PF) касается только бит в младшем байте, а не все значение. Если это все, что вам нужно, то здорово. Но даже тогда мы можем вернуться к коду C и еще больше оптимизировать ее, чтобы сделать меньше работы, что сделает ее быстрее - возможно, быстрее, чем код сборки, исключая одно преимущество, которое когда-либо имело встроенная сборка.
Пока давайте предположим, что вам нужна четность полного значения, так как у вас была оригинальная реализация, которая работала, и вы просто пытаетесь сделать ее быстрее, не изменяя ее поведения. Таким образом, нам нужно исправить логику кода сборки, прежде чем мы сможем даже проиллюстрировать ее. К счастью, поскольку я пишу этот ответ поздно, Ajay Brahmakshatriya (в сотрудничестве с другими) уже проделал эту работу, сохранив при этом дополнительные усилия.
& hellip; кроме, не совсем. Когда я впервые составил этот ответ, мой тест показал, что черновик 9 его "измененного" кода все же не дал того же результата, что и исходная функция C, поэтому он не подходит в соответствии с к нашим тестовым случаям. Вы скажете в комментарии, что его код "работает" для вас, а это означает, что (A) исходный код C выполнял дополнительную работу, делая его бесполезно медленным, что означает, что вы можете, возможно, настроить его, чтобы побить встроенную сборку в своей игре или, что еще хуже, (B) у вас недостаточно тестовых примеров, а новый "оптимизированный" код на самом деле является ошибкой, лежащей в ожидании. С тех пор Ped7g предложил пару исправлений, в которых исправлена ошибка, из-за которой возвращался неверный результат, а также улучшался код. Объем входных данных, требуемый здесь, и количество сквозняков, которые он прошел, должны служить свидетельством сложности написания правильной встроенной сборки для избиения компилятора. Но мы еще не сделали! Его встроенная сборка остается неправильно написанной. В инструкциях SETcc требуется 8-битный регистр в качестве их операнда, но его код не использует спецификатор регистра для запроса, что означает, что код либо не будет компилироваться (поскольку Clang достаточно умен, чтобы обнаружить эту ошибку), либо компилируется в GCC, но не будет выполняться должным образом, потому что эта команда имеет недопустимый операнд.
Я еще раз убедился в важности тестирования? Я возьму его на веру и перейду к эталонной части. Результаты тестов используют окончательный проект кода Ajay с улучшениями Ped7g и мои дополнительные настройки. Я также сравниваю некоторые другие решения из того вопроса, который вы связали, измененный для 64-битных целых чисел, плюс пара моего собственного изобретения. Вот мои результаты тестов (мобильный Haswell i7-4850HQ):
Benchmark Time CPU Iterations
-------------------------------------------------------------------
Naive 36 ns 36 ns 19478261
OriginalCCode 4 ns 4 ns 194782609
Ajay_Brahmakshatriya_Tweaked 4 ns 4 ns 194782609
Shreyas_Shivalkar 37 ns 37 ns 17920000
TypeIA 5 ns 5 ns 154482759
TypeIA_Tweaked 4 ns 4 ns 160000000
has_even_parity 227 ns 229 ns 3200000
has_even_parity_Tweaked 36 ns 36 ns 19478261
GCC_builtin_parityll 4 ns 4 ns 186666667
PopCount 3 ns 3 ns 248888889
PopCount_Downlevel 5 ns 5 ns 100000000
Теперь имейте в виду, что они предназначены для случайных генерируемых 64-битных входных значений, что нарушает предсказание ветвлений. Если ваши входные значения предвзято предвзяты, либо к паритету, либо к неравномерности, тогда предиктор ветки будет работать для вас, а не против вас, и некоторые подходы могут быть более быстрыми. Это подчеркивает важность сопоставления данных, которые имитируют реальные случаи использования. (При этом, когда я пишу общие библиотечные функции, я стараюсь оптимизировать случайные входы, балансируя размер и скорость.)
Обратите внимание, как оригинальная функция C сравнивается с другими. Я собираюсь заявить, что оптимизация его в будущем, вероятно, является большой пустой тратой времени. Поэтому, надеюсь, вы узнали что-то более общее из этого ответа, а не просто прокрутили вниз, чтобы скопировать фрагменты кода.: -)
Функция Naive является полностью неоптимизированной проверкой здравомыслия, чтобы определить четность, взятую из здесь. Я использовал его для проверки даже вашего исходного кода на C, а также для обеспечения базового уровня для эталонных тестов. Поскольку он проходит через каждый бит, один за другим, он относительно медленный, как и ожидалось:
unsigned int Naive(uint64 n)
{
bool parity = false;
while (n)
{
parity = !parity;
n &= (n - 1);
}
return parity;
}
OriginalCCode - это именно то, что кажется - это оригинальный код C, который у вас был, как показано в вопросе. Обратите внимание на то, как он размещается в точности в то же время, что и исправленная версия исправленного кода Ajay Brahmakshatriya! Теперь, поскольку я запустил этот тест в MSVC, который не поддерживает встроенную сборку для 64-битных построений, мне пришлось использовать внешний модуль сборки, содержащий эту функцию, и вызвать его оттуда, что привело к некоторым дополнительным накладным расходам. С встроенной сборкой GCC компилятор, вероятно, смог бы встроить код, таким образом, вызывая вызов функции. Таким образом, на GCC вы можете увидеть, что версия встроенной сборки может быть до наносекунды быстрее (а может и нет). Это того стоит? Ты будешь судьей. Для справки, это код, который я тестировал для Ajay_Brahmakshatriya_Tweaked:
Ajay_Brahmakshatriya_Tweaked PROC
mov rax, rcx ; Windows 64-bit calling convention passes parameter in ECX (System V uses EDI)
shr rax, 32
xor rcx, rax
mov rax, rcx
shr rax, 16
xor rcx, rax
mov rax, rcx
shr rax, 8
xor eax, ecx ; Ped7g TEST is redundant; XOR already sets PF
setnp al
movzx eax, al
ret
Ajay_Brahmakshatriya_Tweaked ENDP
Функция с именем Shreyas_Shivalkar находится от своего ответа здесь, что является лишь вариацией темы "сквозной-каждый бит" и, с ожиданиями, медленно:
Shreyas_Shivalkar PROC
; unsigned int parity = 0;
; while (x != 0)
; {
; parity ^= x;
; x >>= 1;
; }
; return (parity & 0x1);
xor eax, eax
test rcx, rcx
je SHORT Finished
Process:
xor eax, ecx
shr rcx, 1
jne SHORT Process
Finished:
and eax, 1
ret
Shreyas_Shivalkar ENDP
TypeIA и TypeIA_Tweaked - это код из этого ответа, измененный для поддержки 64-битных значений и моей измененной версии. Они распараллеливают операцию, что приводит к значительному улучшению скорости по сравнению с реализацией сквозной схемы. "Измененная" версия основана на оптимизации, первоначально предложенной Мэтью Хендри на Sean Eron Anderson Bit Twiddling Hacks, и дает нам небольшую скорость - над оригиналом.
unsigned int TypeIA(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n ^= n >> 2;
n ^= n >> 1;
return !((~n) & 1);
}
unsigned int TypeIA_Tweaked(uint64 n)
{
n ^= n >> 32;
n ^= n >> 16;
n ^= n >> 8;
n ^= n >> 4;
n &= 0xf;
return ((0x6996 >> n) & 1);
}
has_even_parity основан на принятом ответе на этот вопрос, изменен для поддержки 64-битных значений. Я знал, что это будет медленным, поскольку это еще одна сквозная стратегия, но, очевидно, кто-то думал, что это хороший подход. Интересно посмотреть, насколько медленным оно является на самом деле, даже по сравнению с тем, что я назвал "наивным" подходом, который делает практически то же самое, но быстрее, с менее сложным кодом.
unsigned int has_even_parity(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
if (n & (b << i)) { ++count; }
}
return (count % 2);
}
has_even_parity_Tweaked является альтернативной версией выше, которая сохраняет ветвь, используя тот факт, что булевы значения неявно конвертируются в 0 и 1. Это существенно быстрее, чем оригинал, синхронизирующий в время, сравнимое с "наивный" подход:
unsigned int has_even_parity_Tweaked(uint64 n)
{
uint64 count = 0;
uint64 b = 1;
for (uint64 i = 0; i < 64; ++i)
{
count += static_cast<int>(static_cast<bool>(n & (b << i)));
}
return (count % 2);
}
Теперь мы попадаем в хорошие вещи. Функция GCC_builtin_parityll состоит из кода сборки, который GCC будет испускать, если вы использовали его __builtin_parityll intrinsic. Некоторые другие предположили, что вы используете это внутреннее, и я должен повторить их одобрение. Его производительность наравне с лучшими, которые мы видели до сих пор, и имеет несколько дополнительных преимуществ: (1) он сохраняет код простым и удобочитаемым (проще, чем версия C); (2) он переносится в разные архитектуры, и, как можно ожидать, он также останется там быстрым; (3), поскольку GCC улучшает его реализацию, ваш код может ускориться с простой перекомпиляцией. Вы получаете все преимущества встроенной сборки без каких-либо недостатков.
GCC_builtin_parityll PROC ; GCC __builtin_parityll
mov edx, ecx
shr rcx, 32
xor edx, ecx
mov eax, edx
shr edx, 16
xor eax, edx
xor al, ah
setnp al
movzx eax, al
ret
GCC_builtin_parityll ENDP
PopCount - это оптимизированная реализация моего собственного изобретения. Чтобы придумать это, я вернулся и подумал, что мы на самом деле пытаемся сделать. Определение "четности" представляет собой четное количество заданных бит. Поэтому его можно вычислить просто путем подсчета числа битов набора и тестирования, чтобы увидеть, является ли этот счет четным или нечетным. Это две логические операции. Как повезло, на последних поколениях процессоров x86 (Intel Nehalem или AMD Barcelona и новее) есть инструкция, которая подсчитывает количество установленных бит POPCNT (численность населения или вес Хэмминга), что позволяет нам писать код сборки, который делает это в двух операциях.
(Хорошо, на самом деле три инструкции, потому что есть ошибка в реализации POPCNT на некоторых микроархитектурах, которая создает ложную зависимость от своего целевого регистра, и чтобы обеспечить максимальную пропускную способность из кода, нам нужно разбить эту зависимость, предварительно очистив регистр назначения. К счастью, это очень дешевая операция, которую обычно можно обрабатывать для "бесплатного" путем переименования регистра.)
PopCount PROC
xor eax, eax ; break false dependency
popcnt rax, rcx
and eax, 1
ret
PopCount ENDP
Фактически, как оказалось, GCC знает, что именно этот код генерирует именно этот код для __builtin_parityll, когда вы нацеливаете микроархитектуру, поддерживающую POPCNT. В противном случае он использует приведенную выше резервную реализацию. Как вы можете видеть из тестов, это самый быстрый код. Это не имеет большого значения, поэтому вряд ли это имеет значение, если вы не будете делать это неоднократно в трудном цикле, но это измеримая разница и, по-видимому, вы не будете оптимизировать это так сильно, если только ваш профилировщик не указал, что это горячая точка.
Но команда POPCNT имеет недостаток в том, что она недоступна для старых процессоров, поэтому я также измерил "резервную" версию кода, которая подсчитывает количество пользователей с последовательностью универсальных инструкций. Это функция PopCount_Downlevel, взятая из моей частной библиотеки, первоначально адаптированная из этого ответа и других источников.
PopCount_Downlevel PROC
mov rax, rcx
shr rax, 1
mov rdx, 5555555555555555h
and rax, rdx
sub rcx, rax
mov rax, 3333333333333333h
mov rdx, rcx
and rcx, rax
shr rdx, 2
and rdx, rax
add rdx, rcx
mov rcx, 0FF0F0F0F0F0F0F0Fh
mov rax, rdx
shr rax, 4
add rax, rdx
mov rdx, 0FF01010101010101h
and rax, rcx
imul rax, rdx
shr rax, 56
and eax, 1
ret
PopCount_Downlevel ENDP
Как вы можете видеть из эталонных тестов, все инструкции для бит-twiddling, которые здесь требуются, требуют высокой производительности. Он медленнее, чем POPCNT, но поддерживается во всех системах и все еще достаточно быстро. Если бы вам все-таки понадобилось количество бит, это было бы лучшим решением, тем более, что оно может быть написано в чистом C без необходимости прибегать к встроенной сборке, что потенциально дает еще большую скорость:
unsigned int PopCount_Downlevel(uint64 n)
{
uint64 temp = n - ((n >> 1) & 0x5555555555555555ULL);
temp = (temp & 0x3333333333333333ULL) + ((temp >> 2) & 0x3333333333333333ULL);
temp = (temp + (temp >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
temp = (temp * 0x0101010101010101ULL) >> 56;
return (temp & 1);
}
Но запустите свои собственные тесты, чтобы убедиться, что вам не будет лучше с одной из других реализаций, например OriginalCCode, что упростит работу и, следовательно, потребует меньше общих инструкций. Интересный факт: компилятор Intel (ICC) всегда использует алгоритм подсчета численности населения для реализации __builtin_parityll; он выдает команду POPCNT, если целевая архитектура поддерживает ее, или, иначе, имитирует ее, используя, по существу, тот же код, что и здесь.
Или, еще лучше, просто забудьте весь сложный беспорядок и пусть ваш компилятор справится с этим. Для чего нужны встроенные модули, и там точно для этой цели.
