Conor 0:00

I also, Sean, if you're listening, Sean, it's uh sorry, Sean specific apology to you because uh we we should have done better. We should have done better. Welcome to ADSP the podcast, episode 199, recorded on August 26, 2024. My name is Connor, and today with my co-host Bryce, we chat about stud rotate.

Bryce 0:33

Okay, so let's talk about let's talk about rotate.

Conor 0:36

Let's talk about rotate.

Bryce 0:37

How do you implement rotate?

Conor 0:39

Are you kidding me? Have you not read programming pearls? Have you not watched one of my talks that mentions programming pearls? No. Really?

Bryce 0:48

This is famous, man. It's famous. You you Connor, I am completely shameless. You will not make me feel guilty about not knowing something.

Conor 0:56

Alright. Put your two hands up, put your two hands up. This is called what is it called? The hand algorithm. You gotta put your hands up like this. Alright. Swap the left one, like that. Then you so I like you turned it 180 degrees, do the same thing with the other one, and now do the same thing with the whole thing. What? It's three reverses, my guy. You implement rotate with three reverses. You've got your midpoint.

Bryce 1:19

Hang on, this hand thing you made. Whoa, I got one, two.

Conor 1:24

It's brilliant. Each time you flip each time you flip your hand, that's the equivalent of a reverse. So like you say you got the numbers one to ten representing your ten fingers. You flip the first five, so now you've got five, four, three, two, one. You flip the next ones, so you've got ten, nine, eight, seven, six. And now you f you reverse the whole thing, and what do you end up with? Beautiful. Beautiful, folks. We love it. Six, seven, eight, nine, ten, one, two, three, four, five. We love it, folks. My hands may be small, but the algorithm is beautiful.

Bryce 1:59

You're rotating at the middle point.

Conor 2:02

Yeah, that's how you spend the eight.

Bryce 2:03

In this example. Yeah.

Conor 2:04

In this example, yeah. Well, you can do it at the third point or whatever. But let's let's get the programming pearls. Uh programming pearls by John Bentley. We've all read it, and by we, I mean just me, because Bryce has not. And everyone should read it. It's a fantastic book. And if we talk about the rotate How do you implement reverse? Reverse? It's just a bunch of swaps.

Bryce 2:28

Okay, now walk me through it.

Conor 2:30

Reverse? You've got a list of ten numbers. Swap the first and last. Increment, decrement. Swap the second and second last? Increment decrement.

Bryce 2:41

So easy. So you take um you take the midpoint. Right. You you you but but that approach you just okay. How do you what do you do if you have like just like a forward iterator?

Conor 2:55

If you just have a forward iterator, well then that makes it a lot more complicated.

Bryce 3:00

Yeah, this is why I asked these questions. Uh because okay, so so so so I uh let let's let's let's take a step back. The approach you just the approach you just the approach you just described, you've got a random access iterator to implement reverse, you take like you know, the midpoint, um, or or you just you have a way of being able to move from the back to the to the to the front. And then you start it, you start with the first and the last, and then you swap them, and then you increment the first and you decrement the last, and then you keep swapping until first equals last.

Conor 3:36

Correct. Or technically it's it might not be not equal to, it might be a comparative.

Bryce 3:43

Yeah, it it's it's it's until yeah, until you've reached the position.

Conor 3:46

Until they collide or they go past each other.

Bryce 3:49

Yeah, yeah. Um but uh okay. So what is what is still reverse require iterator category wise? But that but that but for that to work, the reason I said forward, for that to work, you have to be able to take the last and then decrement it and to move backwards. So reverse reverse requires bidirectional iterators in C. And this is probably the reason why.

Conor 4:12

Alright, let me share my screen. I will put a hopefully this doesn't crash anything, folks. I installed Ubuntu 24.04 a month ago or so, and the windowing is terrible. And the snapping, every once in a while, you try to maximize something and boom, crashes your whole UI and then it forces you to log out. So it could happen, does it not? Screen window or tab. Can you see this actually? It does not indicate to me at all if you're seeing this.

Bryce 4:42

I can see it.

Conor 4:43

