Персональный
сайт
Игоря
Сысоева

19.04.2002

Оказывается, qsort() в Solaris работает очень медленно, если в сортируемом массиве много одинаковых подряд идущих значений. На сановском форуме приводятся тексты двух программ - "хорошей":

#define MAXLEN 1500000
#include <stdio.h>

int sortfunc(void* n1, void* n2)
{
    return((*(int*)n1) - (*(int*)n2));
}

main(int argc, char** argv)
{
    int array[MAXLEN];
    int i, count = 1471979;
    for (i = 0; i < 1471979; i++)
        array[i] = rand();
    qsort(array, count, sizeof(int), sortfunc);
}

#define MAXLEN 1500000
#include <stdio.h>

int sortfunc(void* n1, void* n2)
{
    return((*(int*)n1) - (*(int*)n2));
}

main(int argc, char** argv)
{
    int array[MAXLEN];
    int i, count = 1471979;
    for (i = 0; i < 1000000; i++)
        array[i] = rand();
    for (i = 1000000; i < count; i++)
        array[i] = 0;
    qsort(array, count, sizeof(int), sortfunc);
}

Я решил это проверить. В таблице ниже приведены результаты запуска двух программ под разными операционными системами. Не обращайте особого внимания на абсолютные значения, так как тестировалось всё это на разных машинах, под разной нагрузкой и в разных условиях. Windows NT, например, была запущена под VMware. Смотреть нужно третью колонку, показывающую разницу во времени исполнения.

Операционная система	хорошая	плохая	разница
FreeBSD 4.3	1.6	1.2	0.8
Linux RedHat 6.2	3.5	3.0	0.9
Windows NT 4.0 SP5	2	12	6.0
Solaris 7, x86	3.0	65.0	22.0
Solaris 8, x86	2.6	62.0	24.0

В обоих случаях на Solaris "плохая" программа выполняется существенно дольше. На Windows NT, кстати, с qsort() тоже не всё хорошо.

Для того, что бы эти программы не вызывали переполнение стека на Windows, нужно или сделать массив глобальным, или увеличить размер стека при сборке параметром /stack:7000000.

Вы спросите, а имеет ли это какое-либо практическое значение. Оказывается, да. Из-за этого под Solaris'ом очень медленно работают запросы PostgreSQL с сортировкой.

Обновление, 08.05.2004

В Solaris 9 (а возможно, и в одном из апдэйтов Solaris 8), эта ошибка была исправлена — разница в исполнении двух программ равна 0.9, то есть, такая же, как во FreeBSD и Linux.

(C) Игорь Сысоев
http://sysoev.ru