Conor 0:00

Alright folks, well this has been fascinating. We're f from from this little square in Venice that we're sitting in. We hope you enjoyed our this is kind of similar to the Lost Reduction series that we did where we went, you know, three different issuer iterations, except this one all happened within a three-hour period or four hour period.

Bryce 0:17

A three-hour period in a car and wandering around the streets of Venice. So I think this is gonna be it for the uh for the road trip.

Conor 0:35

Welcome to AD SP The Podcast, episode 147, recorded on June 21st, 2023. My name is Connor, and today with my co-host Bryce, we continue to record live from the Slovenia 2023 road trip. This time while walking through the streets of Venice. In today's episode, we revisit the implementation of our Parallel Stud Unique. Alright, folks, we said goodbye on the highway on the way to Venice, but here we are.

Bryce 1:09

Live from the streets of Venice!

Conor 1:11

This is a first, folks. We took you on the road, and now we're taking you on a walk. We are headed to Austria, Ala, Gustafa, something like that, right?

Bryce 1:23

Something like that. And we are in the southeasternmost part of Venice, and the restaurant seems to be a lot further west. So we got about 30 minutes of walking.

Conor 1:33

It is fantastically beautiful here.

Bryce 1:37

Nice, serene, quiet, peaceful in the area that we're in. There are birds chirping, there's nobody on the streets. It's lovely. We are about to cross a bridge. And we took a boat to get here. We dropped off our rental car, our trustworthy steed for the past four days. We dropped it off at the uh the the entrance to Venice. And then we took a little boat uh that took us uh six stops here, and it was a lovely journey, I thought. What did you think?

Conor 2:06

I thought it was fantastic. And now we're gonna chat. Oh, I don't know why.

Bryce 2:12

Well, well, we're gonna chat because we got to the hotel room, we checked in, and Connor, we had been talking earlier about how to implement unique in parallel, and I came out of the bathroom and Connor was just sitting there staring at his suitcase, lost in thought, and he said, I think I figured it out.

Conor 2:28

Yeah, honestly folks, I I apologize. It's gonna be interesting to see how we edit this and how much of the original back and forth we keep in. But I just realized that uh adjacent difference as it exists in Thrust currently, now renamed in the rangeland adjacent transform, is really just uh a map. It's a map looking at two different indices, and it could be a fancy iterator. We don't have a fancy iterator called adjacent transform, but you can actually spell it currently in Thrust with the zip with the zip with the zip iterator and with the transform iterator.

Bryce 3:10

Okay, how do you do that?

Conor 3:11

You basically just zip together two iterators, one pointing at the first element, one pointing at the second element. You zip that together, and then your transform iterator is going to be whether or not they are not equal to each other. Perfect. And ooh, and yeah, and then you're gonna have to use, but that is the copy if that is used. It's using the stencil. So you're using the zip iterator, checking whether they're not equal to each other as the stencil, aka the sequence that's gonna determine whether we copy elements, and then the sequence that we use to copy elements is the original sequence. So there's an overload there that doesn't exist.

Bryce 3:46

I think you should probably explain the stenciled overloads because I don't, those are not part of the standard library, but uh you're referring to the stenciled overload that's just in thrust, right?

Conor 3:54

Correct, yes. This only exists in thrust. I think we actually have talked about it two or three times before, and the last time or one of the times we talked about it, the closest thing that I can think of, um, because it doesn't really often uh exist in too many programming languages or libraries that I've come across, but it does exist in Excel in the form of the sum if function, where you can basically point at two different ranges and you sum a range based on some predicate or you know unary function that evaluates or some condition of another range.

Bryce 4:26

So for like for example, I use that function a lot in a lot of my like accounting uh spreadsheets where I'm like sum up all of the values in this column if I set another column to true or something.

Conor 4:38

Exactly. And currently the copy if as it exists in the STL, this is this is ridiculous, folks. We gotta stop and take a take take a photo here. We're basically on the seawall of Venice here, walking a walking to dinner, recording an episode. I mean, our life is surreal.

Bryce 4:55

We uh life is pretty surreal.

Conor 4:57

We we're so grateful.

Bryce 4:59

Very great, we are very grateful to our all the conferences that invited us out here to speak in Europe, to our employers.

Conor 5:06

Uh I mean my my employers are not paying.

