Как улучшить эту реализацию radix-sort?

Question

Я реализую 2-байтную сортировку Radix. Концепция заключается в использовании Counting Sort, для сортировки младших 16 бит целых чисел, а затем для верхних 16 бит. Это позволяет мне запускать сортировку в 2 итерациях. Первая концепция, которую я имел, пыталась выяснить, как обращаться с негативами. Так как бит знака будет перевернут для отрицательных чисел, то в шестнадцатеричной форме это сделает негативы большими, чем положительные. Для борьбы с этим я перевернул знаковый бит, когда он был положительным, чтобы сделать [0, 2 бил] = [128 000 000 000, 255 255 ...). И когда это было отрицательно, я перевернул все биты, чтобы он варьировался от (000 000 .., 127 255 ..). Этот site помог мне с этой информацией. Чтобы закончить его, я разделил бы целое число на верхний или нижний 16-бит на основе прохода. Ниже приведен код, позволяющий мне это сделать.

static uint32_t position(int number, int pass) { 
    int mask; 
    if (number <= 0) mask = 0x80000000; 
    else mask = (number >> 31) | 0x80000000; 
    uint32_t out = number^mask; 
    return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff; 
} 

Для того, чтобы начать фактическую Radix Sort, мне нужно, чтобы сформировать гистограмму размера 65536 элементов. Проблема, с которой я столкнулся, заключалась в том, что количество введенных элементов было очень большим. Для создания гистограммы потребуется некоторое время, поэтому я реализовал ее параллельно, используя процессы и общую память. Я разбил массив на подразделы размером/8. Затем по массиву разделяемой памяти размером 65536 * 8 каждый процесс создал свою собственную гистограмму. Впоследствии я суммировал все это вместе, чтобы сформировать одну гистограмму. Ниже приведен код, который:

for (i=0;i<8;i++) { 
    pid_t pid = fork(); 
    if (pid < 0) _exit(0); 
    if (pid == 0) { 
     const int start = (i * size) >> 3; 
     const int stop = i == 7 ? size : ((i + 1) * size) >> 3; 
     const int curr = i << 16; 
     for (j=start;j<stop;++j) 
      hist[curr + position(array[j], pass)]++; 
     _exit(0); 
    } 
} 
for (i=0;i<8;i++) wait(NULL); 

for (i=1;i<8;i++) { 
    const int pos = i << 16; 
    for (j=0;j<65536;j++) 
     hist[j] += hist[pos + j]; 
} 

Следующая часть была, где я провел большую часть своего времени, анализируя, как кэш влияет на производительность приставки-сумме. С помощью 8-битного и 11-битного прохода Radix Sort вся гистограмма будет входить в кеш L1. С 16-битами он будет входить только в кеш-память L2. В конце концов, 16-битная гистограмма выполняла самую быструю сумму, так как мне пришлось выполнять только 2 итерации. Я также запускал префиксную сумму параллельно в соответствии с рекомендациями веб-сайта CUDA. На 250 миллионов элементов это заняло примерно 1,5 секунды медленнее, чем 16-разрядное целое. Так что мой префикс сумма в конечном итоге глядя, как это:

for (i=1;i<65536;i++) 
    hist[i] += hist[i-1]; 

Единственное, что осталось было пройти в обратном направлении через массив и поместить все элементы в их соответствующие места в массиве темп. Так как мне нужно было пройти дважды, вместо того, чтобы копировать обратно из массива обратно в массив и снова запускать код. Сначала я запускал сортировку с использованием массива в качестве входного сигнала, а темп - как выход. Затем он запускал его во второй раз, используя temp в качестве входа и массива в качестве вывода. Это мешало мне возвращаться к массиву одновременно. Код выглядит следующим образом для фактического вида:

histogram(array, size, 0, hist); 
for (i=size-1;i>=0;i--) 
    temp[--hist[position(array[i], 0)]] = array[i]; 

memset(hist, 0, arrSize); 
histogram(temp, size, 1, hist); 
for (i=size-1;i>=0;i--) 
    array[--hist[position(temp[i], 1)]] = temp[i]; 

This link содержит полный код, который у меня есть до сих пор. Я проверил тест против quicksort, и он работал от 5 до 10 раз быстрее с целыми числами и плаваниями и примерно в 5 раз быстрее с 8-байтовыми типами данных. Есть ли способ улучшить это?

Answer 1

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

Также из вашего кода я не понимаю, как работают разные процессы. Как вы собираете гистограмму в родительском? у вас есть переменная процесса? В любом случае использование ptrhead было бы гораздо более уместным.