Жизнь без Windows: Кроссплатформенная MulDiv для Delphi

Лично меня достало ради MulDiv вечно подключать Winapi.Windows. Знакомая ситуация? Пишешь код с прицелом на кроссплатформенность, всё красиво, а тут — бац! — нужна MulDiv. И вот уже тянешь за собой всю Windows-зависимость, как якорь.

Рано или поздно надо уходить в кроссплатформенную разработку, почему бы и не избавиться от этой вредной зависимости прямо сейчас?

Что не так с Windows.MulDiv?

Во-первых, она привязана только к Windows. Хотите собрать проект под Linux или Android? Прощай, MulDiv. Во-вторых, Windows API выполняет кучу проверок, обрабатывает edge-кейсы, делает округление — всё это стоит производительности.

Но главное — философия. Зачем тащить за собой системную зависимость ради простой математической операции? Это как использовать атомный реактор, чтобы вскипятить чайник.

При использовании Windows.MulDiv в Delphi замечена одна интересная особенность. Если на вход подавать переменные, определённые как Byte, MulDiv работает в 1.5-3 раза быстрее, чем при всех остальных типах. В примере, который можно скачать в конце статьи, это можно проверить по кнопке MulDiv Test.

Вряд ли это связано непосредственно с WinAPI функцией. Скорее всего, разница связана с:

  1. Неявным преобразованием типов (компиляторная оптимизация)
  2. Эффективностью кэша (меньше данных — больше помещается)
  3. Особенностями передачи параметров в stdcall

Хотя, после ряда экспериментов, подозрения с MulDiv не сняты. Такое ощущение, что проверяет Integer’ы на диапазон, и если они могут быть байтами — то взлетает. Проверю потом. Жаль, нет исходников от Винды.

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

Вариант 1: Просто и понятно

Что здесь важно:

  1. Int64(A) * Int64(B) — не просто прихоть. Умножение двух 32-битных чисел даёт 64-битный результат. Если не привести к Int64, произойдёт переполнение.
  2. inline — директива не для красоты. Для такой маленькой функции накладные расходы на вызов могут быть сравнимые с самими вычислениями. inline позволяет компилятору встроить код прямо в место вызова.
  3. Проверка C = 0 — это философия. Можно было бы положиться на исключение от деления на ноль, но:
    • Исключения дорогие
    • Windows API возвращает -1 в этом случае
    • Предотвращение проблемы лучше, чем её обработка

Минусы:

  • Может быть медленнее виндусовой версии (но ненамного)
  • Результат может не совпадать из-за отсутствия округления по правилам округления

Когда использовать: Когда нужно просто «умножить и разделить», а совпадение с Windows не критично (иногда бывает разница в единицу, ну это ж такой пустяк).

Вариант 2: Точная совместимость

Функция ниже оставлена для понимания, что тут происходит. Вместо неё работает другая, расширенная версия, она в конце этого раздела.

Магия округления: + C div 2

Windows MulDiv округляет к ближайшему целому. Формула простая:

  • Если остаток от деления ≥ половине делителя — округляем вверх
  • Иначе — вниз

Добавление C div 2 перед делением — это математический трюк для такого округления. Пример:

Плюсы:

  • Полная совместимость с Windows API
  • Один в один результаты

Минусы:

  • Медленнее предыдущей из-за дополнительного сложения. А вот функция ниже ещё медленней, но зато результат один в один. Расхождение по времени с оригиналом очень небольшое.

Когда использовать: При портировании кода с Windows, где важна точность совпадения. Для бухгалтера разница в единицу это не пустяк, а срок. Хотя… бухгалтеры ведь работают с currency, им не нужен MulDiv.

Переходим к правильной реализации. В чём проблема: такая понятная и милая функция не округляет правильно на отрицательных числах. Поэтому, вместо неё будем использовать следующую функцию.

Здесь почти всё то же самое. Мы дополнительно анализируем знак будущего результата и приводим аргументы в положительный вид. Далее, вычисляем всё, как для положительных значений, и назначаем ранее найденный знак.

Специализированная версия для x32