Bryce 5:11

Our employers were generous enough to uh uh support us coming to these conferences, even if they weren't uh paying for the travel, they were supporting us coming here as part of our job function. We didn't have to take off uh vacation for this.

Conor 5:24

I'm on vacation right now. Um I mean, I mean I didn't take off vacation when I was at uh at the conferences uh two weeks ago before Switzerland.

Bryce 5:33

Fair this is vacation for me too. I meant I just meant that the like the parts where I'm at the conferences, that's not vacation.

Conor 5:38

Yes. Anyway, super grateful. I mean, it's very amazing that we're doing this podcast live on the seawall of Venice. Uh very beautiful, very sunny.

Bryce 5:48

And and of course we are thankful to all of you, the listeners, uh, because I don't know that we would necessarily be here without uh without all your support.

Conor 5:56

This is true. I mean, the reason for this part of this trip is because we got an email about our podcast statistics that said we were the number eight ranked technology podcast in Slovenia, and so now here we are just outside Slovenia in Venice. Anyways, thanks to everybody for listening. This is wonderful. Feel very grateful in this moment. Back to the STL. The copy if and all other algorithms don't have any overloads that take sort of this uh third sequence, if you will, or second sequence, if you will, that is used. So when you make a call to copy if and you are evaluating a predicate to like copy the even elements, you're always applying that uh predicate to the sequence that you were going to copy from. There's no ability to, you know, evaluate that predicate on a different sequence and copy from another sequence. So thrust thrust has that overload, and the point is that you know this the uh zip iterator combined with the transform iterator to make a uh hand-rolled adjacent transform iterator is going to evaluate to trues and falses. So we obviously don't want to copy those trues and falses, we want to copy the original sequence, which is going to be the values, anyways. And so I just I realized while I was sitting on the bed that I I have one realization is that you Bryce mentioned that we didn't need to do the second unique in the original implementation, and I was thinking, yeah, you could have actually just made sure you don't copy when you were doing the merge. So however you implement that merge, you can deal with the edge cases there as well. So there's a couple different ways to make sure you're avoiding that last unique.

Bryce 7:26

I didn't think about that.

Conor 7:27

Yeah, and then but I was thinking, and then I just realized like, wait a second, this adjacent transform is just basically a modified transform iterator. And transform reduce and other algorithms are just basically transform iterators. Uh you make use of them before you pass them to some final algorithm. And the final algorithm here is copy if there's no reason you couldn't do that anyway. So that's why I was staring, and then I was about to explain to Bryce while I was sitting on the couch. He's like, What's wrong? And I was like, No, I'm just thinking about I I think I I think you can do it in a single pass. And and then I was about to explain it, and he was like, No, no, no, no. We're gonna we're gonna record a podcast while we go to dinner, and I was like, I'm not we're not bringing the mic, and he's like, Why not?

Bryce 8:05

And uh no, so often you and I have a conversation, and then and it's a great conversation, and then afterwards we're like, aha, that should have been a podcast episode. And so I was just trying to preempt that. And it's like sometimes we start to have a conversation, and then we're like, no, no, no, can't talk about that right now. We gotta save it, save it for you, the listener.

Conor 8:22

And so maybe I actually will go and open a PR. I mean it takes forever to build thrust, but this is actually something like I know that this uh zip uh zip iterator combined with the transform iterator trick has it does exist. I'm not sure other places in Thrust, but I've definitely seen CUDA code uh or thrust code, if you will, that uses this pattern. So I I don't think there's actually any reason why it wouldn't work, and then we have successfully achieved Rice's goal of eliminating the linear storage for this.

Bryce 8:51

Well, and here's I have a couple questions. Um, so first of all, when when we were in the car, I looked at the CUDA-specific implementation of Unique and confirmed that it was the version that you described. Did you look at that version or did you look at the generic version? And the generic version did that head flags thing too.

Conor 9:09

I was looking at the version in the generic.nil file. So if that's what the generic is. It it's interesting to me that um And wait, just to fill uh listeners in, Thrust is built in such a way that there's multiple backends that it can target. So it's targets uh I think Thrust building or what thread building blocks from Intel. Anyways, there's a bunch of different backends including CUDA, and so when you go and look at the implementations, usually I just check the generic.

Bryce 9:35

