Improve performance of Cartesian indexing

[maleadt]

Metal GPUs suffer from the way we encode Cartesian indices, presumably because of the integer division that happens when mapping a linear index to a Cartesian, but there may be other causes. In #100 and JuliaGPU/GPUArrays.jl#454, we worked around some of the more egregious performance issues by putting the indices in the type domain such that are known to LLVM, allowing the back-end compiler to optimize code (again, presumably avoiding the division by a constant integer by mapping them onto a bunch of bit operations).

This isn't ideal because it results in significantly more kernels being compiled. Ideally we figure out a way to better encode Cartesian indices, although it's obviously hard to avoid the integer division at all.

Alternatively, we might want to improve https://github.com/maleadt/StaticCartesian.jl, or something similar, so that we can perform this optimization ourselves instead of relying on the Metal back-end compiler, because relying on such an optimization might be fragile (as observed in JuliaGPU/GPUArrays.jl#454 where we needed additional bounds information for the optimization to trigger).

[N5N3]

Does Base.MultiplicativeInverses.SignedMultiplicativeInverse helps here?
If so we can form the vec(::CartesianIndices) on host side and let GPU do magic divrem

[maleadt]

Does Base.MultiplicativeInverses.SignedMultiplicativeInverse helps here?

I'm not sure, I don't have experience with that tool. Can you elaborate? Your PR looked pretty breaking on non-1.10 CI.

[N5N3]

pretty breaking on non-1.10 CI.
My fault, a careless typo.

My further trial shows that SignedMultiplicativeInverse{Int64} is slow on my 1660.
Perhaps do Int128 Multiplication is not a good idea here.

I tried to force every index (Edit: And the array length) to UInt32, then it has similar runtime performance as static CartesianIndices.
But I guess that not acceptable?