Comments 21
Вот в таких задачах ручное программирование на ассемблере (ну или использование специфичных для конкретного компилятора и архитектуры расширений языка, сводящихся к ассемблеру) и даёт иногда колоссальный прирост производительности. Конечно, ценой непереносимости кода, но всегда ли она нужна, не говоря о том, что ничто не мешает предлагать как переносимую реализацию, так и специфичные для конкретных платформ?
Cогласен с вами и с автором, который в первых строках статьи указал:
программист, умеющий грамотно оперировать этими механизмами(в частности в терминах бизнес процессов, требующих 'Здесь и Сейчас', терминах поиска золотой середины между Скоростью и Дизайном) - профессионал.
В идеале, программиста вообще не должна заботить проблема переносимости кода. Однажды написанный (грамотно, без ошибок) код может использоваться много лет.
Простые алгоритмы компиляторы должны уметь векторизовать самостоятельно. Для более сложных (с перестановками, cross-lane операциями) должны существовать универсальные векторные API. Будущее за JIT с компиляцией сразу под целевую платформу. Но проблема в том, что даже с первой задачей они еле справляются. Например, в Java иногда приходится вручную выкидывать абстракции и переделывать код на работу с элементарными типами, потому что компилятор не сумел оптимизировать массив объектов, состоящих из 2-х свойств Int.
Учитывая растущую сложность и разнообразие платформ, к этой задаче давно пора привлечь ИИ. И именно не для генерации платформо-зависимого кода, а для разработки средства глубокого анализа синтаксического дерева.
8, 16, 32, 64 и 128 элементов
Ну это не серьёзно. 128 элементов я чуть ли не ручками могу переставить, так что какой смысл ускорять/мерить 128 элементов? Было б там хотя бы 1000, я б ещё понял.
P.S. Стиль кода у вас конечно оригинальный.
Можете и руками, но будет ли это быстрее чем SIMD? В Яндексе были задачи где это оказалось применимо(в рамках приличного ускорения).
На малых данных это не имеет абсолютно никакого значения. Вы потратите больше энергии на то чтобы написать этот код, чем получите профит на 100 элементах. Не говоря уже о том, что всё это на целых числах тестируется. Это тот самый сказ про микроскопом по гвоздю. Для пущего эффекта надо было ещё CUDA ядра подключить или в GPU шейдер скормить, чтобы оно 128 элементов за 2 такта сорировало.
Код легко переделать на float. Профит получен - и в моей конкретной задаче, которую я описал в самом начале в частности. То, что это непростая оптимизация, я не спорю. Но такие оптимизации даже очень важны. В HFT, скажем, такое очень нужно(я не про этот конкретный алгоритм сортировок). Но что конкретно вы мне хотите доказать? С CUDA еще не факт, что было бы быстрее - все таки гонять малые данные по шине не быстро. Цель статьи - показать что SIMD находит свое применение не только в оптимизации memcpy. И показываю и рассказываю как. Миллионы этим кодом никто не зарабатывает, а усилия которые я трачу, я трачу на свое образование и по своему усмотрению.
Вычисления на малых данных могут происходить очень часто. Например, похожая задача возникает при обработке сетевых пакетов. При современных скоростях бюджет времени — десятки-сотни наносекунд на пакет. Если раньше раньше 128 пакетов обрабатывались 1,5 мкс, а теперь 100 нс, это заметный выигрыш в процентах, хотя и всего ~10 нс на пакет в абсолютных числах.
Было б там хотя бы 1000, я б ещё понял.
Эта сортировка выполняет в logn раз больше сравнений относительно стл-ных сортировок. Но при этом выполняет по 4 их за раз и не страдает всякими накладными расходами на универсальность отсальных сотировок. При больших массивах ассимптотика переиграет ускорение в 4 раза и работать такая сортировка будет сильно хуже.
По поводу исходной задачи. Пробовали ли вы вместо хешмапа использовать бор (ака trie)? При этом лучше обрабатывать не как 128 int-ов, а как 512 октетов. А то, если числа большие, то в каждой вершине свой хешмап для переходов городить придется. И сортировка, естественно остается. По ощущениям, это должно быть быстрее.
Кажется, вы сдублировали столбцы в таблице с результатами. Второй столбец должен быть за stl, я полагаю.
Сортировку миллиона элементов пробовали сравнивать?
Меня радует что сейчас хоть кто-то этим занимается. В конце 90х тема оптимизации с помощью новых инструкций ЦПУ была супер популярной, но появление GPU и медиаакселераторов привело к разработке специализированных библиотек, в которые никто особо не лазит.
Нужно быть готовым к тому, что силикон упрется в предел, и единственным способом ускорения работы компьютеров будет оптимизация софта. И даже если этим станет заниматься ИИ, все равно нужны люди которые в этом шарят.
С одной стороны все отлично, круто.
С другой стороны как обычно: "Как обогнать STL? Взять ПОДЗАДАЧУ, векторы.."
Ещё в медианном фильтре картинок этот алгоритм применяется:
https://habr.com/ru/articles/204682/
там кстати код попроще выглядит, без перетасовок в xmm-регистрах. Используется векторизация в направлении "по массиву" (пикселей) - алгоритм абсолютно аналогичен скалярному, только вместо одного значения работаем с пачками по 16-32 элементов. Поэтому получается всего 6 интринсиков, можно даже и без них, у меня где-то был автовекторизованный вариант.
Но да, это подходит для пикселей, а у вас большой пачки из сортируемых фрагментов может и не быть в наличии.
Да, все верно. Хотя, в статье по вашей ссылке автор пишет:
Кроме того, нам совсем не обязательно полностью сортировать массив, достаточно, что бы в 4-м элементе было требуемое нами значение.
Да, я заметил, но при желании легко исправить на полную сортировку, нужно переделать функцию Sort(__m128i a[9]).
Там сейчас 19 сравнений. Пишут, что для полной сортировки 9 элементов нужно 25, схема есть:
https://www.sciencedirect.com/science/article/pii/S0022000015001397
Как раз преимущество подхода в том, что легко переделать на разные сортировочные сети, не придумывая каждый раз схему перемещения элементов в xmm-регистрах.
Про сортировку чисел и SIMD или как я обогнал STL в 16 раз