And one of the key things about the way that Thrust is designed is to implement a backend, you only actually have to implement a couple of functions like reduce and for each. And if you implement nothing else, then there are generic versions, generic overloads in that generic folder that will get picked up, and they are implemented in terms of those primitives. Um, so like for example, if you didn't want to implement your own, you know, find if, then you could just implement a reduce for your back end. And when somebody calls find if with your backend, it would call the generic version of find if, which is defined in terms of reduce, and then that would call 3D or reduce. But maybe on your platform you wanted to implement your own version of findif because you wanted to do something that was going to short circuit or that was otherwise clever. You could then provide your own customized version of findif and then that would be found instead of the generic version. However, the generic versions in Thrust are often a good way to look at what is a like like general purpose, generic, good way to implement this algorithm in parallel. Because oftentimes looking at the specialized version for a particular implementation, it's a lot more code, it's a lot harder to like understand. And so oftentimes when Connor and I want to, you know, figure out how something's done in parallel for a particular algorithm, we'll just go and look at that generic folder in thrust.

Conor 10:57

Yep, so anyways, I interrupted to explain why we're talking about generic versus kudo. What were you what was your thought, or do you recall what you were thinking about when uh it I'm I'm interested as to why this hasn't occurred to anybody else and whether we're missing something.

Bryce 11:14

Like, because the it it is a big deal for an algorithm to need ON temporary storage versus needing no temporary storage. And it was actually a much bigger deal earlier in the development of libraries like Thrust because GPUs used to have a lot less memory than they did today. If if if if it takes ON temporary storage to unique your array, then if you had a GPU that had four gigabytes of memory, you could only unique array of two gigabytes of memory. And now if you have a this algorithm that doesn't require temporary storage, then you could you could work with a day a data set that is twice as large as pre as you previously could. That's a huge deal. Yeah, what is also interesting, not not and one other thing on that point, and and oftentimes I would be willing to pay a lot more computationally for a problem that doesn't need temporary storage, just so that I can fit the problem size onto the GPU. Even maybe it would even be slower in some cases, and that might be okay just because it lets me run with a larger problem size.

Conor 12:24

Yeah, this is uh I think we should definitely. I mean, we've uh we've talked about I think we were supposed to do some episode on some other thrust algorithm and the implementation of it or some change we could make. But this one is actually it's pretty easy to do, like uh it's it's not that hard. And what's even more interesting is uh a whole other layer on top of this, is there is a sibling algorithm that exists right next to unique that doesn't exist in the STL. Um, do you know what it is, Bryce?

Bryce 12:56

I don't. In thrust.

Conor 12:59

It is uh unique underscore and then one more word. So it's like a unique prefix.

Bryce 13:05

Uh don't think it's unique sort.

Conor 13:08

Um actually, now that I say this out loud, there's actually two unique underscore algorithms.

Bryce 13:12

Unique sort too.

Conor 13:13

There's not a unique sort. There's a unique underscore two different ones. Um listener, play along. Can you think of and also these don't exist in the C standard template library. You uh are going to have to be creative if you're not familiar with Thrust to think. Is there unique if? Not unique if. Good guess though. Uh although I don't know actually what unique if would do, because if underscore if algorithms usually take unary predicates, you could change it to take a binary predicate that would replace the default of uh equal to with something else. But uh or maybe unique if that could be the semantics of it, but no, it is not unique if.

Bryce 13:54

Um I don't know, I'm not sure.

Conor 13:56

Alright, the one I was thinking of was unique underscore count. And uh the other one that popped into my head while I was saying this was unique by key, which is one of the uh segmented uh algorithms.

Bryce 14:09

We talked a little bit about the stencil versions of the thrust algorithms. Um how do they relate, if at all, to the by-key versions of the algorithms?

Conor 14:18

So I think we should save this for a follow-up because when I was actually giving my GTC, I want to say it was 2021 Thrust uh Algorithms talk, I gave a tuck comparing STL algorithms in the standard library versus thrust algorithms. I mentioned all these segmented uh algorithms, yeah, but they're actually really, really poorly named in my opinion, because um some of them, like reduced by key, are actually like a segmented reduction, meaning that you, I believe, uh provide a unary uh function or unary predicate, and it's going to then not actually materialize segments, but it's going to do reductions that basically the unary predicate is gonna be the key function that determines where the segments start and end. So for instance, you could do a reduce by key for once again like contiguous odd and uh elements in a row and then even elements in a row. So your unary function would be odd or even, and then you could do a sum, you could sum those uh elements up. So like you can mentally think about this as like creating a sub list of contiguous even elements and odd elements, and then you sum up those sublists.

