Skip to content
PodSubs
ShowsPeopleGuestsJobsNewsEvents
More
BlogPodCred
Menu
ShowsPeopleGuestsJobsNewsEventsBlogPodCredNetworksSign in
Join nowSign in
  • Shows
  • People
  • Jobs
  • News
  • More
    • Guests
    • Events
    • Blog
    • PodCred
    • Networks
    Join nowSign in

ADSP: Algorithms + Data Structures = Programs

ADSP: Algorithms + Data Structures = Programs artwork

Episode 232: Algorithms! Live from New York!

May 2, 202546 minAudio

In this episode, Conor and Bryce chat about algorithms, overload sets, libraries and more, live from New York! Link to Episode 232 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast: Twitter Conor Hoekstra: Twitter | BlueSky | Mastodon Bryce Adelstein Lelbach Show Notes Date Generated: 2025-04-14 Date Released: 2025-05-02 Thrust Library CUB Library thurst::reduce_by_key thrust::permutation_iterator Clojure partition thrust::transform_reduce Haskell divvy "Algorithm Selection" Blog (std::mismatch) thrust::discard_iterator C++ std::partition_copy thrust::unique_count thrust::tabulate Haskell TranslatemapAdjacent Hoogle Translate iota 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.

ConorLive from New York, it's Monday night. A pine cone? Was that a special thing in New York? Oh, I was gonna say, is we got lots of pine cones in Canada.

BryceWhy are we talking about pine cones? Anyways, you know, I know the comedian who who bombed tonight uh tried to make a callback that failed, but I've got a callback in this episode that I think is gonna be very successful, which is the callback to the reduce by key example that we gave earlier, where you want to reduce um each row in a matrix.

ConorHow'd you feel about the squid fries?

ShimaI expected potato fries with the squid-like essence. Instead, they were pieces of squid that were fried. So I was very shocked. And if I could get French fries at this hour, I would.

BryceInstead of big algorithm library, which is what we have today, that we should have gone with small, composable algorithm library.

ShimaWe're okay with a if then situation where if dog then cat. There, I tried to loop it back into technical things.

ConorWhoa, whoa, whoa, whoa, whoa, whoa. Listen, listen, folks! Welcome to ADSP the podcast, episode 232, recorded on April 14th, 2025. My name is Connor, and today with my co-host Bryce, we record live from New York. We chat about algorithms, overload sets, libraries, and more.

BryceAre we recording now? Yeah, you're not exactly walking in a straight line.

ConorThis line looks entirely straight. Should we do a sobriety test right now? Yes. Here we go. Boom. Boom. Actually, I think I would pass to be honest. We're here, potentially episode 232 on the streets of New York. Do you actually know what street we're on here? You hold the mic. You'll be doing most of the talking.

BryceI think we're on like 23rd and something. Because we're at the we just left the New York Comedy Club after seeing. I'm gonna say two out of the five comedians were really, really good. No, I'm sorry, Shima. I'm sorry. The guy the guy who bombed. He was awful. Yeah, but but he but him bombing was in and of itself amusing.

ConorJust stop talking about pedophilia, folks. If the crowd's not into it, change topics. Don't keep on coming back to pedophilia.

BryceWhat is and like I've seen people bomb at that club before, and like they always, when like they get desperate, they always turn to lewdness. It's like, anyways, why are we in New York, Connor?

ConorWe're here for a actually, I don't actually know the official name. It is a, I think I'm gonna do my best and then uh Bryce will correct me. It is for a modern CUDA C training, a recently developed state-of-the-art training for targeting NVIDIA GPUs. Is is how close was the title of quote modern CUDA C training, end quote?

BryceHow I I think I got that that that is that is what I would call it because the actual official name, which is like Fundamentals of Accelerated Computing and Modern CUDA C ⁇ , is way too long, that's a mouthful. But anyways, Connor is here in New York because uh well you weren't planning on be being here. When did you even when did this even materialize?

ConorSo, yes, to our global listeners. I was asked, uh today is April 14th, I believe. Apologies to my meetup uh attendees that I had to move a meetup that we were supposed to have tonight. Uh I wasn't I was asked initially one week ago on Monday if I was available to help with the training. And I said, if you really need me, the answer is yes. What is this? USPS? Is that what you pointed at?

BryceNo, there was a pine cone.

ConorA pine cone? Is that a special thing in New York? Oh, I was gonna say is we got lots of pine cones in Canada. Why are we talking about pine cones? Anyways, I was asked a week ago. I said uh if you need me, yes, but um I I don't once again I have to say folks, um I'm sorry to disappoint some of our listeners, but if you know, you can tolerate an opinion you might potentially disagree with. Uh we are temporarily trying to boycott the states. It's not going very well because I'm gonna be having three different trips down here over the next two months.

