quicksort and mergesort in glibc

[Andreas Jaeger <aj at suse dot de>]

Jeremy reported a few weeks ago (see PR libc/1611):
>  glibc's qsort() always uses merge sort instead of quicksort if it can 
>  malloc() as much memory as the input array size for temporary storage.
>  However, malloc() will happily reserve the requested temporary storage 
>  even if it is backed only by swap space.  As a result, qsort() runs
>  unexpectedly slowly (an order of magnitude slower than predicted!) if
>  the array size is a large fraction of the machine's physical memory.

Ulrich has added already a fix to stdlib/msort to limit the memory
usage to only a quarter of the machine.

I've used his testcase, fixed it and added it to my sort test routines
(available from ftp.suse.com/pub/people/aj/sort-test.tar.gz).  The
sort test routines use a number of different input sequences (see the
source for details).

The test results show that the typical behaviour of mergesort and
quicksort.  For small sets and smaller data types (arrays of ints and
arrays of doubles) mergesort is definitly faster and behaves better.

With 10000 elements quicksort is faster with the 6 byte struct (size
variant 2).  With 2 million elements, quicksort is also faster (on
average!) for doubles - but mergesort is still better for ints.

We could need an optimal break even point for switching from mergesort
(for smaller numbers) to quicksort.  But this depends on machine
charakteristica like memory size, caches, cpu etc.  Currently we're
sorting all arrays with a size of < 1/4 machine memory with mergesort
(mergesort needs an temporary array as large as the input data), and
use quicksort for larger ones.

Is anybody interested in investigating this?  I don't have enough CPU
cycles to burn the next few weeks and therefore ask for volunteers.

If nobody has any more data, I would suggest to use 1/16 instead of
1/4 - but this is still a rule of thumb.

Andreas


P.S. Here're the test results on an Pentium III/500 Mhz with 256 MB
RAM running glibc 2.1.3 and Linux 2.3.99pre3.  I used the core
routines from glibc.  Sort routine 0 is qsort, routine 1 is msort;
Size variant 0 is an int, variant 1 a double and 2 a record with three
ints (only one is used for comparisions).

Testing with 100 elements
Size of arrays: 0 k for int 0 k for double, 1 k for record
No of tests: 200
Size variant: 0
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0001
min. cmp.: 528
max. cmp.: 1153
avt. cmp.: 710
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0002
min. cmp.: 316
max. cmp.: 316
avt. cmp.: 316
No of tests: 200
Size variant: 1
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0001
min. cmp.: 528
max. cmp.: 1153
avt. cmp.: 710
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0002
min. cmp.: 316
max. cmp.: 316
avt. cmp.: 316
No of tests: 200
Size variant: 2
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0002
min. cmp.: 528
max. cmp.: 1153
avt. cmp.: 710
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0001
min. cmp.: 316
max. cmp.: 316
avt. cmp.: 316

Testing with 1023 elements
Size of arrays: 3 k for int 7 k for double, 11 k for record
No of tests: 275
Size variant: 0
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0012
min. cmp.: 9146
max. cmp.: 23941
avt. cmp.: 12099
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0014
min. cmp.: 5110
max. cmp.: 5110
avt. cmp.: 5110
No of tests: 275
Size variant: 1
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0025
min. cmp.: 9146
max. cmp.: 23941
avt. cmp.: 12099
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0035
min. cmp.: 5110
max. cmp.: 5110
avt. cmp.: 5110
No of tests: 275
Size variant: 2
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0023
min. cmp.: 9146
max. cmp.: 23941
avt. cmp.: 12099
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0033
min. cmp.: 5110
max. cmp.: 5110
avt. cmp.: 5110

Testing with 5000 elements
Size of arrays: 19 k for int 39 k for double, 58 k for record
No of tests: 350
Size variant: 0
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0094
min. cmp.: 55012
max. cmp.: 168263
avt. cmp.: 73612
Sort routine 1
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0068
min. cmp.: 29804
max. cmp.: 29804
avt. cmp.: 29804
No of tests: 350
Size variant: 1
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0147
min. cmp.: 55012
max. cmp.: 168263
avt. cmp.: 73612
Sort routine 1
min. time: 0.0000
max. time: 0.0400
avg. time: 0.0212
min. cmp.: 29804
max. cmp.: 29804
avt. cmp.: 29804
No of tests: 350
Size variant: 2
Sort routine 0
min. time: 0.0000
max. time: 0.0200
avg. time: 0.0122
min. cmp.: 55012
max. cmp.: 168263
avt. cmp.: 73612
Sort routine 1
min. time: 0.0000
max. time: 0.0400
avg. time: 0.0202
min. cmp.: 29804
max. cmp.: 29804
avt. cmp.: 29804