После оптимизации функции выше, получаем более быстрый вариант:

Про тестирование чуть ниже. Но давайте сравним показатели MulDivRounded и MulDiv x32. Последняя явно быстрее.

Специализированная версия для x64

Благодаря комментарию от Peter протестировал вариант, который используется в Lazarus. И, о чудо, под x64 он оказался намного быстрее даже оригинала! Peter, спасибо!

Связано это с тем, что для этого случая используется нативная 64-битная арифметика. Деление через FPU/SSE в 3-5 раз быстрее целочисленного. Умножение int64(A) * int64(B) выполняется одной инструкцией:

SSE2-конвейер работает параллельно. Пока целочисленный конвейер занят другими операциями, SSE2-блок выполняет деление параллельно:

Сравним MulDivRounded и MulDiv x64. Последняя не просто опережает общую реализацию, но и обгоняет оригинал Windows.MulDiv. Причём данные округляются правильно.

И кстати, если сравнить с рисунком выше, можно заметить, насколько 64-битная версия неповоротлива на 32 битах.

Итоговая MulDivX

С учётом новых специализированных версий, сделаем общую функцию, где объединим их плюсы:

Вариант 3: Максимальная скорость

Ахтунг! Ассемблер!

Разбираем ассемблер:

  • .NOFRAME в x64 — говорим компилятору, что не нужно создавать стандартный стековый фрейм. Для такой простой функции это излишне.
  • test r8d, r8d — быстрая проверка на ноль. test выполняет побитовое И, устанавливая флаги, но не сохраняя результат.
  • imul edx — умное умножение. На x86 умножает EAX на EDX, результат в EDX:EAX (64-битный). На x64 — аналогично.
  • idiv ecx — деление 64-битного числа на 32-битное.

Философия минимализма: Всего 4 инструкции для основного случая. Ничего лишнего. Бритва Оккама в действии.

Плюсы:

  • В 3 раза быстрее Windows API
  • Кроссплатформенность (разные реализации для x86/x64/остальное)
  • Проверка деления на ноль

Минусы:

  • Результат может отличаться на 1 из-за отсутствия округления
  • Ассемблер, 🤬 … Люди его не любят. И я тоже.

Когда использовать: В коде, критичном по производительности (performance critical) — рендеринг, аудиообработка, игры.

Тестируем

Мы хотим проверить работоспособность, корректность, быстродействие и кроссплатформенность.

Работоспособность

Кнопка Test1. Выбираем радиокнопками нужный метод. Проверяем A * B div C выбранным методом.

Видим, что на 0 реагирует правильно. Для выбранного метода разницу в 1 прощаем.

Быстродействие и корректность

Кнопка Test2. Выбираем радиокнопками нужный метод. При нажатии кнопки запускается генерация данных. Длина массива определяется в поле Iterations. По умолчанию это миллион (!) итераций на случайных числах от -256 до 256 (то есть байтом тут не пахнет). Проверяем A * B div C на этом количестве итераций, сравниваем с результатом функции Windows.MulDiv.

В результате работы этого теста, последней строкой будет запись: Diff: 0, Diff>1: 0. Это показывается количество несовпадающих значений, и количество, где разница больше 1. В идеале количество несовпадений должно быть 0. Но мы прощаем это для вариантов 1 и 3. Главное, чтобы количество по разнице 1 было всегда 0.

И вот в результате тестирования, видим, что метод, который позиционируется, как абсолютно правильный и совпадающий с Windows.MulDiv — неправильный! Выяснилось, что такая казалось бы уютная функция не распространяется на отрицательные числа. В исходниках выше представлена полная рабочая версия этой функции.

Вот так должна выглядеть функция с правильным округлением. Да, время выполнения увеличилось, но тут уж надо выбирать, что важнее, скорость или абсолютное совпадение. Да и разница по времени, если честно, не особо, по сравнению с оригиналом (ниже есть сравнительные таблички).

Статистический анализ быстродействия

Кнопка Test3. Что тут происходит. Создаётся набор данных в количестве требуемых итераций, и на нём прогоняется каждый метод, включая Windows.MulDiv. И весь этот процесс повторяется сто раз, с целью накопить устойчивую статистику. В конце выводится таблица с временными характеристиками.

