fxdiv

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

Особенности

• высокопроизводительные операции деления через умножение на предвычисленные константы;
• поддержка деления на константы для 32-х и 64-битных целых чисел;
• оптимизация для различных архитектур процессоров (x86, ARM, RISC-V);
• минимальные накладные расходы и отсутствие зависимостей от внешних библиотек;
• поддержка знаковых и беззнаковых типов данных;
• кроссплатформенность и портируемость между компиляторами.

Основные компоненты

FXDIV предоставляет набор функций и макросов для замены операций деления на константные значения более эффективными последовательностями инструкций (подробнее с документацией можно ознакомиться здесь).

Деление на константные значения

Основная задача библиотеки — оптимизация операций деления на константные делители, которые известны во время компиляции. Вместо использования инструкций деления, FXDIV генерирует последовательность умножений и сдвигов, что значительно быстрее на большинстве современных процессоров.

Основные функции деления:

• fxdiv_mulhi_uint32_t() — вычисление старших битов произведения для 32-битных беззнаковых чисел;
• fxdiv_mulhi_uint64_t() — вычисление старших битов произведения для 64-битных беззнаковых чисел;
• fxdiv_div_uint32_t() — деление 32-битного беззнакового числа на константу;
• fxdiv_div_uint64_t() — деление 64-битного беззнакового числа на константу;
• fxdiv_div_int32_t() — деление 32-битного знакового числа на константу;
• fxdiv_div_int64_t() — деление 64-битного знакового числа на константу.

Предвычисленные константы для деления

Библиотека использует заранее вычисленные константы для каждого делителя, которые позволяют заменить операцию деления на комбинацию умножения и сдвигов. Эти константы вычисляются один раз и могут использоваться многократно.

Типы констант:

• fxdiv_uint32_t — структура с константами для деления 32-битных беззнаковых чисел;
• fxdiv_uint64_t — структура с константами для деления 64-битных беззнаковых чисел;
• fxdiv_int32_t — структура с константами для деления 32-битных знаковых чисел;
• fxdiv_int64_t — структура с константами для деления 64-битных знаковых чисел.

Генерация оптимизированного кода

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

Функции генерации констант:

• fxdiv_init_uint32_t() — инициализация констант для деления 32-битного беззнакового числа;
• fxdiv_init_uint64_t() — инициализация констант для деления 64-битного беззнакового числа;
• fxdiv_init_int32_t() — инициализация констант для деления 32-битного знакового числа;
• fxdiv_init_int64_t() — инициализация констант для деления 64-битного знакового числа.

Векторизованные операции

Для повышения производительности при обработке больших массивов данных библиотека поддерживает векторизованные операции деления, которые могут использовать SIMD-инструкции современных процессоров.

Векторизованные функции:

• fxdiv_batch_uint32_t() — пакетное деление массива 32-битных беззнаковых чисел;
• fxdiv_batch_uint64_t() — пакетное деление массива 64-битных беззнаковых чисел;
• fxdiv_batch_int32_t() — пакетное деление массива 32-битных знаковых чисел;
• fxdiv_batch_int64_t() — пакетное деление массива 64-битных знаковых чисел.

Оптимизации для различных архитектур

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

Поддерживаемые оптимизации:

• x86/x86-64: использование инструкций mulx, shrx и других расширений BMI2;
• ARM: оптимизации для архитектур ARMv7 и ARMv8 с использованием NEON;
• RISC-V: поддержка базового набора инструкций и расширений M;
• Адаптивный выбор алгоритма в зависимости от значения делителя.

Инструменты разработки и утилиты

FXDIV включает вспомогательные инструменты для анализа производительности и проверки корректности оптимизаций.

Вспомогательные утилиты:

• fxdiv_benchmark — измерение производительности операций деления;
• fxdiv_test — тесты корректности для всех поддерживаемых функций;
• fxdiv_example — примеры использования библиотеки в реальных сценариях;
• Генераторы отчетов о производительности для разных архитектур.

Использование в проекте

Документация по использованию Conan-пакетов для разработки приложений для ОС Аврора.

На сервере Conan библиотеки заранее собраны и размещены под различные версии ОС Аврора 4 и ОC Аврора 5. Для данных версий представлены архитектуры armv7hl, aarch64 и x84_64.

Библиотеку можно использовать в проекте с помощью данного conanfile.py

from conan import ConanFile

class Application(ConanFile):
    settings = "os", "compiler", "arch", "build_type"
    generators = "PkgConfigDeps"

    requires = (
        "fxdiv/cci.20200417@aurora",
    )    

Процесс локальной сборки описан в документации.