Код C ++ для проверки гипотезы Коллатца быстрее, чем рукописная сборка - почему?

833

Я написал эти два решения для 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).

сын джеффер
источник
232
Вы изучили ассемблерный код, который GCC генерирует для вашей программы на C ++?
Руах
69
Скомпилируйте с, -Sчтобы получить сборку, сгенерированную компилятором. Компилятор достаточно умен, чтобы понять, что модуль выполняет деление одновременно.
user3386109
267
Я думаю, что у вас есть варианты 1. Ваша измерительная техника несовершенна, 2. Компилятор пишет лучшую сборку, чем вы, или 3. Компилятор использует магию.
Галик
18
@jefferson Компилятор может использовать более быструю грубую силу. Например, может быть, с инструкциями SSE.
user253751

Ответы:

1896

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

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

Смотрите также этот более общий вопрос об избиении компилятора рукописным 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)

Питер Кордес
источник
4
Некоторое время назад я опробовал векторизованный подход, он не помог (потому что вы можете добиться большего успеха в скалярном коде с помощью, tzcntи вы заблокированы самой продолжительной последовательностью среди ваших векторных элементов в векторизованном случае).
EOF
3
@EOF: нет, я имел в виду выхода из внутреннего цикла , когда любой один из хитов элементов вектора 1, вместо того , чтобы, когда они все имеют (легко обнаружить с PCMPEQ / PMOVMSK). Затем вы используете PINSRQ и прочее, чтобы поиграть с одним завершившимся элементом (и его счетчиками) и вернуться в цикл. Это может легко превратиться в потерю, когда вы слишком часто выходите из внутреннего цикла, но это означает, что вы всегда получаете 2 или 4 элемента полезной работы, выполняемой на каждой итерации внутреннего цикла. Хороший момент о запоминании, хотя.
Питер Кордес
4
@jefferson Лучшее, что мне удалось - это godbolt.org/g/1N70Ib . Я надеялся, что смогу сделать что-то умнее, но, похоже, нет.
Veedrac
88
То, что поражает меня невероятными ответами, такими как это, является знанием, показанным в таких деталях. Я никогда не буду знать язык или систему до такого уровня, и я не знаю, как. Молодцы, сэр.
camden_kid
9
Легендарный ответ !!
Сумит Джайн
104

Утверждать, что компилятор 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.

