Поразрядная сортировка LSD (Radix Sort)

[@DrSmile]

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

[@rebuilder]

Занятное обсуждение, однако мне видится что несколько переусложнили решение вопроса. Могу конечно ошибаться. За ссылку спасибо.

[@GCU]

А если комбинировать sort step c подсчетом? По логике это будет только 2КБ сверху даже для 64х битных чисел, ведь после sort step старый подсчет больше не нужен.

[@rebuilder]

Идея заманчивая, но нет. К моменту сортировки нужно уже знать место вставки элемента. Эта информация и содержится в вычисленном заранее массиве.
Если производить подсчёт в каждом шаге, то придется дополнительно обходить основной массив каждый раз. Это займёт гораздо больше операций, хотя да, мы экономим пару килобайт. На малых массивах это имеет смысл, а на миллионе элементов каждый дополнительный проход очень дорог.

[@GCU]

В sort step и так происходит обход каждого элемента основного массива, я предлагаю в том же цикле и делать подсчет для следующей перестановки, меняя массивы счётчиков. Да, эти 256 значений нужно будет занулять и потом пересчитать смещения, но это же и так делается.

[@rebuilder]

Если только для следующего разряда, то да, сработает.
Хотя немного собьёт стройность конструкции, ведь что тогда считать на последнем шаге, видимо добавить проверку на не исполнение.
Мысль мне нравиться попробую посмотрю на изменение производительности.

[@rebuilder]

Падение скорости получилась в среднем на 13% при n>1000, стоит ли это 2Кб памяти, сомнительно.
На меньших длинах есть небольшой выигрыш. Возможно данный код поддаётся улучшению.

Код

//======================================================
procedure RSort2(var m: array of Longword);
//--------------------------------------------------
   procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
   var i,temp : Longword;
       k,num1,num2 : Byte;
       offset : array[0..3] of byte absolute temp;
   begin
     if num<3 then                                    // устанавливаем байт для проверки на следующем шаге
       num2 := num+1
     else
       num2:=0;

     for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
       Inc(s_source[i], s_source[i-1]);

     FillChar(s_dest, 256 * SizeOf(Longword), 0);

     num1 := num*8;
     for i := High(source) downto 0 do
     begin
       temp := source[i];
       Inc(s_dest[offset[num2]]);
       k := temp SHR num1;
       Dec(s_source[k]);
       Dest[s_source[k]] := temp;
     end;

   end;
//------------------------------------------------------------------------------
var s : array[0..1] of array[0..255] of Longword;  // Объявляем массив двух корзин первым, для выравнивания на стеке
    i : longword;
    k : Byte;
    m_temp : array of Longword;
begin
  SetLength(m_temp, Length(m));                    // Объявляем временный массив
  FillChar(s[0], 256 * SizeOf(Longword), 0);       // Быстрая очистка первой корзины

  for i := 0 to High(m) do                         // Заполнение первой корзины
  begin
    k := m[i];
    Inc(s[0,k]);
  end;

  Sort_step(m, m_temp, s[0], s[1], 0);             // Вызов сортировки по байтам от младших к старшим
  Sort_step(m_temp, m, s[1], s[0], 1);
  Sort_step(m, m_temp, s[0], s[1], 2);
  Sort_step(m_temp, m, s[1], s[0], 3);

  SetLength(m_temp, 0);                            // Высвобождаем память
end;
//======================================================

[@rebuilder]

Вариант с отдельной функцией сортировки на последнем шаге, падение меньше около 4-5%, уже приемлемо.

код

//==================================================
procedure RSort2(var m: array of Longword);
//--------------------------------------------------
   procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
   var i,temp : Longword;
       k,num1,num2 : Byte;
       offset : array[0..3] of byte absolute temp;
   begin
     num2 := num+1;                                   // устанавливаем байт для проверки на следующем шаге

     for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
       Inc(s_source[i], s_source[i-1]);

     FillChar(s_dest, 256 * SizeOf(Longword), 0);

     num1 := num*8;
     for i := High(source) downto 0 do
     begin
       temp := source[i];
       Inc(s_dest[offset[num2]]);
       k := temp SHR num1;
       Dec(s_source[k]);
       Dest[s_source[k]] := temp;
     end;

   end;
//--------------------------------------------------
   procedure Sort_step_last(var source, dest, s_source : array of Longword);
   var i,temp : Longword;
       k : Byte;
   begin
     for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
       Inc(s_source[i], s_source[i-1]);

     for i := High(source) downto 0 do
     begin
       temp := source[i];
       k := temp SHR 24;
       Dec(s_source[k]);
       Dest[s_source[k]] := temp;
     end;
   end;
//--------------------------------------------------
var s : array[0..1] of array[0..255] of Longword;  // Объявляем массив двух корзин первым, для выравнивания на стеке
    i : longword;
    k : Byte;
    m_temp : array of Longword;
begin
  SetLength(m_temp, Length(m));                    // Объявляем временный массив
  FillChar(s[0], 256 * SizeOf(Longword), 0);       // Быстрая очистка первой корзины

  for i := 0 to High(m) do                         // Заполнение первой корзины
  begin
    k := m[i];
    Inc(s[0,k]);
  end;

  Sort_step(m, m_temp, s[0], s[1], 0);             // Вызов сортировки по байтам от младших к старшим
  Sort_step(m_temp, m, s[1], s[0], 1);
  Sort_step(m, m_temp, s[0], s[1], 2);
  Sort_step_last(m_temp, m, s[1]);

  SetLength(m_temp, 0);                            // Высвобождаем память
end;
//================================================== 

[@GCU]

Я предполагаю что падение связано с уменьшением доступного для сортируемых массивов кэша. Ваш оригинальный алгоритм в цикле работал с 1КБ массивом счётчиков, а новый работает с двумя массивами, т.е. 2КБ.
P.S. Прикольно, что 4*256 = 1024, а 4*16 = 64 (т.е. массив целиком вмещается в кеш-линию если счётчики на пол-байта). В плане кэша MSD был бы лучше, так как уже после одного прохода элементы не будут перемещаться по всему массиву, а только внутри группы.

[@rebuilder]

Пробовал с проходом по 4 бита, падение 30-40%, видимо тут уже кэш не даёт такого преимущества как встроенные инструкции процессора на 1 байтовые вычисления и повторные проходы.
Есть желание опробовать гибрид MSD и LSD для разных проходов, если будут интересные результаты, напишу.

[@rebuilder]

MSD мне не очень нравится накладными расходами на внутренние циклы, размерность которых вероятностная величина. Не вижу как их сделать эффективно.