Если вы считаете, что 64-разрядная команда DIV – это хороший способ разделить на две части, то неудивительно, что выход asm компилятора изменил ваш ручной код даже с -O0 (быстро компилируется, не -O0 дополнительной оптимизации и сохраняет / перезагружается в память после / перед каждым оператором C, поэтому отладчик может изменять переменные).

Обратитесь к руководству Agner Fog’s Optimizing Assembly, чтобы узнать, как писать эффективные asm. Он также имеет таблицы инструкций и руководство для микроархива для конкретных деталей для конкретных процессоров. См. Также wiki для x86 для более совершенных ссылок.

См. Также этот более общий вопрос об избиении компилятора с помощью рукописного asm: Является ли встроенный язык ассемблера медленнее, чем собственный код на C ++? , TL: DR: да, если вы ошибетесь (например, этот вопрос).

Обычно вы прекрасно соглашаетесь с тем, что компилятор делает свое дело, особенно если вы пытаетесь написать C ++, который может эффективно компилироваться . Также см. Сборку быстрее, чем скомпилированные языки? , Один из ответов связан с этими аккуратными слайдами, показывающими, как различные компиляторы 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 делает то же беззнаковое подразделение: это 1 uop, с задержкой 1 c и может работать 2 за такт.

Для сравнения, 32-разрядное деление быстрее, но все же ужасно против сдвигов. idiv r32 – 9 часов, задержка 22-29 c и одна на пропускную способность 8-11c на Haswell.

---

Как вы можете видеть, глядя на gcc -O0 asm output ( Godbolt compiler explorer ), он использует только команды сдвигов . clang -O0 компилируется наивно, как вы думали, даже используя 64-битный IDIV в два раза. (При оптимизации компиляторы используют оба вывода IDIV, когда источник выполняет деление и модуль с одинаковыми операндами, если они вообще используют IDIV)

GCC не имеет абсолютно наивного режима; он всегда преобразуется через GIMPLE, что означает, что некоторые «оптимизации» не могут быть отключены . Это включает в себя распознавание деления на константу и использование сдвигов (мощность 2) или мультипликативного обратного ( фиксированного ) значения с фиксированной точкой (неэнергия 2), чтобы избежать IDIV (см. div_by_13 в вышеупомянутой ссылке для ссылок).

gcc -Os (оптимизация для размера) использует IDIV для разделения без полномочий 2, к сожалению даже в тех случаях, когда мультипликативный обратный код лишь немного больше, но намного быстрее.

---

Помощь компилятору

(сводка для этого случая: используйте uint64_t n )

Прежде всего, интересно посмотреть на оптимизированный выход компилятора. ( -O3 ). Скорость -O0 в основном бессмысленна.

Посмотрите на ваш выход asm (на Godbolt или посмотрите, как удалить «шум» с выхода сборки GCC / clang? ). Когда компилятор не делает оптимальный код в первую очередь: написание вашего источника C / C ++ способом, который помогает компилятору в создании лучшего кода, обычно является наилучшим подходом . Вы должны знать asm и знать, что эффективно, но вы косвенно применяете это знание. Компиляторы также являются хорошим источником идей: иногда clang будет делать что-то classное, и вы можете вручную использовать gcc, чтобы сделать то же самое: см. Этот ответ и то, что я сделал с незанятым циклом в коде @ Veedrac ниже.)

Этот подход переносимый, и через 20 лет какой-то будущий компилятор может скомпилировать его на то, что эффективно для будущего оборудования (x86 или нет), возможно, с использованием нового расширения ISA или автоматической векторизации. Рукописный x86-64 asm от 15 лет назад обычно не был бы оптимально настроен для Skylake. например, сравнение макросов и макросов в этом случае не существовало. То, что сейчас оптимально для ручной архитектуры asm для одной микроархитектуры, может оказаться не оптимальным для других современных и будущих процессоров. Комментарии к ответу @ johnfound обсуждают основные различия между AMD Bulldozer и Intel Haswell, которые оказывают большое влияние на этот код. Но теоретически g++ -O3 -march=bdver3 и g++ -O3 -march=skylake будут делать правильные вещи. (Or -march=native .) Или -mtune=... просто настроить, не используя инструкции, которые другие процессоры могут не поддерживать.