This is in the Programming Pearls book, as we mentioned before, by John Bentley. And it is the Doug McElroy hand-waving description. I was searching for the wrong stuff because I'm pretty sure you can find this image on the internet, but I just went and got a version of the book online.

Bryce 4:59

Hopefully this is uh Okay, so you reverse zero to d minus one, then you reverse d to n minus one, then you reverse zero to n minus one.

Conor 5:08

D being the point at which you want to rotate, um, and n being the length of the list. Uh and then it shows you with uh two hands, with five fingers, the exact thing that we just did.

Bryce 5:19

It is uh Do we do we do we paralyze rotate?

Conor 5:24

We do. That is a separate question though.

Bryce 5:26

So it uses this algorithm?

Conor 5:29

I that's actually a great question. Not reverse, but uh the question is does thrust rotate use three different thrust reverses?

Bryce 5:38

That I would probably I can't imagine that it does because that would be three separate launches. I imagine it does something else weird.

Conor 5:46

Let's find out. All right, we are going, where Bryce is going to the thrust implementation now, folks. That last episode, episode 198, probably only ended up being 10 minutes. I probably tightened it up real tight because uh we didn't talk about much. But now 10 minutes?

Bryce 6:01

Yeah. Why would it why would you post a 10-minute episode?

Conor 6:04

Oh, because uh we're bringing we're bringing back algorithms and data structures content, and we're just 10xing the rest. So we had to 10x most of episode 198. But 199, folks, this is the content that the listener has come for. We're talking about rotate, we're talking about reverses, we're talking about programming pearls, and we're going to find out how we do this in parallel in Thrust. If this was a game show, we'd poll the audience and we'd say, What do you think, folks? Is it three reverses or is it a custom kernel?

Bryce 6:36

Where is rotate?

Conor 6:37

All right, he's taking too long, so do we have a rotate? We might not. Tragedy, folks. I'm at the new CCCL Thrust documentation. It's a beautiful site.

Bryce 6:49

I didn't even try to look at the docs because those docs are a mess.

Conor 6:52

Alright. Well, I was about to say they're absolutely beautiful, folks. Beautiful docs, beautiful new docs. I think Bryce is just a little bitter because he did some work in a dark mode kind of thing. And then they threw that out and they got beautiful new docs now, folks. They're beautiful.

Bryce 7:07

I'm bitter because the search is not wonderful. But no, yeah. The search is fantastic once you learn how to use it. The team does great work, and I shouldn't I shouldn't.

Conor 7:17

And uh there is no rotate, folks. That's why we don't like C anymore, and I'm a full-blown array language programmer.

Bryce 7:31

Let's gotta be a reverse, though, right?

Conor 7:33

There's definitely a reverse.

Bryce 7:36

Yeah, I see reverse. Why is there no rotate?

Conor 7:40

Probably because, you know. They didn't know how to do it. They didn't know about Doug McElroy's algorithm.

Bryce 7:47

I don't accept that.

Conor 7:50

What do you mean you don't accept that?

Bryce 7:51

I do not accept that as the reason that there's no rotate.

Conor 7:57

You know what language you know what language does have a rotate? APL and BQN. Beautiful, folks. Beautiful. Okay, let's look at the generic implementation of reverse. What is looking at the implementation of reverse gonna tell us about So it just does it in terms of swap ranges.

Bryce 8:16

Um so it does the midpoint thing and then it does swap ranges. Okay. So what would a parallel rotate look like? So the na the naive version is gonna do three reverses. Yeah. But the problem is we don't want to do three separate launches, right? So we gotta come up with something better.

Conor 8:43

Um I mean you could do a you could do a rotate copy in one pass very easily, obviously. What would that look like? You c I mean you the way I would do it, it could look like one of several ways, but the way I would do it is I would uh combine a copy if with a permutation iterator. Where the permutation iterator just indexes uh into the correct element, and you could do that by wrapping the uh permutation actually, uh yeah, you could you could use that by basically doing a they have it in rapids, cutie f. Yeah, yeah, yeah. But you could do a counting iterator with a transform iterator and just do the modulus or some kind of you know integer arithmetic to do the indexing.

