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