1 # Copyright 2016 The TensorFlow Authors. All Rights Reserved. 2 # 3 # Licensed under the Apache License, Version 2.0 (the "License"); 4 # you may not use this file except in compliance with the License. 5 # You may obtain a copy of the License at 6 # 7 # http://www.apache.org/licenses/LICENSE-2.0 8 # 9 # Unless required by applicable law or agreed to in writing, software 10 # distributed under the License is distributed on an "AS IS" BASIS, 11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 # See the License for the specific language governing permissions and 13 # limitations under the License. 14 # ============================================================================== 15 """Tests for SparseAdd.""" 16 17 from __future__ import absolute_import 18 from __future__ import division 19 from __future__ import print_function 20 21 import timeit 22 23 import numpy as np 24 25 from tensorflow.python.client import session 26 from tensorflow.python.framework import constant_op 27 from tensorflow.python.framework import dtypes 28 from tensorflow.python.framework import errors_impl 29 from tensorflow.python.framework import ops 30 from tensorflow.python.framework import sparse_tensor 31 from tensorflow.python.ops import gradient_checker 32 from tensorflow.python.ops import math_ops 33 from tensorflow.python.ops import sparse_ops 34 import tensorflow.python.ops.sparse_grad # pylint: disable=unused-import 35 from tensorflow.python.platform import test 36 37 38 def _sparsify(x, thresh=0.5, index_dtype=np.int64): 39 x[x < thresh] = 0 40 41 non_zero = np.where(x) 42 x_indices = np.vstack(non_zero).astype(index_dtype).T 43 x_values = x[non_zero] 44 x_shape = x.shape 45 46 return sparse_tensor.SparseTensor( 47 indices=x_indices, values=x_values, dense_shape=x_shape), len(x_values) 48 49 50 class SparseAddTest(test.TestCase): 51 52 def _randomTensor(self, size, np_dtype, sparse=True): 53 n, m = size 54 x = np.random.randn(n, m).astype(np_dtype) 55 return _sparsify(x) if sparse else x 56 57 def _SparseTensorValue_3x3(self, negate=False): 58 # [ 1] 59 # [2 ] 60 # [3 4] 61 # ...or its cwise negation, if `negate` 62 ind = np.array([[0, 1], [1, 0], [2, 0], [2, 1]]) 63 val = np.array([1, 2, 3, 4]) 64 if negate: 65 val = -np.array([1, 2, 3, 4]) 66 shape = np.array([3, 3]) 67 return sparse_tensor.SparseTensorValue( 68 np.array(ind, np.int64), 69 np.array(val, np.float32), np.array(shape, np.int64)) 70 71 def _SparseTensor_3x3(self, negate=False): 72 return sparse_tensor.SparseTensor.from_value( 73 self._SparseTensorValue_3x3(negate)) 74 75 def _SparseTensor_3x3_v2(self): 76 # [ 1] 77 # [-1.9 ] 78 # [ 3 -4.2] 79 ind = np.array([[0, 1], [1, 0], [2, 0], [2, 1]]) 80 val = np.array([1, -1.9, 3, -4.2]) 81 shape = np.array([3, 3]) 82 return sparse_tensor.SparseTensor( 83 constant_op.constant(ind, dtypes.int64), 84 constant_op.constant(val, dtypes.float32), 85 constant_op.constant(shape, dtypes.int64)) 86 87 def testAddSelf(self): 88 with self.test_session(use_gpu=False) as sess: 89 for sp_a in (self._SparseTensorValue_3x3(), self._SparseTensor_3x3()): 90 for sp_b in (self._SparseTensorValue_3x3(), self._SparseTensor_3x3()): 91 sp_sum = sparse_ops.sparse_add(sp_a, sp_b) 92 self.assertAllEqual((3, 3), sp_sum.get_shape()) 93 94 sum_out = sess.run(sp_sum) 95 96 self.assertEqual(sp_sum.dense_shape.get_shape(), [2]) 97 self.assertAllEqual(sum_out.indices, [[0, 1], [1, 0], [2, 0], [2, 1]]) 98 self.assertAllEqual(sum_out.values, [2, 4, 6, 8]) 99 self.assertAllEqual(sum_out.dense_shape, [3, 3]) 100 101 def testAddSelfAndNegation(self): 102 with self.test_session(use_gpu=False) as sess: 103 sp_a = self._SparseTensor_3x3() 104 sp_b = self._SparseTensor_3x3(negate=True) 105 106 sp_sum = sparse_ops.sparse_add(sp_a, sp_b, 0.1) 107 sum_out = sess.run(sp_sum) 108 109 self.assertEqual(sp_sum.dense_shape.get_shape(), [2]) 110 self.assertAllEqual(sum_out.indices, np.empty([0, 2])) 111 self.assertAllEqual(sum_out.values, []) 112 self.assertAllEqual(sum_out.dense_shape, [3, 3]) 113 114 def testSmallValuesShouldVanish(self): 115 with self.test_session(use_gpu=False) as sess: 116 sp_a = self._SparseTensor_3x3() 117 sp_b = self._SparseTensor_3x3_v2() 118 119 # sum: 120 # [ 2] 121 # [.1 ] 122 # [ 6 -.2] 123 124 # two values should vanish: |.1| < .21, and |-.2| < .21 125 sp_sum = sparse_ops.sparse_add(sp_a, sp_b, thresh=0.21) 126 sum_out = sess.run(sp_sum) 127 128 self.assertEqual(sp_sum.dense_shape.get_shape(), [2]) 129 self.assertAllEqual(sum_out.indices, [[0, 1], [2, 0]]) 130 self.assertAllEqual(sum_out.values, [2, 6]) 131 self.assertAllEqual(sum_out.dense_shape, [3, 3]) 132 133 # only .1 vanishes 134 sp_sum = sparse_ops.sparse_add(sp_a, sp_b, thresh=0.11) 135 sum_out = sess.run(sp_sum) 136 137 self.assertEqual(sp_sum.dense_shape.get_shape(), [2]) 138 self.assertAllEqual(sum_out.indices, [[0, 1], [2, 0], [2, 1]]) 139 self.assertAllClose(sum_out.values, [2, 6, -.2]) 140 self.assertAllEqual(sum_out.dense_shape, [3, 3]) 141 142 def testGradients(self): 143 np.random.seed(1618) # Make it reproducible. 144 with self.test_session(use_gpu=False): 145 for n in [10, 31]: 146 for m in [4, 17]: 147 sp_a, nnz_a = self._randomTensor([n, m], np.float32) 148 sp_b, nnz_b = self._randomTensor([n, m], np.float32) 149 sp_sum = sparse_ops.sparse_add(sp_a, sp_b) 150 nnz_sum = len(sp_sum.values.eval()) 151 152 err = gradient_checker.compute_gradient_error( 153 [sp_a.values, sp_b.values], [(nnz_a,), (nnz_b,)], sp_sum.values, 154 (nnz_sum,)) 155 self.assertLess(err, 1e-3) 156 157 def testAddSparseDense(self): 158 np.random.seed(1618) # Make it reproducible. 159 n, m = np.random.randint(30, size=2) 160 for dtype in [np.float32, np.float64, np.int64, np.complex64]: 161 for index_dtype in [np.int32, np.int64]: 162 rand_vals_np = np.random.randn(n, m).astype(dtype) 163 dense_np = np.random.randn(n, m).astype(dtype) 164 165 with self.test_session(use_gpu=False): 166 sparse, unused_nnz = _sparsify(rand_vals_np, index_dtype=index_dtype) 167 s = sparse_ops.sparse_add(sparse, 168 constant_op.constant(dense_np)).eval() 169 self.assertAllEqual(dense_np + rand_vals_np, s) 170 self.assertTrue(s.dtype == dtype) 171 172 # check commutativity 173 s = sparse_ops.sparse_add(constant_op.constant(dense_np), 174 sparse).eval() 175 self.assertAllEqual(dense_np + rand_vals_np, s) 176 self.assertTrue(s.dtype == dtype) 177 178 def testSparseTensorDenseAddGradients(self): 179 np.random.seed(1618) # Make it reproducible. 180 n, m = np.random.randint(30, size=2) 181 rand_vals_np = np.random.randn(n, m).astype(np.float32) 182 dense_np = np.random.randn(n, m).astype(np.float32) 183 184 with self.test_session(use_gpu=False): 185 sparse, nnz = _sparsify(rand_vals_np) 186 dense = constant_op.constant(dense_np, dtype=dtypes.float32) 187 s = sparse_ops.sparse_add(sparse, dense) 188 189 err = gradient_checker.compute_gradient_error([sparse.values, dense], 190 [(nnz,), (n, m)], s, (n, m)) 191 self.assertLess(err, 1e-3) 192 193 def testInvalidSparseTensor(self): 194 with self.test_session(use_gpu=False) as sess: 195 shape = [2, 2] 196 val = [0] 197 dense = constant_op.constant(np.zeros(shape, dtype=np.int32)) 198 199 for bad_idx in [ 200 [[-1, 0]], # -1 is invalid. 201 [[1, 3]], # ...so is 3. 202 ]: 203 sparse = sparse_tensor.SparseTensorValue(bad_idx, val, shape) 204 s = sparse_ops.sparse_add(sparse, dense) 205 206 with self.assertRaisesRegexp(errors_impl.InvalidArgumentError, 207 "invalid index"): 208 sess.run(s) 209 210 ######################## Benchmarking code 211 212 213 def _s2d_add_vs_sparse_add(sparsity, n, m, num_iters=50): 214 np.random.seed(1618) 215 216 with session.Session(graph=ops.Graph()) as sess: 217 sp_vals = np.random.rand(n, m).astype(np.float32) 218 sp_t, unused_nnz = _sparsify(sp_vals, thresh=sparsity, index_dtype=np.int32) 219 vals = np.random.rand(n, m).astype(np.float32) 220 221 s2d = math_ops.add( 222 sparse_ops.sparse_tensor_to_dense(sp_t), constant_op.constant(vals)) 223 sa = sparse_ops.sparse_add(sp_t, constant_op.constant(vals)) 224 225 timeit.timeit(lambda: sess.run(s2d), number=3) 226 timeit.timeit(lambda: sess.run(sa), number=3) 227 228 s2d_total = timeit.timeit(lambda: sess.run(s2d), number=num_iters) 229 sa_total = timeit.timeit(lambda: sess.run(sa), number=num_iters) 230 231 # per-iter latency; secs to millis 232 return s2d_total * 1e3 / num_iters, sa_total * 1e3 / num_iters 233 234 235 class SparseAddBenchmark(test.Benchmark): 236 237 def benchmarkSparseAddDense(self): 238 239 print("SparseAddDense: add with sparse_to_dense vs. sparse_add") 240 print("%nnz \t n \t m \t millis(s2d) \t millis(sparse_add) \t speedup") 241 242 for sparsity in [0.99, 0.5, 0.01]: 243 for n in [1, 256, 50000]: 244 for m in [100, 1000]: 245 s2d_dt, sa_dt = _s2d_add_vs_sparse_add(sparsity, n, m) 246 print("%.2f \t %d \t %d \t %.4f \t %.4f \t %.2f" % (sparsity, n, m, 247 s2d_dt, sa_dt, 248 s2d_dt / sa_dt)) 249 250 251 if __name__ == "__main__": 252 test.main() 253