Я чувствую, что руководство компилятором к asm, что хорошо для текущего процессора, о котором вы заботитесь, не должно быть проблемой для будущих компиляторов. Они, надеюсь, лучше современных компиляторов при поиске способов преобразования кода и могут найти способ, который работает для будущих процессоров. Несмотря на это, будущий x86, вероятно, не будет страшным ни в чем хорошем на нынешнем x86, и будущий компилятор избежит любых ошибок, связанных с ASM, при реализации чего-то вроде движения данных из вашего источника C, если он не увидит что-то лучше.

Рукописный asm является черным ящиком для оптимизатора, поэтому постоянное распространение не работает, когда inlining делает вход постоянной времени компиляции. Другие изменения также затронуты. Перед использованием asm прочитайте https://gcc.gnu.org/wiki/DontUseInlineAsm . (И избегайте встроенного asm в стиле MSVC: входы / выходы должны проходить через память, которая увеличивает накладные расходы .)

В этом случае ваш n имеет подписанный тип, а gcc использует последовательность SAR / SHR / ADD, которая дает правильное округление. (IDIV и арифметический сдвиг «раунд» по-разному для отрицательных входов, см. Инструкцию SAR insn ref ref ). (IDK, если gcc попытался и не смог доказать, что n не может быть отрицательным, или что такое. Signed-overflow – это неопределенное поведение, поэтому он должен был иметь возможность.)

Вы должны были использовать uint64_t n , поэтому он может просто SHR. И поэтому он переносится в системы, где long 32-разрядный (например, x86-64 Windows).

---

BTW, оптимизированный выход asm gcc выглядит довольно неплохо (с использованием 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, который генерирует вход RDI CMOV, отключен от критического пути, поскольку он также быстрее, чем 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 или ранее вызывает срыв, если вы читаете результаты флага . Вот как они сделали его одним-юпом. Однако специальная кодировка shift-by-1 прекрасна.)

Избежать MOV не помогает с задержкой вообще на Haswell ( может ли MOV x86 быть «свободным»? Почему я не могу воспроизвести это вообще? ). Это значительно помогает в таких процессорах, как Intel pre-IvB и семейство AMD Bulldozer, где MOV не имеет нулевой задержки. Исправленные команды MOV от компилятора влияют на критический путь. BD-комплекс 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 стандартизирует задержки, поэтому нет 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, всегда используя И или ТЕСТ . Глупые компиляторы. : P Это отличные кусочки сложной техники, но умный человек может часто избивать их по мелким проблемам. (В тысячах и в миллионы раз дольше думать об этом, конечно! Компиляторы не используют исчерпывающие алгоритмы для поиска всех возможных способов делать что-то, потому что это займет слишком много времени при оптимизации большого количества встроенного кода, что и есть Они также не моделируют конвейер в целевой микроархитектуре, по крайней мере, не в той же детали, что и IACA или другие инструменты статического анализа, они просто используют некоторые эвристики.)

---

Простая развертка цикла не поможет ; этот цикл является узким местом на задержке цепи зависимостей, связанной с циклом, а не на streamе / пропускной способности цикла. Это означает, что это будет хорошо с гиперstreamом (или любым другим видом SMT), поскольку процессор имеет много времени для чередования инструкций из двух streamов. Это означало бы параллелизацию цикла в main , но это прекрасно, потому что каждый stream может просто проверять диапазон значений n и производить пару целых чисел в результате.

Перенесение вручную в пределах одного streamа также может быть жизнеспособным . Может быть, вычислить последовательность для пары чисел параллельно, поскольку каждый из них берет только пару регистров, и они могут обновлять те же max / maxi . Это создает больше параллелизма на уровне инструкций .

Трюк решает, ждать ли до тех пор, пока все n значений не достигнут 1 прежде чем получить еще одну пару начальных значений n , или разломиться и получить новую начальную точку только для одного, достигшего конечного условия, не касаясь регистров для другая последовательность. Вероятно, лучше, чтобы каждая цепочка работала над полезными данными, иначе вам пришлось бы условно увеличивать счетчик.

---

Возможно, вы даже можете сделать это с помощью SSE, упакованного для сравнения, чтобы условно увеличить счетчик для векторных элементов, где n еще не достигло 1 . И затем, чтобы скрыть еще большую задержку реализации условного приращения SIMD, вам нужно будет держать больше векторов n значений в airе. Может быть, стоит только с 256b-вектором (4x uint64_t ).

