Я написал эти два решения для 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 мс с -O3, 305 мс с-O0

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

См. Руководство по оптимизации сборки Agner Fog, чтобы узнать, как написать эффективный ассемблер. У него также есть таблицы инструкций и руководство по микроархам для конкретных деталей для конкретных процессоров. Смотрите такжеx86 пометьте вики для большего количества ссылок

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

Обычно вы можете позволить компилятору делать свое дело, особенно если вы пытаетесь написать C ++, который может эффективно компилироваться . Также посмотрите, быстрее ли сборка, чем скомпилированные языки? , Один из ответов содержит ссылки на эти аккуратные слайды, показывающие, как различные компиляторы C оптимизируют некоторые действительно простые функции с помощью интересных трюков. Доклад Мэтта Годболта на CppCon2017 « Что мой компилятор сделал для меня в последнее время? Откручивание крышки компилятора »в том же духе.

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.

Как вы можете видеть из -O0вывода asm gcc ( проводника компилятора Godbolt ), он использует только инструкции смены . 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 делает что-то классное, и вы можете держать 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 ref ручной ввод ). (IDK, если gcc попытался и не смог доказать, что nне может быть отрицательным, или что. Переполнение со знаком - это неопределенное поведение, так что он должен был это сделать.)

Вы должны были использовать uint64_t n, так что это может просто SHR. И поэтому он переносим на системы, где 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).

Вход FLAGS 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 , как предварительно IVB, и AMD Bulldozer семьи, где МОВ не нулевой задержкой. Потерянные инструкции MOV компилятора влияют на критический путь. Complex-LEA и CMOV BD имеют более низкую задержку (2c и 1c соответственно), так что это большая доля задержки. Кроме того, узкие места пропускной способности становятся проблемой, потому что у этого есть только два целочисленных канала ALU. См. Ответ @ johnfound , где он получил результаты синхронизации с процессором AMD.

Даже в Haswell эта версия может немного помочь, избегая некоторых случайных задержек, когда некритический моп украл порт выполнения с одного на критическом пути, задерживая выполнение на 1 цикл. (Это называется конфликтом ресурсов). Он также сохраняет регистр, который может помочь при nпараллельном выполнении нескольких значений в цикле с чередованием (см. Ниже).

Задержка LEA зависит от режима адресации , от процессоров семейства Intel SnB. 3c для 3 компонентов ( [base+idx+const]что требует двух отдельных добавлений), но только 1c с 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

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    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 (pre-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 является ошибкой / ограничением производительности. Предположительно, стоит иметь некоторые транзисторы / мощность, чтобы они вели себя как другие мопы, которые идут в один и тот же исполнительный модуль. Единственным преимуществом является взаимодействие с еще одним ограничением uarch: они могут микросинтезировать операнд памяти с режимом индексированной адресации в Haswell, но в Skylake, где Intel удалила ложное депонирование для LZCNT / TZCNT, они «не ламинируют» индексированные режимы адресации, в то время как POPCNT все еще может микрозонить любой дополнительный режим.

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

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

Я поместил исправленный / улучшенный 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; это делает что-то глупое с петлей отсрочки. Использование счетчика 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.

Вывод обеих программ одинаков: максимальная последовательность = 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(показан первым):

  1. [даже странно]
  2. [нечетный] [четный]
  3. [даже] [даже]

  Для того, чтобы перескочить мимо этих 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. Сдвиг вправо первого результата дает нам именно то, что мы хотим.

  КЭД: (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 ++ может генерировать двоичный код, более оптимальный и эффективный, чем код тупого ассемблера.

Однако я считаю, что ваша методология профилирования имеет определенные недостатки. Ниже приведены общие рекомендации по профилированию:

1. Убедитесь, что ваша система находится в нормальном / бездействующем состоянии. Остановите все запущенные процессы (приложения), которые вы запустили или которые интенсивно используют ЦП (или опросите по сети).
2. Ваш размер данных должен быть больше по размеру.
3. Ваш тест должен длиться более 5-10 секунд.
4. Не полагайтесь только на один образец. Выполните свой тест N раз. Соберите результаты и рассчитайте среднее значение или медиану результата.

Для решения проблемы Коллатца вы можете значительно повысить производительность, кэшируя «хвосты». Это компромисс между временем и памятью. Смотрите: памятка ( 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))

Из комментариев:

Но этот код никогда не останавливается (из-за целочисленного переполнения)!?! Ив Дауст

Для многих номеров это не будет переполнено.

Если он будет переливаться - одно из тех невезучих начальных семян, переполненное число будет весьма вероятно , сходится к 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является максимальным для многих других исходных номеров, что в этом особенного? : -O 9232= 0x2410... хммм .. не знаю.

К сожалению, я не могу получить глубокое понимание этой серии, почему она сходится и каковы последствия урезания их до k бит, но с cmp number,1условием завершения, безусловно, можно поместить алгоритм в бесконечный цикл с определенным входным значением, заканчивающимся, как 0после усечение.

Но 27переполнение значения в 8-битном случае является своего рода предупреждением, похоже, если вы посчитаете количество шагов для достижения значения 1, вы получите неправильный результат для большинства чисел из полного набора k-битных целых чисел. Для 8-битных целых чисел 146 чисел из 256 повлияли на ряды усечением (некоторые из них могут все же случайно попасть на правильное число шагов, может быть, мне лень это проверять).

Вы не опубликовали код, сгенерированный компилятором, поэтому здесь есть некоторые догадки, но даже не увидев его, можно сказать, что это:

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, вероятно, быстрее, чем здесь

• MOV 2 и DIV очень дороги; просто сместись вправо

• 64-битный код обычно заметно медленнее, чем 32-битный код, и проблемы с выравниванием более сложны; с такими маленькими программами вы должны упаковать их, чтобы выполнять параллельные вычисления, чтобы иметь шанс быть быстрее 32-битного кода

Если вы сгенерируете список сборок для вашей программы на C ++, вы увидите, чем он отличается от вашей сборки.