Bryce 15:30

Yeah.

Conor 15:30

However, there are bi-key algorithms such as sort by key and unique by key, where these are not segmented algorithms, they are algorithms that I believe are the equivalent of the projections that got added in C20 in the range uh overload algorithms where, for instance, um if you want to sort based on like the length of your string, right? Your projection is std colon-colon size, and you pass that as one of the arguments, and now instead of having to write your custom binary operator that does a comparison on the sizes of your strings, you are just passing the std colon-colon size function, and that is basically the semantics of what the underscore bi-key mean for unique and sort. You're passing some kind of unary function that is then performing the uniqueness and the sorting after applying that uh unary function, I believe. And that is a completely different semantics than the segmented uh reductions. Anyway, so this is why I said we can should kind of save it for a whole other episode because I think it's just like a that's like the equivalent of you know, we've got different suffixes and prefixes, and then like having two two different semantics for them. So like if underscore if meant one thing for copy and one thing for uh another algorithm that uses it.

Bryce 16:57

That second meaning I think is in some way related to the stenciled uh versions. Um, and I'd I I think I would have to think more about what that relation is. Um, but I do agree that I think that the the current nomenclature is a little bit confusing. Um so maybe we should do a whole episode on that. Yeah. But uh it is absolutely beautiful here. We are getting to, I think, more the main part of Venice, and uh it's just gorgeous. It is hot also, it is very hot.

Conor 17:27

So the reason I brought up unique count is that the first question is one, how do you think that's implemented? I actually haven't thought I'm I've kind of thought about it a little bit in my head.

Bryce 17:36

A reduction, I imagine.

Conor 17:38

Yeah, so Bryce just said a reduction. I would guess the same thing, however, naively, you could just once again allocate the linear memory and then just do a plus reduction on that. Ideally they don't do that, and you hand roll your own.

Bryce 17:52

Now the real question is, although actually, why do we have a unique count instead of a unique reduce that's generic and that can take like, you know, uh a plus operator if you want to do count or something, or like to the not a plus operator, but but something that would just do a count if you want.

Conor 18:10

I mean, uh perhaps there's no real use for it, but no, my guess is that the implementation, I would hope that the implementation uh doesn't require that linear um like it doesn't require one the the the uh actually the reason that exists has to be that it doesn't require the copy if at the end. But the question is is does it still require the linear allocation for the adjacent difference? And if it does, that means we can turn that algorithm into not only eliminating the uh linear memory requirement, but like uh it's now avoiding the copy if it's kind of weird now because we're in like this.

Bryce 18:52

It's fine. Keep going. We're Bright Bryce Literally nobody speaks anymore.

Conor 18:58

Bryce Bryce is American, so he doesn't mind uh disrupting everyone else's vacation time. Ooh, it's nice and cool in here.

Bryce 19:05

It is nice and cool in here, which is uh pleasant difference.

Conor 19:09

So I do you you have internet on your phone. Are you able to check right now the unique count implementation? Because my guess my guess is that it actually makes a call to adjacent difference. So we could actually do two refactors here, and the refactor on unique count would be would be massive. Like you're changing basically a linear transform into uh a linear memory transform to an 01 mem memory reduction that would be pretty pretty awesome. While Bryce is looking that up, I will just give the give the listener. I wonder if we can get a donut. We didn't get a donut in Croatia.

Bryce 19:53

That is true, and we didn't we failed to get a donut when we were in Italy.

Conor 19:56

We also failed to run a street. We did walk a street.

Bryce 19:59

Are there these there could be donuts here? Let's check it out.

Conor 20:03

I don't want to walk into a store while recording.

Bryce 20:05

I mean there are donuts.

Conor 20:10

But there are donuts. No, there's one sugar donut.

Bryce 20:17

Oh, perfect. What's your favorite? What's your favorite?

Conor 20:24

I do want like a pressant or yeah.

Bryce 20:31

Alright, I'll take one.

Conor 20:34

