LINUX.ORG.RU

Новая самая быстрая реализация QuickSort на AVX2

 ,


2

6

Вышла железная сортировка для целых чисел максимально полно использующая расширение процессоров x86 AVX2. На данный момент это самая быстрая сортировка вообще. Так же автор щепетильно подошел к вопросу формальной верификации алгоритма. Доступна версия для int32, но по заверениям автора алгоритм легко перенести на другие битности. Особо отмечено что алгоритм можно использовать в криптографических приложениях.

Также автор обещает порт на ARM NEON

>>> Подробности

★★

Проверено: jollheef ()

Ответ на: комментарий от bbk123

Заведи бложек и там окукливайся, смайлодурачок.

anonymous ()
Ответ на: комментарий от bbk123

Залогинился тебе за щёку, сам понимаешь.

anonymous ()
Ответ на: комментарий от anonymous

Давно понятно, что ты анонимный дурак. Можешь не продолжать.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Давно понятно, что ты зарегистрировавшийся дурак. Но такова спецолимпиада.

anonymous ()
Ответ на: комментарий от anonymous

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

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Ты ведёшь себя как бот, как собака Павлова. Тебе покажи флажок незнакомого цвета, и тебя начинает рвать на весь тред.

anonymous ()
Ответ на: комментарий от anonymous

Ты сел в лужу с сортировкой строк, но упорно пытаешься казаться умным. Нет братец, ты дурак.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Ты обосрался с тем, что у сортировки чисел нет применений, и порвался когда тебе привели пример такого применения.

anonymous ()
Ответ на: комментарий от anonymous

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

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Ты задал один вполне конкретный вопрос, а потом начал неадекватно маняврировать.

anonymous ()
Ответ на: комментарий от anonymous

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

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Забудь про строки, сортируем массивы элементов по длине. Есть теперь применение?

anonymous ()
Ответ на: комментарий от anonymous

Вопрос был о практическом применении. Какой практический смысл в сортрировке по длине? Где встречаются такие задачи, когда нужно быстро отсортировать очень много чего по длине?

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Какой практический смысл в сортрировке по длине? Где встречаются такие задачи, когда нужно быстро отсортировать очень много чего по длине?

Непараметрическая статистика © — > анализ вариационных рядов © — > порядковые статистики ©.

quickquest ★★★★★ ()
Ответ на: комментарий от quickquest

Ну и где там такая сортировка? Ссылками на длинные статьи любой дурак закидать может.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Ну и где там такая сортировка?

QuickSort для сотворения вариационного ряда содежится во множестве пакетов мат. статистики и прикладухах для экономистов. Попробуй построить вариационный ряд без сортировки и сразу всё поймёшь.

Ссылками на длинные статьи любой дурак закидать может.

«По просьбе трудящихся» короткие картинки вариационных рядов.

quickquest ★★★★★ ()
Ответ на: комментарий от LjubaSherif

Майнеры монеры это говнокод? Поэтому количество хешей вырастает на 80% на процессоре ryzen 1500, потому что SMT костыль?

steemandlinux ★★★★★ ()
Ответ на: комментарий от FilosofeM

В сортировке нету «лучших» алгоритмов. Все зависит от входящего массива и требований.

BceM_IIpuBeT ★★★ ()
Последнее исправление: BceM_IIpuBeT (всего исправлений: 2)
Ответ на: комментарий от LjubaSherif

Всё это работает на одном единственном ядре

Ого. Каждый день что-то новое узнаешь?

BceM_IIpuBeT ★★★ ()
Ответ на: комментарий от steemandlinux

Наверное есть подвох вроде того, что можно сделать больше попугаев в один поток, но тогда по ядрам распределяться будет хуже. Те два(и более) стула как обычно.

anonymous ()
Ответ на: комментарий от steemandlinux

Майнеры монеры это говнокод?

Да. Можешь дать код и я тебе даже покажу, где именно это говнокод и почему.

Поэтому количество хешей вырастает на 80% на процессоре ryzen 1500, потому что SMT костыль?

Говнокод не может даже в х2.

Я же объяснил как это работает, обычно ядро читает один поток инструкции, а с smt - читает сразу два и объединяет в одно.

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

