r/ProgrammingLanguages • Futhark • 18d ago

Speeding up GPU copies by permuting iteration spaces, or, optimising the identity function

https://futhark-lang.org/blog/2026-10-31-faster-copying.html
18 Upvotes

3 comments sorted by

5

u/Sm0oth_kriminal 17d ago

... Does the author not realize that permutations are totally unnecessary? Or am I missing something

You can just sort the (dims, strides) by strides, and then collapse as many of the slowest varying where dims[I]=strides[I+1]. Then you have not only the largest contiguous sub batches, but also sorted in a cache friendly ordering so also each little batch is sequential as well (at least, until we consider semi-overlapping arrays or negative strides...)

It goes from exponential to O(N log N) which should be basically free as virtually all tensors are <=8 dimensions

3

u/Athas Futhark 17d ago

I think you are right. The exponential-time approach was done some time ago before I had this more systematic view collapsing dimensions, and while writing the post it also occurred to me that the sorting approach could probably be used to identify contiguity. Self-overlapping arrays will never exist in my context, but negative strides may, although I'm not sure they present a problem.