projects / platform / upstream / llvm.git / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: b19cbda) | patch
[mlir][sparse] Reducing computational complexity
authorwren romano <2998727+wrengr@users.noreply.github.com>
Fri, 1 Jul 2022 19:41:01 +0000 (12:41 -0700)
committerwren romano <2998727+wrengr@users.noreply.github.com>
Fri, 1 Jul 2022 19:55:09 +0000 (12:55 -0700)
commit875ee0ed1c5af58cb4909f239093e25a35d7a21a
tree2890d3825b9796538089460cddb402f5661b9191tree | snapshot
parentb19cbda45a01807db0cd39ada302e27ac8e5ccb5commit | diff
[mlir][sparse] Reducing computational complexity

This is a followup to D128847.  The `AffineMap::getPermutedPosition` method performs a linear scan of the map, thus the previous implementation had asymptotic complexity of `O(|topSort| * |m|)`.  This change reduces that to `O(|topSort| + |m|)`.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D129011
mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp diff | blob | history
Domain: System / Toolchain;