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



sysoev.ru
mod_accel
mod_deflate
программирование
windows
freebsd
apache
pppd
unix
web

для писем

Неправильный qsort() в Solaris

 

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);
}
На всех платформах (AIX, Linux, HP-UX), кроме Solaris, эти программы выполняются за практически одинаковое и малое время. На Solaris времена исполнения отличаются в 22 раза.

Я решил это проверить. В таблице ниже приведены результаты запуска двух программ под разными операционными системами. Не обращайте особого внимания на абсолютные значения, так как тестировалось всё это на разных машинах, под разной нагрузкой и в разных условиях. Windows NT, например, была запущена под VMware. Смотреть нужно третью колонку, показывающую разницу во времени исполнения.
Операционная система хорошая плохая разница
FreeBSD 4.3 1.6 1.2 0.8
Беспородный Linux 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 с сортировкой.

(C) Igor Sysoev
http://sysoev.ru