Comments 8
Не все же в курсе как расшифровываются punpckldq, pmaxud, movdqa, pshufd и другие ругательства. И потом у некоторых mips и даже arm да и ассемблер может быть не intel.
ps: не раскрыта тема: если есть сортировка 16 чисел, как её обобщить на сортировку N чисел.
Не могу не признать правоту ваших слов. Данный пост я написал вечером-ночью под сильным впечатлением от того как просто оказалось можно применить SIMD для параллельной сортировки.
Я напишу новую статью с более обобщенным подходом и конкретным пояснением всех шагов сортировки.
Что касается применения конкретных мнемоник, то в случае с ассемблером мне кажется это неизбежное следствие, ассемблерный код всегда узконаправлен на целевую машину. Стоит заметить, что данный код нацелен на подавляющие большинство парка персональных ЭВМ.
не раскрыта тема: если есть сортировка 16 чисел, как её обобщить на сортировку N чисел.Часто рекурсивная сортировка (QuickSort/MegeSort), когда задача сводится к небольшому размеру (обычно меньше 8 элементов), переключается на другой алгоритм, например, сортировку вставками или пузырьком, потому что рекурсивный алгоритм на маленьких массивах неэффективен — много накладных расходов на организацию рекурсии. Вот тут SIMD-сортировка и пригодится.
Возражения что массивы редко бывают четко фиксированной длины
Сортировка массивов фиксированной длины нередко бывает нужна при обработке изображений — тот же медианный фильтр, к примеру — для каждого пикселя нужно отсортировать маленький массивчик окружающих пикселей, чтобы найти медианное значение. Вот была хорошая статья несколько лет назад, там автор делал на сортировочных сетях, есть и «обычная» версия, и SIMD-версия на интринсиках.
Решение в этой статье, конечно, похоже на сортировочную сеть, но разве что не оптимальную а оптимизированную под доступные операции.
Вроде минимальная сеть на 16 чисел это 60 C&S -- http://users.telenet.be/bertdobbelaere/SorterHunter/sorting_networks.html#N16L60D10 -- но она не приметима так как нам надо оперировать блоками по 4.
С большим интересом прочитал Ваш линк и даже реализовал его для 16 чисел, получив таким образом 4 упорядоченных подмассива, к сожалению процесс "слияния" подмассивов в один конечный массив не удается сделать параллельным, что значительно снижает эффективность алгоритма.
Интуитивно создается впечатление, что алгоритм становиться работоспособным не ниже чем на AVX1, при оперировании матрицами 8х8.
А где бенчмарки-то?
Сортировка массивов фиксированной длины с применением SIMD