6 ms·

Wow! Okay, but does it have to be a general transpose? And if so, why? I have no idea about this (which is PERFECT!) so I've started looking: > In linear alge

Wow! Okay, but does it have to be a general transpose? And if so, why? I have no idea about this (which is PERFECT!) so I've started looking: > In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix A by producing another matrix, often denoted by AT (among other notations). I ask, because I need to know if it matters how the solution works, or if all that matters is that the solution works as it should. Thank you! Edit: Do you have a compiled benchmark I can run, for comparison with other solutions?

moonchild 4y ago
> does it have to be a general transpose? And if so, why? There are two answers to this, one less interesting, and one more interesting. The less interesting answer is that it's a primitive in APL, and I have a vested interest in making APL fast. Then, it needs to be a general transpose because the specific case of a 2-d transpose is already well-studied and has high-quality solutions already. As a language feature, the transpose can be thought of as a calculus on indices. This suggests a fairly straightforward implementation strategy where no actual data is moved around; instead, a 'strided representation' is used, storing additional information about the array layout, and the indexing procedure is made aware of this. This seems to be effectively free. So why am I asking you to move data around? This leads into the second interpretation of the transpose, which is as a permutation. Interestingly, this is almost opposite the index-calculus interpretation, because it primarily acts to change the way the data are represented; it doesn't actually need to change how the data are interpreted at all. And this is useful because, when taking into account access patterns, laying the same data out differently can significantly improve locality and therefore performance. If you're familiar with column/row stores, or 'soa'/'aos', these are applications of the 2-d transpose. The general transpose, then, performs the obvious analogue function for higher-dimensional data and is interesting for the same reasons. (The duplicating-axes part is just a novelty, then.) As a starting point, I suggest looking at libfft; as I recall, it has some good 2-d transpose implementations, and links to relevant papers. (Fft is, not-so-coincidentally, an application that can benefit from transposing.) Also interesting may be this paper, and any relevant links that result therefrom: https://www.researchgate.net/publication/273912700_In-Place_Matrix_Transposition_on_GPUs https://www.researchgate.net/publication/273912700_In-Place_... > I need to know if it matters how the solution works, or if all that matters is that the solution works as it should The interface is: I give you a buffer, an element size (probably 1/2/4/8 bytes), a shape projecting a multidimensional interpretation onto that buffer, and a permutation of that shape; you move around the elements of the buffer according to the permutation. How you implement that is up to you (though I will also say that I am also more curious about the general approach you come up with than with the specifics of the implementation). > Do you have a compiled benchmark I can run, for comparison with other solutions? The only place I know of to find implementations is inside of apls; the fast apl implementations are dyalog apl[0] and j[1]. I don't know how optimised their transposes are, though; they might or might not be a good baseline. Here's a simple example to get you started benchmarking inside j: a=. 27 1000 40 77?@$0 NB.declare a to be an array of shape 27 1000 40 77 NB. contents are randomised; this is a memory-heavy algorithm, and apparently writing lots of zeroes can have weird cache effects NB. elements are double-precision floats; so, 8 bytes timex'2 1 0 3|:a' NB. see how long it takes to apply the permutatio 2 1 0 3 to the shape of a 0.34551 10 timex'2 1 0 3|:a' NB. do 10 runs, and take their average 0.301104 Dyalog is similar, but the permutation is specified in a weird way and I don't feel like looking it up atm; poke me about it later if you care to, as they do have better algorithms in some cases. 0. https://www.dyalog.com/ https://www.dyalog.com/ 1. https://www.jsoftware.com/ https://www.jsoftware.com/
- MrYellowP 4y ago
  I'm sorry, but this is a misunderstanding. You give me a problem, tell me the desired solution and I figure it out on my own. What I can provide you with is an optimized, compiled block of assembly code, with source, which solves your problem fast. What I require is a problem (you've stated it) and how the solution is supposed to look like/how the desired output is supposed to be presented/etc. I feel like you didn't actually do that. I guess the software you've linked is supposed to help me; I'll have a look at that. Usually, though, the problem itself is enough, though. Looking at other peoples work messes with creativity. Anyhow, can you execute a block of compiled assembly code? Then all I need is access to the data, how it's laid out and what it is you actually want the code to do. In return you'll get a wacky, working solution you can just plug in. If you can't call compiled binary directly, there's still a way around that using shared memory and having my code run in a separate process. Anyway, I've thought about this. You definitely want the data to be moved? You don't want just more efficient access to it? That'd been trivial to do. If you don't want that, because of cache reasons, then there's a trivial way of not destroying the cache, as long as you know how to access registers directly. Or I can still drop it in-place, I guess. I'm sure we'll get there. I guess next time I need to lay out what's actually "in store".
  - moonchild 4y ago
    I thought I was pretty clear > The interface is: I give you a buffer, an element size (probably 1/2/4/8 bytes), a shape projecting a multidimensional interpretation onto that buffer, and a permutation of that shape; you move around the elements of the buffer according to the permutation but if not, please tell me! The remainder is just providing context for the problem, but you don't have to look at it if you don't care to. > there's a trivial way of not destroying the cache, as long as you know how to access registers directly What do you mean by this? Nt accesses or similar? Those can be helpful in some specific cases, but are not really a general solution. Esp. if there is spatiotemporal correlation between accesses (as is often the case), and you want to be able to take advantage of the caches.
    - MrYellowP 4y ago

