Comments 17
А что произойдет, если мы случайно сложим больше, чем 2^13 чисел, произойдет наихудший сценарий и переносы переполнятся? Это же как-то контролируется?
Как-то недожато. Взяли б из питона тогда имплементацию. Там числа как раз представляются в СС с большим основанием, а потом ещё и алгоритмом карацубы все это складывается, а не наивным сложением.
Алгоритм Карацубы – это про умножение. Ну и думаю, что там сложение простое: оптимизация из статьи – для суммирования кучи чисел... По сути, вынос части работы из цикла суммирования.
Для Python, в основных вариантах использования, это всё теряется на фоне _PyLong_New (PyObject_Malloc), поэтому, для 64-бит архитектур, CPython хранит 30-бит цифры (limb) в uint32_t/int32_t.
Ну, а насчёт, недожато, то да, тема автоматической нормализации не раскрыта, но это объективно, 256-бит числа взяты же с потолка, для примера.
В скалярном коде, возможно, потребуется ещё одно, шестое, сложение сложение и один условный переход, а возможно лучше иметь пять условных переходов с достаточно низкой вероятностью перехода, кто знает?
В векторном коде, неопределённость ещё выше.
Мы нормализуем число, начиная справа, определяя, сколько «десяток» в каждом разряде, вычитая эти «десятки» и перенося их в следующий разряд. 672415 и 736606 действительно дают в сумме 1409021, так что система работает!
Получается, проблему переноса разряда просто перенесли в другое место ( извините за тавтологию),и 17 ассемблерных инструкций вместо adc работают быстрее?
Получается, проблему переноса разряда просто перенесли в другое место ( извините за тавтологию),и 17 ассемблерных инструкций вместо adc работают быстрее?
во первых, это концепт: на большом количестве слагаемых это будет выгоднее, чем adc-цепочка из-за instruction-level parallelism, либо если использовать SIMD, то можно использовать векторизацию
во вторых, команд исполнится на ALU не 17, а 13, т.к. mov-команды здесь исполнятся блоком переименования регистров за 0 тактов: https://agner.org/optimize/microarchitecture.pdf разделы "Register allocation and renaming" различных архитектур
Не просто перенесли в другое место, а собрали в одну операцию то, что в наивном варианте надо сделать 4000 раз. Теперь сериализация из-за зависимости по данным происходит не на каждом сложении, а один раз в несколько тысяч сложений.
Если бы у автора был процессор следующего поколения (Broadwell), он бы мог ускорить сложение, используя инструкции ADCX и ADOX, с помощью которых как раз можно распределить 2 сложения. Конечно, на сотне сложений это будет работать медленнее, но на небольшом кол-ве даст больший перфоманс.
А ещё в AVX-512 есть 2 интересные инструкции: VPMADD52LUQ и VPMADD52HUQ, которые выполняют сложение с умножением над 52-битными целыми числами :)
Правильно ли я понял, что
vpaddq %xmm5, %xmm6, %xmm5 - это AVX
vpaddq %ymm4, %ymm0, %ymm0 - это AVX2
?
Во-первых, в большинстве популярных CPU x86
adcпросто выполняется медленнее, чем обычнаяadd. Так как уadcесть третье входящее значение (флаг переноса), эта команда сложнее, чемadd
Абсолютно неверное утверждение. Команды вида ADD и ADC выполняются с абсолютно одинаковой скоростью и на абсолютно одном и том же оборудовании. Технически разница между ними заключается только в том, что в качестве входного переноса в ADD подаётся нуль, а в ADC -- значение переноса, запомненное при выполнении какой-либо предшествующей команды.
Ну и следует заметить, что эффективность подобных решений зависит от процессора, на котором предстоит выполнять программу. Скажем, на достаточно простых микроконтроллерах это в несколько раз снизит скорость работы, поскольку процессоры там не суперскалярные и выполняют команды последовательно.
На интелах до broadwell микрооперации, отправляющиеся на ALU, принимали не более чем 2 входа, поэтому adc (требующий значения двух входных регистров и значение флага переноса) декодировался в 2 микрооперации, а add - в 1.
Использование флагового регистра, когда в него пишет предыдущий adc и читает следующий, увеличивает длину критического пути в графе исполнения, что напрямую ухудшает throughput цепочки сложений из-за того, что команды в критическом пути должны исполнятся последовательно
Справидливости ради, от этого всего никуда не ушли. Просто за счет уменьшения базы по сравнению с машинным словом появилась возможность не выполнять переносы после каждого сложения, а выполнить их все одним махом в самом конце. Так что метод предложенный тут действительно ускоряет, когда вы складываете много чисел, а не только два.
Как ускорить сложение и вычитание при помощи 2^51