Permutations are an extremely common use case of
AffineMap; however, there are a number of performance problems with the current implementation for that use case.
For example, the current implementation of
AffineMap::getPermutedPosition(unsigned) performs a linear scan of the
ArrayRef, and therefore takes O(n) time for each call. It is a common use case to want to call this method within a loop; however, that introduces an asymptotic slowdown, since it will take O(m*n) time. To avoid the slowdown users must manually float out construction of the inverse permutation so that the whole process takes only O(n+m). However, if the process is called repeatedly, then that means it’ll take O(k*(n+m)), even though the O(k*n) work is k-redundant (i.e., it should take only O(n + k*m)).
Add a new subclass of AffineMap for permutations, and have PermutationMap compute the inverse permutation once and store it alongside the forward permutation. This would allow
getPermutedPosition to execute in O(1) time, without needing to manually float out construction of the inverse map, nor repeatedly constructing the inverse map.
In addition, various permutation-specific methods of AffineMap should be moved to the PermutationMap class instead, since that would allow those methods to avoid verifying that the map is a permutation every time they’re called.
We could have PermutationMap be independent of AffineMap, rather than being a subclass. This would make certain aspects of implementation easier (e.g., don’t need to deal with
dyn_cast). However, I feel that it would make the API less clean, and thus end up pushing more complexity onto the client code.
We may want to add some MLIR syntax for PermutationMap as a new builtin type (i.e., for an attribute wrapper of the PermutationMap itself), so that the MLIR type system can enforce requirements that something be a permutation. However, that’s a more involved change not considered in this RFC.
It might be nice to have some other intermediate classes for more general sorts of invertibility (e.g., PermutationMap < InvertibleAffineMap < RetractableAffineMap < AffineMap), but that development should wait until those classes are actually needed, since detecting/verifying invertibility/retractability requires more work.