Hey, we're on vacation. Vacation calories don't count.

Bryce 20:40

Also, I actually am pretty healthy.

Conor 20:43

Bryce trying to make me feel bad about eating a donut. Shame on you, Bryce.

Bryce 20:46

I'm just kidding. You you I mean I ate worse than you.

Conor 20:49

Donuts are food for the soul.

Bryce 20:50

I ate worse than me. And you're in much better shape than me.

Conor 20:56

Thank you. Have a good day. Alright, folks, Coke Zero's in hand, pastries in hand. We're gonna have to find somewhere to sit down now for a second. Alright, we're walking. Bryce did not get to, we got distracted by the donuts and we did not.

Bryce 21:12

The most important thing. I see benches.

Conor 21:14

Alright, we're gonna go sit down on this bench. Bryce is gonna get back to finding the implementation. And we're gonna eat our if we manage to, while on a road trip, refactor some thrust algorithms to eliminate linear uh memory requirements, that's that's pretty I mean I feel like at this point we should not be on vacation and we should be being we should be being paid for this, you know?

Bryce 21:39

No.

Conor 21:40

All the benches are kind of occupied. Hmm. Do we keep walking? What we are going to see if there's a bench on this other side. There's not. I mean we could just sit. We're just gonna sit on this wall. It looks clean enough.

Bryce 22:04

It doesn't look like it'll kill us. At least not quickly.

Conor 22:14

Alright folks. I'm gonna put the mic down for a second while we take a sip of our Coke Zeros, get our donuts. This donut honestly doesn't look as good as the Roman donut I had. First first bite.

Bryce 22:24

Don't worry, folks. I will take a uh I will record this for posterity.

Conor 22:29

We got it, we're recording.

Bryce 22:36

That's a big miss, not a good donut.

Conor 22:38

Compared to the Rome donuts, I'm gonna look at the sugar.

Bryce 22:41

There is a lot of sugar.

Conor 22:43

It's all it's all uh it's all crustied up, you know?

Bryce 22:45

Yeah.

Conor 22:46

You know, we're gonna suffer through it though, folks. Bryce is taking too long. So we're gonna go find, we're gonna race him. And he's not even trying right now, so I'm probably gonna win. Stay stay tuned, folks. Oh, so I so we just came across unique copies, so I guess there's actually there was three.

Bryce 23:02

If you unique copies in the standard too, right?

Conor 23:05

I actually don't think it is.

Bryce 23:07

Maybe it's not. Alright, we're looking it up. I'm looking that up.

Conor 23:10

Alright, here we go. Unique count.

Bryce 23:12

It is a unique copy is in the standard.

Conor 23:14

Alright, I was wrong.

Bryce 23:17

Wow, I just okay, so I just look at look at this.

Conor 23:21

I found the i I found the issue on uh adding the unique count algorithm. And uh there's a little code snippet that shows a zip iterator, and then just count ifing on that. So it looks like they're actually doing it correctly, but this is just a little code snippet, it's not actually the source. But then a year ago, Jake Hemstad, our colleague, uh says that uh, or he CC's me. And uh he CC'd me to ask about naming because I always get involved in this stuff, and I said, long story short, I agree with Jake that unique count is the correct name. But let's find the PR. The PR.

Bryce 24:03

Also, look at look at this. The third result for unique copy on the internet says stood unique copy can be used to remove all the duplicate elements whether consecutive or not. That's not how it works.

Conor 24:16

Unless if it goes on to say, but you need to sort it first. Yeah. In which case then you can. Like, so to say that you can use it to do that is true, but that is not what it does uh for any arbitrary sequence. Uh 14 files changed. Alright, we're we're getting to it.

Bryce 24:36

No, they're they're the code example here is just wrong. Oh, maybe maybe they mean like that like you could if you have two sets of uniques of the same like value that are not sorted, like it will it will remove those two uniques as long as they're next to each other, but it I think that that's a very confusing idea. Anyways, people on the internet are wrong. I'm angry. Alright, we found the PI yet?

Conor 25:02

We have. We're looking at, right now we're looking at a file called thrust detailunique.inl. Now we're looking at system slash CUDA slash detail slash unique.h.

Bryce 25:14

Oh that one's a m that one's yeah, a lot.

Conor 25:18

