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

AVR NEON

ARM NEON.

Пофиксил. Спасибо.

Так же

Также

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

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

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

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

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

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

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

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

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

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

Владельцам феномо-кукурузы же.

сначала расскажи, как кодишь ты сам. пьяным, надеюсь?

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

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

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

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

гиперпней

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

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

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

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

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

DJB!

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

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

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

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

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

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

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

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

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

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

----

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

----

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ты что дурак? Причём тут длина?

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

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

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

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

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

За своими манёврами следи, дурачок ;-))