переполнение многопоточного стека быстрой сортировки

Question

Я, наконец, закончил доморощенную версию быстрой сортировки, чтобы отсортировать массив структур по элементу char.Причина, по которой я не использую stdlib qsort, заключается в том, что на супербыстрой машине это занимает более 5 минут.

У меня 12 физических и 24 логических ядра (двойной xeon 5690) и 192 ГБ (да, ГБ, а не МБ) оперативной памяти, поэтому я подумал, что смогу использовать это, написав многопоточную версию быстрой сортировки.Но я получаю исключение переполнения стека, предположительно из-за структуры s_stream, которая создается в стеке с каждой рекурсией.У меня есть более 2 400 000 строк для сортировки, поэтому я могу только представить, насколько глубокой должна быть рекурсия (если глубокий - правильный термин).

Я не могу реально уменьшить структуру.Должен ли я просто отказаться от этого и искать другой алгоритм сортировки?Если да, то какой?

struct s_stream {

    char name[100];
    int avg;
    int current;
    int currentY;
    int marrayIndex;

    int xy[2500];
    int zz[2500];

}

    void quickSort(struct s_stream items[], int left, int right)
    {
      int i, j;
      struct s_stream temp;

      i = left;
      j = right;
      temp = items[(left+right)/2];

      do {
            while((strcmp(items[i].name, temp.name) < 0) && (i < right)) { i++; }
            while((strcmp(items[j].name, temp.name) > 0) && (j > left)) {  j--; }
        if(i <= j)
        {
            temp = items[i];
            items[i] = items[j];
            items[j] = temp;

            i++;
            j--;
        }
  } while(i <= j);


    #pragma omp parallel sections
    {
        #pragma omp section
        if(left < j) { quickSort(items, left, j);}

        #pragma omp section
        if(i < right) { quickSort(items, i, right); }
     }
}

Answer 1

Такой массовый параллелизм не очень полезен. Дополнительные затраты на планирование начинают перевешивать преимущества большего количества потоков. Немного выигрыша видно при увеличении количества потоков после числа физических ядер.

Как упомянул Базиль, вы можете вместо этого использовать qsort в stdlib для каждого 12-го массива параллельно, а затем объединить куски вместе.

То, что может убить вашу производительность, это размер ваших структур. 20 Кбайт достаточно велики, чтобы вы разрушали эталон, и на современных процессорах, где важен кеш, это смертельно для производительности. Изменение динамически распределенных xy и zz может привести к значительному увеличению производительности, равно как и сортировка массива указателей.

Answer 2

не используйте рекурсию, найдите достойную итеративную версию вашего алгоритма. Вы всегда можете преобразовать рекурсивный алгоритм в итеративный. Не пытайтесь заранее оптимизировать ваш код («это корень зла», как говорит Кнут :-)). Сначала давайте попробуем ванильную быструю сортировку.

Более важно: сортировать указатели на данные, а не на фактические данные !!!!

Answer 3

Кажется, у вас заканчивается стек.Одним из способов решения вашей проблемы может быть увеличение стека, я думаю, вам следует проверить руководство по компиляции о том, как это сделать.

Другой способ - реализовать это без рекурсии, вот пример реализации http://www.codeproject.com/KB/recipes/QuickSortWithoutRecursion.aspx

Answer 4

Одна из возможностей уменьшить потребление стека - изменить структуру s_stream на:

struct s_stream {
    char name[100];
    int avg;
    int current;
    int currentY;
    int marrayIndex;

    // Instead of int xy[2500]
    int *xy;  // Allocated via malloc()
    int *zz;  // Allocated via malloc()
}

Другой вариант - заменить строку

struct s_stream temp;

на

struct s_stream *temp = malloc(sizeof(s_stream));

и выполнение free(temp); при выходе из функции quickSort.

Потребление стека в реализации быстрой сортировки зависит от выбора оси.Таким образом, другой способ сделать стек менее глубоким - использовать лучший алгоритм для выбора сводной области.

После того, как функция быстрой сортировки выполнена с циклом do { ... } while(i <= j);, может быть возможно обновить i иj, пока items[i].name равно items[j].name.Это может быть полезно в случае, если значение (j-left) слишком сильно отличается от значения (right-i).

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

Answer 5

Алгоритмы сортировки: O (n log n) в своих лучших проявлениях (и не может быть лучше!).

Вы можете сортировать указатели на элементы, а не насами предметы.Это, вероятно, должно решить проблему переполнения стека и, возможно, работать быстрее (не огромное количество данных на элемент).

Существует много книг по сортировке.Прочитайте знаменитые книги по алгоритму Кнута и прочитайте другую хорошую книгу по агорифме.Существуют также параллельные алгоритмы сортировки (я их не очень хорошо знаю, но есть много литературы).Сортировка, вероятно, все еще является предметом исследования, и они являются конференциями и докторами наук.

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