R devel - Apr 2001 - Benchmarking R, why sort() is so slow?

Hello everybody,

I am making a modified version of "Stephan Steinhaus' benchmark test
for
number crunching, v. 2, (see
http://www.scinetificweb.com/ncrunch/ncrunch.pdf for the original version),
comparing several functions of some math/stat software. R is not performing
bad at all... except for the sorting of a 1,100,000 random vector (test #3)
which is the worst of all (see cell F3 in the following table). I simply
used the sort() function. Does anybody has an explanation for that?

Here is a temporary version of the results (sorry for the bad
presentation... a better one and code for all tests will be available soon):

Computer = Intel Celeron 500 Mhz with 256 Mb Ram under Windows 2000 sp1 (all
tests run 3 times)

Tested software: A = O-Matrix 5.1 (native mode), B = O-Matrix 5.1 (Matlab
mode), C = Matlab 6.0 R12, D = Ox 2.20, E = Mathematica 4.01, F = R 1.2.2, G
= Octave 2.1.31, H = Splus 2000 pro R3, I = Matlab 5.3 R11, J = Rlab 2.1, K
= Scilab 2.6, L = Axum 6.0 R2 (Splus mode)

Tests: 3 series (I. matrix calculation / II. preprogrammed matrix functions
/ III. programmation) of 5 tests each. A trimmed mean is considered for each
serie (best and worst scores eliminated). The tests are scaled to be done in
approx. 1 sec on the reference computer with the reference software being
Matlab 6.0 R12 (column C).

Serie I: Matrix calculation
1 = Creation, transposition, deformation of a 1200x1200 matrix, 2 1250x1250
normal distributed random matrix ^1000, 3 = Sorting of 1,100,000
random values, 4 = 550x550 cross-product matrix (b = a'  * a), 5 = Linear
regression over a 700x700 matrix (b = a \ b')

Serie II: Preprogrammed matrix functions
6 = FFT over 900,000 random values, 7 = Eigenvalues of a 220x220 random
matrix, 8 = Determinant of a 750x750 random matrix, 9 = Cholesky
decomposition of a 1000x1000 matrix, 10 = Inverse of a 500x500 random matrix

Serie II: programmation
11 = 225.000 Fibonacci numbers calculation (vector calc.), 12 = Creation of
a 1500x1500 Hilbert matrix (matrix calc.), 13 = Grand common divisors of
35,000 pairs (recursion), 14 = Creation of a 220x220 Toeplitz matrix
(loops), 15 = Escoufier's method on a 22x22 matrix (mixed)

Times are in sec.



Software   A     B     C     D     E     F(R)  G     H     I     J     K
L

Serie I.
--------
1         1.03  1.35  0.95  1.23  2.19  2.79  4.24  2.91  1.00  1.92  2.95
2.67
2         2.60  2.48  0.99  2.91  0.76  2.88  2.76  1.41  2.61  2.38  2.32
1.42
3         1.09  1.10  1.04  3.37  3.13 21.71  6.33  1.84  7.91  4.00  2.72
1.65
4         0.85  0.86  0.98  1.84  4.04  3.88  7.71  1.74  4.57  8.92 14.84
1.61
5         0.72  0.96  1.07  5.47  2.89  5.75  4.32 10.84  6.91  6.31  7.67
9.70
----------------------------------------------------------------------------
----
tr. mean  0.99  1.14  1.01  2.70  2.74  4.17  4.96  2.16  4.70  4.23  4.45
1.98

Serie II.
---------
6         2.21  2.16  0.99  3.83  1.94  2.67  2.70  4.81  4.04  2.23  4.06
4.17
7         0.42  0.42  0.90  1.11  0.95  1.49  2.46  1.68  1.41  3.09  2.94
2.19
8         0.88  0.92  1.06  3.31  5.90  5.98  5.19  2.04  7.96  7.50  9.14
117.0
9         0.96  0.96  1.29  3.74  4.30  3.65  6.54 11.38  4.59  6.64  7.81
8.98
10        0.75  0.76  1.10  2.94  5.24  5.83  3.92  2.48  6.18  7.65  7.61
11.04
----------------------------------------------------------------------------
----
tr.mean   0.75  0.88  1.05  3.33  3.83  4.05  3.94  3.48  4.93  5.74  6.49
8.06

Serie III.
----------
11        0.52  0.39  1.04  0.52  0.41  0.55  1.02  0.96  0.97  0.49  0.60
0.72
12        1.79  2.09  0.98  1.03  3.14  1.30  0.79  2.02  2.03  1.21  1.92
1.86
13        0.38  0.43  1.03  0.76   ?    1.33  0.87  0.71  0.92  6.03  1.23
0.93
14        0.20  0.26  0.92  0.13  1.50  2.56  6.89 14.49  0.78  0.63  4.52
13.46
15        0.22  0.24  1.00  0.13   ?    0.48  1.66 12.12  1.06  0.73  1.32
10.88
----------------------------------------------------------------------------
----
tr. mean  0.79  0.36  1.00  0.47  1.68  1.06  1.19  5.03  0.99  0.86  1.49
4.56
----------------------------------------------------------------------------
----
total    14.62 15.39 15.34 32.33 36.38 62.84 57.40 71.43 52.95 59.73 71.65
188.3
----------------------------------------------------------------------------
----
ovr. mean 0.84  0.79  1.02  2.17  2.75  3.09  3.36  3.44  3.54  3.61  4.14
4.87



Best Regards,

Philippe Grosjean


...........]<(({?<...............<?}))><...............................
 ) ) ) ) )	 __               	 __
