对于稀疏矩阵，Tensorflow使用COO格式而不是CSR有什么明显的原因吗？

Question

我试图从Tensorflow内置的稀疏矩阵乘法API中获取性能优势。凯夫曼建议tf.embedding_lookup_sparse是正确的方法。

但是，embedding_lookup_sparse的性能似乎在我的实验中有些令人失望。虽然它执行较小的矩阵乘法，<1,3196>和<3196,1024>，但稀疏度为0.1的稀疏矩阵不能获得密集矩阵乘法。

如果我的实现是正确的，我认为原因之一是Tensorflow使用COO格式保存所有索引-非零对。我不是这个领域的专家，但是，这不是众所周知的CSR格式在这种计算中表现得更好吗？对于稀疏矩阵表示，Tensorflow内部使用COO格式而不是CSR有任何明显的原因吗？

Answer 1

为了记录在案，你说矩阵乘法，但你的矩阵之一实际上是一个向量(1x3196)。因此，这将使它成为矩阵向量乘法(不同的BLAS核)。我假设你指的是矩阵向量乘法作为我的答案。

是的，理论上CSR应该比COO更快于矩阵向量乘法；这是因为CSR格式的存储大小是O(2nnz + n)与O(3nnzs)，稀疏矩阵向量乘法在很多情况下是内存界的。

与密集矩阵乘法相比，精确的性能差异取决于问题的大小、稀疏性、数据类型和实现。很难说哪种方法应该更快，因为稀疏存储格式引入了间接，这可能导致局部性降低，算术单元的使用(例如，不使用矢量化)很差(呃)。

特别是当矩阵和向量大小太小以至于几乎所有的东西都适合高速缓存时，我期望得到有限的性能好处。稀疏矩阵结构通常对真正大的矩阵更有用，从10 1B×10 1B到1B x 1B不等，这甚至不适合使用密集表示形式在主内存中使用。对于小规模的问题，在我的经验中，与密集格式相比，存储优势通常被局部性和算术效率的损失所抵消。在某种程度上，这是通过混合存储格式(例如块CSR)来解决的，这些格式试图从这两个方面发挥最大的作用，并且对于某些应用程序非常有用(看起来tensorflow不支持这一点)。

在tensorflow中，我假设使用COO格式是因为它对其他操作更有效，例如它支持O(1)更新、数据结构的插入和删除。为了提高这些运算的性能，在稀疏矩阵向量乘法中进行50%的性能交换似乎是合理的。