Я считаю, что лучшей страtagsей для обнаружения 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 s в разных целочисленных регистрах.

Таким образом, цикл может выглядеть так:

 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 часто выходит за frameworks того, что требует руководство по ISA x86, чтобы не нарушать широко используемый код, который не зависит от чего-то, чего он не должен, или это ретроактивно запрещено. Например, Windows 9x не предполагает спекулятивной предварительной выборки записей TLB , что было безопасно когда код был написан, прежде чем Intel обновит правила управления TLB .)

Во всяком случае, LZCNT / TZCNT на Haswell имеют то же самое ложное слово, что и POPCNT: см. Это Q & A. Именно поэтому в asm-выходе gcc для кода @ Veedrac вы видите, что он разбивает цепочку dep с помощью xor-zeroing в регистре, который он собирается использовать в качестве адресата TZCNT, когда он не использует dst = src. Поскольку TZCNT / LZCNT / POPCNT никогда не оставляют свое назначение неопределенным или немодифицированным, эта ложная зависимость от выхода на процессорах Intel является исключительно ошибкой / ограничением производительности. Предположительно, это стоит некоторых транзисторов / мощности, чтобы заставить их вести себя как другие uops, которые идут на один и тот же исполнительный блок. Единственный программно-видимый потенциал заключается в взаимодействии с другим микроархитектурным ограничением: они могут скомпоновать операнд памяти с индексированным режимом адресации на Haswell, но на Skylake, где Intel удалила ложную зависимость для LZCNT / TZCNT, они «не ламинируют», индексированные режимы адресации, в то время как POPCNT все еще может замаскировать любой режим addr.

---

Усовершенствования идей / кода из других ответов:

Ответ @ hidefromkgb имеет хорошее наблюдение, что вы гарантированно сможете сделать одну правую смену после 3n + 1. Вы можете вычислить это еще более эффективно, чем просто оставить проверки между шагами. Однако реализация asm в этом ответе прерывается (зависит от OF, которая не определена после SHRD со счетчиком> 1) и медленна: ROR rdi,2 быстрее, чем SHRD rdi,rdi,2 и использует две команды CMOV на критическом пути медленнее, чем дополнительный TEST, который может работать параллельно.

Я поместил tidied / улучшенный C (который подсказывает компилятору для получения лучшего asm), и протестировал + работать быстрее asm (в комментариях ниже C) на Godbolt: см. Ссылку в ответе @ hidefromkgb . (Этот ответ попал в ограничение на 30 тыс. Символов из больших URL-адресов Godbolt, но ссылки могут быть гнилыми и слишком длинными для goo.gl.)

Также улучшена печать вывода для преобразования в строку и одна write() вместо записи одного символа за раз. Это минимизирует влияние на выбор времени всей программы с помощью perf stat ./collatz (для записи счетчиков производительности), и я де-зафузировал некоторые некритические asm.

---

@ Код Veedrac

Я получил очень небольшое ускорение от правого сдвига, насколько мы знаем, что нужно делать, и проверять продолжение цикла. От 7.5s для limit = 1e8 до 7.275s, на Core2Duo (Merom), с коэффициентом unroll 16.

код + комментарии к Godbolt . Не используйте эту версию с clang; он делает что-то глупое с отсрочкой. Использование счетчика tmp k а затем добавление его для count позже изменяет то, что делает clang, но это немного болит gcc.

См. Обсуждение в комментариях: код Veedrac превосходный на процессорах с BMI1 (то есть не Celeron / Pentium)

Утверждение, что компилятор C ++ может создавать более оптимальный код, чем грамотный ассемблер, является очень плохой ошибкой. И особенно в этом случае. Человек всегда может сделать код лучше, чем может быть у компилятора, и эта конкретная ситуация является хорошей иллюстрацией этого утверждения.

Разница во времени, которую вы видите, связана с тем, что код сборки в вопросе очень далек от оптимального во внутренних циклах.

(Код ниже 32-бит, но может быть легко преобразован в 64-разрядный)

Например, функция последовательности может быть оптимизирована только для 5 команд:

  .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 

Весь код выглядит так:

 include "%lib%/freshlib.inc" @BinaryType console, compact options.DebugMode = 1 include "%lib%/freshlib.asm" start: InitializeAll mov ecx, 999999 xor edi, edi ; max xor ebx, ebx ; max i .main_loop: xor esi, esi mov eax, ecx .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 cmp edi, esi cmovb edi, esi cmovb ebx, ecx dec ecx jnz .main_loop OutputValue "Max sequence: ", edi, 10, -1 OutputValue "Max index: ", ebx, 10, -1 FinalizeAll stdcall TerminateAll, 0 