Bryce 9:26

It's a copy if which boils down to a s to a scan with some flags. Yeah, I I I buy that. I I don't have the proof in front of me, but I buy that.

Conor 9:36

That would have to be a rotate copy though, not a rotate copy.

Bryce 9:39

The problem with the in-place one is that so the the f the f in in your three reverses, um the first two reverses can definitely happen in parallel. Um and like like you you can come up with some sort of segmented uh reverse algorithm to do those those two in a single pass. Because you're reversing from you know zero to D minus one, and then from D to the end of the thing. That those are two completely different things. They're completely independent of each other. You're doing um a similar operation, I suspect. I mean, at the very least, you could launch those two in parallel. Um I suspect you could do them in a single kernel. Um but then the problem is then you have to do this third reverse, which sort of which operates in the entire thing and sort of uh it it is by construction the first two reverses have to happen first. So maybe the answer is that the best you can do is two passes, but as anybody who's listened to this podcast faithfully knows, I I I find it hard to accept a uh multi-pass parallel algorithms. Um so there's gotta be a better way. So there have to be other algorithms for rotate um that are less efficient in the serial case, but maybe are better in the parallel case. So uh what what else what else you got?

Conor 11:17

I'm trying to think of the word. What do they say when they do like uh over under hyped? But it's not hype, it's that reverse is a intellectually extremely simple algorithm, but when it comes Hang on a second.

Bryce 11:35

Hang on a second. Rotate. I said reverse. I said reverse. Rotate only requires forward iterators. So that means that the implementation, I think, is not just three reverses. Um so there must be some better algorithm um than than your three reverses. You don't know, you don't you don't know, cut come on. You're you're supposed to be must rotate. You don't know any better way to do to do rotate than three reverses, or a different way to do rotate than through reverses, rotate algorithm. There's gotta be something else. Parallel rotate. If I Google for parallel rotate, I just get, you know, rotate along a parallel axis. That doesn't help me at all. You're being quiet, are you cooking something?

Conor 12:29

No, I'm just looking at the MSVC STL implementation.

Bryce 12:34

Yeah. Yeah, so so so I I looked at that too. That the those have um state, so they're not immediately.

Conor 12:43

That might explain why you can do it with forward iterators.

Bryce 12:46

Yeah.

Conor 12:48

Let's go to CPP reference.

Bryce 12:50

I want to like, you ever watch that show Who Wants to be a Millionaire? And it's like you have you have you it was a show in like the late 90s. It's the same age, man.

Conor 13:00

We both know what that show is.

Bryce 13:02

Uh I'm explaining for the listener. You'd have three life we we have some, you know, you know, Gen Z and Gen Y's on here. Um you'd have three lifelines that you could use. It was a quiz shit. You'd answer questions and you'd win progressively more money, and you'd have three lifelines, and one of those lifelines was phone a friend. Um and uh I I feel like I want to use my phone a friend. I don't know who I'd phone, but uh I guess Sean. I guess I would phone Sean because he's Mr. Rotate. I called you Mr. Rotate before, but that's you're just you're just Mr. Rotate fanboy.

Conor 13:41

Yeah. Interestingly, CPP reference says that the complexity is at most a distance first to last swaps, which means that it's not the three reverse implementation. Yeah.

Bryce 13:55

Yeah, we we we've we've established it. So I mean, what's the complexity of the three reverses?

Conor 14:01

It's two and it's a little bit.

Bryce 14:02

Oh, it's like yeah, it's two and oh, that's awful. Get that get that nonsense out of here. Why is there not like a Wikipedia page for the rotated algorithm?

Conor 14:11

I'm sharing my screen again, folks. Because I, you know what? I was thinking I looked this up once. I looked this up once. You tell me what you see here, buddy. You tell me what you see here. Uh-huh. Uh-huh.

Bryce 14:21

Yeah, yeah, yeah. So they they they do the through reverses if they can, yeah. And they fall back to doing the stateful thing otherwise.

Conor 14:28

So is that does this mean it's not? I mean, uh, CPP reference could be wrong in saying that um it's well, okay.

