Conor

Hey, hey, I I'm not hearing any better ideas from you. I'm I'm on three hours of sleep here. I've been up since I don't even remember when. Oh yeah, I almost died on the plane, too. That was crazy. That was crazy.

Bryce

You almost died on the plane. Yeah, yeah. You want would you like to elaborate?

Conor

Yeah. I would like to elaborate. Welcome to ADSP the podcast, episode 188, recorded on June 11th, 2024. My name is Connor, and today with my co-host Bryce, we chat about how to implement a parallel merge. Moving on to episode 188. What are we talking about?

Bryce

I I got I got I got a topic.

Conor

Perfect. Save saved our listeners uh from me just rambling.

Bryce

Both of us are just super uh ill prepared to talk about this. But uh so how does parallel merge work? How do how does okay let's take a step back? How does how does serial merge work?

Conor

Serial merge of just two lists?

Bryce

Yeah. Yeah, yeah.

Conor

I mean that's super trivial, no?

Bryce

I wouldn't be asking if it was.

Conor

I mean, if you've got two separate lists and you're merging into a new list, then that is the easiest case, right? You just got two pointers into each array and you're just doing a comparison each time, and while you have the lower value, you copy that into the new list and move the iterator and repeat. Rinse repeat. Okay. Uh in a case where you are trying to do it quote unquote in place, which doesn't really exist for merge, but you're gonna end up doing a bunch of insertions, which is probably gonna be worse. It's gonna be way worse for time complexity. Actually, is it? Interesting, yeah. So what if you want to do an in-place merge where you've got list A and list B, and you're gonna resize list A to be the sum of both your sizes, is that worse time complexity? So like the first one is linear in the length of both of your lists. The second one, I mean, technically, couldn't you do something where you fill it from the back and then you don't need to do a bunch of insertions? Yeah, that's brilliant. Um brilliant, folks. That's what you do. So instead of But it's still linear.

Bryce

It's still linear.

Conor

It's still linear, but I I was imagining if you're filling it from the front, each time you want to insert an element from B into some middle position of A, you're gonna end up, you know, having to reallocate. Well, actually, you won't have to reallocate, but you're gonna have to do these copies of like n elements at a time, or you know, some linear number of elements at a time every time you do an insertion from B. But if you do it backwards, uh you're just basically doing the exact same algorithm. You just have pointers at the end, and you don't need to worry about doing that uh linear copies of elements.

Bryce

All right, so we've we Does this does this get worse if you want to merge k lists, not two lists? No. Do you have to do more comparisons?

Conor

Yeah, you have to do more comparisons, but that's fine.

Bryce

Doesn't that doesn't that or does it? I think it might. So it so at any given, you know, I'm I'm do I I I've got k lists of length M. And uh at any and I so I'm gonna iterate M times. And for each one of those M iterations, I have to I guess it's true, yeah.

Conor

It it becomes K times N.

Bryce

I have to do like Well no, I don't have to do like log K comparisons.

Conor

Why log K.

Bryce

Well, because I've got like K things, I need to s find the smallest, right? So can't can't I just do like a min heap?

Conor

But your values across your K lists are not in a min heap. You just have pointers to whatever value you're at.

Bryce

Right, right. But I'm saying like I got I got k things, I gotta find the smallest one.

Conor

In order to do a log n lookup on k elements, they have to be in a structure that you can do a log k lookup on them. And they're just they're just in some array, so it's it's just gonna be linear.

Bryce

Yeah, yeah. Yeah.

Conor

Okay, so maybe for the k list it is actually k times n. But the the algorithm is still morally the same. Alright, I did linear. You can do parallel.

Bryce

Well, I know I know that uh you know, this is a building block of our of our parallel merge sort, but I don't I don't actually know how it works. We we use this thing called the merge path the parallel merge path algorithm, I think. Let's see if I can understand how this works. I actually have no clue. You have any any intuition? Maybe we should limit ourselves to the to the two-element the two list case to think about this.

Conor

Well, how would I my approach to solving this, not knowing off the top of my head, is how would I implement this in terms of thrust algorithms? Yeah. And you would do this with a copy if algorithm. And could you do it with some kind of scatter iterator or gather iterator if you did some kind of I mean they're already sorted, so right. They're already sorted. But there's gotta be some kind of thing where you do some okay, well hang on, hang on.

Bryce

