Код C++ для проверки гипотезы Коллатца быстрее, чем рукописная сборка - почему?
Я написал эти два решения для Project Euler Q14, в сборке и на C++. Это один и тот же метод грубой силы для проверки гипотезы Коллатца. Решение для сборки было собрано с
nasm -felf64 p14.asm && gcc p14.o -o p14
C++ был скомпилирован с
g++ p14.cpp -o p14
Ассамблея, p14.asm
section .data
fmt db "%d", 10, 0
global main
extern printf
section .text
main:
mov rcx, 1000000
xor rdi, rdi ; max i
xor rsi, rsi ; i
l1:
dec rcx
xor r10, r10 ; count
mov rax, rcx
l2:
test rax, 1
jpe even
mov rbx, 3
mul rbx
inc rax
jmp c1
even:
mov rbx, 2
xor rdx, rdx
div rbx
c1:
inc r10
cmp rax, 1
jne l2
cmp rdi, r10
cmovl rdi, r10
cmovl rsi, rcx
cmp rcx, 2
jne l1
mov rdi, fmt
xor rax, rax
call printf
ret
C++, p14.cpp
#include <iostream>
using namespace std;
int sequence(long n) {
int count = 1;
while (n != 1) {
if (n % 2 == 0)
n /= 2;
else
n = n*3 + 1;
++count;
}
return count;
}
int main() {
int max = 0, maxi;
for (int i = 999999; i > 0; --i) {
int s = sequence(i);
if (s > max) {
max = s;
maxi = i;
}
}
cout << maxi << endl;
}
Я знаю об оптимизации компилятора для повышения скорости и всего остального, но я не вижу много способов дальнейшей оптимизации моего решения по сборке (говоря программно, а не математически).
Код C++ имеет модуль каждого термина и деление каждого четного термина, где сборка - это только одно деление на четное условие.
Но сборка занимает в среднем на 1 секунду больше времени, чем решение C++. Почему это? Прошу в основном из любопытства.
Время выполнения
Моя система: 64-битный Linux на 1,4 ГГц Intel Celeron 2955U (микроархитектура Haswell).
g++(неоптимизировано): в среднем 1272 мсg++ -O3в среднем 578 мсоригинал asm (div) в среднем 2650 мс
Asm (shr)в среднем 679 мс@ johnfound asm, собранный с nasm avg 501 мс
@hidefromkgb asm avg 200 мс
@hidefromkgb asm оптимизировано @Peter Cordes в среднем 145 мс
@Veedrac C++ в среднем 81 мс с
-O3305 мс с-O0
11 ответов
Если вы думаете, что 64-битная инструкция DIV - это хороший способ деления на два, то неудивительно, что вывод asm компилятора превзойдет ваш рукописный код, даже если -O0 (Быстрая компиляция без дополнительной оптимизации и сохранение / перезагрузка в памяти после / перед каждым оператором C, чтобы отладчик мог изменять переменные).
См. Руководство по оптимизации сборки Agner Fog, чтобы узнать, как написать эффективный ассемблер. У него также есть таблицы инструкций и руководство по микроархиту для конкретных деталей для конкретных процессоров. См. Также вики-тег 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 моп, с задержкой 1 с, и может работать 2 за такт.
Для сравнения, 32-битное деление быстрее, но все же ужасно против сдвигов. idiv r32 составляет 9 моп, задержка 22-29 с и одна на пропускную способность 8-11 с в Haswell.
Как вы можете видеть, глядя на GCC -O0 вывод asm ( проводник компилятора Godbolt), он использует только инструкции смены. лязг -O0 компилируется наивно, как вы думали, даже используя 64-битный IDIV дважды. (При оптимизации компиляторы используют оба выхода IDIV, когда источник выполняет деление и модуль с одинаковыми операндами, если они вообще используют IDIV)
GCC не имеет полностью наивного режима; он всегда трансформируется через GIMPLE, что означает, что некоторые "оптимизации" не могут быть отключены. Это включает в себя распознавание деления на константу и использование сдвигов (степень 2) или мультипликативного обратного с фиксированной точкой (не степень 2), чтобы избежать IDIV (см. div_by_13 в приведенной выше ссылке Godbolt).
gcc -Os (оптимизировать по размеру) действительно использует IDIV для деления без степени 2, к сожалению, даже в случаях, когда мультипликативный обратный код только немного больше, но намного быстрее.
Помогаем компилятору
(резюме для этого случая: используйте uint64_t n)
Прежде всего, интересно только посмотреть на оптимизированный вывод компилятора. (-O3). -O0 Скорость в принципе не имеет смысла.
Посмотрите на ваш вывод asm (на Godbolt или посмотрите, как удалить "шум" из вывода сборки GCC/clang?). Когда компилятор не создает оптимальный код, во-первых: написание исходного кода C/C++ таким образом, чтобы руководство компилятора создавало лучший код, обычно является лучшим подходом. Вы должны знать asm и знать, что эффективно, но вы применяете эти знания косвенно. Компиляторы также являются хорошим источником идей: иногда clang делает что-то классное, и вы можете держать gcc в руках то же самое: посмотрите этот ответ и то, что я сделал с не развернутым циклом в коде @Veedrac ниже.)
Этот подход переносим, и через 20 лет какой-нибудь будущий компилятор может скомпилировать его с любым эффективным на будущем оборудовании (x86 или нет), возможно, с использованием нового расширения ISA или автоматической векторизации. Рукописный ассемблер x86-64, созданный 15 лет назад, обычно не будет оптимально настроен для Skylake. Например, сравните и ответвите макрослияние не существовало тогда. То, что сейчас оптимально для ручной сборки asm для одной микроархитектуры, может быть не оптимальным для других текущих и будущих процессоров. Комментарии к ответу @johnfound обсуждают основные различия между AMD Bulldozer и Intel Haswell, которые сильно влияют на этот код. Но в теории g++ -O3 -march=bdver3 а также g++ -O3 -march=skylake будет делать правильные вещи. (Или же -march=native.) Или же -mtune=... просто настроить, без использования инструкций, которые могут не поддерживать другие процессоры.
У меня такое ощущение, что наставление компилятора в asm, которое хорошо для текущего процессора, о котором вы заботитесь, не должно быть проблемой для будущих компиляторов. Надеемся, что они лучше, чем нынешние компиляторы, находят способы преобразования кода и могут найти способ, который будет работать для будущих процессоров. Несмотря на это, будущий x86, вероятно, не будет ужасен во всем, что хорошо на нынешнем x86, и будущий компилятор избежит любых специфичных для asm ловушек при реализации чего-то вроде перемещения данных из вашего C-источника, если он не увидит чего-то лучшего.
Рукописный asm является черным ящиком для оптимизатора, поэтому постоянное распространение не работает, когда встраивание делает ввод постоянной времени компиляции. Другие оптимизации также затронуты. Прочтите https://gcc.gnu.org/wiki/DontUseInlineAsm перед использованием asm. (И избегайте встроенного asm в стиле MSVC: входы / выходы должны проходить через память, что увеличивает накладные расходы.)
В этом случае: ваш n имеет тип со знаком, а gcc использует последовательность SAR/SHR/ADD, которая дает правильное округление. (IDIV и арифметическое смещение "округляют" по-разному для отрицательных входов, см. SAR insn set, ссылка на ручной ввод) (IDK, если gcc попытался и не смог доказать это n не может быть отрицательным, или что. Переполнение со знаком - это неопределенное поведение, поэтому оно должно быть в состоянии.)
Вы должны были использовать uint64_t n так что это может просто шр. И поэтому он переносим на системы, где long только 32-битный (например, x86-64 Windows).
Кстати, оптимизированный вывод 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 циклов за итерацию, узкое место задержки. Внеочередное выполнение позаботится обо всем остальном параллельно с этим (теоретически: я не тестировал счетчики производительности, чтобы увидеть, действительно ли он работает на 5c/iter).
Ввод флагов cmov (создается TEST) быстрее, чем ввод RAX (из LEA->MOV), поэтому он не на критическом пути.
Точно так же MOV->SHR, который производит вход RDI CMOV, вне критического пути, потому что это также быстрее, чем LEA. MOV на IvyBridge и более поздних версиях имеет нулевую задержку (обрабатывается во время переименования регистра). (Он по-прежнему занимает моп и слот в конвейере, поэтому он не свободен, просто нулевая задержка). Дополнительные 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-family, где MOV не имеет нулевой задержки. Потерянные инструкции MOV компилятора влияют на критический путь. Complex-LEA и CMOV BD имеют более низкую задержку (2 c и 1c соответственно), поэтому это большая доля задержки. Кроме того, узкие места пропускной способности становятся проблемой, потому что у него есть только два целочисленных канала ALU. См. Ответ @johnfound, где он получил результаты синхронизации с процессором AMD.
Даже в Haswell, эта версия может немного помочь, избегая некоторых случайных задержек, когда некритический моп украл порт выполнения с одного на критическом пути, задерживая выполнение на 1 цикл. (Это называется конфликтом ресурсов). Это также сохраняет регистр, который может помочь при выполнении нескольких n значения параллельно в чередующемся цикле (см. ниже).
Задержка LEA зависит от режима адресации, от процессоров семейства Intel SnB. 3c для 3 компонентов ([base+idx+const], что занимает два отдельных добавления), но только 1с с 2 или менее компонентами (одно добавление). Некоторые процессоры (например, Core2) выполняют даже 3-компонентный LEA за один цикл, а семейство SnB- нет. Хуже того, семейство Intel SnB стандартизирует задержки, поэтому нет 2с мопов, иначе 3-компонентный LEA будет только 2с как Bulldozer. (3-компонентный LEA работает медленнее на AMD, но не так сильно).
Так lea rcx, [rax + rax*2] / inc rcx только 2с латентность, быстрее чем lea rcx, [rax + rax*2 + 1] на процессорах семейства Intel SnB, таких как Haswell. Безубыточность на BD, а хуже на Core2. Это стоит дополнительного UOP, что обычно не стоит того, чтобы экономить задержку 1С, но задержка является основным узким местом, и Haswell имеет достаточно широкий конвейер для обработки дополнительной пропускной способности UOP.
Ни gcc, ни icc, ни clang (на godbolt) не использовали вывод CF SHR, всегда используя AND или TEST. Глупые компиляторы.:P Это отличные образцы сложной техники, но умный человек часто может победить их в небольших задачах. (Конечно, если подумать об этом в тысячи-миллионы раз дольше! Компиляторы не используют исчерпывающие алгоритмы для поиска всех возможных способов выполнения задач, потому что это займет слишком много времени при оптимизации большого количества встроенного кода, что и является они делают лучше всего. Они также не моделируют конвейер в целевой микроархитектуре, по крайней мере, не так подробно, как IACA или другие инструменты статического анализа; они просто используют некоторую эвристику.)
Простое развертывание цикла не поможет; это узкое место цикла в задержке цепочки зависимостей, переносимой циклом, а не в издержках цикла / пропускной способности. Это означает, что он будет хорошо работать с гиперпоточностью (или любым другим видом SMT), так как у ЦП много времени для чередования инструкций из двух потоков. Это будет означать распараллеливание цикла в main, но это нормально, потому что каждый поток может просто проверить диапазон n значения и производят пару целых чисел в результате.
Чередование вручную в пределах одного потока также может быть целесообразным. Может быть, вычислить последовательность для пары чисел параллельно, поскольку каждый из них принимает только пару регистров, и все они могут обновлять одно и то же max / maxi, Это создает больше параллелизма на уровне команд.
Хитрость заключается в том, чтобы решить, стоит ли ждать, пока все n ценности достигли 1 прежде чем получить еще одну пару стартовых n значения, или следует ли прорваться и получить новую начальную точку только для той, которая достигла конечного условия, не касаясь регистров для другой последовательности. Вероятно, лучше поддерживать каждую цепочку в работе с полезными данными, в противном случае вам придется условно увеличивать ее счетчик.
Вы могли бы даже сделать это с SSE-упакованным материалом сравнения, чтобы условно увеличить счетчик для векторных элементов, где n не достиг 1 еще. А затем, чтобы скрыть еще большую задержку реализации условного приращения SIMD, вам нужно сохранить больше векторов n ценности в воздухе. Может быть, стоит только с вектором 256b (4x uint64_t).
Я думаю, что лучшая стратегия для обнаружения 1 "Липкий" означает маскировать вектор всех единиц, которые вы добавляете для увеличения счетчика. Итак, после того как вы увидели 1 в элементе вектор приращения будет иметь ноль, а +=0 - это неоперация.
Непроверенная идея для ручной векторизации
# 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.
Вы можете и должны реализовать это с помощью встроенных, а не рукописных асм.
Алгоритмизация / улучшение реализации:
Помимо простой реализации той же логики с более эффективным asm, ищите способы упростить логику или избежать лишней работы. например, запоминать, чтобы обнаружить общие окончания последовательностей. Или, что еще лучше, посмотрите на 8 конечных битов одновременно (ответ Гнашера)
@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 моп, 2с латентность. (У них есть входная зависимость от FLAGS, потому что count=0 означает, что флаги не изменены. Они обрабатывают это как зависимость от данных и принимают несколько мопов, потому что моп может иметь только 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 (до Skylake) по-прежнему имеет ложную зависимость от якобы выходного операнда только для записи, как и BSF, для поддержки недокументированного поведения, при котором BSF с input = 0 оставляет свое назначение неизменным. Так что вам нужно обойти это, если не оптимизировать только для Skylake, так что нечего извлекать из дополнительного байта REP. (Intel часто выходит за рамки того, что требует руководство ISA для x86, чтобы избежать взлома широко используемого кода, который зависит от того, чего он не должен, или который запрещен задним числом. Например, Windows 9x не предполагает спекулятивной предварительной выборки записей TLB, что было безопасно когда код был написан, до того как Intel обновила правила управления TLB.)
В любом случае, LZCNT/TZCNT на Haswell имеют такое же ложное депо, что и POPCNT: см. Эти вопросы и ответы. Вот почему в выходных данных gcc для asm для кода @Veedrac вы видите, что он разрывает цепочку dep с нулями xor в регистре, который он собирается использовать в качестве места назначения TZCNT, когда он не использует dst=src. Поскольку TZCNT/LZCNT/POPCNT никогда не оставляют место назначения неопределенным или неизменным, эта ложная зависимость от вывода на процессорах Intel является чисто ошибкой / ограничением производительности. Предположительно, стоит иметь некоторые транзисторы / мощность, чтобы они вели себя как другие мопы, которые идут к одному и тому же исполнительному устройству. Единственный видимый программный плюс - это взаимодействие с другим микроархитектурным ограничением: они могут объединять операнд памяти с режимом индексированной адресации в Haswell, но в Skylake, где Intel удалила ложную зависимость для LZCNT / TZCNT, они "не ламинируют" индексированные режимы адресации, в то время как POPCNT все еще может микрозонить любой дополнительный режим.
Улучшения идей / кода из других ответов:
Ответ @hidefromkgb содержит приятное замечание, что вы гарантированно сможете сделать один правый сдвиг после 3n+1. Вы можете вычислить это более эффективно, чем просто пропустить проверки между этапами. Однако реализация asm в этом ответе не работает (это зависит от OF, который не определен после SHRD со счетом> 1), и медленно: ROR rdi,2 быстрее чем SHRD rdi,rdi,2 и использование двух инструкций CMOV на критическом пути медленнее, чем дополнительный тест, который может выполняться параллельно.
Я поместил исправленный / улучшенный C (который направляет компилятор для создания лучшего asm) и проверил + работает быстрее asm (в комментариях под C) на Godbolt: см. Ссылку в ответе @hidefromkgb. (Этот ответ достиг предела в 30 тыс. Символов из больших URL-адресов Godbolt, но короткие ссылки могут гнить и в любом случае были слишком длинными для goo.gl.)
Также улучшена печать вывода, чтобы преобразовать в строку и сделать один write() вместо того, чтобы писать один символ за раз. Это сводит к минимуму влияние на сроки всей программы с perf stat ./collatz (для записи счетчиков производительности), и я удалил некоторые из некритических асм.
@ Код Ведрак
Я получил очень небольшое ускорение от смещения вправо настолько, насколько мы знаем, что нужно сделать, и проверки продолжения цикла. С 7,5 с для предела =1e8 до 7,275 с на Core2Duo (Merom) с коэффициентом развертывания 16.
код + комментарии к Godbolt. Не используйте эту версию с Clang; это делает что-то глупое с петлей отсрочки. Использование счетчика ТМП 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,
Вывод обеих программ одинаков: максимальная последовательность = 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, все эти шаги, пока вы не разделите их на два восемь раз, полностью определяются этими восемью битами. Например, если последние восемь битов - 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 действительно не велико.
На довольно не связанной ноте: больше хаков производительности!
[первая "гипотеза" была окончательно опровергнута @ShreevatsaR; удалены]
При обходе последовательности мы можем получить только 3 возможных случая в 2-окрестности текущего элемента
N(показано первым):- [даже странно]
- [нечетный] [четный]
- [даже] [даже]
Прыгнуть через эти 2 элемента означает вычислить
(N >> 1) + N + 1,((N << 1) + N + 1) >> 1а такжеN >> 2соответственно.Докажем, что для обоих случаев (1) и (2) можно использовать первую формулу,
(N >> 1) + N + 1,Случай (1) очевиден. Случай (2) подразумевает
(N & 1) == 1, поэтому, если мы предположим (без ограничения общности), что N имеет длину 2 бита, а его битыbaот наиболее до наименее значимого, тоa = 1и имеет место следующее:(N << 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBbгде
B = !b, Сдвиг вправо первого результата дает нам именно то, что мы хотим.QED:
(N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1,Как доказано, мы можем проходить последовательность из 2 элементов одновременно, используя одну троичную операцию. Еще 2 раза сокращение времени.
Полученный алгоритм выглядит так:
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;
}
Здесь мы сравниваем n > 2 потому что процесс может остановиться на 2 вместо 1, если общая длина последовательности нечетна.
[РЕДАКТИРОВАТЬ:]
Давайте переведем это в сборку!
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;
Используйте эти команды для компиляции:
nasm -f elf64 file.asm
ld -o file file.o
Смотрите C и улучшенную / исправленную версию asm от Peter Cordes на Godbolt. (примечание редактора: извините за добавление моих материалов в ваш ответ, но мой ответ достиг предела 30 тыс. символов по ссылкам Godbolt + текст!)
Программы на C++ транслируются в ассемблерные программы во время генерации машинного кода из исходного кода. Было бы практически неправильно сказать, что сборка происходит медленнее, чем в C++. Более того, сгенерированный двоичный код отличается от компилятора к компилятору. Таким образом, умный компилятор C++ может генерировать двоичный код, более оптимальный и эффективный, чем код тупого ассемблера.
Однако я считаю, что ваша методология профилирования имеет определенные недостатки. Ниже приведены общие рекомендации по профилированию:
- Убедитесь, что ваша система находится в нормальном / бездействующем состоянии. Остановите все запущенные процессы (приложения), которые вы запустили или которые интенсивно используют ЦП (или опросите по сети).
- Ваш размер данных должен быть больше по размеру.
- Ваш тест должен длиться более 5-10 секунд.
- Не полагайтесь только на один образец. Выполните свой тест N раз. Соберите результаты и рассчитайте среднее значение или медиану результата.
Из комментариев:
Но этот код никогда не останавливается (из-за целочисленного переполнения)!?! Ив Дауст
Для многих номеров это не будет переполнено.
Если он переполнится - для одного из этих неудачных начальных начальных чисел переполненное число, скорее всего, сойдется к 1 без другого переполнения.
Тем не менее, это ставит интересный вопрос, есть ли циклическое число семян переполнения?
Любая простая конечная сходящаяся серия начинается со значения двух степеней (достаточно очевидно?).
2 ^ 64 переполнится до нуля, что является неопределенным бесконечным циклом согласно алгоритму (заканчивается только 1), но наиболее оптимальное решение в ответе закончится из-за shr rax производя ZF=1.
Можем ли мы произвести 2^64? Если начальный номер 0x5555555555555555, это нечетное число, затем следующее число 3n+1, что 0xFFFFFFFFFFFFFFFF + 1 знак равно 0, Теоретически в неопределенном состоянии алгоритма, но оптимизированный ответ johnfound восстановится, выйдя на ZF=1. cmp rax,1 Петра Кордеса закончится бесконечным циклом (вариант 1 КЭД, "дешево" через неопределенный 0 число).
Как насчет более сложного числа, которое создаст цикл без 0? Честно говоря, я не уверен, что моя математическая теория слишком туманная, чтобы всерьез понять, как с этим бороться. Но интуитивно я бы сказал, что ряд будет сходиться к 1 для каждого числа: 0 <число, поскольку формула 3n + 1 будет медленно превращать каждый не-2 простой множитель исходного числа (или промежуточного) в некоторую степень 2, рано или поздно, Поэтому нам не нужно беспокоиться о бесконечном цикле для оригинальной серии, только переполнение может помешать нам.
Поэтому я просто поместил несколько цифр в лист и посмотрел на усеченные 8-битные числа.
Есть три значения, переполняющие 0: 227, 170 а также 85 (85 идти прямо к 0 двое других продвигаются к 85).
Но нет смысла создавать циклическое переполнение.
Как ни странно, я сделал проверку, которая является первым числом, пострадавшим от 8-битного усечения, и уже 27 подвергается воздействию! Это достигает значения 9232 в правильной не усеченной последовательности (первое усеченное значение 322 на 12-м шаге), и максимальное значение, достигнутое для любого из 2-255 входных чисел без усечения, равно 13120 (для 255 само по себе), максимальное количество шагов, чтобы сходиться к 1 около 128 (+-2, не уверен, стоит ли считать "1" и т. Д.).
Достаточно интересно (для меня) число 9232 является максимальным для многих других исходных номеров, что в этом особенного?:-О 9232 знак равно 0x2410... хм... не знаю.
К сожалению, я не могу получить глубокое понимание этой серии, почему она сходится и каковы последствия обрезания их до k бит, но с cmp number,1 Завершая условие, безусловно, можно поместить алгоритм в бесконечный цикл с определенным входным значением, оканчивающимся как 0 после усечения.
Но ценность 27 переполнение для 8-битного случая является своего рода предупреждением, это похоже на подсчет количества шагов для достижения значения 1, вы получите неправильный результат для большинства чисел из общего набора целых k-битных чисел. Для 8-битных целых чисел 146 чисел из 256 повлияли на ряды усечением (некоторые из них могут все же случайно попасть на правильное число шагов, может быть, мне лень это проверять).
В случае проблемы Коллатца вы можете значительно повысить производительность, кэшируя "хвосты". Это компромисс между временем и памятью. Смотрите: памятка ( https://en.wikipedia.org/wiki/Memoization). Вы также можете посмотреть на решения динамического программирования для других компромиссов времени / памяти.
Пример реализации Python:
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))
Вы не опубликовали код, сгенерированный компилятором, поэтому здесь есть некоторые догадки, но даже не увидев его, можно сказать, что это:
test rax, 1
jpe even
... имеет 50% -ную вероятность ошибочного прогнозирования отрасли, и это будет дорого.
Компилятор почти наверняка выполнит оба вычисления (что стоит пренебрежимо дороже, так как div/mod имеет довольно большую задержку, поэтому умножение-добавление "бесплатно") и следует CMOV. Который, конечно, имеет нулевой процент вероятности быть неверно предсказанным.
Как общий ответ, специально не предназначенный для этой задачи: во многих случаях вы можете значительно ускорить любую программу, делая улучшения на высоком уровне. Как вычисление данных один раз, а не несколько раз, полное избежание ненужной работы, наилучшее использование кэшей и так далее. Эти вещи намного проще сделать на языке высокого уровня.
Написание ассемблерного кода позволяет улучшить работу оптимизирующего компилятора, но это тяжелая работа. И как только это будет сделано, ваш код будет сложнее модифицировать, поэтому гораздо сложнее добавить алгоритмические улучшения. Иногда процессор имеет функции, которые вы не можете использовать на языке высокого уровня, встроенная сборка часто полезна в этих случаях и все же позволяет вам использовать язык высокого уровня.
В задачах Эйлера большую часть времени вы добиваетесь успеха, создавая что-то, выясняя, почему это медленно, создавая что-то лучше, находя, почему это медленно, и так далее, и так далее. Это очень и очень сложно, используя ассемблер. Лучший алгоритм на половине возможной скорости обычно побеждает худший алгоритм на полной скорости, и получить полную скорость в ассемблере не тривиально.
Даже не смотря на сборку, самая очевидная причина в том, что /= 2 вероятно оптимизирован как >>=1 и многие процессоры работают очень быстро. Но даже если процессор не имеет операции сдвига, целочисленное деление происходит быстрее, чем деление с плавающей запятой.
Изменить: ваш milage может варьироваться в зависимости от "целочисленное деление быстрее, чем деление с плавающей точкой" выше. Комментарии, приведенные ниже, показывают, что современные процессоры отдают предпочтение оптимизации деления fp над целочисленным делением. Так что, если кто-то ищет наиболее вероятную причину ускорения, о которой спрашивает этот поток, тогда оптимизация компилятора /=2 как >>=1 будет лучшим 1-м местом для поиска.
На несвязанной ноте, если n странное выражение n*3+1 всегда будет четным Так что проверять не нужно. Вы можете изменить эту ветку на
{
n = (n*3+1) >> 1;
count += 2;
}
Таким образом, все заявление будет
if (n & 1)
{
n = (n*3 + 1) >> 1;
count += 2;
}
else
{
n >>= 1;
++count;
}
Простой ответ:
делать MOV RBX, 3 и MUL RBX дорого; просто ДОБАВЬТЕ RBX, RBX дважды
ADD 1, вероятно, быстрее, чем INC здесь
MOV 2 и DIV очень дороги; просто сместись вправо
64-битный код обычно заметно медленнее, чем 32-битный код, и проблемы с выравниванием более сложны; с такими маленькими программами вы должны упаковать их, чтобы выполнять параллельные вычисления, чтобы иметь шанс быть быстрее 32-битного кода
Если вы сгенерируете список сборок для вашей программы на C++, вы увидите, чем он отличается от вашей сборки.