Решил как-то на досуге накидать тип для удобной работы с длинным беззнаковыми целыми. На плюсах перегрузка операций была изначально, а вот в Object Pascal ее добавили позже, причем с ограничениями. В частности, для перегрузки операций можно использовать только записи (record), но не классы.
В процессе написания, естественно, возникло желание потестить на производительность, пока что только операции сложения/вычитания. Но вот с чем сравнивать результат? Подумал и решил, что можно сравнивать производительность со встроенным 64-битными беззнаковыми целыми (UInt64).
Логика тут такая: Delphi генерирует код в нативных командах процессора, одно сложение - одна команда. А при реализации своего типа с перегруженными операциями взамен нативных команд будет вызов процедуры.
Таким образом, одна команда сложения для UInt64 в случае UInt128 будет заменять на вызов процедуры с 4 обращениями к памяти и двумя командами сложения. Примерно прикинул и подумал, что троекратное снижение производительности в этом случае будет нормально.
Запускаю тест на отладочной версии и получаю следующие результаты: UInt64 на pascal дает примерно 533 млн. сложений в секунду, а UInt128 ‒ 247 млн. Вроде бы не плохой результат: замедление не в 3, а всего лишь в 2.15 раза.
Думаю, а что будет, если переписать UInt64 на assembler? Недолго думая делаю и получаю 3 млрд. 600 млн. регистровых операций в секунуду! Подумать только! 3.6 млрд. 64-разрядных сложений в секунду, Карл! И это старенький, не топовый процессор. Что же сейчас творят топы!?
А я ведь помню еще те времена, когда и сто 16-разрядных операций в секунду были просто мечтой!
И на что тратится это гигантская производительность? Похоже, в основном на то, что бы красиво размывать фон на фотографиях котиков в модных соц. сетях. 😆
С чем еще можно померится производительностью? Вспоминаю, что в Java и в .NET есть встроенный тип BigInteger. Он, правда, весьма универсальный, так как имеет "бесконечную" точность, в отличие от того типа, что делаю я, да еще и знаковый. Но мне интересно, сколько стоит такая универсальность?
На Java писать под Windows мне совсем не хочется, даже консольное приложение, но можно вот взять PascalABC.NET, под него и код-то особо переписывать не нужно. Естественно, организую тест так, что бы данные BigInteger занимали больше 8 байт, но меньше 16, что бы сравнение было корректным.
Вот результаты: UInt64 ‒ 477 млн. операций в секунду. Честно говоря, очень достойный результат для .NET, Delphi в отладочной версии дает чуть больше. А вот BigInteger уже не так хорош: в районе 105 млн. операций в секунду. То есть примерно в 2.5 раза хуже, чем мой тип на Delphi.
Думаю, не такая уж большая цена за универсальность. Но иногда производительность все же важнее.
А потом я компилирую на Delphi вместо отладочного варианта релиз и удивляюсь: код для UInt64 на pascal оказывается быстрее кода на assembler ‒ 4 млрд. 179 млн. сложений! Видимо, Delphi все-таки немного умеет в оптимизацию: в цикле я развернул сложения по 10 штук, что бы снизить погрешность измерения от кода, организующего сам цикл.
Видимо, оптимизатор просек эту тему, и заменил 10 команд сложения на одну. Но это не точно: код в релизе без отладочной информации, а копаться в исходных кодах всех прочих библиотек, которые задействованы по умолчанию в работе программы у меня желания нет.
Но хочу заметить, что .NET так не умеет!
Впрочем, сложение ‒ это так себе тема, гораздо интереснее будет, когда я доберусь до умножения, а особенно ‒ до деления.
> получаю 3 млрд. 600 млн. регистровых операций в секунуду!
ОтветитьУдалитьВроде FX-4350 может выполнять даже 2 сложения за такт, и того под 8 млрд, но это в теории и на удобных данных. Плюс еще можно SIMD прикрутить, это еще в 2 раза ускорит, и того, опять же в теории до 16 млрд.
Одна из оптимизаций которая сильно помогает, это разворачивание цикла с подсчетом нескольких независимых частичных сумм, а после цикла складывание их вместе. Тогда 2 сумматора могут постоянно работать, но опять же не всегда это возможно.
> И на что тратится это гигантская производительность?
Это точно, хотя в целом все ясно: каждые пару лет программист получает новое топовое железо, старый код на нем становится заметно быстрее, а значит можно нагородить очередных абстракций над абстракциями.
> в Java есть встроенный тип BigInteger.
Думаю все будет не радужно, он неизменяемый, а значит основное время думаю уйдет на постоянное создание объектов в куче.
> Вроде FX-4350 может выполнять даже 2 сложения за такт, и того под 8 млрд, но это в теории и на удобных данных.
ОтветитьУдалитьТут есть зависимость, нельзя выполнить второе сложение, пока не закончено первое, из-за того, что второе происходит с учетом бита переноса в результате первого. Так что это можно сделать, выполняя два независимых 128-битных сложения, но это уже весьма не универсальная ситуация.
> Плюс еще можно SIMD прикрутить
Я думал об этом, но пока не могу сообразить, как сделать, так как вроде в SIMD не сохраняется бит переноса. Хотя, может я какую команду и пропустил.
Можно, конечно, и без бита переноса, но на 128-разрядных словах это смысла не имеет. На более длинных - весьма вероятно.
> Одна из оптимизаций которая сильно помогает, это разворачивание цикла с подсчетом нескольких независимых частичных сумм
Возможный вариант, но для гораздо более длинных типов.
> Думаю все будет не радужно, он неизменяемый, а значит основное время думаю уйдет на постоянное создание объектов в куче.
Ну, для операций вида a=b+c, думаю, будет норм. Все же основной затык, кмк, связан с тем, что он оптимизирован для расчета гораздо более длинных чисел. Поэтому использует более подходящие для них оптимизации, которые на коротких данных в 2 64-битных слова менее эффективны.
> можно сделать, выполняя два независимых 128-битных сложения
УдалитьАга, я думал именно в этом контексте когда предлагал частичные суммы.
> вроде в SIMD не сохраняется бит переноса.
Да, я тоже не увидел, вот здесь есть пример как можно его рассчитать https://stackoverflow.com/a/10515345 но согласен, для 128-bit, не думаю что это даст какой-то прирост, скорее все будет еще медленнее.