Episode 169: thrust::unique_count and The Algorithm Advisor
31 minAudio
In this episode, Conor and Bryce chat about thrust::unique_count, other algorithms and the algorithm advisor! Link to Episode 169 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Twitter ADSP: The Podcast Conor Hoekstra Bryce Adelstein Lelbach Show Notes Date Recorded: 2024-02-14 Date Released: 2024-02-16 NYC++ Meetup Second City Toronto ADSP Episode 168: Parallel Mode Pull Request that refactors thrust::inner_product to thrust::unique_count thrust::inner_product thrust::unique_count Thrust mode example Mode Python Counter collection thrust::transform_reduce thrust::reduce_by_key ADSP Episode 147: 🇸🇮 SRT23 - Parallel std::unique Revisited (on a Walk in Venice) Jelly Language Jello Max Consecutive Ones top10 GitHub Repo MLIR: Multi-Level Intermediate Representation Overview Haskell group C++23 std::views::chunk_by thrust::unique_count CUDA Implementation thrust::make_zip_function Algorithm Selection - Conor Hoekstra C++ std::mismatch Zig Language Tweet of Jello Algorithm Advisor Intro Song Info Miss You by Sarah Jansen https://soundcloud.com/sarahjansenmusic Creative Commons - Attribution 3.0 Unported - CC BY 3.0 Free Download / Stream: http://bit.ly/l-miss-you Music promoted by Audio Library https://youtu.be/iYYxnasvfx8
Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.
Transcript
From the show. Tap a time to play from there.
BryceWell, and this is why you should use algorithms instead of raw for loops. Because you can do this not only in some array language like Jelly, but you can also do this in standard C. It's a little bit harder, but there's actually there's so there's an effort to develop um uh a new high-level ILR for claying um using the MLIR framework, which is a framework for sort of developing high-level, more language-specific ILRs that are exist at a level above L VMIR.
ConorWhat is wrong with my voice? I technically haven't said no Jesus, I'm gonna sound like I smoke a. Are you uh using your mic?
BryceI am. Oh, but the microphone would not be on me, so that might be.
ConorIt sounds about a hundred times better.
BryceYou know, minor details. I did turn it on.
ConorHappy Valentine's Day, buddy.
BryceHappy Valentine's Day, Connor. How are you doing? We're recording nice and early in the morning.
ConorYep.
BryceWhat are your big Valentine's Day plans?
ConorUh, it's more like a Valentine. Well, we're not talking about this on the pot.
BryceYeah, we are. Yeah, we are. Ramona and I are doing nothing. It's Ramona's birthday, it's February 13th. So uh we went out for dinner on Saturday and then yesterday. But, you know, it's like impossible to go out on Valentine's Day. There's like it's like it's you know, you have to get a reservation. Everywhere has a special menu where they charge you extra. Um, but since her birthday's the day before, it's like we can just go out the day before. It's great. So we're gonna stay at home. We're gonna our little local Korean place though has a special Valentine's Day menu.
BryceSo I may try to talk her into going out to there. But um, but we're probably gonna stay at home, eat take-in or leftovers, and then I don't know, watch a movie, read books. We're gonna be lazy. So there's like a foot of snow in New York, but we're we're up in Albany, and there is uh there is no snow, which I'm very upset about because it didn't snow at all in New York last year, and I love the snow.
BryceSo we really missed out.
ConorWell, I'm sure you'll be back to the big apple soon.
BryceYeah. Yeah. Uh Friday, actually. And you're gonna come down to the Big Apple.
ConorThis is true. This is true. March 5th to 8th.
BryceWe will be me, you, and Sean Parent.
ConorYes, I we I'm excited. We should actually check the New York C meetup. We happen to know that it is on March 7th, which is the Thursday, I believe. But as of this recording, which for those of you that know when Valentine's Day is, is February 14th. It is not posted on and I assume this is the NYC Plus Plus meetup, not the New York C developers meetup, um, which hasn't been active.
ConorYeah, there's two New York meetups, but this one hasn't been active for a couple years, and then the NYC Plus Plus is the one that Adobe kind of quasi-sponsors now. But yes, there should be a meetup for the C folks. And also, if you're not uh interested in C and you just want to come and hang out for an evening, Bryce and I will be there. I believe Sean Parent is the speaker, if not one of the speakers. No, he'll be the speaker.
ConorAnd yeah, should be a good time. You've uh you've booked us some plans on the Tuesday night. We're going to a I think I saw a comedy club. I accepted a bunch of invites.
BryceAlthough our our our plans our plans may change because uh the dinner venue's gonna change a little bit. But uh yeah, the plan is I think we're gonna go to a comedy club and then go go get food some more.
ConorYep, looking forward to it. Love comedy. Was just at Second City on Monday in Toronto. Not in Chicago.
BryceHopefully, nobody's heard of Second City in Toronto. Is that even a thing?
ConorUh it definitely is. There are three different second city locations. Toronto, Chicago, and I believe New York actually is the other one.
BryceYes. I think it's New York and Chicago. I don't know about Toronto.
ConorI mean, from what I've been told, the a lot of Canada's top comedians come out of Second City.
BryceUm, like Oh, Canada's top comedians. I'm gonna I'm gonna get so canceled for this long time. Have you heard of Mike Myers? Uh I have heard of Mike Myers. Canadians are too nice to be comedians. Uh is that true?
ConorDo we have any mean comedians? I guess that's true. Mike Myers was nice. Jim Carrey was really nice.
BryceHe admits to it.
ConorI mean, it's why that's a thing, is like America.
BryceYou have a Ramona's giving me a look like this is the important podcast content that you need to be recording. So we better get down to business before she comes over here and kills me with a debtor fork.
ConorWell, I mean, we were talking about the C meetup. So link in the show notes. We will add it in post whenever it gets posted. Do you have a topic? I mean, I was gonna we I was gonna follow up on what we chatted about last time because I am I am thrilled with the refactor of the thrust inner product to be count unique. And there's two follow-ups.
BryceThe first follow-up is that Wait, wait, wait, the uh the thrust the thrust inner product of the case?
ConorYes. Uh yes, that is exactly technically not count unique, unique count is the name of the algorithm. But to recap, we were solving or walking through the parallel implementation of the mode algorithm, aka more commonly known as, outside of the world of statistics, as most frequent element. And there's like a one-liner way to solve this in Python where you just reach for the counter collection and then you do a max reduction by looking at the values and then get the key corresponding to that.
ConorPretty straightforward. But the way it worked in the thrust example was to sort, then to do an inner product to get the unique number of keys, and they did that with an inner product, which we refactored to a unique count, then do a reduced by key, and then do a max element at the end of all that. And the two follow-ups are that not only did that example use inner product, which it shouldn't have, my tool or project, yet to be named, yet to be announced, also was using not unique count.
ConorI have sort of this example that generates a reduced by key, and it does the exact same thing where it counts the number of unique keys, but the code that it generated was a count if using zip iterators, which is basically another way to spell how to count the unique number of keys. And when you combine that with the fact that we spent a whole episode in Venice talking about unique count. Do you remember this? When we went and got the donuts and sat and sat in that little square, we initially, that whole sort of um theme or topic theme through our Slovenia trip was how to implement unique in parallel.
ConorBut we we ended up at unique count because I had mentioned that I had had a conversation with Michael, my boss, about how to implement uh unique count, and that you know, one way to do it is with copy ifs and actually calling unique, but you don't actually need to do any of that at the end of the at the end of the day. You can just do a reduction, a count if. And when you combine the fact that like I have this tool that I've done this, I've written this exact similar code to this parallel mode example, didn't reach for unique account.
ConorAnd then you, staring at this code, weren't able to immediately recognize that this inner product was a unique account. And we spent a whole episode in Venice talking about how we could optimize the implementation of unique account. And we actually never followed up from that whole series because you might not remember, but at the end of that, we like we said, we need to go refactor this to make sure that we're not materializing anything in this unique account because we were looking at this struct that was called zip underscore adj short for adjuston underscore not, which was basically a struct that would bundle, it would basically do the trick of zip iterators and complementing your your binary predicate, which you don't really need that.
ConorBut at the end of the day, we thought that that was like calling it was some kernel that was materializing anything. It wasn't. It was basically just the zip iterators. So the refactoring that we said we needed to do, actually we didn't because unique count, calling count if using this little struct was doing the optimal thing. It just looked a bit weird. And so my my my the end of my whole ramble and this sort of you know follow-up is how or how do how did we both miss this? Like in looking at you looking at the parallel mode example, and then in me doing something similar in my own project.
ConorAnd it's like, one, how did that happen? And two, I had this idea once, which I actually have implemented in Jell-O. Maybe I should whip out Jell O again. Back-to-back jello episodes, folks. And let me share my screen. We said we won't do this, but honestly, we're not gonna be, we're it'll be easy for Bryce to explain what I'm about to do here.
BryceSo if we for me to explain. Uh Connor's going in to spin up jello again.
ConorLet's make this full screen. So we're launching Jell O. So let's actually just see what happens if we do this. If we do plus fold on a list of numbers, and actually let's just do five, and then if we do iota, what do you see here? So I the expression that I just wrote essentially was iota plus fold five.
BryceYeah, so he's got an iota to five, and then he's got a plus fold. Uh it says plus fold can be replaced with sum, and then it shows the steps of the algorithm, and the first one is it shows the list of one, two, three, four, five, and then the second one shows the sum of the two. And then it says this is a one-two-q monadic chain.
ConorUh everything after that I've highlighted we can ignore. It's it's really the first part that I'm trying to highlight here.
BryceThe plus fold can be replaced with some.
ConorAnd then what does it say right out of that?
BryceAlgorithm advisor.
ConorYes. Let's look, let's look at another example now. Say that I want to say I want to do the maximum consecutive ones problem, NCO. MCO.
BryceYeah, that's a fun one.
ConorSo if I do this, I typed out just a list of ones and zeros.
BryceI go group and he's got ones and zeros, folks. He's grouping them. He's lengthening them. He's eaching them. And again, it says, alright, so if he's he's got lists, and then he's got group len each. And it says group len each can be replaced with group len algorithm advisor. And it also says that len each can be replaced with len each, or with len space each can be replaced with len underscore each.
ConorSo do you remember at one point that we actually had a meeting where we talked about the idea of something like this?
BryceWhere Yes, I do. I was just about to say, did Jell-O steal this from you, or did you steal this from Jell-O?
ConorNo, no. I Jell O is a I wrote this whole tool.
BryceYou wrote this tool for Jell-O?
ConorJell-O is my tool. I wrote the whole thing.
BryceOh. I didn't realize that.
ConorOh, yeah. Sorry. So Jelly is a pro is a programming language written by, I mean, his online alias is Dennis Mitchell, which is the name of the character from Dennis the Menace, so I'm not actually sure that's his name. It could be. And I wrote a wrapper around the language, which is this tool that basically, if you look at the things in yellow, the atoms in yellow, this OE ligature G, L, and then I think that's the British pound symbol.
ConorThat is that is jelly syntax. So that is actu the actual jelly program for group len each. So jelly is just basically a keyword-ified jelly language. And a part of this tool I realized is that they have so many, like when I hit space, they have so many of these functions that come with the language that half the time I forget that, like, oh, there's a len each or a group len or a specific specialization of some kind of reduction. And so I basically just added a dictionary/slash regex matcher that will let you know when you're using a suboptimal composition of algorithms.
ConorAnd this just brings me back to my observation about the fact that both of us missed opportunities to use unique count, even though we spent like a whole journey. Not a whole not a whole four episodes, but like we got to the fourth episode, and then we're like, what about unique account? And I think we both consider ourselves like algorithm experts, yet we still miss this stuff.
BryceWell, and this is why you should use algorithms instead of raw for loops. Because you can do this not only in some array language like Jelly, but you can also do this in standard C. It's a little bit harder, but there's actually there's so there's an effort to develop uh a new high-level IR for Clang using the MLIR framework, which is a framework for sort of developing high-level, more language-specific IRs that are exist at a level above LVM IR.
BryceAnd one of the cool things that somebody's doing with Clang IR is looking at optimizing and analyzing usage of standard algorithms. And you can if if if everybody expresses their algorithms in terms of the named set of algorithms in a language, then it's pretty easy to write an algorithm advisor for that language. But if you write your things in terms of raw for loops, then the compiler has to figure out, okay, well, this for loop that this person wrote, this is really a bespoke, you know, uh uh unique count.
BryceAnd I can tell them that that they can optimize it in this way. But it's a lot harder to identify that than if you're just like, oh, well, this is an inner product that does this, and oh, actually you can just like like this thing should just be that. Like that, like one of the one of the big benefits of a uh sort of an array style programming model where you're working with array where where array operations are your primitives, not raw for loops, where you have named array operations and be that in C or in an array programming language.
BryceOne of the big advantages of that is that those array operations can be one, implemented in some optimized way by the platform, but two, the platform can look at the composition of different array operations that you're using and identify opportunities for optimizations across those that composition. And that is very, very powerful. And so that that is that is the way by which your like hand-rolled, bespoke, low-level C4 loop can be beaten by higher level code.
BryceIt's entirely possible that you could write an algorithm in something like using some tool like Jelly and get better performance than something like CUDA C simply because when you write it with Jelly, it tells you, oh yeah, you know, you could write it this way instead. And you've and and that thing that both of us, who are probably, I think, considered experts in algorithms, missed, the tool won't miss that.
ConorThat is that is yeah, one of my you know life goals basically is to build this kind of thing either in the form of a library or the form of a language. And like it should be mentioned that the initial one, recognizing that like a plus fold can be replaced with a sum, there's no there's no perf advantage there. But in the example here, when you're doing a group, a group being something that's basically the equivalent of a chunk by, so you're splitting a range up into a range of ranges, and then when you do len each, which is the equivalent of transforming basically a std.
Conorcolon colon distance or std colon colon ranges colon colon distance, this can recognize that at least for the jello implementation or the jelly implementation, a group len each is gonna materialize each of the sort of subranges and then calculate what the length of that, because this is just jelly is implemented in Python at the at the end of the day. But group len doesn't materialize it. It basically just like while it's going through, it it at the same time it's going through it and in quote unquote grouping, it you it's using uh iter tools and more iter tools, which is like Python's iterator facility.
ConorSo um it manages to avoid something that's much less efficient, which depending on what you are lowering this down onto, you could do something extremely similar, right? Like imagine someone that is not aware of unique count and that's making use of thrust unique, and then we're just able to programmatically see, oh, you did a reduction right after this unique. We can just like switch that for you.
BryceYeah, it's you know, I I more and more think that um writing uh writing array primitives yourself instead of using like existing array primitives and using like array style programming, like writing this all by hand is more and more like handwriting assembly uh in instead of you know using some language in an optimizing compiler.
ConorYeah. And that's the thing, like it's already writing efficient either CUDA C code or even you know efficient code that just calls thrust algorithms or cub algorithms is already like a non-trivial thing. Yeah. Like pointing case, episode 168, last last episode. I managed to notice it, but even it took me a second when you were, I think I was trying to take my COVID test, and you were like, hey, hey, hey, pay attention, we need to figure out what this is doing. I read through it, and my first thought actually was like, oh, this is a count if, and I was like, wait a second.
ConorI saw that then I read the comment and I was like, I immediately thought, I'm pretty sure I'm doing this wrong in my own tool. I'll see if Bryce sees it. You didn't see it, and then in the back of my head, we were already running long on that episode, but my thought was like, how are how are we missing this in two different instances? When at the end of the day, perf-wise, the inner product, my count if in my gen my generated code, and the unique count ultimately all do the same thing. So it's not like there's any perf loss, but like from a readability perspective, it's so much more difficult to figure out what that inner product's doing.
ConorAnd in not all cases.
BryceI'm not I'm not sure if that you're right about the um no perf loss, because um unique count in thrust for the CUDA backend has a bespoke uh bespoke implementation.
ConorUm and I don't I don't know that the inner product will lower down to the like isn't the bespoke implementation the count if with that zip add not struct.
BryceNo, no, no, no. That's the generic implementation. The gen for that works for all backends. There's a bespoke kernel for unique count. I'm actually looking at it right now. In the bespoke. Share your screen. Share your screen. Oh, maybe it's just for unique though. Um let's see.
ConorI was gonna say, I'm almost positive because I've I've looked this up now three different times. And the one in the CUDA.
BryceUh no, no, no, no, no, no, no, no. No. It just says this.
ConorYeah, yeah. So so it is. We'll link, we'll we'll permalink this for folks. We'll permalink it to the GitHub line in the main repo of Thrust, which now lives in the NVIDIA CCCL repo. But yeah, it's a so it actually does use a zip iterator. So actually, I have I have no idea what the zip underscore adj underscore not predicate. Like it seems like that's totally unnecessary.
BryceSo what it does is it calls countif, it calls it it makes a zip iterator um of uh zipping adjacent elements. So it basically it's like taking a range and doing adjacent to with it. And then it does a count if on that range and it uses a zip this zip adjacent not a jig.
ConorYou know what this zip8 not predicate function is? So there is a thrust make zip function where you pass it a binary predicate and then it'll it'll apply it to something that has been passed to a zip iterator. So this is basically that exact same thing, but it also performs the complement. So it's basically composing not with zip make zip function. Yeah, I think this should not be like a one-off. Really, there should be a way that we can just compose like a a not fun, because isn't there like a std not fun that does the does this exact thing?
ConorIt will complement the result of a binary predicate. Or even, I guess technically it just complements the result of something that returns uh a Boolean. Anyways, we should we should uh whether we build an algorithm advisor for C or for Thrust.
BryceYou know, and you know what's funny? My word count example that I've I've used for years um could also be implemented with unique count instead of transform reduce. I only just realized that.
ConorYes. Yes. Yes. And this is the thing, is like you've been giving that talk or that example in variations of talks since like what, 2016, I think is the first one I remember seeing.
BryceYeah, but it's it's earlier than that. It's from like 2014. And that's the thing, is like no one Yeah, and unique count would make it so much clearer what it's doing. It's it's because the the way that the parallel word count works is you're basically you like you have some predicate to determine what the end of the word is. Like, okay, when do when do I have a space on the right? Uh like when I have a sp a a non-white space character followed by a space character, that's the end of the world. And then get like that's the transform part, and then the reduce part is just counting all of those instances of the end of a word.
BryceSo what is a parallel word count? I am like counting all all the places, uh uh, you know, all the unique words, all the ends of words.
ConorYeah. And so this is actually another fantastic because we've got we've got like five minutes left. This is a fantastic note to end on that I had temporarily forgotten I wanted to bring up. And first of all, it's actually you're in the clear, because unique count. I looked up the PR, wasn't added until 2022. You're in the clear, buddy. Oh so that's a good good thing to mention.
BryceWait, wait, wait, wait, wait. Why was it added?
ConorIt was added, I think, because someone pointed out that it was a useful algorithm to go along with all of the reduced by key algorithms.
BryceYeah, I kind of remember I kind of remember its addition.
ConorI will we will leave because I I went and found the PR that added it. Because I for those that checked the show notes, probably nobody. We or I went and created a PR to refactor that mode example, and then in the PR, I linked to the other PR that added unique count to initially to thrust. But here is the last note I want to end on, and that is unique count is not like technically it's fine that there exists an algorithm called unique count, but this is not like the correct generic name for this algorithm.
ConorAnd I actually gave a lightning talk at one point called algorithm selection, where I showed that all of these algorithms, like is sorted and is sorted until, and then adjacent find, all of them are in this hierarchy, and the root algorithm that sits at the top of the hierarchy is do you know what it is? It's the arguably the worst named algorithm in all of C.
BryceUm I don't know. Mismatch is what I think what comes to mind. That is it. It is. It is.
ConorAnd that's because really what mismatch is, is it's zip find.
BryceUh I I followed my intuition and it paid off.
ConorYeah, you're crushing the quizzes these years. You're crushing the quizzes. Zip find not is essentially like the generic name for that algorithm. And in this case, like we have the exact same thing. Unique count is at like one of the leaf nodes of this tree, and transform reduces at the top. But in the middle, we've got like a version of count if that bundles this zip iterator pattern. And if you recall, the very first talk I ever gave at C now, I showed a sequential algorithm to solve a problem called dangerous teams that was adjacent reduce, which was basically this transform reduce with the built-in pattern of the zip iterator.
ConorAnd so my point here is that unique count really shouldn't be implemented in terms of countif. It should be implemented in terms of some parallel version of transform reduce called adjacent reduce, where you still have two binary operations, one that performs this transform and one that performs the reduction, but then it takes care of that zip iterator trick for you. Because this pattern is so common. It's so common that even before I had entered the land of parallel thinking, this adjacent reduce thing is so common.
ConorAnd the reduction here is really just summing Booleans. So your binary predicate would be not equal to, similar to the inner product, and then your second binary operation that does the reduction would just be sum. And so, really, then at the end of the day, all you would see inside of unique count is just, you know, a call to adjacent reduce. And really, unique is just like, I don't know, once again, you can still have the algorithm there, but there is no unique in range v3. There is an algorithm called adjacent remove if.
ConorBecause really, unique is just an algorithm which is which is a better. It just does compaction based on a binary predicate.
BryceUnique doesn't capture the fact that it only removes like consecutive things.
ConorYes.
BryceLike if you if you if you tell people who don't know, don't have any of the background, like what does a unique operation do? They're gonna think like it removes all the duplicates.
ConorYeah. I mean and is unique count even the I know that like unique now has a meaning in C, but if you were to have I guess you yeah, you can't do it with adjacent remove if that wouldn't be the best way to do it. It would just be to have like a call to adjacent reduce, at least in parallel land. In sequential land, it'd be fine to call, I guess, adjacent remove if, and then follow that up with a a fold. But anyways, the point being here is that just these names, you know, we can we can be doing better here.
BryceOh yeah, I mean it's all a mess. It's all a big mess.
ConorAnd and really, at the the last thought I have in my head is like, is it better to have like an algorithm advisor that tells the user, hey, here's a better thing? Or is it just better to have a library or a language that like the compiler or their or your tools will do it all for you? So like you never need to think, should I write it way A, way B, way C? At the end of the day, it can just see through everything and will always do the most efficient thing. I think that's honestly what like devs want.
BryceThat's what people want, yeah. I mean, I and I think the question is can we I mean, I clearly we can do that in array programming languages, but the question is can we take those techniques from array programming languages and bring them to um to Python to Rust to C? I think the answer is probably yes.
ConorYeah, stay tuned, folks. The update on Andrew Kelly.
BryceOh yeah, I meant actually maybe Yeah, that was my other thinking, which is that it's been a while since we've had some guest episodes, so let's let's let's bring on the guests.
ConorYeah, maybe I'll maybe I'll fick I'll I'll cut this in somewhere, but we had actually let's go let's go get their name because we love it. We love it on ADSP when people reach out. So on episode 168, we had a couple people ping us. One of them was one of them was Marco Sidentop. Phew. I probab I probably butchered that pronunciation, but thank you, Marco. He pinged us and said, for contacting Andrew Kelly of Zig, I recommend talking to Loris, who is the Zig's VP of community.
ConorAnd um I went ahead and did that. I DM'd Loris on Twitter. Twitter Twitter got back to me. Loris got back to me and said that Andrew's very busy, but he is interested in going on podcasts when he's less busy, and he'll ping us when he is available. So probably not anytime soon, but maybe sometime in 2024, we will get a message from Andrew and we will figure out who we're gonna guest host next time. Be sure to check your 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.
ConorThanks for listening. We hope you enjoyed and have a great day.
BryceLow quality, high quality, that is the tagline of our podcast.
ConorThat's not the tagline. Our tagline is chaos with sprinkles of information.
In this episode, Conor and Bryce chat with Zach Laine about C++26 Reflection vs CRTP, AI, kids & more. Link to Episode 313 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP:...
In this episode, Conor and Bryce chat with Zach Laine about the C++26 contracts fiasco. Link to Episode 312 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...
In this episode, Conor and Bryce talk with Zach Laine about his career and the career changes he has made. Link to Episode 311 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials...
In this episode, Conor and Bryce talk about Bryce's next chapter and where he is leaving NVIDIA for. Link to Episode 310 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The...
In this episode, Conor and Ben chat with Jason Turner about default construction in C++. Link to Episode 309 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...