Добрался наконец-то до умножения. Решил его сделать хитро, отдельно выделив умножение на небольшие целые, с целью оптимизации в первую очередь операций по переводу из разных систем счисления.
Такое умножение можно заменить несколькими операциями сложения и сдвига, думал, что получится быстрее. Но нет, быстрее не получилось, почти одинаково: видимо, лишнее сравнение и косвенный вызов процедуры съедают весь выигрыш. Впрочем, на больших размерностях эффект должен быть более заметен.
Тестирование проводил на нечетных числах, так как умножение на четные быстро обнуляет один из операндов на ограниченном по точности типе.
В результате Pascal в релизе показал 680 млн. 64-битных умножений в секунду, а мое умножение 128-битного на 64-битное - всего около 170 млн. Примерно в 4 раза медленнее. Хотя должно бы быть теоретически медленнее всего чуть больше двух раз. Такова плата за универсальность.
А вот умножение 128 на 128 бит дает 88 млн. умножений в секунду, что уже в 8 раз медленнее чисто 64-битного умножения, что странно. Ведь такая 128-битная операция требует лишь три 64-битных умножения и два сложения. Надо внимательнее посмотреть на свой код, видимо, там можно что-нибудь оптимизировать, я даже догадываюсь, что 😁.
Оценить, насколько хорошо работает PascalABC.NET с его BigInteger достаточно сложно. Дело в том, что он имеет "бесконечную" точность, рассчитывая полное произведение, в том время как мой тип старшую часть, выходящую за 128 бит, теряет. В результате множитель в процессе теста на BigInteger постоянно и очень быстро растет, а вместе с тем растет и вычислительная сложность каждого умножения.
В результате я замерял его производительность так: сначала замерил время выполнения N умножений, отбрасывая после каждого все то, что выходило за пределы 128 бит. с помощью побитового AND.
Затем замерил время N операций AND, и вычел одно время из другого.
В результате BigInteger показал 5.5 млн. умножений в секунду, или в 16 раз медленнее моего варианта 128 на 128 бит. Я считаю, что очень неплохо, с учетом того BigInteger считал полное умножение, получая 256 бит результата, что требует еще одного 64-битного умножения и кучи сложений.
Поначалу я предполагал, что в BigInteger используется универсальный алгоритм умножения, например, методом Фурье, но, судя по всему, там используют разные алгоритмы в зависимости от длины операндов. И на относительно коротких умножениях они используют обычный вариант длинного умножения.
Интересно! А Вы не сравнивали как число операндов влияет на скорость MUL? Возможно версия с одним операндом существенно медленнее так как возвращает все 128-бита?
ОтветитьУдалитьНе знаю как в .NET, но в JVM, на сколько я знаю, нет возможности получить все 128-бита от 64-битного умножения, в итоге приходится хранить длинные числа используя 32-бита, что значительно увеличивает число сложений и умножений.
Нет, не сравнивал такой вариант. Но, кмк, это будет существенно медленнее.
УдалитьОдним полным умножением мы получаем сразу 128 бит произведения. Коротким умножением, по сути 32-битным, потребуется выполнить 4 умножения и 4 сложения для получения того же результата.
Например, У моего процессора полное умножение занимает 6 тактов, и ровно столько же усеченное. Кроме того, усеченное умножение выполняется только над знаковыми числами. Сюда еще надо добавить по 1 такту от каждого сложения. Так что в результате будет серьезный проигрыш в производительности.
А если еще число хранится компактно, то перед умножением его придется разбивать по 32 бита...
Так что не очень вариант для Pascal. Поэтому его и не делал.
Походу, немного ошибся. Можно же выполнять 32-битное полное умножение, вместо 64-битного короткого. Оно побыстрее, примерно 2 в раза, чем 64-битное короткое. Но все равно в целом будет медленнее, чем 64-битное полное умножение.
УдалитьНу и про разбивку тоже я не прав, ее там вроде не нужно.
> Но, кмк, это будет существенно медленнее.
УдалитьДа согласен, я думал в контексте почему 128-битное умножение в 8 раз медленнее 64-битного вместо 3-х с хвостиком. Может как раз из-за активного использования MUL? Как я понимаю процессор в любом случае считает полное произведение, но может то что обновлять нужно 2 регистра и один из них всегда один и тот-же как-то влияет? Вы не смотрели во что Delphi компилирует беззнаковое 64-битное умножение? clang использует 2-х операндовую версию imul
> усеченное умножение выполняется только над знаковыми числами
Оно возвращает правильный результат как для знаковых так и беззнаковых, https://stackoverflow.com/a/42589535 описывает почему так.
Я тут узнал что в clang (и gcc) есть программная поддержка 128 битных типов, скорость не замерял, но вот как компилируется умножение: https://gcc.godbolt.org/z/TxxG6KoWe (1 mulx, 2 imul, 2 add), почитал про mulx - достаточно новая инструкция, не знал о ней. Интересно бы ее сравнить с классическим mul.
> Может как раз из-за активного использования MUL?
УдалитьЭто может быть одной из причин, но не на моем процессоре, так как на нем скорость полной и усеченной команды вроде одинакова. Хочу поэкспериментировать и посмотреть, в чем причина. Но тут не надо забывать, что 64-битное умножение компилятор сделает в регистровой оптимизации, а вот 128-битное, из-за особенности реализации перегрузки операторов в Delphi, операнды будут 100% в памяти. Вот это одна из причина, кмк.
> Вы не смотрели во что Delphi компилирует беззнаковое 64-битное умножение?
Не смотрел, но подозреваю, что тоже IMUL. Не нужно еще один регистр резервировать, поэтому код должен получаться немного оптимальнее.
Я попробую тоже ее включить в новый код, может, получится немножко быстрее. По крайней мере посмотрю, как это будет влиять на моем процессоре.
> ...mulx - достаточно новая инструкция, не знал о ней. Интересно бы ее сравнить с классическим mul.
На первый взгляд, тот же MUL, вид сбоку. CISC-архитектура предрасполагает к тому, что бы творить хаос и беспредел в системе команд. )
Вместо RAX один из источников находится в RDX, ну и можно результат складывать в произвольные регистры. Немножко проще планировать регистровую оптимизацию, но по производительности один в один обычный MUL.
Но самое главное, поддерживается не всеми процессорами, соответственно, надо городить код, который бы в зависимости от того, на каком процессоре исполняется, заменял процедуру умножения. В общем, в таком приложении для этой команды смысла не вижу.