LINUX.ORG.RU

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

 ,


2

6

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

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

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

★★

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

Микрооптимизация - зло. Какой смысл вообще оптимизировать этот убогий алгоритм, у которого худший случай - n^2? Heapsort, Mergesort - лучше.

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

Сразу видно что ты анскильный. Mergesort требует ещё O(N) памяти сверху и её выделение не бесплатно, Heapsort медленнее Quicksort-а, несмотря на худший случай n log n, поэтому есть Intorspective-sort который является наибольее оптимальным для общего случая. А он, в свою очередь использует Quicksort и Heapsort, при том Quicksort идёт в дело первым и только в худшем случае происходит переключение на Heapsort, так что оптимизация Quicksort штука очень нужная и полезная. Ну и да, есть случаи, где заведомо известно что массив не может содержать худшего случая, и тогда Heapsort проигрывает на пару с Mergesort-ом. Или случай когда размер контейнера статичен, тогда Mergesort выигрывает у остальных двух.

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

А я рад что есть люди которым не все равно

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

Реальность сложнее самообмана О-нотацией.

anonymous ()

На данный момент это самая быстрая сортировка вообще

В лучшем случае это может быть самая быстрая быстрая сортировка, но никак не самая быстрая сортировка вообще

Звучит неплохо

Crocodoom ★★ ()

Призыв к владельцам Phenom, Celeron и гиперпней переходить на Core i3?

iZEN ★★★★★ ()

сколько дураков не учишь, они игры всё равно в однопоток делают

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

Как записаться в твою школу скилла?

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

Получить сотый левел в вов очевидно жи.

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

Призыв к владельцам Phenom, Celeron и гиперпней переходить на Core i3?

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

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

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

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

гиперпней

AVX ИНСТРУКЦИИ! AVX ИНСТРУКЦИИ !AVX ИНСТРУКЦИИ! AVX ИНСТРУКЦИИ! AVX ИНСТРУКЦИИ! AVX ИНСТРУКЦИИ! AVX ИНСТРУКЦИИ!

*агрессивные крики князя*

Для тех кто в танке, линк.

https://www.youtube.com/watch?v=x3eFaf3pf6E

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

Я уже объяснял, что TDP процессоров в спецификации не учитывает их постоянную загрузку и задействование всех блоков. Поэтому кулер для 65 Вт процессора нужно покупать с серьёзным запасом по теплоотведению - 125-150 Вт оптимально. Но нет - будут ставить боксовые «демонстраторы».

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

Ты покажи, ткни. Вон штуку из оп-поста вообще только написали.

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

Суть не в том что нет. Довольно много игр под маздаи их требуют. Не вторую итерацию конечно, но на гиперпне и первой то нет. Плюс сегодня нет, а завтра есть и всем этим экономщикам по губам проведут. Как уже с было с тем же SSE

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

Да вам сколько не ори, вы уже подоглохшие слегка.

t184256 ★★★★★ ()

Ура! Теперь искать минимальное/максимальное значение в массиве станет ещё быстрей!

anonymous ()

На данный момент это самая быстрая сортировка вообще.

при условии что данные влазят в кэш второго уровня полностью. Было бы интресно сравнить на обьемах на порядок-два превышающих обьем кэша третьего уровня.

cvv ★★★★★ ()

На AMD Zen два блока SSE работают гораздо быстрее чем один AVX2, т.к. при использовании SMT задействуются оба SSE блока, а AVX там синтетический микрокод загружаемый из AGESA, фактически исполняющийся на паре SIMD блоков.

steemandlinux ★★★★ ()
Последнее исправление: steemandlinux (всего исправлений: 2)

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

Ага: © — > © в 2 раза быстрее :)

quickquest ★★★★★ ()
Последнее исправление: quickquest (всего исправлений: 1)

Только это ни разу не QuickSort, у него время сортировки зависит только от длины массива, но не от содержимого.

----

The NTRU Prime paper explained how to make constant-time sorting software

----

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

сколько дураков не учишь, они игры всё равно в однопоток делают

Зачем ты что то пытаешься высирать если ты ничерта не понимаешь в вопросе? Сколько ты не сетуй на разработчиков игр планировщик задач Windows магическим образом не научится ПРАВИЛЬНО синхронизировать потоки многопоточных приложений, правильно обрабатывать тайминги потока .... e.t.c К тому же ты наверно не учитываешь что пискать многопоточное «AppName» стоит сотни нефти ибо дофигища процессорного и ядерного матана (готовых либ многопотка НЕТ).

anonymous ()

абсолютно непонятно, зачем «самой быстрой реализации на AVX2» для инсталляции требуется... пистон. я так понимаю, чтобы это работало быстро, там просто должен быть обычный ассемблер с соответствующими инструкциями. ничего такого секретного там нет. и пистон там нигде даже рядом не лежал, что самое главное.

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

абсолютно непонятно

Иди посуду подметай.

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

Может для сборки нужен? Ну там, написали собственный make на удаве например

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

Это же DJB, у него всё не как у людей. Гений, понимать надо. Возьми и перепакуй как тебе угодно. Суть не в пайтоне.

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

На AMD Zen два блока SSE работают гораздо быстрее чем один AVX2

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

т.к. при использовании SMT задействуются оба SSE блока

SMT не имеет никакого отношения к блокам и существует совершенно в другом месте.

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

Суть не в пайтоне.

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

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

SMT не имеет никакого отношения к блокам и существует совершенно в другом месте.

Щаз, у AMD можно загрузить SSE в 16 потоков на 8 ядерном проце и прирост будет почти 2 раза, при условии отсутствия ветвлений конечно же.

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

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

Ну ты разберись сначала, что там на пайтоне. Небось инсталлятор, файло распихивающий по нужным местам. Просто возьми исходник сортировки и вкорячь себе в проект, вот и всё.

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

SMT не имеет никакой фактической ценности по части загрузки чего бы то ни было. SMT это некий кастыль, который позволять сливать два потока говнокода в один двойной поток говнокода, тем самым увеличивая его параллельность в 2раза. Всё это работает на одном единственном ядре.

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

Такие вещи никто не пишет руками, хотя( судя по коду) пациент её писал руками. Естественно, что юзать такую парашу как пистон нормальный человек не будет, но пацан просто стал жертвой. Бывает.

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

Пайтон сейчас - самый популярный язык программирования в среде искусственного интеллекта и массивной параллелизации.

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

iZEN ★★★★★ ()

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

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

«Под капотом» другим объектам назначают соответствующее им число.

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

Каким другим объёктам? Какие числа ты назначишь строкам текста? Хеш для этого не подходит.

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

Такие, по которым их сортировать, например длину.

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

Это ты так порвался в потугах задать как можно наиболее неосмысленный вопрос?

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

Ты не знаешь, что такое сортировка строк? Ты таки дурак.

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

Ты забыл слово «лексикографическая»? Или просто тупой?

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

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

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

Какому умолчанию, маня? Это уже твои манёвры пост-фактум.

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