Ooh. There's a struct called zip underscore adj underscore not underscore predicate. Which is basically exactly what you want. Yeah. And here we go. So we are at unique count, if first equals last, return zero, auto size equals the distance between first and last, auto it equals thrust, colon colon, make zip iterator, and then you've got your make tuple first, and then thrust colon colon next first. So that's exactly what I said. You're zipping the first element uh first element and then and the second element, and then you're making a call to one plus thrust colon colon count if. Yeah, passing it, passing your execution policy, and then passing the struct zip underscore adj underscore not predicate. So interesting that at some point, when was so we're this is very all very fascinating. This got merged a year ago. And this PR was this? This looks like it was merged by Allison, but UPSJ, who is Tobias Ribizel, PhD student, research software engineer on HPC Library for Numerical Linear Algebra. It says that sort of this PR, for the common count to allocate to fill pattern, count if, copy if there are some fill algorithms without corresponding count algorithm. And so he just suggested it. I would have thought that uh this was motivated a little bit by the Rapids libraries because I definitely know that these exist in the pandas and like NumPy libraries. But I guess not. I guess we must have hand-rolled our own. Or maybe when this showed up, we replaced it. Uh but the point being is that even though these are sibling algorithms, they weren't implemented at the same time. These this was proposed and then merged a year later.

Bryce 27:12

But you mean you mean unique count and unique?

Conor 27:14

Yeah, unique existed a long time ago. And because of that, even though they're sibling algorithms, this zip pattern is used in the unique count one, but it's not used in the unique one. So this is basically everything but like 100% confirmation that we can go and do this. Um anything, uh, we're sitting on the ground now. We're probably gonna stop recording so we can go to dinner. I'm not sure if Rob's waiting for us. We sure bought our laptops we could We wouldn't have been able to build it on my laptop, unfortunately.

Bryce 27:41

I gotta leave I got uh we got until 5 30 tomorrow morning when I gotta leave for the airport. Uh but uh I think we can get this done by then.

Conor 27:51

You I don't think so. But um, do you have a box we can build on? Because it's I do.

Bryce 27:55

Okay.

Conor 27:56

A box meaning like a box somewhere. It's somewhere in the cloud, yeah.

Bryce 27:59

No, I didn't bring a workstation with me.

Conor 28:02

Alright, folks. Well, this has been fascinating. We're from from this little square in Venice that we're sitting in. We hope you enjoyed our this is kind of similar to the Lost Reduction series that we did where we went, you know, three different iterations, except this one all happened within a three-hour period or four-hour period.

Bryce 28:19

A three-hour period in a car and wandering around the streets of Venice. Uh so I think this is gonna be it for the uh for the road trip.

Conor 28:27

Well, no, we might talk to Rob.

Bryce 28:29

We might talk to Rob. What's what we hey, we have the microphone.

Conor 28:32

What's interesting too is I talked to Michael Garland, my boss, about this, maybe probably two or weeks ago or a month ago. And this is how this whole conversation came up because we were chatting about the implementation of Unique and about like which algorithms could be stream fused or could take advantage of stream fusion, and Unique was uh not able to do that. And maybe explain what stream fusion is. Uh we're not gonna explain what stream fusion is right now, but we'll talk about it in a future episode. But uh so I was talking with Michael, my boss, about this. We'd we talked about I I asked him, do you know how Unique is implemented? We might have mentioned this a couple episodes ago. He mentioned the adjacent difference and copy if, and then I was like, yeah, that makes sense. But then at that point in time, neither of us thought, like, oh, could we could we do better here? But here we are.

Bryce 29:18

Hey, hey, hey, that's what that's what I'm here for.

Conor 29:21

That's what the road trip is all about. We are uh improving algorithm implementations. You heard it here first, folks. No more linear memory requirements for unique copy. I mean, technically there's a linear requirement for the copy part at the end, but the intermediate storage, not necessary. We're sounding up for now. Enjoy your night, folks. Enjoy your night. We will uh we'll be back soon. Adios. Be sure to check the show notes either in your podcast app or at adspthepodcast.com for links to any of the things we mentioned in today's episode, as well as a GitHub discussion where you can leave questions, comments, or thoughts. Thanks for listening. We hope you enjoyed and have a great day.

Bryce 30:03

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

Conor 30:09

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