Не используйте std.random!

Стандартная библиотека использует классический Вихрь Мерсенна (MT19937). Недавно я, вдохновившись эффективностью PCG для шейдерных вычислений, добавил соответствующий модуль в dlib, заменив им rand в dlib.random. Оказалось, что моя функция random для выборки равномерного распределения в диапазоне 0..1 аж в 4 раза быстрее, чем std.random.uniform!

Бенчмарк для 10000000 вызовов:

std.random.uniform: 77 ms, 38 μs, and 3 hnsecs total
dlib.random.random: 19 ms, 599 μs, and 3 hnsecs total

Стандартное отклонение у обеих функций примерно одинаковое:

std.random.uniform: 0.544σ
dlib.random.random: 0.413σ

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

Шучу, конечно. Но специализированная хэш-таблица действительно может быть заметно быстрее встроенных ассоциативных массивов 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 — это обычный линейный обход буфера безо всякой рекурсии и сложной логики.

Не используйте std.algorithm.sort!

Точнее, не используйте бездумно для всего. Я уже как-то писал о неэффективности std.variant, и вот еще один казус: стандартная функция сортировки в Phobos более чем в 100 раз медленнее, чем сортировка вставками (insertion sort) для маленьких массивов. Вот результат бенчмарка для массива из 6 случайных элементов и миллиона вызовов каждой функции:

std.algorithm.sort: 70 ms, 200 μs, and 6 hnsecs total
Selection sort: 572 μs and 6 hnsecs total
Insertion sort: 570 μs and 8 hnsecs total

На массиве из 50 элементов сортировка выбором уже проигрывает, но вставки по-прежнему намного быстрее:

std.algorithm.sort: 494 ms, 694 μs, and 6 hnsecs total
Selection sort: 638 ms and 800 μs total
Insertion sort: 307 ms, 370 μs, and 2 hnsecs total

На массиве из 100 элементов std.algorithm.sort и сортировка вставками начинают показывать примерно одинаковую производительность:

std.algorithm.sort: 1 sec, 525 ms, 667 μs, and 3 hnsecs total
Selection sort: 2 secs, 847 ms, 63 μs, and 7 hnsecs total
Insertion sort: 1 sec, 552 ms, 324 μs, and 9 hnsecs total

Что интересно, при 200 элементах сортировка вставками снова вырывается вперед:

std.algorithm.sort: 6 secs, 138 ms, 993 μs, and 8 hnsecs total
Selection sort: 11 secs, 592 ms, 87 μs, and 7 hnsecs total
Insertion sort: 5 secs, 193 ms, 42 μs, and 1 hnsec total

При 300 элементах и больше std.algorithm.sort уже эффективнее:

std.algorithm sort: 9 secs, 178 ms, 920 μs, and 1 hnsec total
Selection sort: 26 secs, 875 ms, 201 μs, and 1 hnsec total
Insertion sort: 11 secs, 783 ms, 883 μs, and 5 hnsecs total

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

Не используйте std.variant!

Собственно сабж. Оказывается, Variant, стандартная реализация tagged union в Phobos, плоховато подходит для вычислений в реальном времени. Не знаю, что там наворотили, но бенчмарки, которые я сделал при разработке GScript3, показали ускорение в 900%, когда я заменил Variant на кастомный динамический тип. Я замерял выполнение скриптового счетчика от 0 до 100000000, и версия на Variant завершилась за 45 секунд, версия на моем GsDynamic — всего за 5!

О самом языке GScript3 расскажу в ближайшее время — я решил актуализировать этот старый проект и уже сделал много интересного.