Для компиляции этого кода необходим FreshLib .

В моих тестах (процессор AMD A4-1200 с тактовой частотой 1 ГГц) вышеуказанный код примерно в четыре раза быстрее, чем код C ++ из вопроса (при компиляции с -O0 : 430 мс против 1900 мс) и более чем в два раза быстрее (430 мс против 830 мс), когда код C ++ скомпилирован с -O3 .

Выход обеих программ один и тот же: max sequence = 525 на i = 837799.

Для большей производительности: простое изменение наблюдает, что после n = 3n + 1 n будет четным, поэтому вы можете сразу разделить на 2. И n не будет 1, поэтому вам не нужно проверять его. Таким образом, вы можете сохранить несколько операторов if и написать:

 while (n % 2 == 0) n /= 2; if (n > 1) for (;;) { n = (3*n + 1) / 2; if (n % 2 == 0) { do n /= 2; while (n % 2 == 0); if (n == 1) break; } } 

Вот большая победа: если вы посмотрите на самые младшие 8 бит n, все этапы, пока вы не разделите их на 2 восемь раз, не будут полностью определены этими восемью битами. Например, если последние восемь бит равны 0x01, то есть в двоичном формате ваш номер равен? 0000 0001, то следующие шаги:

 3n+1 -> ???? 0000 0100 / 2 -> ???? ?000 0010 / 2 -> ???? ??00 0001 3n+1 -> ???? ??00 0100 / 2 -> ???? ???0 0010 / 2 -> ???? ???? 0001 3n+1 -> ???? ???? 0100 / 2 -> ???? ???? ?010 / 2 -> ???? ???? ??01 3n+1 -> ???? ???? ??00 / 2 -> ???? ???? ???0 / 2 -> ???? ???? ???? 

Итак, все эти шаги можно предсказать, а 256k + 1 заменить на 81k + 1. Что-то подобное произойдет для всех комбинаций. Таким образом, вы можете создать цикл с большим оператором switch:

 k = n / 256; m = n % 256; switch (m) { case 0: n = 1 * k + 0; break; case 1: n = 81 * k + 1; break; case 2: n = 81 * k + 1; break; ... case 155: n = 729 * k + 425; break; ... } 

Запустите цикл до n ≤ 128, потому что в этой точке n может стать 1 с менее чем восемью делениями на 2, и выполнение восьми или более шагов за раз заставит вас пропустить точку, в которой вы достигнете 1 в первый раз. Затем продолжите «нормальный» цикл – или подготовьте таблицу, в которой рассказывается, сколько еще шагов необходимо достичь 1.

PS. Я сильно подозреваю, что предложение Питера Кордеса сделает его еще быстрее. Во всех случаях не будет никаких условных ветвей, кроме одного, и это будет предсказано правильно, кроме случаев, когда цикл фактически заканчивается. Таким образом, код будет чем-то вроде

 static const unsigned int multipliers [256] = { ... } static const unsigned int adders [256] = { ... } while (n > 128) { size_t lastBits = n % 256; n = (n >> 8) * multipliers [lastBits] + adders [lastBits]; } 

На практике вы бы измерили, будет ли обработка последних 9, 10, 11, 12 бит n за раз быстрее. Для каждого бита количество записей в таблице удваивается, и я исключаю замедление, когда таблицы больше не вписываются в кеш L1.

PPS. Если вам нужно количество операций: на каждой итерации мы выполняем ровно восемь делений на два и переменное число операций (3n + 1), поэтому очевидным методом подсчета операций будет другой массив. Но мы можем рассчитать количество шагов (на основе количества итераций цикла).

Мы могли бы немного переопределить проблему: замените n на (3n + 1) / 2, если нечетно, и заменим n на n / 2, если четное. Тогда каждая итерация выполнит ровно 8 шагов, но вы можете считать, что обман 🙂 Итак, предположим, что были r операций n <- 3n + 1 и s операций n <- n / 2. Результат будет в точности ровно n '= n * 3 ^ r / 2 ^ s, так как n <- 3n + 1 означает n <- 3n * (1 + 1 / 3n). Взяв логарифм, найдем r = (s + log2 (n '/ n)) / log2 (3).

