> 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_...

> 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/

1. https://www.jsoftware.com/