Кроссплатформенность

Создаём Multi-Device Application. Пишем небольшой код, где наш MulDiv используется на всю катушку:

Маленький, но очень кроссплатформенный, код

[свернуть]

Результат кроссплатформенного проекта одинаков. Наш MulDiv работает везде. Один и тот же код работает, как минимум, и на Windows, и на Android. На остальных ОСях успешно компилируется, но проверить на физическом устройстве пока возможности нет. Предполагаю, что поведение будет аналогичным.

Бенчмарки

Intel(R) Core(TM) i5-9400 CPU @ 2.90GHz, Delphi XE 7, 1 млн итераций:

Если применяем только переменные типа Byte:

Это изображение имеет пустой атрибут alt; его имя файла - P10.jpg
Вариант32-bit
Время (мс)
Прирост скорости64-bit
Время (мс)
Прирост скорости
Windows API5,23111,031
Вариант 1 (без округления)9,420,569,071,22
Вариант 2 (с округлением / MulDivX)13,75 / 11,410,38 / 0,4611,70 / 10,410,94 / 1,06
Вариант 3 (ассемблер)4,001,314,2132,61

Если применяем переменные любого целочисленного типа:

Вариант32-bit
Время (мс)
Прирост скорости64-bit
Время (мс)
Прирост скорости
Windows API17,40116,411
Вариант 1 (без округления)9,491,839,091,80
Вариант 2 (с округлением / MulDivX)23,68 / 19,520,74 / 0,8917,23 / 14,130,95 / 1,16
Вариант 3 (ассемблер)4,044,313,944,16
Это изображение имеет пустой атрибут alt; его имя файла - P11.jpg

Значения получены, как среднее на 100 циклах по миллиону итераций на каждый вариант. Указана битность тестового приложения. Тесты проводились на Windows 10 Pro x64. На всех платформах побеждает Вариант 3. А «правильный» Вариант 2, как видим, не особо и отстаёт от базы: на 64 битах 0.9-0.95, что вполне неплохо. А улучшенный вариант 2, MulDivX, даже опережает оригинал.

Листинг для копипаста

Кроссплатформенный MulDiv

[свернуть]

Заключение (философское)

Мы часто цепляемся за старые привычки, как за спасательный круг. Winapi.Windows кажется чем-то надёжным, проверенным. Но каждая системная зависимость — это якорь, мешающий плыть в будущее, чёрный ящик, работу которого мы не контролируем.

Написание своей MulDiv — это не просто техническое упражнение. Это шаг к независимости. Шаг к пониманию, что мы контролируем свой код, а не код контролирует нас. Это акт цифрового суверенитета.

В итоге мы получили быстрый кроссплатформенный аналог функции Windows.MulDiv, не обременённый никакими привязанностями и зависимостями. Наша функция MulDiv выполняет ровно то же, что и оригинал. Таким образом, можно использовать старый код без дополнительных правок, надо только убрать Winapi.Windows из предложения uses. А для новых проектов можно сразу использовать MulDivFast, если хотим выигрыш в скорости.

Можно перевести нашу MulDiv на ассемблер. Это будет много строк кода, но работать станет быстрее. Но стоит ли оно того? Получим трудно поддерживаемый код, ненависть коллег и иллюзию оптимизации там, где она не нужна. Мы пишем код для людей, а не для машин.

Все листинги из статьи — готовы к использованию. Копируйте, адаптируйте, улучшайте. Грамотный копипаст — это наше всё. Пишите комментарии.


Скачать

Друзья, спасибо за внимание!

Исходник (zip) 10.1 Кб. Delphi XE 7 (Проверен в XE 13)

Исходник FMX XE 13 (Test4) (zip) 12.8 Кб. Delphi XE 13

Исполняемый файл 32-bit (zip) 820 Kб (Скомпилирован в XE 7 32-bit)

Исполняемый файл 64-bit (zip) 1.03 Мб (Скомпилирован в XE 7 64-bit)


0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest

0 комментариев
Старые
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии