Алгоритм сортировки Radix Compact. Часть 1: реализация на CPU

В одном из моих проектов, который был связан с компьютерным зрением, возникла задача сортировки большого массива чисел (около 100 млн. элементов). Код сортировки должен был выполняться как можно быстрее, причем с возможностью исполнения на нескольких процессорах, и желательно на GPU. Сортировка реализованная в стандартной библиотеке C++ не подходила: она основана на алгоритме Quick Sort, который на данный момент не поддается массивному распараллеливанию на GPU. Поиск других способов привел к алгоритму Radix Sort, но в найденных источниках описывалась реализация требующая большого расхода памяти, точнее памяти требовалось: (количество элементов массива) * (размер radix массива). Для массива 100 млн. элементов и radix массиве размером 256 элементов памяти потребовалось бы 25.6 Гб, мало реальное требование, на текущий момент развития вычислительной техники. Но для распараллеливания вычислений алгоритм Radix Sort подходит неплохо, собственно поэтому автор попытался доработать этот способ, чтобы уменьшить расход памяти до приемлемых значений.

Для начала посмотрим на общую схему алгоритма Radix Sort, по шагам выполнения:
Итак, возьмём массив двухзначных десятичных чисел (десятичных для упрощения рассуждений), которые нужно отсортировать по возрастанию значений:

12, 10, 45, 29, 74, 32, 11, 47, 22,27.

Для выполнения сортировки нужно создать вспомогательный массив (в текущей статье он называется radix массив). Размер массива должен быть 10 элементов, заметим, что количество элементов должно быть равно максимальному значению числа сортировки (что такое число сортировки будет понятно из дальнейших рассуждений). Вспомогательный массив вначале пуст и выглядит так:

Проход 1 заполнения radix массива.
Начинаем заполнять radix массив: для этого берем первое число из массива сортировки: 12, берем его последнюю цифру (2) и сохраняем число 12 в элементе radix массива с индексом 2, radix массив будет выглядеть так:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
		12

Далее берем второе число из исходного массива: 10, сохраняем его в элементе с индексом 0:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
		12			45

Таким же способом копируем все числа из исходного массива в radix массив, в конечном итоге он приобретет такой вид:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
10	11	12,32,22		74	45		47,27		29

После того как все числа скопированы в radix массив копируем их уже в новый массив, начиная с первого элемента radix массива, получится такой результат:
10,11,12,32,22,74,45,47,27,29.

Как видим, исходные числа еще не отсортированы, нужно выполнить дополнительный проход заполнения radix массива (заметим, что для двузначных десятичных чисел всего нужно сделать 2 прохода, для трехзначных 3, для четырехзначных 4, и т.д.).

Проход 2 заполнения radix массива.
Берем первое число из промежуточного массива сортировки: 10, берем его предпоследнюю цифру (1) и сохраняем число 10 в элементе radix массива с индексом 1:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
	10

Далее берем второе число из промежуточного массива: 11, сохраняем его в элементе с индексом 1:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
	10,11

И так далее, заполняем весь radix массив числами из промежуточного массива, индекс позиции числа в radix массиве равен значению предпоследней цифры исходного числа:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
	10,11,12	22,27,29	32	45,47			74

Все, теперь достаточно скопировать числа из radix массива в новый массив и числа будут отсортированы в порядке возрастания значений:
10,11,12,22,27,29,32,45,47,74.

Сейчас рассмотрим как реализуется запись в radix массив практически, при выполнении кода сортировки на CPU. Понятно, что значения чисел, которыми заполняется radix массив надо где-то хранить, причем делать это максимально быстро (это критически важно для алгоритмов сортировки). В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве, т.е. каждый элемент это тоже массив, в который записываются исходные числа, как раз здесь скрыта причина высокого расхода памяти. Из-за того, что мы не знаем заранее какие исходные числа нам нужно сортировать, то приходится резервировать место в каждом элементе radix массива под все числа исходного массива. Для нашего упрощенного примера пришлось бы резервировать память в размере 10x10 элементов, в случае же рабочего варианта потребовался бы размер памяти 256*10, что много. Посмотрим иллюстрацию организации памяти radix массива для нашего примера, на втором проходе заполнения:

	12	29
	11	27		47
	10	22	32	45			74

Как видим, такая схема выделения памяти приводит к ее перерасходу, схема избыточна и затратна. Попробуем найти способ организации radix массива, который не требовал бы перерасхода памяти. Вначале подумаем: а сколько памяти вообще надо? Столько, сколько элементов в исходном массиве! Как же практически реализовать хранение исходных чисел? Автором были рассмотрены разные схемы: динамическое выделение памяти, при такой схеме radix массив выглядит так (упрощенно):

void*

void*

void*

void*

void*

void*

void*

void*

void*

void*

Вторая схема заключалась в выделении памяти в дополнительном массиве, числа из одного элемента radix массива хранятся в виде связанного списка, а в radix массиве хранится индекс первого элемента списка.
Оба этих способа позволяют сократить расход памяти до приемлемого уровня, но при практической реализации показали низкую скорость работы: самым медленным оказался способ с динамическим выделением памяти, быстрее был способ использующий связанные списки. Причина низкого быстродействия оказалась в затратном вызове функции перераспределении памяти для первого случая и высоких задержках при случайном доступе к памяти во втором случае.

В результате был найден третий способ, более оптимально использующий память, но требующий дополнительного прохода radix массива после его заполнения (но т.к. в radix массиве небольшое количество элементов, то это приемлемо), итак схема такая: создаем дополнительный массив в котором храним исходные числа, но не в виде связанного списка, а в виде: исходное число, индекс числа в radix массиве. А в radix массиве храним общее количество исходных чисел для каждого элемента radix массива. После прохода 2 эти массивы будут выглядеть так:
Radix массив:

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
count: 0	count: 3	count: 3	count: 1	count: 2	count: 0	count: 0	count: 1	count: 0	count: 0

Дополнительный массив (в нем хранятся пары: исходное значение, индекс значения в radix массиве):

10,1

11,1

12,1

32,3

22,2

74,7

45,4

47,4

27,2

29,2

Далее делаем дополнительный проход radix массива, в нем вычисляем индексы позиций заполнения итогового массива числами из дополнительного массива, результат дополнительного прохода (промежуточный radix массив):

Idx0	Idx1	Idx2	Idx3	Idx4	Idx5	Idx6	Idx7	Idx8	Idx9
IdxR: -1	IdxR:0	IdxR:3	IdxR:6	IdxR:7	IdxR: -1	IdxR: -1	IdxR:9	IdxR: -1	IdxR: -1

Примечание: значение -1 показывает, что элемент не задан.

И наконец заполняем итоговый массив числами из дополнительного массива (используя значения из промежуточного массива): например для первого числа (10,1) позиция копирования будет 0, для четвертого числа (32,3) позиция копирования будет 6, для шестого числа (74,7) позиция копирования будет 9. Если позиция копирования числа уже занята, то ищем первый не занятый элемент в итоговом массиве.

Полученный массив:
10,11,12,22,27,29,32,45,47,74.
Как видим, результат верен.

Описанный способ сортировки был назван Radix Compact, по его свойству: пониженному расходу памяти, по сравнению с оригинальным Radix Sort.
Сейчас сравним общие свойства алгоритма Radix Compact со свойствами алгоритма Quick Sort (для случая сортировки 32-х битных чисел и radix значению 8 бит):

	Radix Compact	Quick Sort
Вычислительная сложность, лучший случай	N*( 2 ) + 256*1	N*Log(N)
Вычислительная сложность, худший случай	N*( 8 ) + 256*4	N2
Дополнительный объем памяти	N + size(radix array)	Log(N)
Возможность массивно-параллельного вычисления	Да	Нет
Доступ к памяти	Умеренно случайный	Линейный
Локальность данных при обработке (важна для размещения данных в кэше CPU)	Достаточная	Высокая

Теоретически алгоритм Radix Compact имеет неплохие характеристики, что же, проверим это на практике. Для начала сравним результаты работы алгоритмов на «домашнем поле» Quick Sort: в однопоточной реализации на массивах 32-х битных чисел:



Тестирование проводилось на CPU Intel i5-3330 (3000 МГц), объем памяти: 16 ГБ, ОС: Windows 8.0 64-бит. Код сортировки Radix Compact написан на C++, реализация Quick Sort: std::sort(). Примечание: тестировался немного доработанный Radix Compact, а так же время работы Radix Compact не включает время выделения памяти.

Как видим, даже в самых выигрышных для Quick Sort условиях Radix Compact превосходит его в скорости работы до 7 раз, проигрывая только на массивах маленького размера (до 100 элементов). Это понятно, т.к. в Radix Compact требуется дополнительная обработка небольшого radix массива, для массивов большого размера это время практически не влияет на результат, но для маленьких массивов оно оказывается существенным. Впрочем в целом результаты Radix Compact вполне достойные. В следующей части статьи я напишу о результате адаптации алгоритма к выполнению на GPU, распараллеливание вычислений обещает дать еще больший выигрыш по сравнению со стандартным Quick Sort.