Bryce 14:39

Find out whether these people are compliant. Yeah, so I was gonna say Oh, this this episode this episode might end with us filing some bugs. I'm not filing any bugs, but you can go ahead and uh Yeah, at most last minus first swaps, the standard says.

Conor 14:55

So yeah, this code, we will link this code. It's Microsoft STL slash a bunch of stuff slash inc slash X utility, and it says if const expert is CPP17 random access iterator. I've uh elaborated a bit, that's not exactly how it reads. And then it's got three calls to reverse. Then it says else if const expert is CPP bidirectional iterator. It's got the same thing except uh auto-temporary reverse until sentinel unchecked call. And then otherwise it's got an else case where it does does a bunch of, you know, uh stateful stuff and a couple iterators uh with a do while loop followed by a while loop. You don't see that every day, folks.

Bryce 15:46

Okay, so I'm filing uh I'm I'm I'm getting we're getting to the bottom of this.

Conor 15:51

Here, what are you fine- what are you filing?

Bryce 15:53

I want to know why they're not following the standard.

Conor 15:56

And also, is there actually a way to do a rotate?

Bryce 16:00

I don't think there well to do a rotate in what with last minus first swaps? Yeah, there is. There's the the the the the way, the stateful way, right?

Conor 16:11

Well, so say you've got 10 integers and you want to do a three rotate, meaning, and it's just an iota sequence. So it's one to ten, and you want to put one, two, three at the back, so that's a three rotate. The first thing you could do is just swap the first three with the last three, and then you end up with the sequence, assuming that it's one to ten, so there's no zero, so we're one indexed here, you're gonna end up with uh eight, nine, ten at the beginning, then four, five, six, seven, one, two, three. And so then you've only done whatever. Uh in this case, three out of your ten possible swaps. So the question is can you turn, can you turn the eight, nine, ten, four, five, six, seven into four, five, six, seven, eight, nine, ten in seven swaps? And if you use four swaps to get the four, five, six, seven to the front, what do you end up with? You end up with so I think it actually is possible. You end up with four, five, six, seven.

Bryce 17:09

So we don't we don't have to file a bug against the standard, just against the implementation.

Conor 17:13

Uh yeah, four, five, six, seven, and then the eight, nine, ten is gonna end up a little bit jumbled. But the point being is that like whatever order the eight, nine, ten is, uh, you've got three swaps left to get three values into their correct positions, and you won't need all of them. Uh because you really need like maximum two swaps of those three, and it'll vary depending on the uh rotate that you're doing. So it definitely can be done.

Bryce 17:44

Just not this way. Is that so alc dot alc dot rotate paragraph four states that the complexity is at most uh last minus first uh swaps uh but this uh three uh reverses approach um is.

Conor 18:12

If you have a forward iterator though.

Bryce 18:15

Can you not do better with the forward iterator?

Conor 18:16

No, I was gonna say if you have a four, like does that kind of algorithm work with the forward iterator? Let's actually read through it.

Bryce 18:22

Is it two for the for the three reverses? Is it exactly two two n swaps?

Conor 18:28

Oh wait. I don't we're man, there's a few listeners that are upset. How many swaps does reverse take? We're we're idiots.

Bryce 18:35

Oh, we are idiots.

Conor 18:37

Takes n over two.

Bryce 18:38

Takes n over two. Yes, we are idiots.

Conor 18:41

We are idiots. We apologize to the listener that's been listening screaming into their heads.

Bryce 18:45

You know what the funny thing is? The funny thing is, Connor. We we like at the front end of this, I asked, how did we how do we implement reverse? And we it's not it's not like we didn't think about this. We literally talked about how you implement reverse, and we talked about, oh yeah, it's like you take the midpoint and then like you swap the things up to the midpoint. Yeah.

Conor 19:04

This is the problem though.

Bryce 19:06

I almost filed the bug report. I almost looked like a complete ass.

Conor 19:11

That's the thing, though, is in school they teach you that the coefficient doesn't matter when it time when it comes to time complexity. But this is a and so your brain is a lot of the times, or at least my brain, shaves that but the standard in this case, the standard in this case is not giving a time it's not giving a like big thing.