( ( ( ( ( 	|__)              	|  _
 ) ) ) ) )	|   hilippe       	|__)rosjean
( ( ( ( ( 	Marine Biol. Lab., ULB, Belgium
 ) ) ) ) )	                  	 __
( ( ( ( ( 	|\  /|            	|__)
 ) ) ) ) )	| \/ |ariculture &	|__)iostatistics
( ( ( ( (
 ) ) ) ) )	e-mail: phgrosje at ulb.ac.be or phgrosjean at sciviews.org
( ( ( ( ( 	SciViews project coordinator (http://www.sciviews.org)
 ) ) ) ) )      tel: 00-32-2-650.29.70 (lab), 00-32-2-673.31.33 (home)
( ( ( ( (
 ) ) ) ) )      "I'm 100% confident that p is between 0 and 1"
( ( ( ( (                                  L. Gonick & W. Smith (1993)
 ) ) ) ) )
.......................................................................

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at
stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

> Hello everybody,
> 
> I am making a modified version of "Stephan Steinhaus' benchmark
test for
> number crunching, v. 2, (see
> http://www.scinetificweb.com/ncrunch/ncrunch.pdf for the original version),
> comparing several functions of some math/stat software. R is not performing
> bad at all... except for the sorting of a 1,100,000 random vector (test #3)
> which is the worst of all (see cell F3 in the following table). I simply
> used the sort() function. Does anybody has an explanation for that?
it seems to depend:

R> x <- rnorm(1100000)
R> Rprof("sort.out")
R> b <- sort(x)

needs

hothorn at artemis:~ > R CMD Rprof sort.out 

Each sample represents 0.02 seconds.
Total run time: 24.9399999999996 seconds.

but

R> x <- sample(1:100, 1100000, T)
R> Rprof("sort3.out")
R> b <- sort(x)

needs

hothorn at artemis:~ > R CMD Rprof sort3.out  

Each sample represents 0.02 seconds.
Total run time: 4.2 seconds.

on a Intel PIII 450 MHz, 256 MB, SuSE Linux 6.3, R-1.2.3

Torsten

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at
stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

"Philippe Grosjean" <phgrosje at ulb.ac.be> writes:
> Hello everybody,
> 
> I am making a modified version of "Stephan Steinhaus' benchmark
test for
> number crunching, v. 2, (see
> http://www.scinetificweb.com/ncrunch/ncrunch.pdf for the original version),
> comparing several functions of some math/stat software. R is not performing
> bad at all... except for the sorting of a 1,100,000 random vector (test #3)
> which is the worst of all (see cell F3 in the following table). I simply
> used the sort() function. Does anybody has an explanation for that?
The internal algorithm is a shellsort, which is supposedly of
complexity O(n^1.25) and has decent worst-case behaviour. Other
algorithms like quicksort have typical performance of O(n log n) but
extreme cases of O(n^2).

For large vectors the O(n^.25/log(n)) relative complexity is going to
make a difference, although the observed differences seem larger.

There are very likely better choices of sort algorithm...

-- 
   O__  ---- Peter Dalgaard             Blegdamsvej 3  
  c/ /'_ --- Dept. of Biostatistics     2200 Cph. N   
 (*) \(*) -- University of Copenhagen   Denmark      Ph: (+45) 35327918
~~~~~~~~~~ - (p.dalgaard at biostat.ku.dk)             FAX: (+45) 35327907
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at
stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._