title: TensorFlow tf.sparse_tensor_dense_matmul
body: <p>I run a small experiment to benchmark the tf.sparse_tensor_dense_matmul operation. Unfortunately, I am surprised by the result.</p>
  
  <p>I am running a sparse matrix, dense vector multiplication, and vary</p>
  
  <ul>
  <li>the number of columns of the sparse matrix (decreasing)</li>
  <li>the number of rows of the dense vector (decreasing)</li>
  <li>the sparsity of the sparse matrix (increasing)</li>
  </ul>
  
  <p>While increasing the sparsisy for each run, I decrease the columns. This means that the number of non-zero values (nnz) stays always the same (100 per row).</p>
  
  <p>When measuring the time needed for computing the matml operation, I would expect, that it will stay the same (since the output size nor the nnz varies).</p>
  
  <p>What I see instead is the following:
  <a href="https://i.stack.imgur.com/zlw6q.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zlw6q.png" alt="enter image description here"></a></p>
  
  <p>I looked into the C++ code to see if I can spot any reasons for the result. Though, also taking the C++ code into account I would expect the same time for each run. If I understand the code right, it loops through all nnz values of the sparse matrix (<a href="https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L239" rel="nofollow noreferrer">https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L239</a>). For each nnz value it loops through all columns of the second dense matrix (in my case it is only one column since it is a vector) (<a href="https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L245" rel="nofollow noreferrer">https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L245</a>).</p>
  
  <p>The only point where I could imagine that the number of rows of the second matrix/vector effects the performance is <a href="https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L246" rel="nofollow noreferrer">https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.cc#L246</a> if it loops through all the rows of the second matrix/vector insight the "maybe_adjoint_b" function to get to the currently needed row. </p>
  
  <p>[What disturbs me about the "maybe_adjoint_b" call is, that it gets called with the variable "k" passed over as the row index. Though, I thought "m" would be the row index and "k" the column index of the sparse matrix.]</p>
  
  <p><strong>Question:</strong> Why do I get different execution times for the matmul operation, even though the nnz and the output sizes are always the same? </p>