[mlir][sparse] optimizing permutation validity check in toMLIRSparseTensor

[wrengr]

Summary

The previous sorting-based check was O(n*log n). The new implementation is O(n).

This is a followup to the refactoring of D133462, D133830, D133831, and D133833.

Depends On D133833

[wrengr]

rebase

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

 // TODO: generalize beyond 64-bit indices.
 template <typename V>
 static SparseTensorStorage<uint64_t, uint64_t, V> *
 toMLIRSparseTensor(uint64_t rank, uint64_t nse, const uint64_t *shape,
                    const V *values, const uint64_t *indices,
                    const uint64_t *perm, const DimLevelType *sparsity) {
 #ifndef NDEBUG
   // Verify that perm is a permutation of 0..(rank-1).
-  std::vector<uint64_t> order(perm, perm + rank);
-  std::sort(order.begin(), order.end());
-  for (uint64_t i = 0; i < rank; ++i)
-    if (i != order[i])
+  std::vector<bool> seen(rank, false);
+  for (uint64_t i = 0; i < rank; ++i) {
+    const uint64_t j = perm[i];
+    if (j >= rank || seen[j])
       MLIR_SPARSETENSOR_FATAL("Not a permutation of 0..%" PRIu64 "\n", rank);
+    seen[j] = true;
+  }
 
   // Verify that the sparsity values are supported.
   for (uint64_t i = 0; i < rank; ++i)
     if (sparsity[i] != DimLevelType::kDense &&
         sparsity[i] != DimLevelType::kCompressed)
       MLIR_SPARSETENSOR_FATAL("Unsupported sparsity value %d\n",
                               static_cast<int>(sparsity[i]));
 #endif