Ответ 1
Если вы считаете, что 64-разрядная команда DIV - это хороший способ разделить на две части, то неудивительно, что выход asm компилятора превосходил ваш ручной код даже при -O0 (быстро компилировать, без дополнительной оптимизации и хранения/перезагружать в память после/перед каждым оператором C, чтобы отладчик мог изменять переменные).
Смотрите Agner Fog Optimizing Assembly guide, чтобы узнать, как писать эффективные asm. Он также имеет таблицы инструкций и руководство для микроархива для конкретных деталей для конкретных процессоров. См. Также x86 теги wiki для более перфекционных ссылки.
См. также более общий вопрос об избиении компилятора с помощью рукописного asm: Является ли язык встроенной сборки медленнее, чем собственный код на С++?. TL: DR: да, если вы сделаете это неправильно (например, этот вопрос).
Обычно вы прекрасно соглашаетесь на компилятор, особенно если вы попытаетесь написать С++, который может эффективно компилироваться. Также см. сборка быстрее, чем скомпилированные языки?. Один из ответов связан с этими аккуратными слайдами, показывающими, как различные компиляторы C оптимизируют некоторые действительно простые функции с помощью трюков.
even:
mov rbx, 2
xor rdx, rdx
div rbx
В Intel Haswell, div r64 - 36 часов, с задержкой 32-96 циклов и пропускной способностью по одному на 21-74 циклов. (Кроме того, 2 раза настроить RBX и нулевой RDX, но выполнение вне очереди может запустить их раньше). Высокоуровневые инструкции, такие как DIV, являются микрокодированными, что также может вызывать узкие места переднего плана. В этом случае задержка является наиболее важным фактором, поскольку она является частью цикла Целевая цепочка зависимостей.
shr rax, 1 выполняет одно и то же беззнаковое деление: It 1 uop, с задержкой 1c и может работать 2 за такт.
Для сравнения, 32-разрядное деление быстрее, но все же ужасно против сдвигов. idiv r32 - 9 часов, задержка 22-29 c и одна на пропускную способность 8-11c на Haswell.
Как вы можете видеть из gcc -O0 asm output (Godbolt explorer, он использует только команды shifts. clang -O0 компилируется наивно, как вы думали, даже используя 64-битный IDIV в два раза. (При оптимизации компиляторы используют оба выхода IDIV, когда источник выполняет деление и модуль с одинаковыми операндами, если они вообще используют IDIV)
GCC не имеет абсолютно наивного режима; он всегда преобразуется через GIMPLE, что означает, что некоторые "оптимизации" не могут быть отключены. Это включает в себя распознавание деления по константе и использование сдвигов (мощность 2) или мультипликативного обратного преобразования с фиксированной точкой (non power of 2), чтобы избежать IDIV (см. div_by_13 в приведенной выше ссылке godbolt).
gcc -Os (оптимизация для размера) использует IDIV для разделения без полномочий 2,
к сожалению, даже в тех случаях, когда мультипликативный обратный код лишь немного больше, но намного медленнее.
Помощь компилятору
(сводка для этого случая: use uint64_t n)
Прежде всего, интересно только посмотреть на оптимизированный вывод компилятора. (-O3). -O0 скорость в основном бессмысленна.
Посмотрите на свой выход asm (на Godbolt или посмотрите Как удалить "шум" из сборки сборки GCC/clang?). Когда компилятор не делает оптимальный код в первую очередь: Написание вашего источника C/С++ способом, который помогает компилятору создавать лучший код, как правило, лучший подход. Вы должны знать ас и знать, что эффективно, но косвенно применяете это знание. Компиляторы также являются хорошим источником идей: иногда clang будет делать что-то классное, и вы можете вручную взять gcc в то же самое: см. этот ответ и то, что я сделал с незанятым циклом в коде @Veedrac ниже.)
Этот подход переносимый, и через 20 лет какой-то будущий компилятор может скомпилировать его на то, что эффективно для будущего оборудования (x86 или нет), возможно, с использованием нового расширения ISA или автоматической векторизации. Рукописный x86-64 asm от 15 лет назад обычно не был бы оптимально настроен для Skylake. например в то время не было сопоставления макросов и макросов. То, что сейчас оптимально для ручной архитектуры asm для одной микроархитектуры, может оказаться не оптимальным для других текущих и будущих процессоров. Комментарии к ответу @johnfoundобсудите основные различия между AMD Bulldozer и Intel Haswell, которые сильно влияют на этот код. Но теоретически g++ -O3 -march=bdver3 и g++ -O3 -march=skylake будут поступать правильно. (Или -march=native.) Или -mtune=... просто настроить, не используя инструкции, которые другие CPU могут не поддерживать.
Я чувствую, что руководство компилятором к asm, что хорошо для текущего процессора, о котором вы заботитесь, не должно быть проблемой для будущих компиляторов. Они, надеюсь, лучше современных компиляторов при поиске способов преобразования кода и могут найти способ, который работает для будущих процессоров. Несмотря на это, будущий x86, вероятно, не будет ужасен ни в чем хорошем на нынешнем x86, а будущий компилятор избежит любых ошибок, связанных с ASM, при реализации чего-то вроде движения данных из вашего источника C, если он не увидит что-то лучше.
Рукописный asm является черным ящиком для оптимизатора, поэтому постоянное распространение не работает, когда inlining делает вход константой времени компиляции. Другие изменения также затронуты. Перед использованием asm прочитайте https://gcc.gnu.org/wiki/DontUseInlineAsm. (И избегайте встроенного asm в стиле MSVC: входы/выходы должны проходить через память которая добавляет накладные расходы.)
В этом случае: ваш n имеет подписанный тип, а gcc использует последовательность SAR/SHR/ADD, которая дает правильное округление. (IDIV и арифметический сдвиг "round" по-разному для отрицательных входов, см. SAR insn set ref manual entry). (IDK, если gcc попытался и не смог доказать, что n не может быть отрицательным или что-то такое. Signed-overflow - это поведение undefined, поэтому он должен был быть способен.)
Вы должны были использовать uint64_t n, поэтому он может просто SHR. И поэтому он переносится в системы, где long является только 32-разрядным (например, x86-64 Windows).
BTW, gcc оптимизированный выход asm выглядит довольно неплохо (используя unsigned long n): внутренний цикл, который он встраивает в main(), выполняет следующее:
# from gcc5.4 -O3 plus my comments
# edx= count=1
# rax= uint64_t n
.L9: # do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
mov rdi, rax
shr rdi # rdi = n>>1;
test al, 1 # set flags based on n%2 (aka n&1)
mov rax, rcx
cmove rax, rdi # n= (n%2) ? 3*n+1 : n/2;
add edx, 1 # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)
cmp/branch to update max and maxi, and then do the next n
Внутренний цикл является ветвящимся, а критический путь цепи зависимых от цикла циклов:
- 3-компонентный LEA (3 цикла)
- cmov (2 цикла на Haswell, 1c на Broadwell или позже).
Всего: 5 циклов за итерацию, узкое место ожидания. Выполнение вне порядка позаботится обо всем остальном параллельно с этим (теоретически: я не тестировал с помощью счетчиков perf, чтобы увидеть, действительно ли он работает на 5c/iter).
Вход FLAGS cmov (созданный TEST) быстрее, чем выход RAX (из LEA- > MOV), поэтому он не находится на критическом пути.
Аналогично, MOV- > SHR, который генерирует вход CMOV RDI, отключен от критического пути, поскольку он также быстрее, чем LEA. MOV на IvyBridge и позже имеет нулевую задержку (обрабатывается при переименовании регистра). (Он по-прежнему занимает uop и слот в конвейере, поэтому он не бесплатный, просто нулевая латентность). Дополнительный MOV в цепочке детектора LEA является частью узкого места на других процессорах.
cmp/jne также не является частью критического пути: он не переносится в цикле, поскольку управляющие зависимости обрабатываются с предсказанием ветвления + спекулятивным исполнением, в отличие от зависимостей данных от критического пути.
Избиение компилятора
GCC здесь неплохо справился. Он мог бы сохранить один байт кода, используя inc edx вместо add edx, 1, потому что никто не заботится о P4 и его ложных зависимостях для инструкций по модификации частичного флага.
Он также может сохранить все инструкции MOV, а TEST: SHR устанавливает CF = бит сдвинут, поэтому мы можем использовать cmovc вместо test/cmovz.
### Hand-optimized version of what gcc does
.L9: #do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
shr rax, 1 # n>>=1; CF = n&1 = n%2
cmovc rax, rcx # n= (n&1) ? 3*n+1 : n/2;
inc edx # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)
См. ответ @johnfound для другого умного трюка: удалите CMP, разветкив его на результат SHR-флага, а также используя его для CMOV: ноль, только если n было 1 (или 0) для начала. (Удовлетворительный факт: SHR с count!= 1 на Nehalem или ранее вызывает срыв, если вы читаете результаты флага. Это то, как они сделали его одним-юпом. по-1 специальная кодировка в порядке.)
Избегание MOV не помогает с задержкой вообще на Haswell (Может ли MOV x86 действительно "бесплатно" ? Почему я не могу воспроизвести это вообще?). Это значительно помогает в таких процессорах, как Intel pre-IvB и семейство AMD Bulldozer, где MOV не имеет нулевой задержки. Компилятор впустую команды MOV действительно влияют на критический путь. BD complex-LEA и CMOV являются как более низкой задержкой (2c, так и 1c соответственно), поэтому это большая часть задержки. Кроме того, проблемы с пропускной способностью становятся проблемой, поскольку она имеет только два целых ALU-канала. См. ответ @johnfound, где он получает результаты с процессора AMD.
Даже в Haswell эта версия может немного помочь, избегая некоторых случайных задержек, когда некритический uop крадет порт выполнения от одного на критическом пути, задерживая выполнение на 1 цикл. (Это называется конфликтом ресурсов). Он также сохраняет регистр, который может помочь при выполнении нескольких n значений параллельно в чередующемся цикле (см. Ниже).
Задержка LEA зависит от режима адресации, на процессорах Intel SnB-семейства. 3c для 3 компонентов ([base+idx+const], который принимает два отдельных добавления), но только 1c с 2 или менее компонентами (один добавить). Некоторые процессоры (например, Core2) выполняют даже 3-компонентный LEA за один цикл, но SnB-family этого не делает. Хуже того, Intel SnB-family стандартизирует задержки, так что нет 2c uops, в противном случае 3-компонентный LEA будет всего 2c, как Bulldozer. (3-компонентный LEA на AMD тоже медленнее, просто не так).
Итак, lea rcx, [rax + rax*2]/inc rcx - это только 2c-латентность, быстрее, чем lea rcx, [rax + rax*2 + 1], на процессорах Intel SnB-семейства, таких как Haswell. Разрыв на BD, и хуже на Core2. Это стоит лишний uop, который обычно не стоит экономить 1c латентность, но латентность является основным узким местом здесь, и Haswell имеет достаточно широкий конвейер для обработки дополнительной пропускной способности.
Ни gcc, icc, ни clang (on godbolt) не использовали выход SHR CF, всегда используя AND или TEST. Глупые компиляторы.: P Это отличные кусочки сложной техники, но умный человек может часто избивать их по мелким проблемам. (В тысячах и в миллионы раз дольше думать об этом, конечно! Компиляторы не используют исчерпывающие алгоритмы для поиска всех возможных способов делать что-то, потому что это займет слишком много времени при оптимизации большого количества встроенного кода, что и есть они делают лучше всего. Они также не моделируют трубопровод в целевой микроархитектуре, а просто используют некоторые эвристики.)
Простая развертка цикла не поможет; этот цикл является узким местом на задержке цепи зависимостей, связанной с циклом, а не на потоке/пропускной способности цикла. Это означает, что это будет хорошо с гиперпотоком (или любым другим видом SMT), поскольку процессор имеет много времени для чередования инструкций из двух потоков. Это означало бы распараллеливание цикла в main, но это прекрасно, потому что каждый поток может просто проверять диапазон значений n и создавать в результате пару целых чисел.
Перемещение вручную внутри одного потока может быть жизнеспособным, также. Может быть, вычислить последовательность для пары чисел параллельно, поскольку каждый из них принимает только пару регистров, и они могут все обновить те же max/maxi. Это создает больше уровень уровня parallelism.
Трюк решает, ждать ли до тех пор, пока все значения n не достигнут 1, прежде чем получить еще одну пару стартовых значений n, или разбить и получить новую начальную точку только для того, конечное условие, не касаясь регистров для другой последовательности. Вероятно, лучше всего держать каждую цепочку в работе над полезными данными, иначе вам придется условно увеличивать счетчик.
Возможно, вы даже можете сделать это с помощью пакета SSE для упаковки, чтобы условно увеличить счетчик для векторных элементов, где n еще не достигло 1. И затем, чтобы скрыть еще большую задержку реализации условного прироста SIMD, вам нужно будет держать больше векторов значений n в воздухе. Может быть, стоит только с 256b-вектором (4x uint64_t).
Я думаю, что лучшей стратегией для обнаружения 1 "липкой" является маскировка вектора all-ones, который вы добавляете для увеличения счетчика. Итак, после того, как вы увидели в элементе 1, вектор инкремента будет иметь нуль, а + = 0 - нет-op.
Непривязанная идея для ручной векторизации
# starting with YMM0 = [ n_d, n_c, n_b, n_a ] (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1): increment vector
# ymm5 = all-zeros: count vector
.inner_loop:
vpaddq ymm1, ymm0, xmm0
vpaddq ymm1, ymm1, xmm0
vpaddq ymm1, ymm1, set1_epi64(1) # ymm1= 3*n + 1. Maybe could do this more efficiently?
vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit
vpsrlq ymm0, ymm0, 1 # n /= 2
# There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure. Probably worth it
vpblendvpd ymm0, ymm0, ymm1, ymm3 # variable blend controlled by the sign bit of each 64-bit element. I might have the source operands backwards, I always have to look this up.
# ymm0 = updated n in each element.
vpcmpeqq ymm1, ymm0, set1_epi64(1)
vpandn ymm4, ymm1, ymm4 # zero out elements of ymm4 where the compare was true
vpaddq ymm5, ymm5, ymm4 # count++ in elements where n has never been == 1
vptest ymm4, ymm4
jnz .inner_loop
# Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero
vextracti128 ymm0, ymm5, 1
vpmaxq .... crap this doesn't exist
# Actually just delay doing a horizontal max until the very very end. But you need some way to record max and maxi.
Вы можете и должны реализовать это с помощью intrinsics, вместо рукописного asm.
Улучшение алгоритма/реализации:
Помимо реализации одной и той же логики с более эффективным asm, найдите способы упрощения логики или избегайте избыточной работы. например memoize для обнаружения общих окончаний последовательностей. Или еще лучше, посмотрите на 8 конечных бит сразу (gnasher ответ)
@EOF указывает, что tzcnt (или bsf) может использоваться для выполнения нескольких итераций n/=2 за один шаг. Это, вероятно, лучше, чем SIMD-векторизация, потому что никакая инструкция SSE или AVX не может это сделать. Тем не менее он по-прежнему совместим с выполнением нескольких скалярных n в разных целочисленных регистрах.
Итак, цикл может выглядеть так:
goto loop_entry; // C++ structured like the asm, for illustration only
do {
n = n*3 + 1;
loop_entry:
shift = _tzcnt_u64(n);
n >>= shift;
count += shift;
} while(n != 1);
Это может привести к значительно меньшему количеству итераций, но сдвиги с переменным числом замедляются на процессорах Intel SnB-семейства без BMI2. 3 uops, 2c latency. (У них есть зависимость ввода от FLAGS, потому что count = 0 означает, что флаги не модифицированы. Они обрабатывают это как зависимость данных и принимают несколько uops, потому что uop может иметь только 2 входа (до HSW/BDW в любом случае)). Это тот вид, на который ссылаются люди, жалующиеся на сумасшедший дизайн CISC x86. Это делает процессоры x86 медленнее, чем они были бы, если бы ISA была разработана с нуля сегодня, даже в основном аналогичным образом. (т.е. это часть "налога x86", который стоит скорость/мощность.) SHRX/SHLX/SARX (BMI2) - большая победа (1 минута /1 с).
Он также ставит tzcnt (3c на Haswell и позже) на критический путь, поэтому он значительно продлевает полную задержку цепи зависимостей, связанной с циклом. Однако он устраняет необходимость в CMOV или для подготовки регистра, удерживающего n>>1. Ответ @Veedrac преодолевает все это, откладывая tzcnt/shift для нескольких итераций, что очень эффективно (см. ниже).
Мы можем безопасно использовать BSF или TZCNT взаимозаменяемо, поскольку n никогда не может быть нулем в этой точке. Механический код TZCNT декодируется как BSF на процессорах, которые не поддерживают BMI1. (Бесконечные префиксы игнорируются, поэтому REP BSF работает как BSF).
TZCNT работает намного лучше, чем BSF на процессорах AMD, которые его поддерживают, поэтому неплохо использовать REP BSF, даже если вам не нужно устанавливать ZF, если входной сигнал равен нулю, а не выход. Некоторые компиляторы делают это, когда вы используете __builtin_ctzll даже с -mno-bmi.
Они выполняют то же самое на процессорах Intel, поэтому просто сохраняйте байты, если это все имеет значение. TZCNT на Intel (pre-Skylake) по-прежнему имеет ложную зависимость от якобы выходного операнда только для записи, так же как и для BSF, для поддержки недокументированного поведения, при котором BSF с input = 0 оставляет цель немодифицированной. Поэтому вам нужно обойти это, если не оптимизировать только для Skylake, так что ничего не получить от дополнительного байт REP. (Intel часто выходит за рамки того, что требует руководство по ISA x86, чтобы не нарушать широко используемый код, который зависит от чего-то, чего он не должен, или это ретроактивно запрещено. Например: Windows 9x не предполагает спекулятивной предварительной выборки записей TLB, что было безопасно, когда код был написан, до того, как Intel обновит правила управления TLB.)
В любом случае, LZCNT/TZCNT на Haswell имеют то же самое ложное значение, что и POPCNT: см. этот Q & A. Вот почему в gcc asm output для кода @Veedrac вы видите разрыв цепочки dep с xor-zeroing в регистре, который он собирается использовать в качестве адресата TZCNT, когда он не использует dst = src. Поскольку TZCNT/LZCNT/POPCNT никогда не покидают свой пункт назначения undefined или немодифицированы, эта ложная зависимость от выхода на процессорах Intel является исключительно ошибкой/ограничением производительности. Предположительно, это стоит каких-то транзисторов/мощности, чтобы заставить их вести себя как другие uops, идущие к одному и тому же исполнительному блоку. Единственный программно-видимый потенциал - во взаимодействии с другим микроархитектурным ограничением: они могут скомпилировать операнд памяти с индексированным режимом адресации на Haswell, но на Skylake, где Intel удалили ложную зависимость для LZCNT/TZCNT, они "не ламинируют" индексированные режимы адресации, в то время как POPCNT все еще может замаскировать любой режим addr.
Усовершенствования идей/кода из других ответов:
@hidefromkgb answer имеет хорошее наблюдение, что вы гарантированно сможете сделать одну правую смену после 3n + 1. Вы можете вычислить это еще более эффективно, чем просто оставить проверки между шагами. Однако реализация asm в этом ответе прерывается (зависит от OF, который undefined после SHRD со счетом > 1) и медленный: ROR rdi,2 быстрее, чем SHRD rdi,rdi,2, и используя две инструкции CMOV на критический путь медленнее, чем дополнительный TEST, который может работать параллельно.
Я поместил tidied/улучшенный C (который помогает компилятору создать лучший asm) и протестировал + работать быстрее asm (в комментариях ниже C) вверх на Godbolt: см. ссылку в @hidefromkgb answer. (Этот ответ попал в предел 30 тыс. char из больших URL-адресов Godbolt, но shortlinks может гнить и слишком долго для goo.gl.)
Также улучшена печать вывода, чтобы преобразовать в строку и сделать один write() вместо того, чтобы писать один char за раз. Это минимизирует влияние на выбор времени всей программы с помощью perf stat ./collatz (для записи счетчиков производительности), и я де-запутывал некоторые некритические asm.
Код @Veedrac
Я получил очень небольшое ускорение от правого сдвига, насколько мы знаем, что нужно делать, и проверку продолжения цикла. От 7.5s для limit = 1e8 до 7.275s, на Core2Duo (Merom), с коэффициентом unroll 16.
code + comments в Godbolt. Не используйте эту версию с clang; он делает что-то глупое с отсрочкой. Использование счетчика tmp k, а затем добавление его в count позже изменяет то, что делает clang, но это немного болит gcc.
См. обсуждение в комментариях: код Veedrac отлично работает на процессорах с BMI1 (то есть не Celeron/Pentium)