Если мы выполняем цикл до n ≤ 1,000,000 и имеем предварительно вычисленную таблицу, сколько итераций требуется от любой начальной точки n ≤ 1,000,000, тогда вычисление r, как указано выше, округленное до ближайшего целого, даст правильный результат, если s действительно велико.

On a rather unrelated note: more performance hacks!

• [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

• When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

  1. [even] [odd]
  2. [odd] [even]
  3. [even] [even]

  To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N << 1) + N + 1) >> 1 and N >> 2 , respectively.

  Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

  Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds:

   (N << 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb 

  where B = !b . Right-shifting the first result gives us exactly what we want.

  QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1 .

  As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this:

 uint64_t sequence(uint64_t size, uint64_t *path) { uint64_t n, i, c, maxi = 0, maxc = 0; for (n = i = (size - 1) | 1; i > 2; n = i -= 2) { c = 2; while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2) c += 2; if (n == 2) c++; if (c > maxc) { maxi = i; maxc = c; } } *path = maxc; return maxi; } int main() { uint64_t maxi, maxc; maxi = sequence(1000000, &maxc); printf("%llu, %llu\n", maxi, maxc); return 0; } 

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly!

 MOV RCX, 1000000; DEC RCX; AND RCX, -2; XOR RAX, RAX; MOV RBX, RAX; @main: XOR RSI, RSI; LEA RDI, [RCX + 1]; @loop: ADD RSI, 2; LEA RDX, [RDI + RDI*2 + 2]; SHR RDX, 1; SHRD RDI, RDI, 2; ror rdi,2 would do the same thing CMOVL RDI, RDX; Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs. CMOVS RDI, RDX; CMP RDI, 2; JA @loop; LEA RDX, [RSI + 1]; CMOVE RSI, RDX; CMP RAX, RSI; CMOVB RAX, RSI; CMOVB RBX, RCX; SUB RCX, 2; JA @main; MOV RDI, RCX; ADD RCX, 10; PUSH RDI; PUSH RCX; @itoa: XOR RDX, RDX; DIV RCX; ADD RDX, '0'; PUSH RDX; TEST RAX, RAX; JNE @itoa; PUSH RCX; LEA RAX, [RBX + 1]; TEST RBX, RBX; MOV RBX, RDI; JNE @itoa; POP RCX; INC RDI; MOV RDX, RDI; @outp: MOV RSI, RSP; MOV RAX, RDI; SYSCALL; POP RAX; TEST RAX, RAX; JNE @outp; LEA RAX, [RDI + 59]; DEC RDI; SYSCALL; 

Use these commands to compile:

 nasm -f elf64 file.asm ld -o file file.o 

---

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor’s note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)

C++ programs are translated to assembly programs during the generation of machine code from the source code. It would be virtually wrong to say assembly is slower than C++. Moreover, the binary code generated differs from compiler to compiler. So a smart C++ compiler may produce binary code more optimal and efficient than a dumb assembler’s code.

However I believe your profiling methodology has certain flaws. The following are general guidelines for profiling:

1. Make sure your system is in its normal/idle state. Stop all running processes (applications) that you started or that use CPU intensively (or poll over the network).
2. Your datasize must be greater in size.
3. Your test must run for something more than 5-10 seconds.
4. Do not rely on just one sample. Perform your test N times. Collect results and calculate the mean or median of the result.

From comments:

But, this code never stops (because of integer overflow) !?! Yves Daoust

For many numbers it will not overflow.

If it will overflow – for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.

Still this poses interesting question, is there some overflow-cyclic seed number?

Any simple final converging series starts with power of two value (obvious enough?).

2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to shr rax producing ZF=1.

Can we produce 2^64? If the starting number is 0x5555555555555555 , it’s odd number, next number is then 3n+1, which is 0xFFFFFFFFFFFFFFFF + 1 = 0 . Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The cmp rax,1 of Peter Cordes will end in infinite loop (QED variant 1, “cheapo” through undefined 0 number).

How about some more complex number, which will create cycle without 0 ? Frankly, I’m not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.

So I just put few numbers into sheet and took a look on 8 bit truncated numbers.

There are three values overflowing to 0 : 227 , 170 and 85 ( 85 going directly to 0 , other two progressing toward 85 ).