johnfound
источник
6
Да, это умно. SHR устанавливает ZF, только если EAX был 1 (или 0). Я упустил это при оптимизации -O3вывода gcc , но я обнаружил все другие оптимизации, которые вы внесли во внутренний цикл. (Но почему вы используете LEA для приращения счетчика вместо INC? В этой точке нормально закрывать флаги и приводить к замедлению всего, кроме, возможно, P4 (ложная зависимость от старых флагов для INC и SHR). LEA может ' не может работать на таком количестве портов, что может привести к конфликтам ресурсов, что приведет к более частой задержке критического пути.)
Питер Кордес
4
О, на самом деле Bulldozer может стать узким местом по производительности при выводе компилятора. Он имеет более низкую задержку CMOV и трехкомпонентный LEA, чем Haswell (который я рассматривал), поэтому в вашем коде цепочка dep, переносимая циклами, составляет всего 3 цикла. Он также не имеет инструкций MOV с нулевой задержкой для целочисленных регистров, поэтому потраченные на M ++ инструкции M ++ фактически увеличивают задержку критического пути и представляют собой большую проблему для Bulldozer. Так что да, ручная оптимизация действительно значительно превосходит компилятор для процессоров, которые не настолько ультрасовременны, чтобы прожевать бесполезные инструкции.
Питер Кордес
95
« Утверждать, что компилятор C ++ лучше, является очень плохой ошибкой. И особенно в этом случае. Человек всегда может сделать код лучше, что и эта конкретная проблема является хорошей иллюстрацией этого утверждения». Вы можете отменить его, и он будет столь же действительным , « Утверждать, что человек лучше, является очень плохой ошибкой. И особенно в этом случае. Человек всегда может сделать код хуже , чем тот, и этот конкретный вопрос является хорошей иллюстрацией этого утверждения». Так что я не думаю, что у вас есть смысл здесь , такие обобщения неверны.
luk32
5
@ luk32 - Но у автора вопроса вообще не может быть никаких аргументов, потому что его знание ассемблера близко к нулю. Любые аргументы о человеке против компилятора неявно предполагают человека со средним уровнем знаний. Более того: теорема «написанный человеком код всегда будет лучше или такой же, как код, сгенерированный компилятором», очень легко доказать формально.
johnfound
30
@ luk32: опытный человек может (и обычно должен) начать с вывода компилятора. Так что, пока вы тестируете свои попытки убедиться, что они действительно быстрее (на целевом оборудовании, которое вы настраиваете), вы не можете сделать хуже, чем компилятор. Но да, я должен согласиться, что это довольно сильное утверждение. Компиляторы обычно работают намного лучше, чем начинающие программисты. Но обычно можно сохранить одну или две инструкции по сравнению с тем, что предлагают компиляторы. (Не всегда на критическом пути, хотя, в зависимости от уарча). Они очень полезные части сложной техники, но они не "умные".
Питер Кордес
24

Для большей производительности: простое изменение заключается в том, что после 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 действительно не велико.

gnasher729
источник
2
Или создайте таблицы поиска данных для умножения и добавления констант вместо переключателя. Индексирование двух таблиц по 256 записей быстрее, чем таблица переходов, и компиляторы, вероятно, не ищут этого преобразования.
Питер Кордес
1
Хм, я на минуту подумал, что это наблюдение может доказать гипотезу Коллатца, но нет, конечно, нет. На каждые возможные 8-битные конечные шаги уходит конечное число шагов, пока они не пройдут. Но некоторые из этих концевых 8-битных комбинаций удлиняют остальную часть цепочки битов более чем на 8, поэтому это не может исключать неограниченный рост или повторяющийся цикл.
Питер Кордес
Для обновления countвам нужен третий массив, верно? adders[]не говорит вам, сколько правых сдвигов было сделано.
Питер Кордес
Для больших таблиц стоило бы использовать более узкие типы для увеличения плотности кэша. На большинстве архитектур нагрузка с нулевым расширением uint16_tочень дешева. На x86 это так же дешево, как расширение нуля от 32-битной unsigned intдо uint64_t. (MOVZX из памяти на процессорах Intel нужно только моп нагрузки порта, но процессоры AMD действительно нуждаются в АЛУ , а также.) Ах Кстати, почему вы используете size_tдля lastBits? Это 32-битный тип с -m32и даже -mx32(длинный режим с 32-битными указателями). Это определенно неправильный тип для n. Просто используйте unsigned.
Питер Кордес
20

На довольно не связанной ноте: больше хаков производительности!

  • [первая «гипотеза» была окончательно опровергнута @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 + текст!)

hidefromkgb
источник
2
Нет такого интеграла Q, что 12 = 3Q + 1. Ваш первый пункт не так, метинкс.
Veedrac
1
@Veedrac: поэкспериментировал с этим: он может быть реализован с лучшей asm, чем реализация в этом ответе, используя ROR / TEST и только один CMOV. Этот асм кодирует бесконечные циклы на моем процессоре, поскольку он, очевидно, полагается на OF, который не определен после SHRD или ROR с числом> 1. Он также идет на все, чтобы попытаться избежать mov reg, imm32, очевидно, чтобы сохранить байты, но затем он использует 64-битная версия регистрируется везде, даже для xor rax, raxнее, поэтому в ней много ненужных префиксов REX. Очевидно, нам нужно только REX для регистров, содержащихся nво внутреннем цикле, чтобы избежать переполнения.
Питер Кордес
1
Результаты синхронизации (от Core2Duo E6600: Merom 2,4 ГГц. Complex-LEA = задержка 1c, CMOV = 2c) . Лучшая одношаговая реализация внутреннего цикла asm (от Johnfound): 111 мс за цикл этого цикла @main. Вывод компилятора из моей де-обфусцированной версии этого C (с некоторыми переменными tmp): clang3.8 -O3 -march=core2: 96ms. gcc 5.2: 108 мс. Из моей улучшенной версии внутреннего цикла asm clang: 92 мс (должно быть заметно большее улучшение в семействе SnB, где комплексный LEA равен 3c, а не 1c). Из моей улучшенной + рабочей версии этого цикла asm (с использованием ROR + TEST, а не SHRD): 87мс. Измерено с 5 повторениями перед печатью
Питер Кордес
2
Вот первые 66 рекордсменов (A006877 на OEIS); Четные я выделил жирным шрифтом: 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799, 1117065, 150135 1723519, 2298025, 3064033, 3542887, 3732423, 5649499, 6649279, 8400511, 11200681, 14934241, 15733191, 31466382, 36791535, 63728127, 127456254, 169941673, 226588897, 268549803, 537099606, 670617279, 1341234558
ShreevatsaR
1
@hidefromkgb Отлично! И теперь я ценю вашу другую точку зрения: 4k + 2 → 2k + 1 → 6k + 4 = (4k + 2) + (2k + 1) + 1 и 2k + 1 → 6k + 4 → 3k + 2 = ( 2k + 1) + (k) + 1. Приятное наблюдение!
ShreevatsaR
6

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

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

  1. Убедитесь, что ваша система находится в нормальном / бездействующем состоянии. Остановите все запущенные процессы (приложения), которые вы запустили или которые интенсивно используют ЦП (или опросите по сети).
  2. Ваш размер данных должен быть больше по размеру.
  3. Ваш тест должен длиться более 5-10 секунд.
  4. Не полагайтесь только на один образец. Выполните свой тест N раз. Соберите результаты и рассчитайте среднее значение или медиану результата.
Мангу Сингх Раджпурохит
источник
Да, я не проводил никакого формального профилирования, но я запускал их оба раза и могу сказать 2 секунды из 3 секунд. В любом случае, спасибо за ответ. Я уже собрал много информации здесь
сын Джеффер
9
Вероятно, это не просто ошибка измерения, рукописный код asm использует 64-битную инструкцию DIV вместо сдвига вправо. Смотри мой ответ. Но да, правильные измерения тоже важны.
Питер Кордес
7
Точки марки являются более подходящим форматированием, чем блок кода. Пожалуйста, прекратите помещать ваш текст в блок кода, потому что он не является кодом и не использует моноширинный шрифт.
Питер Кордес
16
Я действительно не вижу, как это отвечает на вопрос. Это не расплывчатый вопрос о том , ассемблера или C ++ код может быть быстрее , --- это очень конкретный вопрос о фактическом коде , который он услужливо предоставленной в самом вопросе. В вашем ответе даже не упоминается ни один из этих кодов и не проводится какое-либо сравнение. Несомненно, ваши советы о том, как оценивать, в основном верны, но их недостаточно, чтобы дать реальный ответ.
Коди Грей
6

Для решения проблемы Коллатца вы можете значительно повысить производительность, кэшируя «хвосты». Это компромисс между временем и памятью. Смотрите: памятка ( 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
Ответ gnasher показывает, что вы можете сделать гораздо больше, чем просто кэшировать хвосты: старшие биты не влияют на то, что происходит дальше, а add / mul только распространяют перенос влево, поэтому старшие биты не влияют на то, что происходит с младшими битами. т. е. вы можете использовать поиск по LUT для одновременной обработки 8 (или любого количества) битов с умножением и добавлением констант для применения к остальным битам. Запоминание хвостов, безусловно, полезно во многих подобных проблемах и для этой проблемы, когда вы еще не думали о лучшем подходе или не доказали его правильность.
Питер Кордес
2
Если я правильно понимаю идею Гнашера выше, я думаю, что хвостовое запоминание - это ортогональная оптимизация. Таким образом, вы могли бы сделать и то и другое. Было бы интересно выяснить, сколько вы можете получить, добавив памятку в алгоритм gnasher.
Эмануэль Ландехольм
2
Возможно, мы сможем удешевить запоминание, сохранив только плотную часть результатов. Установите верхний предел на N, а выше этого, даже не проверяйте память. Ниже используйте hash (N) -> N в качестве хэш-функции, поэтому key = position в массиве и не требует сохранения. Ввод 0средств еще не представлен. Мы можем дополнительно оптимизировать, только сохраняя в таблице нечетное N, поэтому хеш-функция n>>1отбрасывает 1. Запишите пошаговый код, который всегда должен заканчиваться на n>>tzcnt(n)или, чтобы убедиться, что он нечетный.
Питер Кордес
1
Это основано на моей (непроверенной) идее, что очень большие значения N в середине последовательности с меньшей вероятностью будут общими для нескольких последовательностей, поэтому мы не пропускаем слишком много, не запоминая их. Также, что N разумного размера будет частью многих длинных последовательностей, даже тех, которые начинаются с очень большого N. (Это может быть желаемое за действительное; если это неправильно, то только кэширование плотного диапазона последовательных N может проиграть против хэша таблица, в которой могут храниться произвольные ключи.) Проводили ли вы какое-либо тестирование скорости попадания, чтобы увидеть, имеют ли близкие начальные N сходство в значениях их последовательности?
Питер Кордес
2
Вы можете просто сохранить предварительно вычисленные результаты для всех n <N, для некоторого большого N. Таким образом, вам не нужны служебные данные хэш-таблицы. Данные в этой таблице будут в конечном итоге использоваться для каждого начального значения. Если вы просто хотите подтвердить, что последовательность Коллатца всегда заканчивается на (1, 4, 2, 1, 4, 2, ...): это может быть доказано, что это эквивалентно доказательству того, что при n> 1 последовательность в конечном итоге будет быть меньше, чем оригинал. И для этого кеширование хвостов не поможет.
gnasher729
5

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

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

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

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

Ped7g
источник
«переполненное число, скорее всего, будет сходиться к 1 без другого переполнения»: код никогда не останавливается. (Это предположение, так как я не могу дождаться конца времен, чтобы быть уверенным ...)
Ив Дауст
@YvesDaoust о, но это так? ... например, 27серия с усечением 8b выглядит следующим образом: 82 41 124 62 31 94 47 142 71 214 107 66 (усечено) 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 (остальное работает без усечения). Я не понимаю тебя, прости. Он никогда не остановится, если усеченное значение будет равно некоторым из ранее достигнутых в текущем продолжающемся ряду, и я не могу найти такое значение в сравнении с усечением k-бит (но я также не могу понять теорию Math, почему это выдерживает усечение 8/16/32/64 бит, просто интуитивно я думаю, что это работает).
Ped7g
1
Я должен был проверить оригинальное описание проблемы раньше: «Хотя оно еще не доказано (проблема Коллатца), считается, что все стартовые числа заканчиваются на 1». ... хорошо, не удивительно , что я не могу понять его с моими ограниченным туманной Math знаниями ...: D А из моих листовых экспериментов я могу заверить вас , что делает сходиться для каждых 2- 255чисел, либо без усечения (к 1), или с 8-битным усечением (до ожидаемого 1или 0для трех чисел).
Ped7g
Хем, когда я говорю, что это никогда не останавливается, я имею в виду ... что это не останавливается. Данный код работает вечно, если вы предпочитаете.
Ив Дауст
1
Проголосовал за анализ того, что происходит при переполнении. Цикл на основе CMP может использовать cmp rax,1 / jna(то есть do{}while(n>1)), чтобы также завершиться на нуле. Я подумал о создании инструментальной версии цикла, который записывает максимальное nвидимое, чтобы дать представление о том, как близко мы подошли к переполнению.
Питер Кордес
5

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

test rax, 1
jpe even

... имеет 50% -ную вероятность ошибочного прогнозирования ветки, и это будет дорого.

Компилятор почти наверняка выполнит оба вычисления (что стоит пренебрежимо дороже, так как div / mod имеет довольно большую задержку, поэтому умножение-добавление «бесплатно») и следует CMOV. Который, конечно, имеет нулевой процент вероятности быть неверно предсказанным.

Damon
источник
1
Существует некоторая закономерность ветвления; например, за нечетным числом всегда следует четное число. Но иногда 3n + 1 оставляет несколько завершающих нулевых битов, и именно тогда это будет неправильно предсказано. Я начал писать о делении в своем ответе и не обращал внимания на этот другой большой красный флаг в коде ОП. (Также обратите внимание, что использование условия четности действительно странно по сравнению только с JZ или CMOVZ. Это также хуже для ЦП, потому что ЦП Intel могут использовать макрос TEST / JZ, но не TEST / JPE. Агнер Фог говорит, что AMD может объединить любой TEST / CMP с любым JCC, так что в этом случае это только хуже для читателей)
Питер Кордес
5

Даже не смотря на сборку, наиболее очевидная причина заключается в том, что /= 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;
}
Дмитрий Рубанович
источник
4
Целочисленное деление на самом деле не быстрее, чем деление FP на современных процессорах x86. Я думаю, это связано с тем, что Intel / AMD тратят больше транзисторов на свои делители FP, потому что это более важная операция. (Целочисленное деление на константы может быть оптимизировано для умножения на модульное обратное). Проверьте таблицы insn Agner Fog и сравните DIVSD (число с плавающей запятой двойной точности) с DIV r32(32-разрядное целое число без знака) или DIV r64(намного более медленное 64-разрядное целое число без знака). Специально для пропускной способности разделение FP выполняется намного быстрее (одиночная мера вместо микрокодирования и частично конвейерная передача), но задержка также лучше.
Питер Кордес
1
Например, на процессоре Haswell OP: DIVSD составляет 1 моп, задержка 10-20 циклов, один на пропускную способность 8-14 с. div r64составляет 36 моп, задержка 32-96 с и пропускная способность 21-74 с. Skylake обладает еще более высокой пропускной способностью деления FP (конвейерная передача по одному на 4c с не намного лучшей задержкой), но не намного быстрее целочисленного div. То же самое и в семействе AMD Bulldozer: DIVSD - 1M-op, задержка 9-27c, по одному на пропускную способность 4.5-11c. div r64составляет 16M-ops, задержка 16-75c, по одному на пропускную способность 16-75c.
Питер Кордес
1
Разве деление FP в основном не совпадает с показателями целочисленного вычитания, мантиссы с целочисленным делением, обнаружения денормалей? И эти 3 шага могут быть сделаны параллельно.
MSalters
2
@MSalters: да, это звучит правильно, но с шагом нормализации в конце сдвигаются биты между экспонентой и мантиссой. doubleимеет 53-битную мантиссу, но все же значительно медленнее, чем div r32на Haswell. Так что это определенно только вопрос того, сколько аппаратных средств Intel / AMD выбрасывает для этой проблемы, потому что они не используют одни и те же транзисторы как для целочисленных, так и для делителей fp. Целое число является скалярным (нет деления на целое-SIMD), а вектор один обрабатывает векторы 128b (а не 256b, как в других векторных ALU). Важно то, что целочисленный div - это много мопов, большое влияние на окружающий код.
Питер Кордес
Эх, не сдвигайте биты между мантиссой и показателем степени, но нормализуйте мантиссу со сдвигом и добавляйте величину сдвига к показателю степени.
Питер Кордес
4

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

Написание ассемблерного кода позволяет улучшить работу оптимизирующего компилятора, но это тяжелая работа. И как только это будет сделано, ваш код будет сложнее изменить, поэтому гораздо сложнее добавить алгоритмические улучшения. Иногда процессор имеет функции, которые вы не можете использовать на языке высокого уровня, встроенная сборка часто полезна в этих случаях и все же позволяет вам использовать язык высокого уровня.

В задачах Эйлера большую часть времени вы добиваетесь успеха, создавая что-то, выясняя, почему это медленно, создавая что-то лучше, находя, почему это медленно, и так далее, и так далее. Это очень, очень сложно, используя ассемблер. Лучший алгоритм на половине возможной скорости обычно побеждает худший алгоритм на полной скорости, и получить полную скорость в ассемблере не тривиально.

gnasher729
источник
2
Полностью с этим согласен. gcc -O3сделал код, который был в пределах 20% от оптимального на Haswell, для этого точного алгоритма. (Получение этих ускорений было основной целью моего ответа только потому, что это то, что задал вопрос, и имеет интересный ответ, а не потому , что это правильный подход.) Значительно большие ускорения были получены из преобразований, которые компилятор будет крайне маловероятно искать как откладывание правых сдвигов или выполнение 2 шагов за раз. Гораздо большие ускорения, чем это может быть в памятных / поисковых таблицах. Все еще исчерпывающее испытание, но не чисто грубая сила.
Питер Кордес
2
Тем не менее, наличие простой, очевидно правильной реализации чрезвычайно полезно для тестирования других реализаций. Вероятно, я просто посмотрю на вывод asm, чтобы убедиться, что gcc сделал это без ответвлений, как я ожидал (в основном из любопытства), а затем перешел к алгоритмическим улучшениям.
Питер Кордес
-2

Простой ответ:

  • делать MOV RBX, 3 и MUL RBX дорого; просто ДОБАВЬТЕ RBX, RBX дважды

  • ADD 1, вероятно, быстрее, чем здесь

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

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

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

Тайлер Дурден
источник
4
1): добавление 3 раза было бы глупо по сравнению с LEA. Также mul rbxна процессоре Haswell OP имеется 2 мопа с задержкой 3c (и 1 на тактовую пропускную способность). imul rcx, rbx, 3только 1 моп, с той же задержкой 3c. Две инструкции ADD будут 2 мопа с задержкой 2c.
Питер Кордес
5
2) ADD 1, вероятно, быстрее, чем здесь . Нет, OP не использует Pentium4 . Ваша точка 3) является единственно правильной частью этого ответа.
Питер Кордес
5
4) звучит как полная чушь. 64-битный код может быть медленнее с массивными структурами данных, потому что большие указатели означают большую площадь кеша. Но этот код работает только в регистрах, и проблемы с выравниванием кода одинаковы в 32- и 64-битном режиме. (Как и проблемы с выравниванием данных, понятия не имею, о чем вы говорите, поскольку выравнивание является более серьезной проблемой для x86-64). Во всяком случае, код даже не касается памяти внутри цикла.
Питер Кордес
Комментатор понятия не имеет, о чем идет речь. Выполнение MOV + MUL на 64-битном процессоре будет примерно в три раза медленнее, чем добавление регистра к себе дважды. Другие его замечания в равной степени неверны.
Тайлер Дурден
6
Ну, MOV + MUL определенно глуп, но MOV + ADD + ADD по-прежнему глупо (на самом деле ADD RBX, RBXдвойное выполнение умножится на 4, а не на 3). Безусловно, лучший способ lea rax, [rbx + rbx*2]. Или, сделав это трехкомпонентным LEA, сделайте также +1 с lea rax, [rbx + rbx*2 + 1] (задержка 3c на HSW вместо 1, как я объяснил в своем ответе). Мое мнение состояло в том, что 64-битное умножение не очень дорого для недавние процессоры Intel, потому что они имеют безумно быстрые целочисленные единицы умножения (даже по сравнению с AMD, где та же MUL r64задержка составляет 6c, с пропускной способностью один на 4c: даже не полностью конвейерная.
Peter Cordes