Testing with 10000 elements
Size of arrays: 39 k for int 78 k for double, 117 k for record
No of tests: 375
Size variant: 0
Sort routine 0
min. time: 0.0000
max. time: 0.0400
avg. time: 0.0206
min. cmp.: 120013
max. cmp.: 379273
avt. cmp.: 161980
Sort routine 1
min. time: 0.0000
max. time: 0.0400
avg. time: 0.0133
min. cmp.: 64608
max. cmp.: 64608
avt. cmp.: 64608
No of tests: 375
Size variant: 1
Sort routine 0
min. time: 0.0000
max. time: 0.0600
avg. time: 0.0322
min. cmp.: 120013
max. cmp.: 379273
avt. cmp.: 161980
Sort routine 1
min. time: 0.0200
max. time: 0.0600
avg. time: 0.0448
min. cmp.: 64608
max. cmp.: 64608
avt. cmp.: 64608
No of tests: 375
Size variant: 2
Sort routine 0
min. time: 0.0000
max. time: 0.0600
avg. time: 0.0282
min. cmp.: 120013
max. cmp.: 379273
avt. cmp.: 161980
Sort routine 1
min. time: 0.0200
max. time: 0.0600
avg. time: 0.0434
min. cmp.: 64608
max. cmp.: 64608
avt. cmp.: 64608

Testing with 100000 elements
Size of arrays: 390 k for int 781 k for double, 1171 k for record
No of tests: 450
Size variant: 0
Sort routine 0
min. time: 0.1200
max. time: 0.5800
avg. time: 0.2661
min. cmp.: 1507806
max. cmp.: 5736360
avt. cmp.: 2114881
Sort routine 1
min. time: 0.1200
max. time: 0.2000
avg. time: 0.1529
min. cmp.: 815024
max. cmp.: 815024
avt. cmp.: 815024
No of tests: 450
Size variant: 1
Sort routine 0
min. time: 0.1800
max. time: 0.8600
avg. time: 0.4304
min. cmp.: 1507806
max. cmp.: 5736360
avt. cmp.: 2114881
Sort routine 1
min. time: 0.5000
max. time: 0.6200
avg. time: 0.5712
min. cmp.: 815024
max. cmp.: 815024
avt. cmp.: 815024
No of tests: 450
Size variant: 2
Sort routine 0
min. time: 0.1400
max. time: 0.9000
avg. time: 0.4195
min. cmp.: 1507806
max. cmp.: 5736360
avt. cmp.: 2114881
Sort routine 1
min. time: 0.5000
max. time: 0.6400
avg. time: 0.5661
min. cmp.: 815024
max. cmp.: 815024
avt. cmp.: 815024

Testing with 2000000 elements
Size of arrays: 7812 k for int 15625 k for double, 23437 k for record
No of tests: 550
Size variant: 0
Sort routine 0
min. time: 3.8800
max. time: 18.3200
avg. time: 7.2862
min. cmp.: 39586860
max. cmp.: 177197115
avt. cmp.: 56573208
Sort routine 1
min. time: 3.7400
max. time: 4.3800
avg. time: 3.9830
min. cmp.: 20769984
max. cmp.: 20769984
avt. cmp.: 20769984
No of tests: 550
Size variant: 1
Sort routine 0
min. time: 5.4000
max. time: 27.2600
avg. time: 11.7817
min. cmp.: 39586860
max. cmp.: 177197115
avt. cmp.: 56573208
Sort routine 1
min. time: 14.0000
max. time: 15.0800
avg. time: 14.6400
min. cmp.: 20769984
max. cmp.: 20769984
avt. cmp.: 20769984
No of tests: 550
Size variant: 2
Sort routine 0
min. time: 5.5600
max. time: 30.6800
avg. time: 11.9991
min. cmp.: 39586860
max. cmp.: 177197115
avt. cmp.: 56573208
Sort routine 1
min. time: 14.3600
max. time: 15.5000
avg. time: 14.7696
min. cmp.: 20769984
max. cmp.: 20769984
avt. cmp.: 20769984

-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.rhein-neckar.de