But there’s no value creating cyclic overflow seed.

Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already 27 is affected! It does reach value 9232 in proper non-truncated series (first truncated value is 322 in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is 13120 (for the 255 itself), maximum number of steps to converge to 1 is about 128 (+-2, not sure if “1” is to count, etc…).

Interestingly enough (for me) the number 9232 is maximum for many other source numbers, what’s so special about it? :-O 9232 = 0x2410 … hmmm.. no idea.

Unfortunately I can’t get any deep grasp of this series, why does it converge and what are the implications of truncating them to k bits, but with cmp number,1 terminating condition it’s certainly possible to put the algorithm into infinite loop with particular input value ending as 0 after truncation.

But the value 27 overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value 1 , you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I’m too lazy to check).

You did not post the code generated by the compiler, so there’ some guesswork here, but even without having seen it, one can say that this:

 test rax, 1 jpe even 

… has a 50% chance of mispredicting the branch, and that will come expensive.

The compiler almost certainly does both computations (which costs neglegibly more since the div/mod is quite long latency, so the multiply-add is “free”) and follows up with a CMOV. Which, of course, has a zero percent chance of being mispredicted.

Even without looking at assembly, the most obvious reason is that /= 2 is probably optimized as >>=1 and many processors have a very quick shift operation. But even if a processor doesn’t have a shift operation, the integer division is faster than floating point division.

Edit: your milage may vary on the “integer division is faster than floating point division” statement above. The comments below reveal that the modern processors have prioritized optimizing fp division over integer division. So if someone were looking for the most likely reason for the speedup which this thread’s question asks about, then compiler optimizing /=2 as >>=1 would be the best 1st place to look.

---

On an unrelated note , if n is odd, the expression n*3+1 will always be even. So there is no need to check. You can change that branch to

 { n = (n*3+1) >> 1; count += 2; } 

So the whole statement would then be

 if (n & 1) { n = (n*3 + 1) >> 1; count += 2; } else { n >>= 1; ++count; } 

As a generic answer, not specifically directed at this task: In many cases, you can significantly speed up any program by making improvements at a high level. Like calculating data once instead of multiple times, avoiding unnecessary work completely, using caches in the best way, and so on. These things are much easier to do in a high level language.

Writing assembler code, it is possible to improve on what an optimising compiler does, but it is hard work. And once it’s done, your code is much harder to modify, so it is much more difficult to add algorithmic improvements. Sometimes the processor has functionality that you cannot use from a high level language, inline assembly is often useful in these cases and still lets you use a high level language.

In the Euler problems, most of the time you succeed by building something, finding why it is slow, building something better, finding why it is slow, and so on and so on. That is very, very hard using assembler. A better algorithm at half the possible speed will usually beat a worse algorithm at full speed, and getting the full speed in assembler isn’t trivial.

For the Collatz problem, you can get a significant boost in performance by caching the “tails”. This is a time/memory trade-off. See: memoization ( https://en.wikipedia.org/wiki/Memoization ). You could also look into dynamic programming solutions for other time/memory trade-offs.

Example python implementation:

 import sys inner_loop = 0 def collatz_sequence(N, cache): global inner_loop l = [ ] stop = False n = N tails = [ ] while not stop: inner_loop += 1 tmp = n l.append(n) if n <= 1: stop = True elif n in cache: stop = True elif n % 2: n = 3*n + 1 else: n = n // 2 tails.append((tmp, len(l))) for key, offset in tails: if not key in cache: cache[key] = l[offset:] return l def gen_sequence(l, cache): for elem in l: yield elem if elem in cache: yield from gen_sequence(cache[elem], cache) raise StopIteration if __name__ == "__main__": le_cache = {} for n in range(1, 4711, 5): l = collatz_sequence(n, le_cache) print("{}: {}".format(n, len(list(gen_sequence(l, le_cache))))) print("inner_loop = {}".format(inner_loop)) 

The simple answer:

• doing a MOV RBX, 3 and MUL RBX is expensive; just ADD RBX, RBX twice

• ADD 1 is probably faster than INC here

• MOV 2 and DIV is very expensive; just shift right

• 64-bit code is usually noticeably slower than 32-bit code and the alignment issues are more complicated; with small programs like this you have to pack them so you are doing parallel computation to have any chance of being faster than 32-bit code

If you generate the assembly listing for your C++ program, you can see how it differs from your assembly.