1function test44(longtests)
2%TEST44 test qsort
3
4% SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
5% SPDX-License-Identifier: Apache-2.0
6
7fprintf ('\ntest44\n------------------------------------- qsort tests\n') ;
8
9if (nargin < 1)
10    longtests = 0 ;
11end
12
13nlist = [0 1 5 100 50e3 103e3 200e3 1e6 ] ;
14if (longtests)
15    nlist = [nlist 10e6 100e6] ;
16else
17end
18
19[save_nthreads save_chunk] = nthreads_get ;
20nthreads_max = feature ('numcores') ;
21
22rng ('default') ;
23
24for n = nlist
25
26fprintf ('\n========================== n %g million\n', n / 1e6) ;
27
28fprintf ('\n----------------------- qsort 1b\n') ;
29
30% qsort1b is not stable; it used only when I has unique values
31I = int64 (randperm (n))' ;
32J = int64 ((n/10)* rand (n,1)) ;
33IJ = [I J] ;
34
35tic
36IJout = sortrows (IJ, 1) ;
37t = toc ;
38
39tic
40[Iout, Jout] = GB_mex_qsort_1b (I, J) ;
41t2 = toc ;
42
43fprintf ('MATLAB: sortrows %g sec  qsort1b: %g  speedup: %g\n', t, t2, t/t2) ;
44
45assert (isequal ([Iout Jout], IJout))
46
47fprintf ('\n----------------------- qsort 2\n') ;
48
49I = int64 ((n/10)* rand (n,1)) ;
50J = int64 (randperm (n))' ;
51IJ = [I J] ;
52
53tic
54IJout = sortrows (IJ) ;
55t = toc ;
56
57tic
58[Iout, Jout] = GB_mex_qsort_2 (I, J) ;
59t2 = toc ;
60t2_just = grbresults ;
61assert (isequal ([Iout Jout], IJout));
62
63fprintf ('MATLAB: sortrows %g sec  qsort2: %g %g speedup: %g\n', ...
64    t, t2, t2_just, t/t2) ;
65
66for nthreads = [1 2 4 8 16 20 32 40 64 128 256]
67    if (nthreads > 2*nthreads_max)
68        break ;
69    end
70    % tic
71    [Iout, Jout] = GB_mex_msort_2 (I, J, nthreads) ;
72    tp = grbresults ; % toc ;
73    if (nthreads == 1)
74        tp1 = tp ;
75    end
76    assert (isequal ([Iout Jout], IJout));
77    fprintf ('msort2: %3d: %10.4g ', nthreads, tp) ;
78    fprintf ('speedup vs 1: %8.3f ', tp1 / tp) ;
79    fprintf ('speedup vs MATLAB: %8.3f\n', t / tp) ;
80end
81
82fprintf ('\n----------------------- qsort 3\n') ;
83
84I = int64 ((n/10)* rand (n,1)) ;
85J = int64 ((n/10)* rand (n,1)) ;
86K = int64 (randperm (n))' ;
87IJK = [I J K] ;
88
89tic
90IJKout = sortrows (IJK) ;
91t = toc ;
92
93tic
94[Iout, Jout, Kout] = GB_mex_qsort_3 (I, J, K) ;
95t2_just = grbresults ;
96t2 = toc ;
97assert (isequal ([Iout Jout Kout], IJKout))
98
99fprintf ('MATLAB: sortrows %g sec  qsort3: %g  speedup: %g\n', t, t2, t/t2) ;
100
101for nthreads = [1 2 4 8 16 20 32 40 64 128 256]
102    if (nthreads > 2*nthreads_max)
103        break ;
104    end
105    % tic
106    [Iout, Jout, Kout] = GB_mex_msort_3 (I, J, K, nthreads) ;
107    tp = grbresults ; % toc ;
108    if (nthreads == 1)
109        tp1 = tp ;
110    end
111    assert (isequal ([Iout Jout Kout], IJKout));
112    fprintf ('msort3: %3d: %10.4g ', nthreads, tp) ;
113    fprintf ('speedup vs 1: %8.3f ', tp1 / tp) ;
114    fprintf ('speedup vs MATLAB: %8.3f\n', t / tp) ;
115end
116
117end
118
119fprintf ('\ntest44: all tests passed\n') ;
120nthreads_set (save_nthreads, save_chunk) ;
121
122