Ну вот хт берёт два твоих потока говнокода с менее чем одной инструкцией, объединяет и получается что-то вида abababab и уже будет исполнятся (одна_или_менее * 2).

Как ты можешь из этого понять - одному потоку ничего не мешает дать ядру те самые 2инструкции, если ты напишешь код нормально. И хт тебе ничего не даст.

LjubaSherif ()
Ответ на: комментарий от bbk123

а по какому критерию строки сортируем? по алфавиту? это сортировка массивов чисел( сравниваем числа); по длине? опять же числа..

Thero ★★★★★ ()

получается что идеальной сортировки нету, но теперь есть quick sort на avx2. и хорошо.

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

barberry ★★ ()
Последнее исправление: barberry (всего исправлений: 1)
Ответ на: комментарий от barberry

осталось avx2 программно реализовать на чем-то более старом.

xmikex ★★★ ()
Ответ на: комментарий от bbk123

А какой практический смысл в сортировке исключительно чисел?

Пол треда прочел, и наконец-таки встретил вопрос по существу. А действительно, как с помощью этого сортировать что-то полезное? Ну кроме как писать в старшие разряды какую-то метрику объектов, в младшие - их индексы, и потом запускать эту сортировку?

segfault ★★★★★ ()
Ответ на: комментарий от segfault

А действительно, как с помощью этого сортировать что-то полезное?

Наипростейший пример: ранговая фильтрация ©.

quickquest ★★★★★ ()
Ответ на: комментарий от LjubaSherif

Да. Можешь дать код и я тебе даже покажу, где именно это говнокод и почему.

Т.е. код от которого напрямую зависит доход майнера - говнокод? Почему же все написали говнокод?

Ну и где тут говнокод?

https://github.com/fireice-uk/xmr-stak/tree/master/xmrstak/backend/cpu/crypto

steemandlinux ★★★★★ ()
Ответ на: комментарий от steemandlinux

где тут говнокод

Первый попавшийся там исходник состоит больше чем наполовину из магических констант.

anonymous ()
Ответ на: комментарий от steemandlinux

Что «криптография»? Может ещё на ассемблере переписать, «криптография» же.

anonymous ()
Ответ на: комментарий от Thero

Сортируем строки между собой по алфавиту, а не символы в строках.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

так и? мы получаем массив массивов чисел.. его сортировка сводится к нескольким сортировкам чисел. да для этого надо будет немного дописать алгоритм.

Thero ★★★★★ ()
Ответ на: комментарий от bbk123

Сортируем строки между собой по алфавиту

А символы — это теперь не числа?

BceM_IIpuBeT ★★★ ()

давно бы уже взяли и добавили пару инструкций для аппаратной сортировке в кремнии

и никаких срачей, и никаких переписываний ёпта

anonymous ()
Ответ на: комментарий от FilosofeM

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

Quasar ★★★★★ ()
Ответ на: комментарий от LjubaSherif

Кто виноват в том, что на амд палёный авх?

Да он везде такой, ибо микрокод.

Quasar ★★★★★ ()
Ответ на: комментарий от bbk123

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

Quasar ★★★★★ ()
Ответ на: комментарий от quickquest

Если бы в каждом персональном компьютере был чип ПЛИС для пользовательских нужд, это открыло бы огромные возможности.

Quasar ★★★★★ ()

никаких переписываний ёпта

Тогда будешь перепаивать. Но, кстати, можно сделать сортирный акселератор для PCIe. И версия пузырьком на USB для бедных

Deleted ()
Ответ на: комментарий от Deleted

И версия пузырьком на USB для бедных

Кстати, «Пузырёк» — лучший алгоритм для диска с 3 головками и сортировщика на «пузырьковых доменах» ©.

quickquest ★★★★★ ()
Ответ на: комментарий от Iron_Bug

никто не юзает

Поумерь ЧСВ, ты — не все. У всех питон и так стоит.

mersinvald ★★★★ ()
Ответ на: комментарий от bbk123

надо будет допишем, тут ведь надо ещё понять как криптостойкость сохранить и определить нужна ли она тут, в остальных случаях более узкоспецифичные алгоритмы сортировки оптимизированные с учётом наиболее вероятных входных данных будут выигрывать в реальных задачах по скорости, но явно проигрывать в безопасности, но опять же вопрос нужна ли она тут?

Thero ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.