Алгоритм сортировки 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.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 23

    0
    Интересно, а каков оптимальный radix скажем для диапазона int32? 2, 16, 256? Если он мал, то велико количество итераций с генерацией промежуточных результатов, и длина списка в каждой ячейке велика. Если он большой — то сканирование самого radix-массива занимает время…
      0
      Для чисел int32 на тестах быстрее всего работает сортировка с radix значением 8 бит, т.е. сортировка всего массива выполняется в 4 прохода. Еще сортировка тестировалась с radix значением 16 бит, но размер radix массива получается большой, не влазит в кеш CPU, из-за этого хоть прохода надо 2, но итоговая скорость ниже, да, и проход массива занимает больше времени, конечно
        0
        Вероятно, уже очень скоро размер кеша L1 превысит 256 КБайт, и, соответственно, наиболее эффективным будет использование 16 бит
          0
          Откуда информация про L1 размером 256 КБайт? По-моему его не делают такого размера из-за проблем с проектированием CPU, то есть просто не могут.
      0
      После прочтения статьи у меня появилось два вопроса:
      1. с чего вы взяли, что QuickSort не поддается распараллеливанию? Например, parallel_sort в intel tbb использует QuickSort;
      2. с чего вы взяли, что QuickSort не использует дополнительной памяти? Классическая рекурсивная реализация использует как минимум log N памяти;
        0
        1. Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
        2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.

        Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.
          0
          Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.

          ок, я неправильно понял фразу в первом параграфе.
          не требут дополнительной памяти.

          если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.
            0
            ок, я неправильно понял фразу в первом параграфе.


            Сейчас попробую поправить статью, буду искать как это сделать.

            если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.


            Т.е. QSort требует памяти Log(N )? Понятно, да, не знал, спасибо что подсказали, опять же попробую поправить.
              0
              Хотите Quicksort без памяти на стек? Это очень просто, но, разумеется, увеличит время.
              1) Вспоминаем, что с помощью разделения массива, используемого в quicksort, мы можем разделить его на две части произвольно заданного размера (0..K-1 и K..N-1) в среднем за O(N) операций, причём без использования рекурсии;
              2) Учимся без рекурсии перебирать фрагменты массива, длина которых равна степени двойки, а смещение — кратно этой степени. Причём отрезки перебираем в порядке уменьшения длины.
              3) Каждый такой отрезок делим на две части с помощью алгоритма из п.1. Если правая часть не пересекается с сортируемым массивом, ничего не делаем.
              Так, для массива из 13 элементов нам надо будет выполнить деления:
              0-7 и 8-12
              0-3 и 4-7
              8-11 и 12-12
              0-1 и 2-3
              4-5 и 6-7
              8-9 и 10-11
              и упорядочить каждый 2-элементный фрагмент.
                0
                В QuickSort вы не выбираете размеры подмасивов, вы выбираете опорный элемент, а в зависимости от опорного элемента получаются разные размеры подмасивов, так что ваша стройная теория о делении пополам не работает.
                  0
                  Почему? Я продолжаю делить тот подмассив, в который попала середина. Как, по-вашему, работает быстрый поиск медианы, и вообще, n-й статистики?
                    0
                    А как вы реализуете поиск медианы без рекурсии и дополнительной памяти?
                      +1
                      Туплю, там конечно же хвостовая рекурсия, так что я не прав.
                    0
                    Другой вариант. После того, как разделили массив на три части (меньше опорного элемента — равные ему — больше его), находим в первой части минимальный элемент, и ставим его в конец этой части. Переходим к сортировке последней части. Чтобы найти начало последней неотсортированной части, берём её последний элемент X, и просматриваем массив в обратную сторону в поисках элемента, меньшего X (это можно делать как линейным, так и бинарным поиском). Первый встреченный (т.е. последний по массиву) такой элемент и будет опорным, неотсортированный фрагмент начинается сразу за ним. Если все просмотренные элементы были больше X, нам надо сортировать начало массива.
                    То есть, стек кодируется непосредственно порядком элементов.
                    Число сравнений, к сожалению, в 3-4 раза больше, чем при обычном quicksort.
            +3
            Quick Sort, который на данный момент не поддается распараллеливанию

            А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.

            В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве, т.е. каждый элемент это тоже массив, в который записываются исходные числа, как раз здесь скрыта причина высокого расхода памяти.

            Это где вы такую реализацию видели? O_o

            Если позиция копирования числа уже занята, то ищем первый не занятый элемент в итоговом массиве.

            И далеко вы собираетесь идти искать?

            В результате был найден третий способ, более оптимально использующий память, но требующий дополнительного прохода radix массива после его заполнения

            Как ваш способ соотносится со стандартной реализацией?

            Возможность параллельного вычисления

            Не очевидно это. Как вы собираетесь распараллеливать?

            Локальность данных при обработке — Достаточная

            Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.
              +1
              А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.

              Про QuickSort: имелось в виду массивно-параллельные вычисления, на GPU, хотелось бы посмотреть на реализацию такого распараллеливания, если это возможно.

              В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве

              Это где вы такую реализацию видели? O_o


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

              И далеко вы собираетесь идти искать?


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

              Не очевидно это. Как вы собираетесь распараллеливать?


              Будет во второй части статьи, пока рано говорить, но вроде бы найден способ, который должен неплохо работать на GPU. Надо делать до конца и тестировать. Вторую часть быстро не обещаю, т.к. статья пишется параллельно с основной работой.

              Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.


              Про «умеренный случай» как раз это имелось в виду, написал так, потому что:

              1. При чтении массива на первом проходе доступ линейный.
              2. Случайная запись гораздо лучше случайного чтения, т.к.: а) в CPU есть буферы записи б) не всегда запись случайная в) в такой ситуации помогают кеши CPU.

              Вот поэтому результаты сортировки неплохие по скорости получаются (по сравнению со стандартным QSort), что ж еще надо?
              0
              Спасибо за статью. Во второй части статьи (radix на GPU) очень хотелось бы посмотреть на сравнение radix с bitonic.
                0
                Да, спасибо ) если дойдет до тестов, т.е. скорость сортировки будет приемлемой, то сравню с bitonic.
                0
                В итоге вам понадобилось, всё-таки, не менее 2*N ячеек (включая исходный массив)? Достаточно использовать N+R*(K+1) (R^K не меньше диапазона чисел, т.е. 2^32), т.е. хранить K копий счётчиков/указателей элементов — на рекурсию. Сортировать надо будет со старших разрядов, индекс извлекать прямо из значения, а при перекладывании элементов в нужные участки не заботиться об их порядке. По памяти получается экономнее, а по фрагментарности доступа — не хуже, чем со вспомогательным массивом.
                  +1
                  Да не нужно хранить пары, достаточно завести radix массив размером radix+1 (11 в случае десятичных чисел) и при подсчете адресоваться к элементам idx[i+1], idx[0] не трогать. Затем сделать дополнительный проход по radix массиву, в котором в элементы записать сумму текущего и предыдущего элемента: idx[i] = idx[i] + idx[i-1] (idx[0] остается равным 0). Таким образом, в radix массиве будут индексы, по которым следует писать в вспомогательный массив. В итоге, делая проход по исходному массиву, адресуясь по элементам radix массива и инкрементируя их, можно заполнить вспомогательный массив.
                    0
                    хочется проду
                      0
                      Для прода читаемость и поддерживаемость, как правило, важнее скорости работы. А эти два параметра у кода
                      std::sort(a.begin(), a.end());
                      всяко выше.
                        0
                        Имел ввиду продолжение статьи

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

                    Самое читаемое