File: tmask_diary.txt

package info (click to toggle)
suitesparse-graphblas 7.4.0%2Bdfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm
  • size: 67,112 kB
  • sloc: ansic: 1,072,243; cpp: 8,081; sh: 512; makefile: 503; asm: 369; python: 125; awk: 10
file content (87 lines) | stat: -rw-r--r-- 3,132 bytes parent folder | download | duplicates (4)
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
Results on a Dell XPS13 laptop, MATLAB R2020a, GraphBLAS v5.0.6,
16GB RAM, Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz.  GraphBLAS using
4 threads.


n: 2048 nnz(C): 20432 nnz(M) 2048
create C: 0.012005 sec
C(M)=A in GrB    : 0.005219 sec
C(M)=A in builtin: 0.024435 sec  GrB speedup: 4.68193

n: 4096 nnz(C): 40908 nnz(M) 4096
create C: 0.034915 sec
C(M)=A in GrB    : 0.002945 sec
C(M)=A in builtin: 0.114939 sec  GrB speedup: 39.0285

n: 8192 nnz(C): 81876 nnz(M) 8191
create C: 0.029753 sec
C(M)=A in GrB    : 0.008706 sec
C(M)=A in builtin: 0.59389 sec  GrB speedup: 68.2162

n: 16384 nnz(C): 163789 nnz(M) 16384
create C: 0.071706 sec
C(M)=A in GrB    : 0.009273 sec
C(M)=A in builtin: 2.52994 sec  GrB speedup: 272.828

n: 32768 nnz(C): 327633 nnz(M) 32767
create C: 0.147284 sec
C(M)=A in GrB    : 0.014384 sec
C(M)=A in builtin: 12.4234 sec  GrB speedup: 863.699

n: 65536 nnz(C): 655309 nnz(M) 65536
create C: 0.32691 sec
C(M)=A in GrB    : 0.025189 sec
C(M)=A in builtin: 65.9221 sec  GrB speedup: 2617.1

n: 131072 nnz(C): 1310677 nnz(M) 131070
create C: 0.806615 sec
C(M)=A in GrB    : 0.055393 sec
C(M)=A in builtin: 276.215 sec  GrB speedup: 4986.46

n: 262144 nnz(C): 2621396 nnz(M) 262142
create C: 1.69602 sec
C(M)=A in GrB    : 0.071006 sec
C(M)=A in builtin: 1077.34 sec  GrB speedup: 15172.5

n: 524288 nnz(C): 5242830 nnz(M) 524288
create C: 2.901 sec
C(M)=A in GrB    : 0.114191 sec
C(M)=A in builtin: 5855.03 sec  GrB speedup: 51274

n: 1048576 nnz(C): 10485713 nnz(M) 1048576
create C: 6.02499 sec
C(M)=A in GrB    : 0.197391 sec
C(M)=A in builtin: 27195.8 sec  GrB speedup: 137776

n: 2097152 nnz(C): 20971475 nnz(M) 2097152
create C: 13.0739 sec
C(M)=A in GrB    : 0.406119 sec
C(M)=A in builtin: 100799 sec  GrB speedup: 248200

n: 4194304 nnz(C): 41942995 nnz(M) 4194304
create C: 27.2005 sec
C(M)=A in GrB    : 0.855162 sec

based on the timings above, it appears that MATLAB R2020a is using an
method that takes O(nnz(C)^2) time, since the time increases by about
a factor of 4 each time nnz(C) doubles in size.  By contrast, GraphBLAS
takes about O(nnz(C)) time (perhaps with a lower order log(d) term
as well, if d is the max # of entries in any given column of C; the details
depend on which of my 40+ algorithms get selected, via a heuristic,
by the assign meta-algorithm).

The last problem that MATLAB finished took about 28 hours, while GraphBLAS
took 0.41 seconds, for a speedup of about quarter million.  I estimate the
time MATLAB would take for the unfinished problem would be about 4.5 days,
compared with 0.86 seconds in GraphBLAS, which would be a speedup of roughly
450,000x to 500,000x.  However, it's also possible that the laptop would
run out of memory, on this problem or the next.

Extrapolating, on a system with larger memory, it would be quite easy to
create a problem for which MATLAB would finish the problem but would be
millions of times slower than GraphBLAS.  The only limitation is how long
one would be willing to wait for MATLAB.

To put this speedup into perspective, the speed of light is 10 million times
faster than a car driving on the interstate at 67 miles/hour.