Hang on. Uh let's start with the dumbest way you could do this, right? The dumbest way would be like you just do like some sort of segmented sort, right? Like you just resort the entire thing in parallel. Like we know how to sort this.

Conor

I mean that's not a merge though. I mean, tech I mean, okay, yeah, sure. If you want to do the dumbest thing possible, create a new list and just dumbest and just sort sort it. But that is I feel like you haven't answered the question. Uh I mean, technically, if you're in an interview and someone says implement a parallel merge, and then you write the function body merge, and then you just you just do a copy if to the back of the first vector after resizing, and then you call thrust sort. I mean, technically you did implement a parallel merge. Not exactly, I think, what the interviewer would have been asking for, but you know.

Bryce

Sure, sure. But what I'm what I'm saying is it's only uphill from here.

Conor

I mean, if we want to if we want to say that, I mean, you probably could choose something worse. Uh you know. I I I I I don't even want to uh you could have some like you know nested reductions or something like that. Call a call a max rare, uh, you know, copy it over and then do basically uh hand roll a parallel insertion sort or bubble sort or whatever the heck it's called. Find uh just repeated reductions. Anyways, that's uh you could go downhill, is all I'm saying.

Bryce

Yeah. So continue with your idea.

Conor

Well, I don't I don't really have uh my idea was only half baked. It's like you have a copy if with some kind of like iterator sequence, like you know, there's the permutation iterator, and is there some way that you could get like if you if you combine the vectors, is there some way that you could construct a permutation iterator that when combined with a copy if results in that final uh merged sorted sequence? So imagine you've got the lists like one, two, three, four, five, six, seven, eight, nine, ten, and then you've got another list, one, two, three, four, five, six, seven, eight, nine, ten. You put those together. So now you've got one to ten, followed by one to ten, and so the permutation iterator would go from like the first element to the eleventh element, then back to the second element, and then to the twelfth element, and it would repeat that until you got all 20 elements done. So that that permutation iterator combined with a copy if algorithm gets you your merged sequence. And a copy if is just a scan underneath the hood. The question is, is like, uh, how do you is it possible to construct that permutation iterator based off of it's like it's data dependent, right? So most permutation iterators they follow some kind of pattern.

Bryce

So how are you gonna construct this permutation?

Conor

So yeah, uh that that's the final question, is is is it even possible to construct uh it doesn't even need to be a permutation iterator. There's other iterators. It but it seems like the permutation iterator is the closest one to like what we want, but uh how do you So describe to me again how you'd construct this? Well, I don't know. I'm I'm I'm only like uh 60% of the way. I went from 50% of the way there to being 60% of the way there.

Bryce

Just describe for me again what you want this permutation iterator to what you want this iterator to.

Conor

If you've got if you've got two sequences of one to ten, you put those together in a single list. So you've got the values one, two, three, four, five, six, seven, nine, ten, followed by one, two, three, four, five, six, seven, nine, ten. So you want your permutation iterator. I will visually show this to Bryce, but the listener cannot see this. You're at one, and then you want to jump to the 11th element, which is also one. And then you want to jump back to the second element, then to the twelfth element, the third element, then the thirteenth element. And that way, when you c when you copy if with a permutation iterator, you're gonna end up with one, one, two, two, three, three, four, four, five, five.

Bryce

This this sounds similar to an iterator that I wrote for thread scheduling a while back, and by a while back I mean like ten years ago, which I called a spiral iterator. Because when you're um when you're stealing from work cues in a in a high performance threading system, you want to steal from the work cues that are that are closest to you. And so the spiral iterator would it would first check the the queue that's one past you, and then it would check the queue one behind you, then it would check the queue two past you, then it would check the queue two behind you. And it in so it would sort of checks in a spir uh a spiral shape that grows outwards. This kind of reminds me of that.

Conor

Um it's not exactly a spiral, but the only reason it reminds you of that is just because the data is one to ten and then one to ten. If the date if the two lists were one to ten and eleven to twenty, your permutation iterator should just be an iterator that goes fr left to right.

Bryce

It would still remind me of this. Because like you can think of it as going like sh and then going shw.

Conor

And then going sh but like it's only reminds you of that for this data. If you change the data so that when you combine list one and list two, it's just a monotonically increase in sequence. There's no shooing back and forth. The iterate the permutation iterator just goes left to right.

Bryce

