containers

dlib 1.7

В рамках Dagon 2.0 скопилось множество улучшений для dlib, и данный релиз подытоживает эту работу.

Добавлен модуль dlib.math.base — замена std.math, которая заменяет некоторые часто используемые функции быстрыми интринсиками LLVM при компиляции LDC (подробнее об этом тут). Ускорены следующие элементарные функции: fabs, sqrt, sin, cos, tan, ceil, floor, round, trunc, rint, nearbyint, pow, exp, exp2, log, log2, log10, fmax, fmin, fma, copysign. В среднем они вдвое быстрее, чем в Phobos. Единственный нюанс, который следует помнить — лучше не импортировать оба модуля одновременно, иначе будет конфликт, и вам придется использовать квалифицированные имена при вызовах.

Добавлена встроенная SIMD-оптимизация для перемножения матриц 4×4 (Matrix4x4f). Это ускоряет оператор в 3-4 раза. В связи с этим удален модуль dlib.math.sse как устаревший, неподдерживаемый и, как выяснилось, нерабочий под x86_64.

Хэш-таблица FlatHashMap из Dagon 2.0 добавлена в библиотеку как dlib.container.hashmap. Реализация xxHash64, соответственно, — как dlib.hash.xxhash64 в новом пакете dlib.hash. Напомню, что это очень быстрая реализация ассоциативных массивов без использования сборщика мусора, которая в десятки раз эффективнее, чем dlib.container.dict и в 1,5-2 раза — чем встроенные ассоциативные массивы D.

Полностью переработан dlib.random — пакет теперь работает на основе перемешанного конгруэнтного генератора (PCG), реализованного для 32- и 64-битных чисел. Это современный эффективный генератор псевдослучайных чисел, который превосходит как Вихрь Мерсенна (std.random), так и линейный конгруэнтный генератор (rand в стандартной библиотеке C). Добавлены новые функции choice (случайный выбор из заданного множества вариантов) and rollDice (случайное целое число от 0 до заданного порога). Функция seed, генерирующая зерно для инициализации генератора из системной энтропии, теперь использует функцию смешивания fmix64 из MurmurHash3 вместо mix Боба Дженкинса.

Не используйте ассоциативные массивы!

Шучу, конечно. Но специализированная хэш-таблица действительно может быть заметно быстрее встроенных ассоциативных массивов D. На днях начал писать менеджер ассетов для Dagon 2.0 и решил заодно заменить dlib.container.dict для хранения ссылок на ассеты чем-то поэффективнее. Результатом стал класс FlatHashMap — таблица, которая хранит все элементы в одном непрерывном блоке памяти, что значительно улучшает производительность за счет кэш-дружественности. Кроме того, такая таблица работает в среднем за постоянное время, что выгоднейшим образом отличает ее от префиксного дерева (на котором основан dlib.container.dict) — скорость префиксного дерева пропорциональна длине ключей, а flat hash map работает с хэшами фиксированного размера.

В качестве хэш-функции я взял быстрый xxHash64, который можно использовать в реальном времени. Моя версия в Dagon — это частичный D-порт xxhash-clean, минимальной референсной реализации xxHash. Результаты бенчмарка следующие: вставки у FlatHashMap получились аж в 36 раз быстрее, чем у dlib.container.dict, и в 1,7 раз быстрее, чем у ассоциативных массивов. Поиск — в 15 раз быстрее, чем у dlib.container.dict, и в 1,6 раз быстрее, чем у ассоциативных массивов. Эффективен и opApply — это обычный линейный обход буфера безо всякой рекурсии и сложной логики.

dlib 0.5

Не так давно состоялось очередное крупное обновление коллекции библиотек dlib — вышла версия 0.5, наиболее значительным нововведением которой стала поддержка ручного управления памятью (РУП). Но — обо всем по порядку…

  • Новый модуль dlib.core.memory предоставляет средства для ручного выделения и высвобождения динамической памяти, независимые от сборщика мусора и основанные на malloc/free. Имеется поддержка структур, классов и массивов. При использовании классов рекомендуется использовать интерфейс ManuallyAllocatable и перегружать метод free, который ответственен за удаление объекта — в противном случае корректное удаление в некоторых случаях не гарантировано (например, при доступе через интерфейс или родительский класс).
  • Началась работа по переводу всей dlib на РУП. Так, загрузчики изрбражений (PNG, JPEG, TGA, BMP) в новой версии полностью независимы от сборщика мусора. Для этого активно используется паттерн абстрактной фабрики, ответственный за создание изображений  в памяти. Кстати, в загрузчике PNG значительно улучшена поддержка индексированных изображений, для них добавлена поддержка альфа-канала.
  • Кроме того, на РУП переведены некоторые контейнеры из dlib.container — BST, ассоциативный массив. Реализован полностью ручной динамический массив (dlib.container.array).
  • Еще одна новинка — ООП для структур (dlib.core.oop). Это экспериментальный модуль, реализующий для структур прототипный стиль ООП с поддержкой множественного наследования и параметрического полиморфизма. Полностью заменить классы он, конечно, не может, но окажется весьма полезен, если нужно создавать объекты с наследованием в стеке. В будущем планируется переписать некоторые внутренние механизмы dlib с использованием этой легковесной объектной системы.
  • В пакете dlib.math появилась поддержка дуальных кватернионов. Это частный случай алгербы Клиффорда, обобщение кватернионов на поле дуальных чисел. Их можно использовать, например, для описания движения тел в кинематике — один дуальный кватернион охватывает и перенос, и вращение. Кстати, реализация обычных кватернионов через инкапсуляцию теперь совместима с векторами.
  • Изменения коснулись и пакета вычислительной геометрии. Усеченная пирамида (dlib.geometry.frustum) теперь задается с нормалями ограничивающих плоскостей, указывающими наружу пирамиды. Подвергся изменению API проверки пересечения Frustum с AABB. Исправлены ошибки в реализации AABB и плоскости.