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.
BryceYou almost died on the plane. Yeah, yeah. You want would you like to elaborate?
ConorYeah. 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?
BryceI I got I got I got a topic.
ConorPerfect. Save saved our listeners uh from me just rambling.
BryceBoth 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?
ConorSerial merge of just two lists?
BryceYeah. Yeah, yeah.
ConorI mean that's super trivial, no?
BryceI wouldn't be asking if it was.
ConorI 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.
BryceIt's still linear.
ConorIt'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.
BryceAll 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?
ConorYeah, you have to do more comparisons, but that's fine.
BryceDoesn'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.
ConorIt it becomes K times N.
BryceI have to do like Well no, I don't have to do like log K comparisons.
ConorWhy log K.
BryceWell, 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?
ConorBut your values across your K lists are not in a min heap. You just have pointers to whatever value you're at.
BryceRight, right. But I'm saying like I got I got k things, I gotta find the smallest one.
ConorIn 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.
BryceYeah, yeah. Yeah.
ConorOkay, 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.
BryceWell, 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.
ConorWell, 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.
BryceHang 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.
ConorI 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.
BryceSure, sure. But what I'm what I'm saying is it's only uphill from here.
ConorI 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.
BryceYeah. So continue with your idea.
ConorWell, 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.
BryceSo how are you gonna construct this permutation?
ConorSo 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.
BryceJust describe for me again what you want this permutation iterator to what you want this iterator to.
ConorIf 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.
BryceThis 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.
ConorUm 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.
BryceIt would still remind me of this. Because like you can think of it as going like sh and then going shw.
ConorAnd 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.
BryceOh, okay, I understand.
ConorYou are correct, it it does do this kind of spiraling thing.
BryceOkay, so the permutation iterator you're describing basically has to do the merging. Yeah. So you're asking for a magic black box.
ConorHey, 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.
BryceYou almost died on the plane. Yeah, yeah. You want would you like to elaborate?
ConorYeah, 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.
BryceWe're we rarely are in first class, we usually fly in business class.
ConorOkay. 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.
BryceI was just You're lucky they didn't divert you're lucky you didn't get a medical diversion.
ConorWell, 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.
BryceAnd 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.
ConorNo, that's past Iceland.
BryceOh, 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.
ConorOh, 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.
BryceUh 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.
ConorWe should just bring uh we should just bring, you know, Dwayne on. Uh Dwayne Merrow. Get him to explain it to us.
BryceThat's not a bad idea. Not a bad idea at all. Do we want to do that?
ConorWe work. I mean, he's on my team. We could pretty easily reach out to him. Be like, hey Dwayne.
BryceYay.
ConorWe'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.
BryceI think he'd be equally excited about uh sorts and merging. All right, I gotta run.
ConorBe 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.
BryceLow quality, high quality, that is the tagline of our podcast.
ConorIt's not the tagline. Our tagline is chaos with sprinkles of information.