News for hackers. Stuff that matters.
Re:tolower() in bulk at speed by MrYellowP on Monday June 27, 2022 @06:48PM (#31901931)
Had I known anyone cares about this ...

Anything else anyone cares about, that could use a speedup... ?

Re:tolower() in bulk at speed by moonchild on Monday June 27, 2022 @09:15PM (#31902972)
Produce a fast, in-place, ideally parallel implementation of the generalised transpose, which arbitrarily rearranges the axes of a multidimensional array (potentially duplicating some of them).
Re:tolower() in bulk at speed by MrYellowP on Tuesday June 28, 2022 @04:53AM (#31905602)
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?

Re:tolower() in bulk at speed by moonchild on Tuesday June 28, 2022 @06:41AM (#31906119)
> 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/

Re:tolower() in bulk at speed by MrYellowP on Tuesday June 28, 2022 @10:28AM (#31908124)
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".

Re:tolower() in bulk at speed by moonchild on Tuesday June 28, 2022 @10:51PM (#31915914)
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.

Re:tolower() in bulk at speed by MrYellowP on Thursday June 30, 2022 @08:14AM (#31931415)
You're right. You were.

I wasn't. I was too intimidated, because i'm not a "professional" working in the industry, thus I have little to no knowledge about what others are doing and often terms that others are using. Like how I had no idea what "general transpose" means ... but now I know.

> 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

I can work with that! Do you have an "in" and "out" example as a reference,

or should I just make my own?

What CPU are we talking about?

How does the shape look like?

Do you have example data I can start working with?

I've never worked with other people!

Thanks!

PS: Does it really have to be in-place replacement?

Re:tolower() in bulk at speed by moonchild on Friday July 01, 2022 @03:29AM (#31943467)
No worries.

> I had no idea what "general transpose" means ... but now I know

FWIW pretty much no one else in industry knows what a transpose it, let alone a general one. It's rather obscure :)

> What CPU are we talking about?

amd64 with avx2 is probably the most important target.

> How does the shape look like?

> example

The shape is a list of natural numbers. Its length is the number of dimensions in the array, and each element is the length of the corresponding axis. For instance, suppose the contents of the array are the numbers 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23. Then, if the shape is 2 3 4, that is a 2x3x4 brick. The length of the array is 24 (being the product 2*3*4), and the structure may be elucidated by the following tabular display:

   0  1  2  3
   4  5  6  7
   8  9 10 11
  
  12 13 14 15
  16 17 18 19
  20 21 22 23
Applying the permutation 1 2 0 to this shape yields an array of shape 3 4 2, and requires the following result:

   0 12
   1 13
   2 14
   3 15
  
   4 16
   5 17
   6 18
   7 19
  
   8 20
   9 21
  10 22
  11 23
> Does it really have to be in-place replacement?

Well, that's the trick, isn't it? :P

Re:tolower() in bulk at speed by MrYellowP on Wednesday July 06, 2022 @07:10AM (#31999284)
AMD! Convenient, because I'm running a 5900HS right now. :D

Wait ... you want to be able to pick the permutation? I thought it's about a fixed transposition, but you want to choose? lol

What a complicated mess! 234 ... two blocks of data, containing three lines of data, containing four entries of data.

I'm not sure the example is sufficient for me to understand. I hope I can figure this out for other cases than 1 at the start, which seems to be a bad example for understanding this. if 1 was 2, do I instead, then, pick every second number?

I'm trying to wrap my head around this, starting with wikipedia.

Why don't you use a better data structure? Seems rather wasteful, CPU-wise, not coming up with some more generic structure that makes it easier to permute?

But ... I guess that's not allowed, otherwise you'd not need in-place replacement.

On the other hand, as long as I store everything in-place it shouldn't matter, as long as the result is correct.

But are you sure you need in-place replacement as long as you can get the correct, permutated result? Do you request the same results more than once?

Yes, I keep asking again looking for a way to avoid it. I have to make sure I cover everything and know the desired outcome exactly. Like, if you just care about the result itself, then that's different to having to store it in memory.

Hm. Given that there's some sort of memory limitation ... How much space do I have, in bytes/kbytes, for code? Can I allocate my own memory?

Questions, questions, questions. Details, details, details.

Re:tolower() in bulk at speed by mlochbaum on Tuesday June 28, 2022 @12:07PM (#31909499)
Figured I may as well start writing a notes page on Transpose instead of just replying here:

https://mlochbaum.github.io/BQN/implementation/primitive/tra...

(EDIT: missed a 0 in the first version and got the wrong timing for Dyalog)

For the particular case you give, the axis permutation swaps two axes, so it's invertible and the same left argument applies in both J and APL (may require adjustment for ⎕IO of course). I measure Dyalog the same as J, 0.3s. This array has a large fixed axis at the end, meaning that chunks of 77 floats (over half a kB) stay together, and the best way is just to move each of these with memcpy. Seems both languages miss this optimization? 0.3s is only 2.2GB/s. The array's definitely too large to fit in even L3 cache but this seems too slow for an in-memory copy.

Re:tolower() in bulk at speed by moonchild on Wednesday June 29, 2022 @02:22AM (#31917070)
Thanks.

> cache associativity

This one is annoying. Nt accesses might help, though probably not for the in-place case. You mention padding; the paper I linked uses padding as well, to shorten cycle length for inplace+parallel. Although, I would guess that dimensions which are nice to the cache will be not-nice to the blocking, and vice versa

> Of course larger loops are possible as well. But most of the time it's really the base case that's important. The base case also handles two axes most of the time, but can incorporate all the 2D optimizations like blocking.

Unless I am misunderstanding--reversing the axes of an array of shape 1e6 1e3 2 2 will have an inner loop dealing with the two innermost axes, and some extra dispatch outside of that. Which is not ideal, obviously--the inner loop only deals with 4 elements.

Re:tolower() in bulk at speed by mlochbaum on Tuesday June 28, 2022 @12:22PM (#31909713)
No, I think they're both using memcpy. perf says they're spending all the time in libc at least. The total time is a little slower than operations like rotate that I know are using memcpy (0.18s), so the chunk size does seem to introduce some overhead.
Re:tolower() in bulk at speed by moonchild on Wednesday June 29, 2022 @02:09AM (#31917003)
Glibc strings functions are ok, but not great (but one-size-fits-all is hard, and for all I know they could be fine here).

While 512 bytes seems like a lot, the core loop is likely 4x unrolled avx; that is 128 bytes per iteration, so only 4 iterations. And it probably tries to align the dst, so annoying dispatch overhead (which you could avoid by working in batches of k at a time, eg k=4 for double floats and avx in the general case).

Re:tolower() in bulk at speed by mlochbaum on Wednesday June 29, 2022 @08:58AM (#31919497)
The big difference is the access pattern: see the benchmarks below. Index does the small memcpys, but it speeds up if the indices are in order (my earlier benchmark used ⌽, not ⊖, because I don't remember APL any more). So prefetching might help. I guess it's possible that a larger-scale blocking would too?

But 5GB/s for ⊖ isn't great either. In an application that uses these huge arrays and needs the best performance (most don't!), it needs to be split up, ideally into sections that fit in L1, so that multiple array operations can be applied to those chunks and stay CPU-bound (at least for transpose, maybe not for arithmetic). That's why I wouldn't be too interested in optimizing this case.

        ⎕IO←0 ⋄ ar←,[0 1 2]a←?27 1000 40 77⍴0
        ci←(⊢⍴∘⍳×/)3↑⍴a  ⍝ cell indices

        i←⍉ci ⋄ cmpx '2 1 0 3⍉a' 'ar[i;]'
    2 1 0 3⍉a → 2.8E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    ar[i;]    → 2.8E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

        i←5⊖ci ⋄ cmpx '5⊖a' 'ar[i;]'
    5⊖a    → 1.2E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    ar[i;] → 1.7E¯1 | +46% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
Re:tolower() in bulk at speed by MrYellowP on Thursday July 07, 2022 @08:48AM (#32013362)
Well, I guess you won't be responding anymore. Sorry, I can't wrap my head around the problem properly and it takes way too much time figuring it out, which shouldn't be necessary.

The example given is insufficient. I've tried figuring out how this whole thing works, but I didn't find any actually good explanation that's not written for mathematicians.

I've read through the other comments and it even looks like people are approaching this problem mathematically, which makes no sense to me.

There's someone mentioning that his code apparently uses memcopy and I'm wondering if he actually really knows what he's doing, because that's just massive overheard for elements which - as I believe - fit into registers.

Compilers don't write the best code out there, period. After several generations of this attitude, how would people even know, if all they ever do is having blind faith that the compiler will do their job?

Anyhow, I digress into ranting ...

I have several solutions in mind, but apparently I require actual data and at least a few examples that aren't so simple that they don't actually reflect the desired outcome.

I'm sorry about that. It's just how I work. I need something to work with and the scope of this is way beyond reasonability, because all the learning involved does not appear to be at all required for solving the problem.

So, instead of doing it myself (I'd still love to), I'll just tell you the solution I came up with.

To me, this problem seems solvable just by writing code dynamically. Based on how you want the result to be laid out, you just drop blocks of assembly code meant to perform the tasks required to solve the problem.

Tasks, like, "read the element from memory" and "write it somewhere else".

There's room for exploration, by trying different methods of reading and writing the elements. There's more ways than mov to do the job.

How all of this would work:

You know your memory access patterns, both for reading and for writing.

You can sort the access patterns based on linear locality. If it boils down to one "cacheline per read" and you're not allowed to change the structure of the data to make things easier on the cache, then that's just how it is and there's no way around it.

With your sorted access patterns, you start writing the blocks of adjusted (memory addresses) compiled code into your executable memory.

Given that there's different ways of doing the reads/writes, you could do what I'd do and have several different blocks of code to experiment with. Like, one can abuse push/pop for memory transfers, eight byte per.

If you want to be really fancy you'd make a benchmark shuffling around the access patterns (the blocks of code and its respective variations) until you find the quickest, assuming there's any practical value for you in doing so.

I know I would, because this problem can be brute-forced.

Now you execute your created block of code, which then rewrites it all in place, hopefully making proper use of pipelining.

And if you want to go really, really fancy ... you do it multithreaded.

I can see that working ... and I can see room for tinkering. Further exploration follows after a working prototype.

Well ... so far that's all I have. From my perspective this problem is solvable, because it's just memory accesses and, including exploration of possible optimizations, clever use of registers.

Looking at it from a mathematical perspective and trusting the compiler to figure out how to do it quickly doesn't at all appear to me like it's going to cut it.

Thank you for coming to my TED talk.