Is transposition a common enough operation that it might be better to avoid it by having versions of the operations/functions that take matrices that do the necessary transpositions implicitly?
Switch in place is inefficient for data stored in memory, like a matrix.
The most efficient way to swap 2 values stored in memory is to use 2 load instructions and 2 store instructions, like "load X in R1; load Y in R2; store R1 in Y; store R2 in X".
Therefore, for swapping memory values the XOR trick has never been useful, in the entire history of automatic computers.
For swapping data that is stored in internal CPU vector registers or matrix registers there are special shuffle instructions, which implement various kinds of transpositions.
Switch in place was efficient mostly in the distant past, for swapping general-purpose registers in those CPUs that did not have dedicated exchange/swap instructions. Intel/AMD CPUs always had exchange instructions, so switch in place has never been useful on them in any circumstances, since the very launch of the IBM PC, 45 years ago.
Today, the XOR trick might have remained useful for swapping general-purpose registers in some microcontrollers, but in the most popular ISAs, like ARM-based or RISC-V, most GPRs are equivalent, so the need to swap them arises very rarely, only in certain kinds of loops, and even there swapping can frequently be avoided by unrolling the loops.
The thing about linear algebra that strikes me as funny is that I faintly remember every instructor I ever have met says it is easy. Just learn the matrix cookbook and you’ll be good. At last, when you actually implement it, the ideas are simple in theory but in practice you’ll run into quadratic runtime almost all the time and it’s really hard to do well on CPUs. So is linear algebra hard? Maybe not on paper but in reality it’s really fucking difficult to get it to do what you want precisely and quickly
What an article, richly illustrated with diagrams, going deep into technical details to squeeze 4x performance improvement. The knowledge and experience that took to write this is worth gold.
It might benefit the world if there was philanthropic funding for people like this to do more public research and writing. Imagine there's so much information and wisdom in some people's brains, that deserve the chance to be written down and released in the public domain.
The AVX2 SIMD version is not ideal. Too many instructions, and it needs constant vectors. I would rather do it like that https://godbolt.org/z/cn6YKbfYd
I feel like the importance of padding is a bit understated on this page - BLAS and LAPACK require LDA and LDB parameters, and you can definitely tune these to the page size of a particular system/machine to improve performance.
When working with BLAS/LAPACK or other matrix libs, you can often apply a little linear algebra to reshape the problem rather than the input data to avoid a transpose altogether
13 comments
[ 2.6 ms ] story [ 33.2 ms ] threadThe most efficient way to swap 2 values stored in memory is to use 2 load instructions and 2 store instructions, like "load X in R1; load Y in R2; store R1 in Y; store R2 in X".
Therefore, for swapping memory values the XOR trick has never been useful, in the entire history of automatic computers.
For swapping data that is stored in internal CPU vector registers or matrix registers there are special shuffle instructions, which implement various kinds of transpositions.
Switch in place was efficient mostly in the distant past, for swapping general-purpose registers in those CPUs that did not have dedicated exchange/swap instructions. Intel/AMD CPUs always had exchange instructions, so switch in place has never been useful on them in any circumstances, since the very launch of the IBM PC, 45 years ago.
Today, the XOR trick might have remained useful for swapping general-purpose registers in some microcontrollers, but in the most popular ISAs, like ARM-based or RISC-V, most GPRs are equivalent, so the need to swap them arises very rarely, only in certain kinds of loops, and even there swapping can frequently be avoided by unrolling the loops.
It might benefit the world if there was philanthropic funding for people like this to do more public research and writing. Imagine there's so much information and wisdom in some people's brains, that deserve the chance to be written down and released in the public domain.
Actually I think I recall some GPUs storing textures that way, but I'm not entirely sure.
I feel like the importance of padding is a bit understated on this page - BLAS and LAPACK require LDA and LDB parameters, and you can definitely tune these to the page size of a particular system/machine to improve performance.
When working with BLAS/LAPACK or other matrix libs, you can often apply a little linear algebra to reshape the problem rather than the input data to avoid a transpose altogether