Сейчас попробую поправить статью, буду искать как это сделать.
если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.
Т.е. QSort требует памяти Log(N )? Понятно, да, не знал, спасибо что подсказали, опять же попробую поправить.
1. Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.
Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.
А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.
Про QuickSort: имелось в виду массивно-параллельные вычисления, на GPU, хотелось бы посмотреть на реализацию такого распараллеливания, если это возможно.
В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве
Это где вы такую реализацию видели? O_o
Нигде, т.к. это взято из доступных описаний алгоритма Radix Sort, видимо практически такой вариант использовать нельзя.
И далеко вы собираетесь идти искать?
Спасибо что вникли в суть рассуждений, но понятно что именно так не собирается никто делать, в реализации схема чуть-чуть посложнее. Написал про поиск чтобы понятнее был ход рассуждений по алгоритму.
Не очевидно это. Как вы собираетесь распараллеливать?
Будет во второй части статьи, пока рано говорить, но вроде бы найден способ, который должен неплохо работать на GPU. Надо делать до конца и тестировать. Вторую часть быстро не обещаю, т.к. статья пишется параллельно с основной работой.
Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.
Про «умеренный случай» как раз это имелось в виду, написал так, потому что:
1. При чтении массива на первом проходе доступ линейный.
2. Случайная запись гораздо лучше случайного чтения, т.к.: а) в CPU есть буферы записи б) не всегда запись случайная в) в такой ситуации помогают кеши CPU.
Вот поэтому результаты сортировки неплохие по скорости получаются (по сравнению со стандартным QSort), что ж еще надо?
Для чисел int32 на тестах быстрее всего работает сортировка с radix значением 8 бит, т.е. сортировка всего массива выполняется в 4 прохода. Еще сортировка тестировалась с radix значением 16 бит, но размер radix массива получается большой, не влазит в кеш CPU, из-за этого хоть прохода надо 2, но итоговая скорость ниже, да, и проход массива занимает больше времени, конечно
Сейчас попробую поправить статью, буду искать как это сделать.
Т.е. QSort требует памяти Log(N )? Понятно, да, не знал, спасибо что подсказали, опять же попробую поправить.
2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.
Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.
Про QuickSort: имелось в виду массивно-параллельные вычисления, на GPU, хотелось бы посмотреть на реализацию такого распараллеливания, если это возможно.
Нигде, т.к. это взято из доступных описаний алгоритма Radix Sort, видимо практически такой вариант использовать нельзя.
Спасибо что вникли в суть рассуждений, но понятно что именно так не собирается никто делать, в реализации схема чуть-чуть посложнее. Написал про поиск чтобы понятнее был ход рассуждений по алгоритму.
Будет во второй части статьи, пока рано говорить, но вроде бы найден способ, который должен неплохо работать на GPU. Надо делать до конца и тестировать. Вторую часть быстро не обещаю, т.к. статья пишется параллельно с основной работой.
Про «умеренный случай» как раз это имелось в виду, написал так, потому что:
1. При чтении массива на первом проходе доступ линейный.
2. Случайная запись гораздо лучше случайного чтения, т.к.: а) в CPU есть буферы записи б) не всегда запись случайная в) в такой ситуации помогают кеши CPU.
Вот поэтому результаты сортировки неплохие по скорости получаются (по сравнению со стандартным QSort), что ж еще надо?