Bryce 19:27

They're talking about number of swaps. It's it's it's saying exact. Yeah, but we promise it will be.

Conor 19:32

But that's the problem, is that like we have I have a mental model that taught that thinks in terms of linear, quadratic, linear rhythmic, and then whenever there is like a it's technically half linear, right? It's a half O of N, but like you ignore that half. But in this case, if we had paid attention to it, we would have realized that the three reverses when you've got two partial reverses that equal a full reverse followed by a full reverse is ultimately that number of swaps.

Bryce 20:00

The f the first two reverses, each one of those is a fourth of your swaps.

Conor 20:04

I also, Sean, if you're listening, Sean, it's uh specific apology to you because uh we we should have done better. We should have done better.

Bryce 20:13

But but anyways, let me ex let me let me explain for for for the listener a minute be fine. So the first two reverses each operate on half of the input, and so that each one of those reverses does a fourth of the swaps.

Conor 20:25

And then the it's incorrect to say half. They it works on a uh you know one minus percentage, and then the other one does the other. So technically you can do a zero rotate, which is just a reverse.

Bryce 20:37

Yeah.

Conor 20:46

Yes. And I said well.

Bryce 20:47

So I'm gonna show I'm gonna show you how close I was to filing this bug report.

Conor 20:51

And and I'll just to correct what I said and listen to the remote. Yes, he is he is very close to filing the bug. But yes, when I said uh zero rotate equals a reverse, it e the it it means that the first half of the rotate algorithm would be a reverse. Technically a zero rotate is a no-op, just so that we're not getting we don't have listeners once again yelling it into their uh So can we do a segmented reverse?

Bryce 21:20

And by that I mean can we launch a reverse kernel where we say here's two different ranges, reverse both of them. Because that is what essentially we would need to get from three passes down to two passes. And admittedly, you could also just launch the two independent reverses in parallel. But if you didn't want to do that, if you wanted to launch one big single pass as you do when you're gonna GPU. Matt rhymed, I appreciate that. Um, can that be done? Is this a scan?

Conor 21:55

Well, I was thinking that you could do something similar to unique by key, but then I remembered that actually, because like what you what you want is a reverse by key. Similar to a reduced by key, but the reduced does a reduction.

Bryce 22:05

So in Cobb in Thrust, the way reverse gets implemented is you uh find the midpoint, uh you just assume random access. So you find the midpoint and then you do you do swap ranges um from first to mid and then uh uh with the reverse iterator to last. So what is swap ranges? I don't even know where that is. Oh no, there it is. Okay. I think that one's pretty simple. Yeah, it's just a parallel four. So I don't I think that since reverse ends up being implemented with a parallel four, which has no communication, um, I think any way of combining any way of implementing a segmented reverse is gonna be worse. Because implementing a segmented reverse, you're gonna have to know when you've e reached the end of one of those segments. And that means you're gonna need communication. And so that's gonna be strictly worse than an embarrassingly parallel uh approach. And so I think we've finally hit upon an example on this podcast of an algorithm where um more passes is gonna be better. Specifically, I think the best approach for this is gonna be to launch, uh, assuming that there's not some other completely different algorithm, the best approach to implementing the three reverse or a reverse-based rotate is gonna be to launch the two um uh initial reverses, the two reverses of half the sequence in parallel, um, and then to launch the third reverse is uh like as a dependency that depends upon the first two. Unless, unless he said, unless there's a way to do this all in a single pass, in which case the benefit of keeping everything in memory may be worth it. But actually, yeah, so if you could do this in a way where you didn't have to go back to global memory, um where you load and store each thing from global memory a single time, that would I think be better than than the the three reverses approach. So I think that I think there's a better algorithm out here.

Conor 24:34

Well, we will leave that to a future episode because we have hit the limit. Which brings us to episode two hundred, folks. Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

Bryce 24:57

Low quality, high quality. That is the tagline of our podcast.

Conor 25:03

That's not the tagline. Our tagline is chaos with sprinkles of information.