ConorThis is the first of the three. But yeah, you know, things are a bit crazy. Anyway, so a week ago I said yes if you need me, but preferably no. It turns out they did need me. You notified me on Wednesday, I got approval on Thursday, and here we are on Monday. And uh yeah, we're here with my beautiful fiance. Do you want to say hi, sweetie?

ShimaHello.

ConorWhat a lovely voice. And uh, and so yeah, we were here for a training. The training I think went phenomenally.

BryceI think it was well, and I should I should explain that like I got asked to do this training like 10 days ago, which is a little bit short notice. And it's not this is not like a training I've done before. This is like an eight-hour training, but I you know, like I give a lot of talks. If if someone asks me to give a talk at work, like I'm like, sure, fine, whatever. But they like I was initially told, like, oh, there will be like 20 people, and I was like, all right, that's fine. Like 20 people, like we like to have a 10 to 1 ratio of instructors to students. So I'm like, I'll find one person in the New York area.

BryceAnd so then I ask, like, we there's a lot of people on my team who like live in New York. There's maybe like four or five people, and I ask all of them, and they're like every single problem, like one person's like, I gotta take my dog somewhere, one person's getting work done in the house, renovations, like, like everybody had something. I was like, uh oh. And then and then like we have some planning meeting, and somebody's like, oh yeah, there'll be 80 to 100 people. And I'm like, wait, that is a lot more people than I expect.

BryceAnd so now, like, my search expands beyond New York, and I'm asking like everybody who I even remotely work with in Boston, and then I'm like, oh, Toronto's nearby. So maybe I'll ask Connor. Long story short, we ended up flying two people from Toronto in, and then uh two people from Boston came, and then one person came all the way out from California for like less than 24 hours to uh to do this training. But it turned out great. We had a great time. We taught people lots of things about CUDA C. Great questions were asked. A fun time was had by all, and I have not lost my voice yet.

BryceProfessor Bryce is uh maybe that'll be a thing. Maybe that'll be a thing. We'll see.

ConorAnd I will say they were phenomenal students, if you will. I mean, they're all professionals, so maybe calling them students isn't the right word. But yeah, great questions.

BryceAnd there was one really interesting question. So one of the examples in the talk was this is a problem that a recent talk I gave in uh on CUDA C, I started talking about uh I gave an example of using some of the reduced by key algorithms. We've talked about them on the podcast before. But we were uh like the canonical example of reduced by key is you want to like reduce the uh rows of a row major matrix C. Like you want to do one reduction for each row. And so reduced by key, what it does is it takes a uh a sequence of keys as an input and then a sequence of values as an input.

BryceAnd for each run of consecutive keys, so for each sequence of consecutive keys that are all the same, it'll reduce that that set of values. Um and so if you've got a row major matrix and you want to reduce each row, well each row is contiguous. So the key that you use is just the row that that particular element is in. But what if you want to do a reduced by key of uh the columns? Well, the columns are not contiguous, so the key sequence for the column of each cell would be like 0, 1, 2, 3, 4, 5, 6, 7, 8.

BryceAnd reduced by key, it it only works on, it only combines consecutive keys that are the same. So if you have a bunch of keys that have the same column ID, but they're not next to each other in the key sequence, it doesn't matter. They're gonna be separate groups. And so someone was asking, well, how would you do uh reduced by key on that? And just there's you know, you could have a new algorithm, like an unordered reduced by key, or one that like does a sort or something. But uh we were we were sort of theorycrafting there, and you know, uh Connor, I was saying I think you can do it with reduced by key.

BryceYou just need the right type of iterator. And Connor, you suggested how it can be done.

ConorI mean, it's quite obvious. And uh and also, too, it's obvious for me because in a research project I implemented an algorithm that was called chunk fold, where chunk is the equivalent of the C23 chunk that takes an integer, uh, which is basically this, right? You're you're the doing a chunking by an integer size and then folding afterwards is the equivalent of doing a row-wise summation on a 2D matrix. And the way that I do that is exactly what you did. So the column-wise one is is pretty intuitive, and then we have a fancy iterator in thrust called the permutation iterator.

ConorAnd so you could just build up that index uh permutation sequence that gives you the columns. Would it be efficient? Definitely not. Uh, but it would it would get the job done.

BryceAnd so the idea here, I think, is that you would have the key sequence where you'd have all the column IDs contiguous, and then you would the the value sequence would be the thing that would be the permutation iterator. So in effect, you're doing like a reduce that also does a transpose of the data, like a reduced by key with a transpose built in there. And it's actually interesting because there are more efficient ways to do a transpose than with the permutation iterator. And so, like, maybe we need to have some sort of transpose iterator that under the hood the library could recognize that it's a transpose and use some efficient transpose mechanism.

BryceBecause the problem with doing like the the um the reduce, like the the the column summation, the problem is that you're doing a gather. So you're you're striding through memory with these big strides, and so that can be inefficient. Uh, and so there may be a slightly more efficient way to do this. I don't know. I don't know whether there's like some way to write some transpose iterator that's gonna be better or that would be recognized by the underlying algorithms. But it was a really good question that someone asked. And uh and now I want to go and I want to add it as another example to uh to one of my talks.

BryceI don't know. Did you did you have any interesting encounters with people today? Did you learn anything new?

ConorUh did I personally learn anything new? I don't think so. But I think I my overall takeaway is that the the folks at this corporate entity that Well, I don't believe you.

BryceThere's no way you didn't learn one new thing, at least.

ConorI didn't learn one. Oh, um yes, I mean actually I I did learn I thought you meant from the questions and the interaction with the students. But uh from the trainings, yes. I mean, uh uh similar to one of the other trainee individuals, I did not know what the third uh integer parameter of the triple Chevron kernel launch is, and that was for dynamic shared memory. Yeah. Admittedly, I spend very little of my time writing raw kernels most of the time.

BryceYou should not. That's a bad you should not do that. You should not do that because it's very hard to do that correctly, and there's libraries, and you should just use libraries.

ConorWhich is which is 67% of the point of the training is target thrust, target cub. We have many very optimized Baikuda Ninja libraries that you can use so that you do not have to write your own kernels. And so I don't I don't want to throw our other uh TA under the bus, but someone asked, what is that uh third uh triple chevron uh parameter? And in my head I was like, yeah, I didn't get asked that question, but I would have also had to ask, and it was for dynamic shared memory. Uh so yeah, I did I definitely did learn.

BryceYeah.

ConorAnd uh so definitely I learned a few things. Um what was a few of the times I was actually working through the training because I had not seen the training before. Um I always forget that uh with NVCC generic lambdas are not supported, so I I naturally always reach for uh auto-type in the parameter list of a host and device annotated lambda with MVCC, and that'll fail to compile. It's a simple fix, but almost like every single time for the first couple examples, I would write that and then be corrected.

ConorUh there's a few other things too. I can't remember them all off the top of my head. But yes, from the training itself, the like uh not in the first half, definitely all of that stuff is uh my expertise. Uh but in the the second half of the training, definitely there was some stuff I picked up.

BryceI feel like there were other things we were supposed to talk about. God, I have a list somewhere. But after after eight hours of talking and then a comedy show, my brain is is not sufficiently like you know, there to remember things. But what else what else are we supposed to talk about? What else?

ConorI mean, we went to dinner. I mean, Shima was there. We can get Shima's review on the comedy club. Uh you said what, two of the I think two of the five were good.

BryceThe there was uh the first and the last. The first no, the first and the second. The first guy who who had he had a he had a joke, his last joke was about uh or his last sequence of jokes. There was this reference to these tortoises, you know, being intimate, and the guy was wearing like two or three jackets, and he kind of looked like a tortoise, and I swear it was intentional. I swear that man intended to look like a tortoise. He was funny, and there was this uh this uh this tall uh Jewish fellow who had a very, very long face who's talking about his crazy neighbor, and uh and I just thought I thought he was the best.

BryceI thought it was hilarious.

ConorWhat say Yushima? We're giving the mic over to my fiance. Her I don't know, not first time, but you've been on the podcast a few times before. Here we go, we're sitting down. Which we'll try not to upset the other patrons.

BryceSharing that comedy club is crazy. Nobody cares um what I think about comedy.

ConorThere are many people that care.

ShimaOkay, let me see. So my review of the comedy show is that admittedly it's better than Toronto comedy. We're very familiar with the Toronto comedy scene. And I have to admit that the New York comedy is better. So I'll give you that admission. Other than that, there were five comedians, two women, three men. Four out of five, I thought were very funny, and I think objectively people would think it was funny. There's just one guy that bombed. Which is okay. That happens. Yeah, nobody really related with his jokes, and that's okay.

ShimaBut the other four were very funny. So it was a good, it was a good night.

ConorWas it the other four? I mean, I know the last one, she was pretty good too. Was the other one pretty good?

ShimaThat's actually the other one was very funny, yeah. She was the one that was like, uh, yeah, like I pr people say, like, don't you pray? She's like, I meditate.

ConorOh yeah, yeah, yeah. Just in a the same direction five times. That was that was pretty good. One good joke. Price is wait, before I move over, because we're we've got this kind of we're separated by this big white table here. And we we gotta record for at least like 50 more minutes to get a full episode out of this. Um what else would you like to say? We went to a Korean restaurant tonight with uh some other NVIDIA folks. A lovely dinner. We talked shop, a lot of talk about the future, the plans for the the training, the company.

ShimaThe singularity.

ConorThe singularity, yeah. What was your review of the the dinner?

ShimaIt was a great dinner. What else was there to say? Lovely food, lovely company.

ConorHow'd you feel about the squid fries?

ShimaI expected potato fries with a squid-like essence. Instead, they were pieces of squid that were fried. So I was very shocked. And if I could get French fries at this hour, I would.

ConorAnd this is totally off topic for this podcast, but we had two different individuals talk to us about our potential future acquisitions of pets, specifically dogs and a little bit cats. Uh have we has our as a you know, partnership, has our view evolved of what we will be acquiring?

ShimaWe're okay with a if-then situation. We're if dog then cat. There, I tried to loop it back into technical things. Because you guys refuse to talk technical.

ConorWhoa, whoa, whoa, whoa, whoa, whoa. Listen, listen, folks. It's a very technical podcast.

BryceI did I did my part. I did my part.

ConorYeah, Alsa too. You know, uh Bryce is known for, you know, we are Mr. and Mr. Tangent, you know. We talk about how many episodes have we had, Bryce? Alright, say goodbye, sweetie. I'm gonna go over there and we're gonna continue recording.

ShimaGoodbye.

ConorThat's such a lovely voice. We're mariner, folks. We're mariner. How many times, Bryce, have we started recording an episode? And like two minutes in, we went in a completely different direction, and the first two minutes was this is what we're gonna talk about, and then the remaining 28 minutes is we talked about absolutely nothing to do with what we talked about in the first two minutes. How many times?

BryceI think that's it's been a lot of times. I think that's I think that's my fault. I think that's on me for the most part. Oh gosh, I'm trying to think about what else you were supposed to talk about. Oh, what else are we?

ConorYeah, we can spin this into the topics that we had before that we never got to on the previous recording. You wanted to, so anyways, this is the um this is gonna be one episode, folks. So we're gonna we're gonna call this I don't know, New New York, New York plus something else. The training was great. Hope to do this again in the future. And I think the yeah, the folks at the training they they loved it. I think they got a lot out of it, and they were great. Spinning back to a couple episodes ago, the last time we recorded, we ended up doing the Tesla or not to Tesla and talking about AI a bunch, and we didn't get to overload sets.

ConorDo you want to talk about overload sets right now? Or do you want to talk about the stuff that we were supposed to bring up from earlier today? Because we can take this in two different directions. I mean, that was one of the topics that you want. What? I don't know. I think there was a few other things that you wanted to talk about from earlier today, but I'm not sure which ones you were.

BryceI feel like I'm slowly Oh god, I'm turning into such a C personality. I feel like I'm slowly over the course of many years assembling content for a book, which I know like every every person once they reach a certain age in the C community starts writing a book. But uh I've been thinking more about like design. And um and wait, wait, one second.

ConorExcuse me? Excuse me. Did you guys forget a phone?

BryceOh, oh, Connor just noticed that somebody left a phone. Connor, the hero, the hero. So alright, I I will I hate to do this to my coworkers. I hate to do this to my coworkers, and I'll preface this by saying, I don't mean to shame anyone, okay? I don't mean to shame anyone. I'm not, this is not a tactic to push forward any changes. However, I'm gonna explain a situation.

BryceSo we have an interface. Uh uh, there's this this method on a should we move to these couches over here? We can move to those couches. We'll tell the story about the cookies. All right, I'll tell the story about the cookies now. So we were at this training all day. I was doing the lecture part, and then there were these instructors who were going up for the interactive parts. So I was talking a lot, and I was told at lunch, well, first of all, at lunch I picked a box lunch that did not have a cookie in it. And I was sad, so then I picked a different box lunch that had a cookie in it, but that cookie was not particularly good.

BryceAnd then I was promised later in the day that there would be a cookie bar, and you know what happened, Connor? Was there a cookie bar?

ConorUh there was not, and the patrons that were attending the training did get live updates when we came back from break and there was no cookie bar.

BryceBut then one of my coworkers who had come in from Toronto, Ashwin, uh, he uh he asked where I would get cookies from, and I mentioned, well, there's you know Levine, Levine, there's uh Maman, uh a couple other places, and then he offered to uh order cookies for the uh the whole team. And uh I was a little hesitant, but I was like, you know what? I could use a cookie. So we got these Levine cookies, and these Levine cookies, they are they're not really cookies, they're like cakes. They're like they're like big, thick things.

BryceIt's like a thousand calories. But uh I I ate I ate one of them nice and warm, and it was it was just perfect. Anyways, back to overload sets. Um so yeah, so this again, apologies to my coworkers, don't mean to make anyone feel bad, but there's this method on a class, and it's called weight. And there's two different overloads of weight. One overload takes no argument, and the other overload takes a object.

BryceAnd the first overload of weight, when you call it, it blocks the caller. The second overload of weight does not block the caller. It tells the object, you object, should wait upon this thing that I'm passing to you. So, like the the the object that you're calling it on is this thing that we call a stream. And so the first overload of weight that takes no argument, it says, hey, I want to block until this stream of work is is finished.

BryceAnd then the second overload of weight says, tell this stream of work to wait on another stream of work, but it does not block the caller. And I think that this is not the correct design. Because I could understand if you just had the second semantics. If you had the function, you called it wait, but it didn't block. It just told the thing to wait upon some other thing. But I can't. Cannot abide having two uh uh uh overloads, the same thing, where one of them will block the caller, but the other one will not block the caller.

BryceI think that this is confusing, and I think that this is not good interface design. And I feel that a good overload resolution set should have the same semantic behavior, and for anything that has a subtlety, like for example, whether a parameter is modified, whether or not the function blocks, things like that, anything that's got caveats that requires nuance to understand should be the same across all of the all of the members of that overload set.

BryceAnd if there is two different, you know, if two different overloads in this overload set have some subtle nuanced differences, like one of them synchronizes and one of them does not, then those should be two separate functions. Or if one of them modifies a parameter and one of them does not modify that parameter, those should be two separate functions. And I feel like there is some fundamental design principle here that belongs in the book of Bryce API design.

ConorThe Book of Bryce. I look forward to to reading that.

BryceHonestly, yeah. That is what I would call it, I'm sure, because you know, my ego is very large.

ConorYeah, I mean, uh I like it. I like it. I mean, I don't think anyone would expect anything less. Um honestly have nothing to add. I I completely agree. And when I I was trying to like brainstorm in my head what are the the good overloaded functions or APIs that I can think of. Like the the one that came to mind is from Clojure. It's a partition function that is kind of a sliding window or chunking function where it it takes a sequence and chunks it into different sequences. I I don't remember what the default behavior is.

ConorI think it's uh a chunking behavior, but it has overloads of it, which lets you set the stepping and like the windowing size, you know. And you know, it's basically that the API that has the fewest parameters just has defaults basically for the others. So the behavior is achievable by the one that has an overload that has more parameters. And so definitely the what you're talking about here, it's like you can't get to the first weight function from the second one, correct?

ConorBecause it's just completely different semantics. That's correct. So yeah, I mean like you're telling me this, and yeah, it just sounds it just sounds like I like that rule.

BryceSo I like that rule that if it's if it's an if it's got if the overload is that there's like multiple like new additional parameters, if it's like some of them are defaulted, that that you should be able to get to the most defaulted version from the the more explicit versions. I think that that is that is another good rule to go into the book of design. Yeah, I like that rule a lot. Well, there's another rule that um I remember when we were designing my first committee paper, the uh binary binary transform reduce, there was, or maybe it was one of the scan algorithms, but there was it was one of these algorithms that takes a bunch of different parameters.

BryceLike it takes like two operators, and then like maybe maybe it was one of like maybe it was like the binary-binary transform reduce. So it took two operators and then an initial value. And there was some question about what the ordering of the whether like whether it should be like operator one, init, operator two, or like init operator operator. And I thought that init operator operator made more sense, but uh stl, not the not the library, but the person who maintains the Microsoft standard library, um, he made this argument that when when you have these additional parameters for new overloads, that they should sort of be additive, that the order should be the same, that you should not, if you have like a three-argument version and a four-argument version, that the position of the of the arguments should not move.

BryceLike if the th the third argument should not become the fourth argument in the next overload, that if it was the third argument in the in the version that had just three arguments, that it should remain the third argument and that the fourth argument should be added. And and that that was why you should have this somewhat unintuitive ordering where it's like operator, init, operator, instead of having the init come before both of the operators. And I thought that that made sense too, and I guess it helps with like overload resolution to avoid ambiguities in some cases too.

BryceBut his argument was not about the disambiguating, his argument was just that like like that this is the more natural way to to to have it uh be. And that that that was compelling to me.

ConorWell, what's uh what's interesting about that is I agree with what you're saying, but I know the exact thing you're talking about, and that is that the thrust transform reduce and the C17 stood transform reduce have a different parameter order. And I'm almost positive that thrust is the one that does uh binary operator init binary operator, but the std transform reduce from C17 does init operator operator.

BryceWhich it is possible that younger Bryce was stubborn and at the time fought for and successfully advocated for the order that made more sense to him, and only later, retroactively in my mind, I came along, I came around to agree with STL. And it's also possible that we only realized the mistake too late and that we weren't able to fix it. Well, because I mean a nit's always necessary, so I thought that the one that was I think this was I think this may have been in the order of maybe the parameters for the scan because um inclusive scan and exclusive scan, because in in exclusive scan you always have to have the initial value.

BryceUm whereas in an inclusive scan it's optional. So in an exclusive scan, the order is um you know inputs, outputs, initial value with operator. Um and then for inclusive scan it's um uh uh operator initial value uh because uh you uh uh uh you can have the operator without an initial value with inclusive scan, but for exclusive scan, you always have to have the initial value. So it might have been something around one of the scans or maybe around the transform scan um algorithms, the the compound transform scan algorithms, that may have been it.

BryceThe transform inclusive scan and transform exclusive scan. I remember it was something with two operators. And the transform inclusive scan and transform exclusive scan have two operators because they had the scan operator and they had the transform operator.

ConorOkay, uh yeah, that makes sense. If you're talking about the scans, I was thinking about the transform reduces.

BryceUh somebody could go to like the meeting minutes from like 2017 C committee meetings and find when STL made these points, it would have been in like the library minutes from very early committee days. But uh I think that the the key point is that is this argument is not the specific history here, but this argument that STL made that that about that if you have uh uh an overload that takes two arguments and an overload that takes three arguments and an overload that takes four arguments, and that the that it's additive, that that it's the s the the the first two arguments are the same in all on all four of these overloads, that you should not move if it's the same argument, you should not move around its position across different overloads.

BryceAnd I think that was compelling to me.

ConorYeah, I mean that completely syncs with my sense of like you should be able to replicate, like for instance, in in the same kind of partition function enclosure that leads to a couple of these sliding chunking functions, Haskell only provides you the most generic version where you provide a step value and a window value, which you can spell the stride, chunk, and slide versions by specifying one and a value of n for either or of the parameters.

ConorBut the point being is like at the generic level, you have you can spell everything. You know, it's like it's when you I I posted that blog post once that talks about how std mismatch is the most generic version of a bunch of you know, is sorted, it's and whatnot. Like sometimes you don't need two uh sequences, you just need one sequence, and so you can ignore the second iterator to, you know, you're kind of bending and and uh what did what did Ben call it? It's like you're you're bending the algorithms in a perverse way, that's not how they're intended to be used, but you can spell a single iterator like reduction with a two-iterator algorithm by just ignoring one of them or discarding one of them.

ConorAnd it's this idea that you at the top level you want to be able to spell everything. And so, anyways, to getting back to the the weight API, if you're if you got different semantics and it it's doing different things, that yeah, it just um like I I have nothing to add to that in that uh other than that, I just like I agree. Yeah, like if it's got different semantics, that sounds like it should be two different APIs, right?

BryceAnd you know that what you just were talking about about uh the discarding there made me think of um you know, we have this special iterator in Thrust called a discard iterator. And it's something that I don't think we ever really see uh we don't have in the standard library, and it's because there's not really algorithms that need it. And the reason is I don't think there's any algorithms really in the standard library that take two outputs, are there?

ConorUh there is only a sync actually let's play a game. It came up in a past episode. Probably the listeners might know. There's only one alb algorithm that outputs to two different output iterators. Can you name it? Probably not.

BryceI don't is it one of those set ones or something? Or like the partition or something like there?

ConorIt is, it is. It is partition copy.

BryceYeah.

ConorSo partition part takes a unary predicate and everything that passes it writes to the beginning, and then everything that fails writes to the end. Uh, so that you end up with a partitions kind of predicate sorted sequence. Partition copy does the same thing, but it just it's a linear pass. Anything that passes writes to the first output, anything that fails writes to the second output. Um, other than that, though, um, so yeah, it's potentially if you only cared about the first, but like if you only care about the first, you know, predicate passing elements, that's that's just a copy if.

ConorYou don't you don't need to use a partition copy with a discard iterator on the second output iterator. We have an algorithm for that, which is why it probably doesn't exist.

BryceAnd uh, you know, I know the comedian who who bombed tonight uh tried to make a callback that uh that that failed, but I've got a callback in this episode that I think is gonna be very successful, which is the callback to the reduce by key um uh example that we gave earlier, where you're you want to reduce um each row in a matrix. Um and uh these by key algorithms in Thrust that take both a key's input and a and a values input, they uh they take two outputs, a key's output and a values output.

BryceAnd this is useful because in some cases you you you want to keep you know what you want to keep the association of this was the key for this group, you know, the this this group of values that I reduced, this value that's the aggregate of this you know group, I want to know what the key is. In the case of the you know, row-wise reduction, if our if our key is what row am I on, then in this output vector, the the you know, each the index of each element in the output vector corresponds to what the row was.

BryceAnd so you don't need the key's output here. And you don't want to write the key output to somewhere in memory if you don't need it, because that's gonna waste memory, badwith, bandwidth, and it's gonna race waste storage. And so Thrust has this discard iterator. And what a discard iterator does is it when it's dereferenced, it returns this proxy object that when you assign to it, it just does nothing. So it just like ignores the write.

BryceUm and because we have these by-key algorithms in Thrust, and we also have a couple other types of algorithms that take two outputs, um, and because of these, we we have this discarded iterator in Thrust. Um, and I think it's most commonly used with the bi-key algorithm. So there's a few other places where it's used, but uh until we introduce bi-key algorithms to the standard library, it's not something that we would that we would need. But this is one of the one of the fancy iterators that we have in Thrust that we showed in the course today, but that's just not something that's in the standard library yet because there's a bunch of algorithms in Thrust that aren't in the standard library that really ought to be, like these bi-key algorithms that let you do these batched operations and are really quite powerful.

ConorWell, I mean, we we're gonna have to revisit this topic because um I mean it's it's been too long that I've been working on the stuff that I've been working on that ha hasn't been published, but it is imminently this year, uh especially after the most recent stuff that I've been working on. It's gonna be out in the wild, people are gonna be able to use it, but two of the motivational examples that I talk about are Unique Count, which we spent much time in Venice many years ago. Was it many years ago? We don't know, but it was it feels like a long time ago. But Unique Count, which is really just uh a zip iterator with a not equal to pass to a reduce, which ultimately I'm not sure if we actually ever revisited that topic.

ConorBut anyways, unique count is a it is a hand-rolled specialization of fancy iterator plus algorithm. Transform reduce, a hand-rolled, similarly spelled version of a fancy iterator, transform iterator, plus uh an algorithm reduce. And I realized there's a third one today in Thrust, and it is Tabulate, uh, which is just uh a counting iterator, aka iota for my array language fans out there, plus a uh transform.

ConorAnd it's one of my big motivating points is that you know we have these hand-rolled bespoke algorithms that are a combination of a fancy iterator and an algorithm, but it's the algorithms that we provide you that do these are limited. It's tabulated, it's unique account, it's transform reduce, and then outside of that, you have to go and compose them yourself. Whereas we could be providing you with an API that does this all behind the scenes and makes it a lot easier. Like it's still a it's still a fantastic resource. Don't go write your kernels by yourself, reach for this stuff.

ConorBut I think in the future we could be providing you a more ergonomic way to spell this stuff that does it automatically behind the scenes. Stay tuned, 2025, hopefully gonna get published.

BryceSo, one of the reasons why we do the the composed operations, one of the arguments, like one of the arguments for things like transform reduce and transform inclusive scan and transform exclusive scan um is that it's more efficient uh on some platforms, some backends uh for like the parallel version to have these fused algorithms instead of being able to um uh well okay, the argument at the time, but this was before we had ranges. So the reason that we had like transform reduce was because it's more efficient than doing a transform followed by a reduce, and we didn't have a transform iterator at the time.

BryceI think that was the argument. Um and and you know that there's there's also this claim that like, okay, like maybe thrust should have a tabulate because maybe there's some there's some faster way under the hood that we could do transform plus counting iterator. Um I think in practice it's not. I think in practice it just maps down to that. But there are certainly there are some cases where there's something that could be expressed as you know a composition of other algorithms where there's a more efficient way to do it. However, and and there's an argument that we don't know what all of those cases are today, and that for common use cases, it makes sense to have a named algorithm so that maybe we come up with some faster way of implementing it.

BryceAnd there's a bunch of cases in Thrust where we know that there's a faster way of implementing the algorithm, but we implement it through composition today just because it's not been it's not been an important enough use case to implement the faster path. Even despite all of that, I think that there's an argument to be made that instead of instead of big algorithm library, which is what we have today, that we should have gone with small, composable algorithm library. And like one of the reasons that I feel this way is that if you think about the surface area of the algorithm library as being just like a couple of key entry points that are in then composition on top of them, one I think it makes it easier to port to interesting new targets and back ends, especially for parallelism, but also I I think it would give people a stronger intuition about how to compose.

BryceLike if instead of having instead of having count, um if if you just had, you know, like reduce, and instead of having like max element, you just had reduce with max, I think that if people had to write reduce with max, instead of writing max element, people might think more about composition and in customizing algorithms with composable iterators and ranges, and that might mean that they would be more likely to use reduce with some, you know, compositional thing instead of writing their own function.

BryceAnd so maybe, maybe we made a mistake in going with, you know, the big algorithm library, and that a smaller set of composable primitives would have taught people a different programming model that would have made them think more about how to compose things, and that people would spend less time writing raw for loops and reinventing the world.

ConorI 1,000% agree with this, and I have thought a lot about too like introducing this kind of library, the pedagogy around it, and you know, there are these high-level generic, you know, scan, reduce, map. But there are other algorithms in that category, and like literally in the docs, I'm not sure if you noticed on the um the hyperlinks on the side of that screenshot I sent you, there's a star next to like in each category, you know, one index maps, you know, there's a uh star at the top with map, and then everything else is just a specialization of that.

ConorAnd there's certain algorithms that like fall by the wayside that you know, my Google Translate website, map adjacent, which is what it's called in Haskell. It was initially called adjacent difference in C11, then it's called the JSON transform in C23, it's called prior and Q, it's called zip width and Haskell. It's it's this algorithm that falls by the wayside, and so people don't even recognize it by name. But the point being is that teach people the generic version, give them specializations, but let them know that like if we're not providing you the specialization, it's just a custom binary operation that you can pass to one of these things.

ConorI see. She must tell and leave. Do not leave. I'm gonna put this in the episode. Do not leave me. Do not leave me. I thought she was happy, folks, with her head on my chest and getting head pets, but she could not suffer through one more word uttered about binary operations and algorithms. So we're gonna wind this down in the next we said two, but I'm gonna extend it to three.

BryceI mean, I I think there's maybe a middle ground where we could have just explicitly defined the algorithms that are compositions as saying like these are compositions. And in fact, in thrust, because that's often how we define things, like we when we're teaching thrust or in the documentation, we like explicitly say, like, you know, like in fact, like like this is equivalent to that, and in fact, it is implemented that way. Like, I commonly, when I'm talking about transform reduce and thrust, I often say, yeah, in in thrust, the you know, speed align implementation of transform reduce is just reduce called with the transform iterator.

BryceWe do not customize the transform reduce, you know, algorithm for the CUDA back end. We just rely on the generic one that just calls reduce with the transform iterator. Um, and I think like telling people that, like, you know, they can still call the easy transform reduce version, but like being able to tell them that I think it makes people really like get the compositional aspect that like we rely, like it's the most important algorithm, and we rely on the composition for that speed of light code path.

ConorSomething that's crazy though, and uh hopefully this doesn't go to four minutes when I we initially said two, but then I extended it to three. But it's that I see the love of my life is nicking my leg, telling me that she wants to go brush her teeth. We're gonna leave it all on the pod, folks. Is that uh tabulate is the name for counting iterator, which is a poorly named Iota. So, like the name in C.

BryceYou think wait, you think the counting iterator is a poorly named iota? I think iota is a poorly named counting iterator.

ConorThe point is there's disagreement, but so here's what's crazy, folks. In C11, it's called iota. In thrust, it's called sequence. As an iterator in thrust, it's called counting iterator. So we've got sequence, iota, counting iterator, and then if you add the counting iterator to the transform algorithm, you get tabulate. So now we've got iota, we've got sequence, we've got counting plus transform equals tabulate, and on top of that, in rapids, the counting plus transform iterator was such a common pattern, we created a new iterator called the counting transform iterator.

ConorAnd all of this is to say, is that like, yes, I agree that hard coding some of this, if you got a happy path, whatever, but the point being is you want to do all the different variations. So just build build the composable version, chef's kiss. Final words. We're signing off, we're in New York, we're at the Evelyn Hotel. I'm not sure how Bryce is getting home. What are your final thoughts, Bryce? Tell the people what they need to hear.

BryceWell, I was just wondering about like, you know, okay, what's the archaeology of why do we have sequence and tabulate and counting iterator? And I realized, and this is a great cliffhammer, I realized we could get answers to all these questions because we our coworker Jared creates the library that we talk about all the time. We could talk to Jared.

ConorWe need to talk to Jared, and we're also gonna bring on Georgie, who gave, in my opinion, what might have been the best. It's up there with prices from the GTC 2025 conference. We gotta get Georgie on because this new uh hands-on start with Thrust, go to Cub, write your own kernel, and how do you write your own kernel that matches the speed of life that's offered by Thrust and Cub? We're gonna have them on, we're gonna talk about it. Links in the show notes. Final thoughts once again, signing off.

BryceI I was able to hold my sneeze in until you finish getting your audio up. All right, Bryce needs to see live from New York. It's Monday night.

ConorAnd Shema's asleep now. She has been a super trooper.

ShimaBye.

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.

Open the transcript file

Hosts and Guests

Nobody is credited on this episode yet.

Credit the people on this episode

Be the first to rate this episode

More episodes

All episodes
  1. Episode 313: C++26 Reflection vs CRTP, AI, Kids & More with Zach Laine

    Nov 20, 202647 minAudio

    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:...

    • Apple Podcasts

    Credit the people on this episode

  2. Episode 312: The C++26 Contracts Fiasco

    Nov 13, 202652 minAudio

    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:...

    • Apple Podcasts

    Credit the people on this episode

  3. Episode 311: Career Changes, GPUs & More with Zach Laine

    Nov 6, 202628 minAudio

    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...

    • Apple Podcasts

    Credit the people on this episode

  4. Episode 310: Leaving NVIDIA for... ?

    Oct 30, 202624 minAudio

    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...

    • Apple Podcasts

    Credit the people on this episode

  5. Episode 309: Default Construction & CppCon 2026 with Jason Turner

    Oct 23, 202629 minAudio

    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:...

    • Apple Podcasts

    Credit the people on this episode