C - Сортировка массива указателей структур медленнее, чем сортировка структур напрямую (qsort)

Question

Я сортирую миллионы структур, организованных в массиве с qsort-функцией стандартной библиотеки c. Я попытался оптимизировать производительность, создав массив указателей структуры с одинаковой длиной. В отличии от моих ожиданий времени выполнения второго варианта медленнее:

QSort массива структур: 199s QSort массива указателей структур: 204

Я ожидал, что время для замены указателей блоков в память будет быстрее, чем перемещение структур (размер 576). Могу ли я иметь какие-либо утечки производительности или это известное поведение?

Answer 1

Здесь есть другие проблемы.

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

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

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

Answer 2

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

Если вы конвертируете в массив указателей, то доступ к данным, скорее всего, замедляется, так как структуры сохраняют свой «несортированный» порядок, в то время как их указатели сортируются. Но, сравнивая структуры, необходимо следовать указателям на их «несортированные» экземпляры, которые могут вызвать промахи кэша данных.

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

struct index_type { 
    key_type key; 
    data_type *data; 
}; 

И теперь, вы бы отсортировать массив index_type вместо массива указателей на data_type. Поскольку ключ хранится в самом массиве, вы избегаете проблемы следующих указателей на ваши «несортированные» структуры.

Answer 3

я сделал быструю проверку здравомыслие, используя эту структуру (который имеет размер 576, когда int является 32-битным)

struct test 
{ 
    int value; 
    char data[572]; 
}; 

Я инициализируется динамически выделенный массив 1 млн структур с этим кодом

for (int i = 0; i < count; i++) 
{ 
    array[i].value = rand(); 
    for (int j = 0; j < 572; j++) 
     array[i].data[j] = rand(); 
} 

И я отсортированный массив с этим кодом

int compare(const void *ptr1, const void *ptr2) 
{ 
    struct test *tptr1 = (struct test *)ptr1; 
    struct test *tptr2 = (struct test *)ptr2; 
    return tptr1->value - tptr2->value; 
} 

int main(void) 
{ 
    int count = 1000000; 
    ... 
    qsort(array, count, sizeof(struct test), compare); 
    ... 
} 

Время инициализации массива составляло 4,3 секунды, а время сортировки массива составляло 0,9 секунды.

Затем я модифицировал код для создания массива указателей на структуры и отсортировал массив указателей. Время инициализации было еще 4,3 секунды (большая часть времени инициализации вызвана вызовом rand() 500 миллионов раз). Сортировка массива указателей заняла 0,4 секунды. Сортировка массива указателей была более чем в два раза быстрее, чем сортировка массива структуры напрямую.

Итак, мой вывод состоит в том, что ваш код имеет некоторые массовые недостатки, которые не имеют никакого отношения к qsort.

Answer 4

Который быстрее будет зависеть, в общем, от размера структуры. Для структур, которые имеют такой же размер, как указатель, тогда должно быть очевидно, что сортировка структур будет быстрее, чем сортировка указателей на структуры. По мере увеличения размера структуры будет достигнута точка, где обратное истинно (представьте себе сортировку массива из 1 Мб структур: большую часть времени вы проводите в memcopy()). Там, где именно эта точка лежит, будет зависеть от вещей, находящихся вне контроля кода (структура кэша, размер кэша и т. Д.). Если это важно для вас, то лучше всего экспериментировать и измерять.