Oh, okay, I understand.

Conor

You are correct, it it does do this kind of spiraling thing.

Bryce

Okay, so the permutation iterator you're describing basically has to do the merging. Yeah. So you're asking for a magic black box.

Conor

Hey, hey, I have I'm not hearing any better ideas from you. I'm I'm on three hours of sleep here. I've been up since I don't even remember when. Oh yeah, I almost died on the plane, too. That was crazy. That was crazy.

Bryce

You almost died on the plane. Yeah, yeah. You want would you like to elaborate?

Conor

Yeah, I would like to elaborate. Although my girlfriend said that I I didn't almost die, but you know, she's a doctor, so what does she know? Um she says I tend to the over be overly dramatic at times. Yeah. But I went to sleep on the last hour of the flight to Reykjavik from Toronto, and I I slept with my head on like the pullout uh tray table, because I'm not fancy like Bryce, you know, in first class with the kick out bed or whatever. And I woke up.

Bryce

We're we rarely are in first class, we usually fly in business class.

Conor

Okay. Well, you know, potato, tomato, tomato. It's just semantics as a callback to episode 187. Uh anyways, I woke up, long story short, I had I think cut off some of the blood, however, my neck was sleeping to my brain, and so my brain was like extremely short of oxygen, and I felt so lightheaded, I was like, I thought I was gonna be sick. And then I asked the guy if I could go to the washroom, and I got like halfway to the back of the plane and basically like passed out coincidentally, like right next to a doctor. She was like, Oh, this guy needs help. And uh I didn't like I didn't I didn't come to and like realize what was going on for like four minutes. Like I was if you've ever had like a head rush, imagine that times a thousand. Like I my head was so high in the clouds, no pun intended.

Bryce

I was just You're lucky they didn't divert you're lucky you didn't get a medical diversion.

Conor

Well, we were we were 30 minutes away from Reykjavik, and I'm not sure if you know anything about Iceland, but there's nowhere I I think I literally said at one point, I was like, there's nowhere this plane could like go.

Bryce

And at one point I started not if it if it if it had been if it had been like 30 minutes earlier, it could have been diverted to London, Edinburgh.

Conor

No, that's past Iceland.

Bryce

Oh, this was to Iceland. Yeah, yeah, yeah. You connected in Iceland. I understand that. I understand. I thought you were talking about going to Norway, yes. Okay, yes.

Conor

Oh, yeah, yeah, yeah. This was the Toronto to Iceland leg. I understand. And yeah, once at one point I started talking about Oprah because uh three sisters and a mother. Uh I watched a lot of Oprah uh when I was in high school. And there was an episode where they were trying to shed some light on this terrible thing that was happening where high school kids were basically like purposely asphyxiating, they were like choking each other specifically to do to like do that thing where you cut your oxygen and blood from the brain, then you pass out, but then when you wake up from passing out, you get like the craziest head rush possible. But it's extremely dangerous, and a bunch of kids were dying from this, and so Oprah had this like special episode where she was like being like, you know, kind of like it was uh don't do this, don't eat the Tide Pods of its day, you know, like uh don't do this really stupid thing. Anyways, I was trying to tell the flight attendants, I was like, oh, this is like uh I accidentally did what Oprah was talking about that one time. Yeah, I don't think they understood what I was saying, but uh well, I'm glad you didn't die, buddy. Yeah, apparently I I wasn't close to death. It was I would have been fine.

Bryce

Uh well we're gonna have to uh call it here because I gotta go run a fairly important meeting um that uh is at 5 p.m. local time, so we'll see if I survive that. So yeah, we're gonna have to talk more about this this merge algorithm. So you you you gotta you gotta research the thing that we do in in Cub is called merge path. I don't know how it worked. If anybody knows how it works, let us know.

Conor

We should just bring uh we should just bring, you know, Dwayne on. Uh Dwayne Merrow. Get him to explain it to us.

Bryce

That's not a bad idea. Not a bad idea at all. Do we want to do that?

Conor

We work. I mean, he's on my team. We could pretty easily reach out to him. Be like, hey Dwayne.

Bryce

Yay.

Conor

We'll just trick him. We'll say we'll say uh hey, we want to talk about scans, and he'll be here in a heartbeat.

Bryce

I think he'd be equally excited about uh sorts and merging. All right, I gotta run.

Conor

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

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

Conor

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