moonchild 4y ago

> does it have to be a general transpose? And if so, why? There are two answers to this, one less interesting, and one more interesting. The less interesting answer is that it's a primitive in APL, and I have a vested interest in making APL fast. Then, it needs to be a general transpose because the specific case of a 2-d transpose is already well-studied and has high-quality solutions already. As a language feature, the transpose can be thought of as a calculus on indices. This suggests a fairly straightforward implementation strategy where no actual data is moved around; instead, a 'strided representation' is used, storing additional information about the array layout, and the indexing procedure is made aware of this. This seems to be effectively free. So why am I asking you to move data around? This leads into the second interpretation of the transpose, which is as a permutation. Interestingly, this is almost opposite the index-calculus interpretation, because it primarily acts to change the way the data are represented; it doesn't actually need to change how the data are interpreted at all. And this is useful because, when taking into account access patterns, laying the same data out differently can significantly improve locality and therefore performance. If you're familiar with column/row stores, or 'soa'/'aos', these are applications of the 2-d transpose. The general transpose, then, performs the obvious analogue function for higher-dimensional data and is interesting for the same reasons. (The duplicating-axes part is just a novelty, then.) As a starting point, I suggest looking at libfft; as I recall, it has some good 2-d transpose implementations, and links to relevant papers. (Fft is, not-so-coincidentally, an application that can benefit from transposing.) Also interesting may be this paper, and any relevant links that result therefrom: https://www.researchgate.net/publication/273912700_In-Place_Matrix_Transposition_on_GPUs https://www.researchgate.net/publication/273912700_In-Place_... > I need to know if it matters how the solution works, or if all that matters is that the solution works as it should The interface is: I give you a buffer, an element size (probably 1/2/4/8 bytes), a shape projecting a multidimensional interpretation onto that buffer, and a permutation of that shape; you move around the elements of the buffer according to the permutation. How you implement that is up to you (though I will also say that I am also more curious about the general approach you come up with than with the specifics of the implementation). > Do you have a compiled benchmark I can run, for comparison with other solutions? The only place I know of to find implementations is inside of apls; the fast apl implementations are dyalog apl[0] and j[1]. I don't know how optimised their transposes are, though; they might or might not be a good baseline. Here's a simple example to get you started benchmarking inside j: a=. 27 1000 40 77?@$0 NB.declare a to be an array of shape 27 1000 40 77 NB. contents are randomised; this is a memory-heavy algorithm, and apparently writing lots of zeroes can have weird cache effects NB. elements are double-precision floats; so, 8 bytes timex'2 1 0 3|:a' NB. see how long it takes to apply the permutatio 2 1 0 3 to the shape of a 0.34551 10 timex'2 1 0 3|:a' NB. do 10 runs, and take their average 0.301104 Dyalog is similar, but the permutation is specified in a weird way and I don't feel like looking it up atm; poke me about it later if you care to, as they do have better algorithms in some cases. 0. https://www.dyalog.com/ https://www.dyalog.com/ 1. https://www.jsoftware.com/ https://www.jsoftware.com/

MrYellowP 4y ago
I'm sorry, but this is a misunderstanding. You give me a problem, tell me the desired solution and I figure it out on my own. What I can provide you with is an optimized, compiled block of assembly code, with source, which solves your problem fast. What I require is a problem (you've stated it) and how the solution is supposed to look like/how the desired output is supposed to be presented/etc. I feel like you didn't actually do that. I guess the software you've linked is supposed to help me; I'll have a look at that. Usually, though, the problem itself is enough, though. Looking at other peoples work messes with creativity. Anyhow, can you execute a block of compiled assembly code? Then all I need is access to the data, how it's laid out and what it is you actually want the code to do. In return you'll get a wacky, working solution you can just plug in. If you can't call compiled binary directly, there's still a way around that using shared memory and having my code run in a separate process. Anyway, I've thought about this. You definitely want the data to be moved? You don't want just more efficient access to it? That'd been trivial to do. If you don't want that, because of cache reasons, then there's a trivial way of not destroying the cache, as long as you know how to access registers directly. Or I can still drop it in-place, I guess. I'm sure we'll get there. I guess next time I need to lay out what's actually "in store".
- moonchild 4y ago
  I thought I was pretty clear > The interface is: I give you a buffer, an element size (probably 1/2/4/8 bytes), a shape projecting a multidimensional interpretation onto that buffer, and a permutation of that shape; you move around the elements of the buffer according to the permutation but if not, please tell me! The remainder is just providing context for the problem, but you don't have to look at it if you don't care to. > there's a trivial way of not destroying the cache, as long as you know how to access registers directly What do you mean by this? Nt accesses or similar? Those can be helpful in some specific cases, but are not really a general solution. Esp. if there is spatiotemporal correlation between accesses (as is often the case), and you want to be able to take advantage of the caches.
  - MrYellowP 4y ago