Memory Efficiency Benchmarking

Setup

• Instance: c4.xlarge
• AMI: ami-153b1b70 (Amazon Linux AMI)
• Command used: valgrind --tool=massif --max-snapshots=10 --depth=1 python /myEFSvolume/sparse_jun/benchmark/python/sparse/independent_dot.py --num-omp-threads 4 --batch-size 128 --feature-dim 1000000 --output-dim 256 --arraytype sparse --density 0.0001

Summary

• Memory consumed for CSR NDArray is 50 times lesser compared to dense NDArray when the density is 0.01% and the memory consumed for CSR NDArray is slightly more compared to dense NDArray when the density is 10.24%.

• Memory consumed for RSP NDArray is 55 times lesser compared to dense NDArray when the density is 0.01% and the memory consumed is very close to dense NDArray when density is 81.92%. (Note that the meaning of density for CSR is different from density of RSP. Please see below for explanation).

• For dot operators we see significant memory savings for sparse data. For a density of 0.01% which is close to the density for real world datasets like kdda, avazu and criteo, we see that dot(csr, rsp) memory consumption is 65 times lesser compared to dot(dense, dense), and 30 times lesser compared to dot(csr, dense).

CSR vs Dense Storage Comparison

Dimensions: 128 * 1M

• Allocated a uniformly distributed ndarray for sparse and dense of shape (128, 1M) and compared peak memory consumption

Density(%)	Peak Memory Consumption (Sparse)	Peak Memory Consumption (Dense)	Ratio of Memory Consumption
0.01	29	1456	50.20689655
0.02	32	1456	45.5
0.04	34	1456	42.82352941
0.08	40	1456	36.4
0.16	53	1456	27.47169811
0.32	78	1456	18.66666667
0.64	130	1456	11.2
1.28	232	1456	6.275862069
2.56	437	1456	3.33180778
5.12	846	1456	1.721040189
10.24	1626	1456	0.895448954

RSP vs Dense Storage Comparison

• Allocated a uniformly distributed ndarray for rsp and dense of shape (1M, 256) and compared peak memory consumption
• NOTE: for rsp density doesn't mean number of nnzs / total elements in the matrix. the density is approximately equal to the ratio of non zero rows to the total number of rows (This is because rand_ndarray tries to generate a single dimension array with shape (shape[0]) with random values between 0 and 1 and selects only those indexes from array with values less than density. This array is used as the indices array and the rest are set to zeros. Thus the density is in most cases equal to the number of non zero rows/total rows)

Density(%)	Peak Memory Consumption (Sparse)	Peak Memory Consumption (Dense)	Ratio of Memory Consumption
0.01	52	2903	55.82692308
0.02	52	2903	55.82692308
0.04	52	2903	55.82692308
0.08	54	2903	53.75925926
0.16	56	2903	51.83928571
0.32	61	2903	47.59016393
0.64	70	2903	41.47142857
1.28	88	2903	32.98863636
2.56	126	2903	23.03968254
5.12	202	2903	14.37128713
10.24	351	2903	8.270655271
20.48	654	2903	4.43883792
40.96	1222	2903	2.375613748
81.92	2399	2903	1.210087536

dot(csr, rsp) vs dot(csr, dense) Peak Memory consumption Comparison

• rhs_density is the same as lhs_density
• lhs_shape = (128, 1000000) , rhs_shape = (1000000, 256)

Density(%)	Peak Memory Consumption (Sparse)	Peak Memory Consumption (Dense)	Ratio of Memory Consumption
0.01	52	1575	30.28846154
0.02	52	1575	30.28846154
0.04	54	1575	29.16666667
0.08	57	1575	27.63157895
0.16	65	1575	24.23076923
0.32	87	1575	18.10344828
0.64	132	1575	11.93181818
1.28	221	1575	7.126696833
2.56	400	1575	3.9375
5.12	758	1575	2.077836412
10.24	1480	1575	1.064189189

dot(csr, rsp) vs dot(dense, dense) Peak Memory consumption Comparison

• rhs_density is the same as lhs_density
• lhs_shape = (128, 1000000) , rhs_shape = (1000000, 256)

Density(%)	Peak Memory Consumption (Sparse)	Peak Memory Consumption (Dense)	Ratio of Memory Consumption
0.01	52	3380	65
0.02	52	3380	65
0.04	54	3380	62.59259259
0.08	57	3380	59.29824561
0.16	65	3380	52
0.32	87	3380	38.85057471
0.64	132	3380	25.60606061
1.28	221	3380	15.29411765
2.56	400	3380	8.45
5.12	758	3380	4.459102902
10.24	1480	3380	2.283783784