From: Qingqing Zhou <zhouqq@cs.toronto.edu>
To: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
Date: Thu, 16 Feb 2006 11:28:37 +0800
Message-ID: <dt0rn0$2km1$1@news.hub.org> (raw)
References: <43F38867.6010701@gpdnet.co.uk>
<19510.1140036968@sss.pgh.pa.us>
<19779.1140038874@sss.pgh.pa.us>
<43F39E53.1020009@gpdnet.co.uk>
<20781.1140046109@sss.pgh.pa.us>
"Tom Lane" <tgl@sss.pgh.pa.us> wrote
>
> I did this 100 times and sorted the reported runtimes.
>
> I'd say this puts a considerable damper on my enthusiasm for using our
> qsort all the time, as was recently debated in this thread:
> http://archives.postgresql.org/pgsql-hackers/2005-12/msg00610.php
>
> 100 runtimes for glibc qsort, sorted ascending:
>
> Time: 866.814 ms
> Time: 1234.848 ms
> Time: 1267.398 ms
>
> 100 runtimes for port/qsort.c, sorted ascending:
>
> Time: 28314.182 ms
> Time: 29400.278 ms
> Time: 34142.534 ms
>
By "did this 100 times" do you mean generate a sequence of at most
200000*100 numbers, and for every 200000 numbers, the first half are all
zeros and the other half are uniform random numbers? I tried to confirm it
by patching the program mentioned in the link, but seems BSDqsort is still a
little bit leading.
Regards,
Qingqing
---
Result
sort#./sort
[3] [glibc qsort]: nelem(20000000), range(4294901760) distr(halfhalf)
ccost(2) : 18887.285000 ms
[3] [BSD qsort]: nelem(20000000), range(4294901760) distr(halfhalf) ccost(2)
: 18801.018000 ms
[3] [qsortG]: nelem(20000000), range(4294901760) distr(halfhalf) ccost(2) :
22997.004000 ms
---
Patch to sort.c
sort#diff -c sort.c sort1.c
inline patch 1: sort1.c Wed Feb 15 22:21:15 2006 (+0/-3 lines) download inline-1.patch*** sort.c Thu Dec 15 12:18:59 2005
--- sort1.c Wed Feb 15 22:21:15 2006
***************
*** 35,43 ****
{"BSD qsort", qsortB},
{"qsortG", qsortG}
};
! static const size_t d_nelem[] = {1000, 10000, 100000, 1000000, 5000000};
! static const size_t d_range[] = {2, 32, 1024, 0xFFFF0000L};
! static const char *d_distr[] = {"uniform", "gaussian", "95sorted",
"95reversed"};
static const size_t d_ccost[] = {2};
/* factor index */
--- 35,43 ----
{"BSD qsort", qsortB},
{"qsortG", qsortG}
};
! static const size_t d_nelem[] = {5000000, 10000000, 20000000};
! static const size_t d_range[] = {0xFFFF0000L};
! static const char *d_distr[] = {"halfhalf"};
static const size_t d_ccost[] = {2};
/* factor index */
***************
*** 180,185 ****
--- 180,192 ----
swap(karray[i], karray[nelem-i-1]);
}
}
+ else if (!strcmp(distr, "halfhalf"))
+ {
+ int j;
+ for (i = 0; i < nelem/200000; i++)
+ for (j = 0; j < 100000; j++)
+ karray[i*200000 + j] = 0;
+ }
return array;
}
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: zhouqq@cs.toronto.edu, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
In-Reply-To: <dt0rn0$2km1$1@news.hub.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox