In this episode, Conor and Bryce chat about how to implement a parallel mode algorithm. Link to Episode 168 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-07 Date Released: 2024-02-09 ADSP Episode 167: Phone Tag Zig Language Van Gogh Starry Night Lego Mode cuCollections (parallel hashmap) Jello Haskell id Jelly Language Python Prompt Toolkit cub::DeviceRunLengthEncode C++23 std::views::chunk_by Haskell groupBy Haskell group C++20 std::views::transform Tweet of Jello Solution thrust::sort thrust::inner_product thrust::transform_reduce thrust::count_if thrust::unique_count thrust::reduce_by_key thrust::max_element Rust max_by_key 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.
ConorIt's a two-range transform reduce where you're looking at adjacent elements, and then the the binary operation that you're applying to those two adjacent elements is not equal to, and then you're doing a reduction of plus. So here's what's beautiful is that this is a bit obfuscated. There is a much, much nicer way of implementing this.
BryceIt's amazing to me how often we see these like fundamental parallel algorithmic patterns come back.
ConorToday with my co-host Bryce, we chat about how to implement a parallel mode. Alright, well now I'm recording too. Alright, you looking at my screen?
BryceYes, but you need to you need to be slow and gentlemen.
ConorHit the Windows key. Type sound. Leave the play black. Oh no.
BrycePlay black? Play black. Play black?
ConorPlay listen, listen, alright, listeners. If this makes it in, I apologize. I am I'm pretty deathly ill right now. The fact that I'm even recording this is a testament to the importance that I the the reverence that I have for the platform that we we've created. 167 episodes. This is gonna be 68.
BryceWe've been cutting in pretty close though. We used to always have like a queue of episodes in the pipeline, but like the past two to three weeks, it's just been like, oh crap, it's Wednesday or Thursday, we gotta record something. Although I gotta say, that's true. I think uh I think phone tag one of my favorites.
ConorI mean, here's a question while we're fixing our audio, because my audio is still clipping like crazy. Did you actually listen to the fourth part?
BryceIt's on my speed list. I'm gonna do it today, hopefully.
ConorI knew. I knew he wouldn't have folks.
BryceBut importantly, I did actually listen to the second part, which was you. I did I didn't know. Well, that's because you needed to in order to be debated not listening to the second part.
ConorThat actually would have been pretty entertaining. Everyone would have been like, what the heck? But then I would have, I would have, as soon as I heard what you were saying, I was like, I got it. He just he didn't listen. He just recorded his own side of the conversation. Anyways.
BryceI actually I actually could have pulled it off because I in in my in my second message, the third part, I I asked a second. Kind of was starting a new topic, yeah.
ConorYeah, yeah, yeah. You could have just said, oh, that's really interesting, really interesting. Got a follow-up question, and then that would have been that would have been funny. Um anyways. Hit this little speakers thing, click properties. Well, we're not gonna fix it in today's episode. I will look into this and uh we're supposed to have a guest, but we reached out should we should we say who we reached out to? Sure. Te tease the listener.
ConorWe reached out to Andrew Kelly, but he's a busy guy, I guess, and he did not reply to our email. Yes. Yeah. If you happen to have a personal line to Andrew Kelly, creator of the Zig language, who is no longer on Twitter or Reddit, let us know. Reach out to him on our behalf. I think he'd like to talk to us, especially considering we our space over the last year and a bit has been, you know, a a big portion of our conversation has been, you know, C ⁇ , Rust, Circle, Hilo, etc., all the successor languages.
ConorAnd although Zig is not a successor language at all, it does compete in an adjacent space, which is the C space. Kind of Zig. Rust is arguably to C what Zig is to C, although a bunch of people are going to be upset that I just made that comparison because Zig doesn't do much for memory safety. My point is, is Zig is like a modern quote unquote better C. That's still gonna upset some people. The same way that a lot of people argue Rust is a modern better C. Anyways, let the you know, internet have a field day with that.
ConorDo you have a topic?
BryceI do I do have a topic. Um, however, I also have a problem. And the problem is that the heater is on right now and it's very loud. Now I could turn it off, but it's also freezing cold here, and I like I can't feel my extremities. So I'm not really sure what to do about that.
ConorI mean I'll I'll fix it as best I can in post, and already the listener is being upset by my nasally voice. So, you know, episode 168, it's not the best quality in terms of the audio experience that we're bringing you, but you know what? The alternative was just either we didn't ship and we missed our first week in 167 weeks, which I'm not about that life. I don't care if I'm in the hospital because I got a concussion on a bike accident.
BryceHoney, you gotta remember, you gotta help me remember to turn this heat on later. Oh, I uh I nearly died on a dog toy just a moment ago. So Ramona Ramona got herself uh the uh Van Gogh Starry Night Lego set, which has how many pieces? 2,136 pieces. And she has begun assembling it. Woo! How long is it supposed to take?
RamonaIt's two eight hours, but I think it's gonna take faster because I'm halfway through and I've just been doing a couple of hours.
BryceAnd uh have we lost any Legos yet?
RamonaWe have not.
BryceHowever, the dog has decided to plop herself down over some of the b bags of Legos, so there is dog fur all over the Lego.
ConorWell, stay tuned, listener, till episode 169, when we find out how long it took Ramona to finish the Van Gogh Starry Night Lego.
BryceI I have a I have a theory, which is that this is gonna be like an ongoing project over the course of the next the next two weeks of our lives, and there's just gonna be Legos everywhere, and I'm gonna I'm gonna step in them at night and my feet are gonna get all cut up. It's gonna be fun. Anyways, you know how to implement you know how to implement parallel mode?
ConorParallel mode, as in the statistical stat? It's the statistical stat. Man, I'm on my A game today. Ever heard of statistical stats? They're my favorite kind of stats. Um parallel mode. Yes, parallel mode. Mode is the most common, correct? Median's the middle, average is average, and mode is the most frequent. It is so sad that I had to pause. I'll leave that pause in there for you, folks.
ConorThat pause was a genuine, you know, I'm hopped up on daytylenol, couple of zinc pills. Uh I'm really hoping that that pause was brought to you by the mental fog that I have and not like my neural degeneration at age 33. Parallel mode.
BryceSo m mode is it's it's the the number or the the the value that appears most frequently.
ConorIf you've got a parallel hash map, like in Cuco, that's pretty simple.
BryceYeah, so that's like you do like a you know histogram style.
ConorYeah, and then just a reduction afterwards. Um pretty good guess. Parallel mode. I mean, ooh, obviously that would be I'm not actually sure which is more performant on a GPU, but I can I can solve that in like 10 characters and in jellyfish. Or is it jelly?
BryceShow me.
ConorIs it jelly? Show me or tell me. It's actually publ show um I can't show you. I could show you, but we don't do that here on ADSP Podcast anymore because that's show me. Alright. Alright. Only because I'm sick, I'm gonna allow myself. I mean, I still am sharing my screen, I just realized. Let's take our little WSL terminal. Whoa, look at that. There we go. Can't mention that because that's not public yet. We're gonna cancel out of that Docker. Hop into Jell-O.
ConorI guess that means we can never publish the video of this one. Nope. Nope. Although, honestly, it should be on our 2024 goals or New Year's resolutions, not that we'd be setting it a bit late. I keep getting people telling me that we got to put this stuff on YouTube because apparently the youth. The youth, Bryce, and we care about the youth. We care about the youth. Apparently, they don't listen to podcasts, and because of that, the number one podcasting platform is YouTube. And we're missing out on a huge demographic. And we don't we don't like that. Anyways, back to Jell-O.
ConorJell O is a pipe.
BryceI couldn't put this video on YouTube as I sit here in my pajamas with my fancy winter coat on top because it's cold.
ConorActually, I wore it. I mean, I think that's I think that's part for the course. That's the, you know, you you talk enough about your first class flights as uh if you were wearing just your pajamas, they'd be disappointed. You know, they're expecting a pajama top coat combo.
BryceBut these pajamas are my Emirates first-class pajamas.
ConorSo let's mix this up a bit. So I'm typing out a list of numbers where two is gonna be the mode.
BryceAnd I think I've got two basics he's got like eight numbers there, just like you know, a test case.
ConorAnd yes, it's not uh whatever, we're not gonna comprehensively test this, but uh I believe the the solution, and the reason I said that I could do this so quickly is note that I'm typing in jello, but this what I have typed so far, I typed ID, which is the keyword in Jell-O for identity. But the conversion of ID, which I borrowed from Haskell, because that's what Haskell calls the identity function, is a superscript one in Jelly. Fantastic, folks. But wait, the what of what Jell Jelly is a code golfing language that is even for an array language, Unicode glyph fan such as myself, uh very difficult to decipher, to comprehend because it's just using a bunch of stuff.
ConorAnyway, so superscript one is the identity function. We're just doing that to show that we got our expression, but we're gonna replace this ID for the identity function with, and look at that autocomplete. Absolutely beautiful, brought to you by Prompt Toolkit of the Python programming language, folks. And what do you think this function is right here, Bryce? It's R L E. R-L-E. What do you think that stands for? I mean, you should know. You should know, man. Run length encoded? That is correct, folks. And actually, run length and code is not what we want yet.
ConorWe need to sort first.
BryceI just, I gotta say, I after like two years of this podcast of me just completely failing at quizzes, I feel like this year has been very good to me.
ConorYep, fantastic. You're crushing it. So now we have we have a sort followed by an RLE, a run length encode.
BryceWe should explain what run length what run length encoding is.
ConorOoh, would you like to explain or should I explain? You go you go for it. Run length encode is a it's a fantastic algorithm. We love it. We love it, folks. And it's actually kind of a super specialized chunk by. So we've talked about chunk by quite a bit over the last year, which is a view that showed up in C23, but it exists in other languages like the D language and Haskell under the name group by. It takes a binary predicate and then it chunks your list into sublists based on whenever that binary predicate fails.
ConorAnd in Haskell, in a library called data.list dot ht, they have a version of this called group by, and then they have a specialized version called group where the binary predicate is fixed to equal to. So if you have chunk by equal to in C23 with views, that'll give you a range of ranges where each range is the contiguous elements that are equal to each other. So in my case, our example list is one one, or it's actually one one, three, two, four, two, two, six, two. But if you sort that, you get two ones, four twos, one three, one four, and one six.
ConorAnd so if you were to go chunk by equal, and actually, I think if we go sort and then group, I think group is the name. Look at that. Beautiful.
BryceSo so we we should also mention like run-length encoding is uh uh it's sort of it's often a building block in things like compression, right? Yes. It it it it is a way to take take data and express it in a different way, which is a shorter sequence.
ConorYes, and we didn't even get to the full explanation of run length encode, because I've just gotten excited about chunk by, which is called group by in this Haskell library, and then it has the specialization.
BryceIn JellOr, that's why I stepped in, because uh you know one of the two people on this podcast have to be the adult in the room.
ConorOh no, we we we had track of the stack. We we knew the topic stack and we were coming back to it, but in Jell-O, uh the equivalent of group in Haskell is also called group. So you can see here, well, you guys can't see, or the folks listening can't see, but I started with a list of, however, 10 elements, and now the resulting after you go sort group is that we have these uh inner lists. And note that if it has a single element in Jell O for whatever reason, it just keeps it as a single element. A little bit confusing because it's kind of uh but anyways, run length encode is basically a chunk by equal to followed by a map, or what we call in in views land and C LAN a transform, where we are basically doing a make tuple and then using a unary function on each of for each of the elements in our two tuples.
ConorSo like a make pair, the first one is gonna be head, aka the first value of our subrange, and then the second value is gonna be size. There is no elegant way to spell this in C. Like literally, it would be std colon colon views colon colon transform parentheses, and then you're gonna spell a lambda, which is gonna be an empty capture list. Then you're gonna go paren auto, and then like ref ref r for the range, n paren, and then in braces return std colon colon make pair.
ConorTechnically, I think with CTAD, you don't even need to spell what it's gonna be. And uh then you're gonna go uh range dot first and dereference that or like range r dot front, comma, uh std colon colon distance of the range. And this would necessitate it it being like a sized range. Oh look, you want to be on the pod? Ramona was on the pod. No, she doesn't want to be on the pod. Do you want to come say hi to Bryce at least?
ShimaHi Bryce.
ConorOh, she just said that uh she listened to our phone tag podcast literally just today.
BryceUh she listens to the podcast.
ConorI didn't mention you? Oh, yeah. So this is why I was asking if you want to be on the pod, because last time when I was recording on Thursday, Shima actually leant into the mic and recorded the welcome to ADSP the podcast, but then I ended up cutting it. And so now this is your opportunity.
ShimaEven though I did it better.
ConorUh she kind of did it better.
ShimaHello, welcome to ADSP Podcast. Recorded on January 30, 2024 to February 1st, 2024, and released today, February 2nd, 2024. On this episode, Bryce and I played Bone Tag. He's in Florida, and I just got back from Costa Rica.
BryceEverybody's on the podcast now. Do you have COVID, Connor?
ConorWe're gonna find out in a couple minutes here, once we're done this recording.
BryceUh No, no, no. Connor, we're gonna find out, we're gonna find out live on this episode.
ConorDo you want me to do a COVID test while we're explaining? Yes, I do want you to do a COVID test.
BryceSo literally, did you get this from the hospital?
ConorI've been sick since Monday.
BryceAnd anyways, while I'm opening up this This, it's great podcast content, I gotta tell you.
ConorAnyways, I spelt out, almost finished spelling out the lambda that would go inside the views transform to turn the result of our chunk by into basically a list of pairs where the first one is the value in that contiguous sequence, and the second one is the length. AK you are run length encoding uh your values, which is uh I'm not sure if it's related to like Huffman encoding, but it's like as soon as you start doing compression stuff, it comes up as like a very classic example if you need to, you know, reduce the density of the stuff you're storing. This is gonna be hard to type and do this COVID test at the same time.
ConorBut here, I'll I'll continue typing to go back to our sort RLE, and note that sort space RLE is in Jell-O, but like I said, Jell O is a Python wrapper around this jelly code golf language. So really the Jelly Code is S under dot, and then I don't even know how to read this like O E R. Should we ask ChatGPT? So the symbol O E is known as the Latin small ligature O E. Okay. So like how do we how do we refer to that? We just call it OE?
ConorIt's the OE ligature? Sure. Alright, we're done with this.
BryceYeah.
ConorSo it's it's S under dot OE ligature r, which is technically only two symbols. And now what we need to do is we need to. I wonder if we can do a I think it's a each last, or is it uh is it a last each, I think. There we go. And then a max. So in jello speak, look at how, look at that. We got syntax highlighting.
BryceWhoa, whoa, whoa, but hang on, but this is this has only given you the count of which one has the highest.
ConorOh yeah.
BryceYou haven't actually given the mode, right? So the the answer that you that he's given us here is that it's the count of how many times does the mode appear, not actually what the mode is.
ConorThat's true. So really you wanna you wanna max with a custom binary operation, but there's another way to do this, which is index max. But I don't think you can do that. You can do that each last index max, and then we're gonna need to use a combinator. So this gets us the index, which is index one.
BryceOh, he's cooking here, folks. He's cooking.
ConorI mean, this is still definitely gonna be less than 10 characters in in jello. Uh in jelly. That was the challenge. How do you do select?
BryceHang on one second, Connor. Oh, oh, I've been told that there have been zero missing pieces in the Lego project thus far. Zero lost pieces, zero missing pieces. Zero lost pieces as well.
ConorI don't know how to choose, I don't know how to index into this array, because I'm not a jelly expert. But basically we just need one more thing. So it's sort RLE dot each last index max, which gets us the index. And technically, if you've got multiple of them, it'll return you all the indexes. And then is there a filter? Compress. Keep? Ooh, there's a keep. A keep. Does the keep need to go in front? Does the keep need to go in front? There it is, folks. Boom. Ah, that didn't work.
BryceWhat do you mean didn't work? Gave you the right answer. No, that's not the right answer. Get rid of the plus one. Wait, oh. I'm confused about what you think didn't work.
ConorUm, because I think this is getting us the first right? It's not actually getting us the second. And so, yeah, my expression. Oh. My expression when I did last should actually be first head. So it's actually one. So that makes me think that that makes me think that this is a it gives you the zero indexes. Which then this plus one. Is that it? It's still not it. I don't know what this two, three thing is. Anyways, the details of how to spell this in jello.
ConorRight now we're at one, two, three, four, five, six, seven, eight, nine, ten, eleven technically, but I'm not sure. We'll work on it. We'll post it in the show notes.
BryceBut how about we look at how Thrust does this? Mode? Yeah, there's an example. I was looking through exam um Thrust examples, trying to find good examples for things for uh async algorithms. So I was looking, I I wanted examples of code that uses multiple parallel algorithms in some sequencer ordering and would be interesting test cases for asynchronous for an asynchronous parallel algorithms interface.
BryceUm so I just went I went through all the thrust examples, but actually, you know what the interesting problem was that I've been like one of the more interesting examples that I've now got in my paper is the rainwater problem from uh from your talk that we've discussed in this um uh episode. Um but uh let's talk about how this mode works.
ConorWait, so just just to recap, the two different solutions I proposed were just a parallel hash map, which you can find in the Ku Collections library, and the second one was a sort followed by a like max by key aka max reduction where you've got some custom binary operation that is doing the reduction on the first one, or the the the the basically length of each of your sequences, and then it keeps a pair of things and throws out the last thing. Um but now we're gonna see how this happens in thrust.
BryceYeah. So the thrust example, so first it is a sort with a comment that says sort data to bring equal elements together. Pretty straightforward. Then it does an inner product. An inner product where the um where the the reduction is a plus. Is that right? And the hang on, take a look at this and help me sort sort this out.
ConorSorry, I was uh disassembling my COVID test so that to make sure that we get the listeners uh report by the time we finish wrapping this up. So we got on line 41 a thrust sort. And then we've got on line forty five a thrust copy. And then we've got a Count the number of unique keys, which is an inner product, aka transform reduce.
BryceAnd it's got as the so it's a it's so it's a binary transform reduce. It's like the the um adjacent transform reduce where it's looking at every two adjacent elements. It's checking whether they're not equal to each other, and then uh it it's doing a sum. So it's essentially doing doing like a parallel word count. Um I've talked I've uh uh used that as an example a bunch of talks where you're looking for like the ends of words or the ends of sequences. Connor is now inserting the uh the swab up into his nose.
BryceIt looks like he's not having a fun time, I gotta tell you.
ConorMy eyes are watering a little bit, that's for sure.
BryceUh but but so so this this transform reduce, it's transform reduce where it's got two input sequences. One is the elements from you know zero to n minus one, and the second one is the elements um from uh one to n. So every transform is going to look at two adjacent elements, and the transform operation is not equal to, um, which will return uh true once for every start of every new unique element, and then we just reduce that transform pseudo-sequence, and that gives us the count of how many unique keys we have.
BryceUm that's kind of cool because that it's got the that parallel word count problem embedded inside of it.
ConorWe're we're gonna pause here though. We're gonna pause here. This is fantastic. I don't think the listener necessarily followed that because I didn't necessarily follow that, but we've got an inner product, aka transform reduce, where the and the the thing, yeah, so that you've got the parallel word count as in the two ranges. It's a two-range transform reduce where you're looking at adjacent elements, and then the the binary operation that you're applying to those to those two adjacent elements is not equal to, and then you're doing a reduction of plus. So here's what's beautiful is that this is a bit obfuscated. There is a much, much nicer way of implementing this.
ConorWell, is it actually nicer? There's an alternative way of implementing this, which we have also talked about on this podcast with respect to a different problem that is actually yeah, actually, this is uh this is messed up. You need to refactor this. But uh yeah.
BryceSo I didn't write this code.
ConorReframing, reframing. How should this code actually be spelt? And it's and if you need a hint, I'll give it to you in three seconds, because it is the the hint is gonna be like, it's actually absurd that we're doing this. All right, lay it on me. Read the comment above this inner product on line 48.
BryceYeah. Count number of unique keys. It should probably be some form of count.
ConorWhat algorithm would you reach for with a comment that says count the number of unique keys? I would probably reach for count. I would probably reach for unique count.
BryceOh, there's a unique count.
ConorWeren't you at my presentation in January, which we can't name what it was about, where this was one of the motivating examples that I used. Like it is actually this is fantastic. In my 2.0 version of that presentation, I'm going to use this because there's no std unique count, but there is a thrust unique count. And the way that thrust unique count is implemented is using a count if with a zip iterator that it zips adjacent elements together. And what's what's what's confusing is not just the choice of inner product, but also that like not equal to technically is returning you a Boolean, because it's a predicate operation.
ConorAnd then you're summing Booleans, which C allows, but if you tried to do something like this in Rust or Java, it would yell at you and say you can't sum Booleans. Anyways, we have the algorithm, a one-line algorithm for this whole thing called unique count. And even our you know, NVIDIA engineers and actually potentially when this was written, unique count didn't exist.
BryceSo I this example I believe predates unique account being in Thrust. All right.
ConorFantastic though, folks.
BryceWe love it. We love it. The reason I say that that I think it predates uh unique account is because this is spelled as inner product, not as transform reduce. And inner tr Thrust didn't have transform reduce until uh later in its evolution. I mean, still very early in its revolution, like we were still in college, but but later. Okay. So here's the part where I think that this approach starts to break down or it becomes less optimal than what you um also update on update on the COVID test.
ConorI spent too long uh and it all evaporated, so now I need to start over um but continue.
BryceOkay, so next it it we create two O number of unique element device vectors, and and we're going to use these to count the multiplicity of each key. And we're going to do that by doing a reduced by key that is on the original data and writes to. What is this doing? There's a lot of iterators here.
ConorA reduced by key, there's a bunch of different versions of it.
BryceWhoa, whoa, whoa, whoa, whoa. Hang on, hang on. This reduced by key takes one, two, three, four, five iterators? Yeah. Okay, so the first two iterators are the input sequence. The the the next iterator is the key, and then you've still got two more iterators.
ConorSo so here's the thing about here's here's the here's the thing about reduced by key is that reduced by key has two outputs. Uh it has both the keys and the values. And here's what actually, Michael Garland, my boss and I, had a discussion about this the other day, because scam the scan by key algorithms only have one output, and that's the uh the values. They don't have the keys. Reduced by key has two outputs, the keys and the values, but it actually only makes sense in the case where your binary operator is an equal to predicate. What if your binary operator is like less than?
ConorWhat do you put, what do you output for the key? Because in the case where your binary predicate is equal to, you know that all of the values in your sub, your basically your segment, your sub segments.
BryceWhat what what what what predicate? You mean the reduction operator?
ConorSo reduced by key in this example doesn't give you, you're looking at one out of six, doesn't give you uh if you look at the docs right here, it says this version of reduced by key uses the function object equal to. But there's an overloaded version that lets you customize this binary operator. And technically, I think what they wanted you to do.
BryceOh, yeah, it uses equal to to test for equality.
ConorYes. But you can customize that to any predicate. And I think it wants you to, in general, to only ever use equal to or basically like an overloaded equal to that works for your custom type. But technically, there's nothing preventing you from using like less than or less or like less equal, in which case you're gonna end up with a bunch of different values in your subsegment that are different, and it's like which one do you use? I think when I checked, it uses the last one, but like it's basically the key output is nonsensical unless if your binary predicate that is passed, either by default or by u, isn't equal to predicate.
ConorAnyway, so what you're seeing here is that you've got your keys output, your counts output. The constant iterator is so that you can sum up. You're basically doing a run length in code, and if we sum up the actual keys, you're gonna get some like the number of keys times the key. And we don't want that. We just want the sum. So how do you do that? You sum up a bunch of ones where one corresponds to every single element, and then your first two iterators is your input. Reduce by key, and this was the whole point of that presentation, is that like I can generate all of this. Well, I shouldn't say that because the kind of a little teaser is the tool that I've been working on generates this, like I can write a couple like a couple keywords and poof, it works.
ConorI literally have a thing called chunk by len that like generates all of this. And actually, including the inner product, but my inner product is not that. It's a count if with a zip iterator.
BryceNow, I'm pretty sure that doing a run-length encoding is better than what they're doing here. And one of the reasons that I've I feel that it's better is that they need more temporary storage here. Well, yeah, no. They need that well one, they need temporary storage in general. I mean, you can do the if you're okay with doing it in place, you can do the run-length encoding in place. But here you need to store both the keys and the counts. I know I guess you have to do that in run-length encoding too. Is this just a uh less elegant way to write run length and code?
BryceYeah, I think it is. Okay. So we do a run length encode, and then Well, the run length encode hasn't happened yet.
ConorOr yes, this is a less elegant way to do run length and code. Which doesn't exist in thrust, but it does exist in code.
BryceAnd then what we do is we do uh thrust max element to find the index of the maximum count.
ConorIn this case, what you're doing is because you're you don't like in my Jell-O program, your run length encode gave you a list of tuples, but in this example, you've got two separate lists with two separate iterators. So you do the max element on the counts, and then you use that iterator to basically back out the index and then index into the keys, is what it's doing here. Whereas my explanation was like, well, you want to do like a max.
BryceSo in Rust, there's an algorithm called max by key, which you can basically give it a uh projection like like exists in C20 and 23 views, do the max by that, and then it'll return you the tuple, and then you just want to index into the first one, which is the So one thing that occurred that that I thought that occurred to me when I was looking at how you do this in Jello, and that occurs to me now again, is there's another way that you could do this, which um is, I think, objectively a worse way, but perhaps will lead us to a better algorithm, which is you could do sort run-length encoding and then sort again to get because what once you have the run-length encoding, sorting the run-length encoding will give you.
BryceBut I I I wonder if the the thing about that that's potentially a revelation to me is um if you think about it that way in terms of like you essentially need to do two sorts, um, is there some way to combine that final sort or that final find with the run-length encoding itself? And I think the answer is yes. I th I think you could do a run-length encoding where you also, during the run-length encoding, find the maximum element. I'm I'm actually I'm I'm compl I'm 100% certain that you can now do this because run-length encoding is implemented as a scan under the hood.
BryceBecause it's just like stream compaction. Yeah. I'm fairly certain that you can write, I think you need to write a bespoke kernel for it. But I think you can write a bespoke kernel that does the run-length encoding, but keeps track of which um run is the longest run, and then gives you the answer, and then you don't have to do that third pass of the of the max element. I'm trying to think about how exactly would this look. I think we'd have to dive into how the Cub run length encoding algorithm is implemented to truly get to the bottom of this and see if we can do this in two passes.
BryceBut one interesting thing about this algorithm is that because of the the first sort, which seems to me unavoidable, it is almost certainly uh you know a two-pass algorithm. You'd want to do this as a two-pass algorithm. Because you need to you need to sort the data first. Um like I can I can see a path where by which we can combine the later passes, but if I need to sort the whole thing, I just there's there's no way for me to avoid this having two parallel passes. Unless we can find a way to not need to do the sort.
BryceUm and I mean the the one approach to that would be the histogram style approach that you suggested at first, of like, oh, you have a parallel hash map. And that is all I that is almost certainly gonna be the fastest way to do this, um, I think. Uh because with the parallel hash map, you you don't need to sort. Um you don't even really need multiple passes. So that's just gotta be the best one, right? And you know, you know what? A fun problem that we should talk about in the future. How would we do a parallel rolling mode?
ConorYeah, that's a little more complicated.
BryceI think that's a little bit more complicated.
ConorWell, we should land this plane because we've got two minutes left. But uh, while Bryce was uh pontificating this is what I was, or you can you can't see my screen anymore because you're the one sharing. I cannot. Or yeah. This is what my tool, my unnamed tool, like generates all this. Um you can literally see like there's the make there's the make constant iterator.
BryceYeah.
ConorDiscard iterator because I like you can't use this for RLE because I'm discarding the keys, but like the equal to, the plus, and this count if with a zip iterator is exactly what they've spelt using an inner product, which of course mine is much nicer. Um anyways, folks. That's beautiful. That that's very cool, Connor. That's very cool. We can't show, we can't tell that we can't tell the listener.
BryceYou know, it it it it it really amazes me how you know you just you happen to check your tool and it spits out basically the same pattern. And and that same pattern that we saw in that thrust example is also um more or less the way that you do it in uh uh in in jello. And it's just it's amazing to me how often we see these like fundamental parallel algorithmic patterns come back. Like the more and more we look at how do you solve a problem in parallel, um, the more and more I find that it it breaks down into like one of three or four different fundamental answers.
BryceYou know, like it's a it's a it's a reduction, it's a sort, it's a scan, or it's uh stream compactation, which is what run length encoding is. Or it's just like a parallel for leap. Like almost everything that we've talked to has boiled down to one of those. And in some cases, two of those, but usually when it's two of those, it's a sort followed by one of those.
ConorYeah.
BryceIt's just it's just mind-blowing to me how how how often we get these deja vu moments of like, hey, we've seen this before, haven't we?
ConorYep, completely agree. And you might have missed it in that presentation, but this this is the code that I had to write to get that.
BryceWhew.
ConorWe will de we will demo that hopefully in the future at some point, folks. I think the best way to end this is by me stopping sharing my screen and by showing the negative COVID test, folks.
BryceOh, hang on, you gotta hold it back a little bit because sometimes that line can be very faint. Nope. Yeah, it looks like Connor doesn't have COVID. Connor's just sick.
ConorFantastic.
BryceWell, I hope you feel better, buddy. I I am reminded of a time during the pandemic when you thought you had COVID, but could not get access to a COVID test. And so I I bought, I had COVID tests because I'm a little hoarder and I had had a stock of them. So I took the COVID test down to FedEx, and I I overnight FedExed it to you in Canada at what can only be described as an exorbit fee.
BryceAnd did that arrive overnight, Connor?
ConorIt did not.
BryceIt did not. It got held up by Canadian customs for a while. I think, did you ever get it?
ConorI did. It was, I think, two or three days later, and I I did test positive.
BryceI thought it was a while.
ConorYeah.
BryceI don't remember why there was the great urgency for me to get you that COVID test. Uh I think it was just you couldn't get the test and you didn't want to go out and risk exposing people. No. And so I was just like, hang on, I got you.
ConorAt the time you couldn't get tests in Canada. There was a period of time where they basically said you can no longer you couldn't buy them or get them at a store, and you also couldn't go like unless unless if you were like pregnant or you met some criteria, you couldn't go in and get one. And then when I told you this, you were like, this is ridiculous, I have the solution.
BryceYeah. But was it actually useful, or am I correct in remembering that before the COVID test arrived, you found some other way to get a COVID test?
ConorI did. Uh there was a couple, I don't know if they were rogue operations, but like uh I did find a place that would give me a test, and then I did test positive there. But I used yours a couple days later and test positive again. So they were, they did come in, they did have some utility. It was not zero.
BryceUm but anyways, FedEx, I'd like a refund, please.
ConorYeah, we've been waiting a couple years, FedEx.
BryceUh I think it was like $120 or something. It was like not cheap. It was it was up there. But anything for my buddy, anything for my buddy.
ConorBe sure to check the show notes either in your podcast app or at adspthepodcast.com for links to any of the things we mentioned, 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.
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:...