Bryce

You you look like your apartment looks like the saddest place on earth. Here's the thing, it's like there with a hoodie.

Conor

The hoodie is for echo cancellation. I figure if I put the hoodie up, it captures more of the sound.

Bryce

It's for echo cancellation. A line that will go down is one of the greats in the annals of podcasting.

Conor

Welcome to ADSP the podcast, episode 25, recorded on May 12th, 2021. My name is Connor, and today with my co-host Bryce, we revisit the problem maximum consecutive ones and discover a missing algorithm. So here's the thing. So now so let's take a moment to explain uh my place to you. I have a bed, I have a desk, and I have an office chair. Um, and so the echo's awful. I don't have any other chairs, so right now I have carted my office chair from my office through the kitchen, through the living area, through my bedroom, into the closet. And my You're in a closet right now? Yeah, it's sort of. It's like it's like an open closet, so it's a it's a closet without like doors in the midst of a hallway. So it's only really got it's not like a closed closet. So like here's the entrance, and also to it's actually works out quite nice. So my laptop, I cart my laptop and put it on the top of like this little drawer thing that's a part of the closet, and then I pull out the second drawer, which is my socks and boxer drawer, and then that's where I put the mic, and it actually works like perfectly.

Bryce

Um does this apartment have windows? Because I have not seen evidence that this apartment is.

Conor

Have you not seen my view, bro?

Bryce

No, I have not seen your view. Oh, okay. That's a pretty good view. That's a pretty good view. Oh, that's a pretty good view. That's a pretty good so you're in downtown now. I'm gonna have a better view when I'm in New York.

Conor

Uh you know why? It's your bright.

Bryce

Do you know why I'm gonna have a better view in New York?

Conor

Because your price.

Bryce

Because I'll be looking at New York City, not Toronto.

Conor

Boom!

Bryce

Take that, Canadians.

Conor

Here's what I'll say about New York. I visited once, twice, I can't recall. It smells like garbage.

Bryce

Um, you get used to that. You get used to that. It gives a character. The smell gives a character.

Conor

Do you want to know why it smells like garbage price?

Bryce

Well, usually because there's a lot of garbage.

Conor

There's like the same way that in the winter time there's big piles of snow on the corners of street in Toronto. There are big piles of garbage.

Bryce

Oh, but bro, bro, you don't even you don't even understand. In New York, between like Christmas and so so the the um the the sanitation workers in New York has a very excellent union. Um and and from like, I think it's like from Christmas to January, there's like no trash pickup. Like none. And so during this period of time, some quite substantial piles accumulate. Yeah, but the the the smell, the smell gives the city character.

Conor

It's a problem because I like to run specifically outside and I can't be inhaling garbage.

Bryce

It's not that bad. It's not that bad. You're making it sound you're making it sound like it smells everywhere.

Conor

It doesn't smell everywhere. Central Park was quite nice, and if you're most of the places along the sort of what in Vancouver is called the Stanley Park, the seawall, that's what they call it. Uh you can go for like a walk and it's a uh, you know, pathway that sort of surrounds the park and it's right next to the ocean. That sort of happens in New York. Anyways, enough about New York. Um anyways, I got this dope set up, and uh my apartment's too big that I would have to furnish it too much. So I'm pretty sure I'm gonna I'm I'm getting my sister, my older sister's moving to Calgary, and so I'm acquiring one coach, one shelf, and two patio chairs.

Bryce

Um but that's still Can you just can you can you please just just appoint your sisters to decorate your place? Just just for for my benefit. I've only met one-third of your sisters, but I'm I'm confident that they're they're all classy people who can take care of this problem and it'll make me sleep better at night.

Conor

I can I'm definitely gonna outsource it to uh to individuals. It will uh it's not gonna be my responsibility. But this doesn't explain. You asked about the webcam, so I have an external webcam, uh, which I do not. I take my chair, I take my laptop, but the webcam stays on the desk.

Bryce

I can bring the webcam next time, but um it's uh it look it's a very it's right now I'm looking at Connor, and Connor looks like the protagonist in a movie about like a rogue hacker. He's like super blurry, and he's got his hoodie on, and he's in like a white void.

Conor

The hoodie is for echo cancellation. I figure if I put the hoodie up, it it captures more of the sound.

Bryce

It's for echo cancellation. A line that will go down is one of the greats in the annals of podcasting history.

Conor

Oh man, it's um yeah, I I feel it's I wish we had been putting these on YouTube because uh the the delta from my last place where I was right next to windows and had great lighting and had a plant behind me, lots of color, and now I'm just a shadow in the dark. Yeah. All right.

Bryce

So I guess we should probably do do our thing, right?

Conor

Yeah, that this is all going in the podcast. This is all that was all gold. Uh and now we will start talking about max consecutive ones.

Bryce

This is actually I I think I solved it. I think I solved it.

Conor

This is our second time for transparency because at ADSP the podcast, we're all about transparency. This is the second time. We recorded this on Mother's Day, but it it was it was a good recording, but I was a bit confused and I was staring at the code that Bryce was sharing with me, and I figured our listeners are gonna be super lost. So we we said this.

Bryce

This is the third time, Connor. Because it's true. That's true. Like three weeks, no, maybe four weeks before that. So, okay, all right, all right. We should take a step back. We should take a step back.

Conor

Nah, let's take two steps forward.

Bryce

First, Connor, why don't you explain the max consecutive ones?

Conor

Right, yeah. Let's do a mini recap. So this is probably what, the second or third time at least, that this has uh come up in our podcast. It was a problem that I solved or or showed the solution to using parallel thrust algorithms in my GTC talk that happened in April. And very briefly to recap, uh, you're given a sequence of ones and zeros. And the problem is to simply return uh the length of the longest contiguous sequence of ones. So for example, if your sequence is one one, zero zero, one one one, uh you have basically two sequences of ones, which are of length two and three. So the answer to that problem would be three. And in my talk, the way that I, if you know, you for the full solution, I guess we'll link to our previous episode where we first talked about this, and I'll also link to the GTC talk. It's basically using an algorithm called thrust reduce by key, which first segments the sequence into contiguous elements of equal value. So you're gonna end up with three sequences, two ones, two zeros, and uh three ones, and then by default it does a plus reduction. So you're gonna end up with the values two, zero, and three, all the zeros always sum to zero. And then once you have those three values, you just take a max element. And at the end of that episode, or uh sort of halfway through, I think we we were discussing, or you were discussing, or I guess we were both discussing. Oh wow.

Bryce

I said, I think this can be done in a single pass.

Conor

Correct.

Bryce

A more efficient implementation existed. Now, we should clarify that. First, Connor asked me, what algorithm would you use to implement this? And I gave the wrong answer, I didn't I gave the answer that was not what he had in mind, not what he showed in his CGC talk. And then I was like, ah, but I think it can be done in a single pass. And of course, not not wanting, not being able to live with the shame of having failed to accurately identify the algorithm in my own library that did this. An algorithm which two years prior I had taught Connor about, I was like, I must go solve this.

Conor

And so In in your defense, you did at an earlier date in time come to me without even me asking you and said, Hey, you can solve this problem or a similar problem using reduce by key. And at the time I didn't know about it.

Bryce

And I said, Was that when maybe we met? Yeah, that was probably when we met.

Conor

Yeah, that that was literally January of uh 20 2019 when I think I first gave the algorithm intuition talk at the the meetup, which we're gonna be attending in like an hour to do a C now.

Bryce

Okay, so after this embarrassing incident where I failed to correctly identify the algorithm that I had taught Connor about, you know, when we first met, that that is an algorithm in my own library. I was like, all right, forget the rest of my Saturday. I am gonna go implement this. And I went and I wrote it. Uh wrote a single pass implementation of this algorithm in terms of a reduction. Um uh and uh and then I told I I got on the the Twitter DMs and I told Connor, come on, man, we gotta go record another episode right now. Like I'm so excited, and we recorded, and that was some great podcast material that's never gonna see the light of the day.

Conor

And and I should add, I should add, you said, let's record a 10-minute addendum. And I think I was in the middle of something, and I was like, I'm sort of busy, and you were like, just this would be tens. 55 minutes of addendum later.

Bryce

And the conclusion in that addendum was because I was still sort of writing the code as I was talking with Connor, the conclusion was, oh wait, no, there was a bug in my thing. So then I was like, all right, well, cancel that whole that whole 55 minutes. And then um, then I think later that week I was doing yoga with my mom. I do yoga with my mother twice a week. And inspiration hit me. I realized how I could solve this problem. Um, and I and I went and I coded up a little bit, but uh something distracted me. So I I I never mentioned it to Connor again. But then last week I was speaking with my friend Tony Lewis, and uh we were talking uh about uh what belongs in the C ⁇ standard library, my C ⁇ now keynote. But then at the end of our conversation, he mentioned this podcast episode and this problem, and he said, Oh hey, I think I I think I found a solution to it. Um and he showed me his solution, and his solution was in terms of in terms of a scan. And we'll explain we'll explain more about that in a little bit. But I looked at his solution, I was like, aha, yes, this is not only do you have the right answer, but this reminds me that Connor and I have to do another attempt at at uh at solving this problem in a single pass. And then on Mother's Day, we recorded that episode, and then afterwards we were like, well, Connor was like, yeah, the way that we explained that was too confusing. So then now attempt number three is today.

Conor

And also shout out shout out to all the moms. Happy, happy Mother's Day, belatedly.

Bryce

Hi, mom. Thank you for doing for doing yoga with me. She's a yoga instructor slash lawyer, and uh she she gives me free yoga classes on Zoom twice a uh twice a week, which is absolutely wonderful. And it's a great way to connect with your mother, especially during the pandemic. And uh, and tell me, Connor, what did you send your mother from from uh Mother's Day?

Conor

Why are you bringing this up? Because now I gotta cut this out. Our family is not a big gift family. I did a three-hour Zoom call with my three sisters. My dad popped in for a little bit. I was confused. My my parents don't listen to this, but I was confused on why we didn't invite. I felt so bad for my dad, like because it was a three-hour call, and I think he showed up at like the hour and a half mark, and I was like, poor dad, he's just off over in like a different room, jealous of the five.

Bryce

I sent my mother, her favorite wine, two bottles of it, a cheese pairing, and I may have sent other stuff, I don't remember. And then I sent my grandmother uh chocolates, flowers, probably some other stuff, because I I am a good son. Anyways, anyways, let's move on to the algorithm. Okay, so the problem we're trying to solve is we've got an input sequence and we want to count all uh the the longest run of consecutive ones. So we want a single pass parallel algorithm. So whenever we've got a problem that amounts to counting, um uh this usually boils down to being a reduction. So something like a count or like a std count or a max element, etc. You're you're um uh you're looking to look through all of the data and and find, you know, one answer. Um so the intuition is okay, maybe we can write this as a single pass parallel reduction. So almost any time that you're paralyzing a problem, the first thing that you do is you split up the input into you know sub subranges. And I think that's where we should start in explaining this. So let's imagine we've got our input sequence and we split it up into um uh sections and then we assign some thread to work with each section. Well, let's think about naively what we want each thread to do. Well, we're looking for the longest consecutive run in the entire sequence. So sort of the first thing that seems sensible is the each thread should figure out within its subsequence what's the longest sequence in that region, right? Does that make sense? Okay. But that's not actually good enough because what if the longest run happened to span across two of these regions? That like thread zero has, you know, ten elements, and thread one has ten elements, and the longest run spans from the last five elements of thread zero to the first five elements of thread one. Well, now somehow we need to find that sequence. Um and that means that we have to propagate information from left to right, from thread zero to thread one. So how do we do that? Well, the approach that I took, and the approach that Tony Lewis took is to create a summary for each region. And we'll talk about how that gets created in a minute, but for each sort of chunk of the input, we're gonna create a summary. And that summary needs to have three key pieces of information. The first piece of information is what is the longest run in that section? We already said that, that's pretty straightforward. But it also needs to identify what is on the on the left-n boundary of this section. Um what is the the character at the leftmost boundary, and how many times is that repeated? So like let's say that um let's say that the start, like we said thread zero is ten elements. Let's say that uh the first two of those elements were zero. Well, then on the left side of thread zero's chunk, there is a run of two zeros. Um and then let's maybe say at the end of that ten element section, the last three elements are ones. So uh on the right of thread zero's section, uh there's a run of three ones. And and we need that information about what are what is the first run in each section and the last run in each section. Because when when the the thread with the next section, the next consecutive section, is looking for its longest run, it needs to ask its neighbor, right? Because it needs to check, hey, you know, I've got a run at the start of my sequence. I have a run of you know four ones at the start of my sequence. And I need to know is there a run of ones at the end of the elements that you know are right before my elements? And if there are, then I need to combine that run with this run because that might be the longest run. Does that still that still make sense?

Conor

Yeah, makes complete sense.

Bryce

So how do we get these summaries? Um uh well, the this summary is a data structure. Uh the way that I structured this data structure is, you know, i I first I created a data structure called a run. And a run is just a uh a value and a size. The way that I chose to solve this problem, I solved the more general case of counting the max consecutive number of elements of the same value and also recording what their value was. So a run is a value and a size. And then a summary consists of three runs. There's um uh the first run in that section, there's the last run in that section, and then there's the longest run in that section. And then there's also a Boolean flag that I need to keep because um uh there's a special case, and the special case is if the entire section was one element repeated the entire way through, um, I have to handle that a little bit a little bit specially. But that's not that's not super important. Well, it's it's important to get it right, but it's not sort of critical to the uh to the algorithm. So our input is you know some value type. Let's just call it t. So when we take two t's and we feed them into our reduction operator, that's how we generate the first set of summaries. When we reduce two elements, we can create a summary that describes those two elements. Now, likewise, if we have a reduction over one of these summaries in one element, we can also uh uh uh combine that into a summary. Because, you know, if you think about it, that w in a a section, like if in if we have just one element in isolation, um uh it's pretty easy to construct a summary to it. If we just have one element, well, the first run in one element is the element itself and its length is one. The last run for one element is the element itself and its length is one. And the longest run is the element of itself and its length is one. And so um uh likewise, you know, in the in the more general case, when we have two different when we have a summary on the left side of the reduction and a summary on the right side of the reduction, um you know, we can combine those two and produce a summary that describes the entire region. But for all of this to work, we need a guarantee. And the guarantee is that the summary the left hand side of the reduction has to contain information for a set of elements that are before and consecutive with the right hand side. So in the let's let's go back to the case of just two v two elements. So our reduction operator needs to needs the guarantee that if you call it on two elements of the input sequence, you're calling it on two elements of this input sequence that are right next to each other, that are consecutive, uh, and that there's no elements in between them. And then that produces a summary. And if you reduce two summaries, you need the guarantee that, hey, these are summaries for two regions of elements that are right next to each other. So what do we call this uh uh uh requirement? Um well, uh specifically what we're asking for. is we want a uh a reduction that will not commute the input elements. So so commutativity is is the property of an operation that says, you know, A plus B equals is the same thing as saying B plus A. But in our case, that doesn't work for this algorithm. We need a reduction that promises that it won't reorder the inputs in that way. So does C have that today? Well there's stdacumulate. St.acumulate promises that it won't reorder the inputs. But stdaccumulate actually makes even stronger guarantees than that. It promises that it will associate the operations in a very specific order. And and the order that it prescribes completely prevents parallelism, which kind of defeats the whole point of what we're trying to do. We want a parallel max consecutive once. So so accumulate will work for non-commutative and non-associative operations. And what we have here is we have an operation that is non-commutative, but it is associative. Okay, so there is another option which we added in C17. It's called std reduce std reduce is like the opposite end of the spectrum from stdaccumulator. Std reduce is allowed to arbitrarily reorder the inputs and it's allowed to perform the operations in whatever order it wants. It's allowed to associate the operations in any way that it wants. So std reduce only supports things that are both commutative and associative. But the benefit of it is that it can be parallelized. But this presents a problem for us because std reduce like again as I said we have an operation here that is associative but not commutative. And we want to do a reduct a parallel reduction on it. And we simply don't have that primitive in C today or in thrust today. In our previous recordings I um I hypothesize that thrust re thrusts reduction might actually make this guaranteed that thrusts reduction might actually not commute the inputs and so it might actually work for this even though it's not documented that way. But one of my colleagues later pointed out no it actually does it actually does in some cases reorder the inputs because um when oftentimes when you're uh when you're computing things on GPUs you want to sort of swizzle or transpose the input elements or instead of doing things exactly in order you want to sort of do things by slices so that you get memory coalescing. Now the interesting thing is we we don't have any reduction operation that does this but there's another class of algorithms called scans. A reduction gives you back a single result. A scan gives you back uh the partial sums.

Conor

So it gives you back the result of accumulating the result of the accumulation um uh uh incrementally yes incrementally so it gives you every incremental and partial sum is act yeah partial sum is actually that's borrowing sort of from the C you know pre-C ⁇ 11 algorithm name but arguably like that's that's a suboptimal name because the sum implies like you're sort of hard coding the semantics of the default binary operation plus that comes with the algorithm into the algorithm name which is why scan which is what we call the C 17 parallel versions is better because it's you know even though it's not maybe evocative of what the algorithm's doing it's it's you you know you can use partial sum to do a partial max or a partial min or a a partial product. It's basically a reduction that's just every step of the way you're outputting the incremental result at that point.

Bryce

So to be able to output that incremental result as you go, you need you you you can't commute the inputs, right? That that because if you do then you're gonna you're gonna produce the wrong you know partial results. So these scan operations these parallel scan operations like std reduce the the C parallel scan operations um uh do not do not support non-associative operations but they support non-commutative operations and that's exactly what we need we have a reduction operator that is non-commutative but it is associative so you know what one option would be you know okay well I I want to do a sum um that's uh uh associative but not commutative I don't have a a parallel way to do that with std reduce so I could just use a scan right and in fact I I think we've learned since we came across this problem that that's what some of our users do. But this is of course inefficient if you just need the one final result it's quite inefficient that you have to write out all of the incremental sums somewhere. Right.

Conor

So I think the conclusion of our discovery and our our our our exploration our journey our journey to this algorithm is that we are missing an algorithm.

Bryce

We are missing a reduction that is that supports non-commutative operations but requires that operations uh uh be associative um and and we can't just relax we can't just change std reduce to um uh support this because it it turns out that in our implementation and in in thrust and for GPUs and also in some other implementations we take advantage of the the freedom that std reduce gives implementations to reorder the inputs that's actually a useful thing. So no what we what we need is we need a new algorithm. I I don't know what we call it. Do you have any ideas on what we call it?

Conor

Well we didn't we bring this up you know we can't talk about uh all the all the content of the meeting but we had a meeting earlier in the week at NVIDIA with um some ISO folks and didn't Michael Garland who's the head of research said we should we should we should clarify for Michael Garland and Bill Daly who's the actual head of research am I fired?

Bryce

Michael Garland is the director of our um uh parallel uh systems and algorithms research group he is not the director of all of you research my bad this is why this is why Bryce is you know he's climbing the ladder I uh I just I just typed this stuff into the keyboard.

Conor

But yeah uh Michael suggested Associate of Reduce and I I think you know even to pause before trying to name it is it's a terrible name by the way this is uh this is like the last couple weeks of going back and forth and you know in this you know uh reduction tennis match that uh Bryce and I have been having um uh live on this podcast is that this this has been like a uh monumental sort of because because reductions are they're so important they're so fundamental. I mean Ben Dean has a whole talk called Stood Accumulate Exploring an Algorithmic Empire where he shows that like 77 of the 90 or of 90 of the algorithms that exist in the standard uh library of algorithms in C are implementable in terms of a reduction and and one of the remarks that I made the very first time I gave my algorithm intuition talk is that you know std accumulate it's a bad name introducing C plus seven C 17's std reduce which is a much better sort of generic name. And in hindsight, uh I think that's like a mistake to to like have that as sort of like a not a motto but like a slogan of like you know introducing C17 std reduce a better named version of std accumulate. Because it's not fundamentally stdaccumulate and std reduce are two different algorithms and basically what what this episode is in which this is probably going to end up going closer to an hour because I I think it's important is that we're we're you know it std accumulates on the left and it says we don't require anything commutative non-commutative associative non-associative we don't care we'll make it work. And std reduce says hold your horses you need both associative and commutative otherwise uh no bueno we're not doing anything. And basically what we've identified here is oh we have a problem technically we could solve it using a scan because scans don't require commutativity and and that's what we have here but we don't want a scan. We want we want an equivalent reduction that does the exact same thing but that just doesn't require that commutativity and uh you know enter what Bryce just said is we're we're missing this algorithm. And if users actually are scanning and because that's one of the properties of a scan is that the last element of a scan is always equal to the equivalent reduction. And if that's basically what people are doing is just scanning and then taking the last element there's there's basically perf that's being left on the floor. And and because reductions in my opinion they're so fundamental that I I think that we should definitely be adding this. And it's not the first time actually it's the first time this has come up where I've been like wow this is this is important. But it's actually come up in meetings on on Rapids the team that I work on where people have pointed out oh yeah if we just sort of had like a parallel fold left um we could do this a little bit more efficiently but that was sort of the you know that was the last thing that was said and then we just moved on um because yeah you know it's so it's so interesting to to see you to have seen you reach that that conclusion Connor and I'll tell you why because when when when you and I first met you were already an algorithms wizard um uh and you know you we we've told the story before of how we first met when you gave a talk at the Bay Area C user group um on algorithm intuition and um uh afterwards you know you and I chatted and like at least two of the things that we chatted about was one I I told you about reduce by key but we also talked about you know you you had suggested that accumulate that reduce was a better named version of accumulate that was the first place we suggested it and I pointed out to you that in some of your examples that it it didn't necessarily work because of the assumption of um of uh uh you know you you were using some sort of heterogeneous reduction similar to the one that I just described where the reduction operator produces a different type like the this this max consecutive ones up uh algorithm I I described in that algorithm the inputs types are t's but the reduction operator returns summaries and then you know uh it also has overloads that take summaries and T's and reduce summaries and overloads that take summaries and summaries but correct me if I'm wrong before like at that time when you gave that talk before you came to work at NVIDIA you worked on algorithms but you hadn't really w worked on parallel algorithms is that right correct yeah and it's you know now that you've had the experience thinking about how to write parallel algorithms and sort of like where the that's the default mode that you're in you know you you've you've come to appreciate the the subtlety and the distinction between those two and how important like these semantics are um and it's just it's just so so fascinating to me to see you have reached that point.

Bryce

And and I think it speaks to something that's really fundamental about parallel programming which is you you need this whole different mindset. You know when when I think about a problem about how to how to implement an algorithm I I'm not the best algorithms person. I I will freely admit that that is not my expertise or specialty. If you put Connor and I in a room and ask us to solve an algorithm, Connor's gonna probably do a better job of it than me. But I have a bit more experience with parallel programming than Connor. So if you put us in a room and you tell me like my my default reaction is going to be to try to solve the problem in parallel that's just that's just how I've I've wired myself to think. And you know one of the first tools that that I reach for is you know how is there a way that I can express this in terms of a reduction or like what parallel primitive can I express this in. And actually I think I think Connor that you and I have a joint talk in our future a joint talk in our future I'm sure I'm sure there's a at least one joint and I think that talk is going to be like how to write reduction algorithms. Because you're right they are so powerful and and one of my takeaways from this whole experience has been that um they're even more powerful than I had thought and to the to the degree that a large chunk of my job seems to be identifying how people can rewrite something as a reduction.

Conor

Right. And that's and that's the thing is that like when I think about you know you're you're much more of a you know 10-year 20 year thinker of what does the future of programming look like but but you know when when I picture it in my head you know there's sort of two as it stands like sort of routes you can go to writing some parallel program. You can write CUDA kernels or you can write your program in terms of algorithms. And I think it's a at least for me it's a lot easier to express or solve a problem in terms of algorithms that other people have written and and that might be just my functional programming or APL bias. Like I'm I'm used to reaching for maps and reductions and partitions and different algorithms and piping them together. That's basically the thrust model um you know you you have a collection of algorithms you find a way to compose your problem uh and and select them or you can go and write a custom CUDA kernel and you know I I I think Leslie uh lay posted once on Twitter uh a Drake meme of when he's in that song where he's got like the no and the yes face and uh you know he says custom kernels custom CUDA kernels no uh thrust algorithms like yes please or whatever. And and don't get me wrong there's a time and a place in Rapids when we need a CUDA kernel for um you know optimal efficiency or we we can't express something in terms of thrust algorithms. You know they're they're our go-to tool we we do that I'm we're currently I'm working on a PR right now that uh is doing that. But I think for a large percentage of problems um they can be easily expressed in terms of whether it's a reduction or an algorithm that's in you know thrust or cub. And I think that's going to be a way easier you know you use the sort of the the on-ramp uh analogy all the time it's a way easier on ramp to go from oh I know how to do std colon colon insert algorithm to thrust colon colon algorithm um and you know seeing that like it's it's made me appreciate you know you mentioned oh in my talk I had sort of examples I can pinpoint one of them and it was implementing count if in terms of a std reduce and that doesn't work um because basically your accumulator is going to be some size t or some int32 which is keeping track of how many and then your uh element that you're currently looking at could be anything it's just a value type. And so what if you're counting the number of 42s that show up in a list of numbers? Well due to the fact that you're using a std reduce usually in a in a an accumulate your accumulator's on the left so that's your running sum of how many times we've seen this and then your value uh of whether that's a 42 or a non-42 number is going to be your your right uh element in your binary operation. But std reduced it could swap those around and then accidentally instead of doing a plus one because you encountered a 42, you actually added 42 to your running sum. So it completely breaks. And I think I I had an idea at the time that I was writing this code and it didn't work. But I I I was just like yeah but I just like std reduce it's just a better name. And so I I don't want to type std accumulate on my slideware. I want to type std reduce and that was uh I think it's a it's an okay mistake to make at that time but in hindsight um I I definitely I'm sad.

Bryce

I wonder whether you could do that count if implementation with the missing reduce algorithm.

Conor

You can do it with the missing reduce aka associative reduce or find the better name but there's already an existing algorithm that you can solve that problem with. Ooh play along we're playing that we're playing the play along game where Bryce guesses the algorithm and see I would have thought I would have assumed that it was a reduce um so if you're an APL programmer listening to this problem so here's the problem just that we're we're implementing countif which is an algorithm that uh given a list of numbers or a list of values but we'll simplify it we'll just assume we have a list of numbers it returns you the number of times that number shows up so assume you've got the list one two three forty two four five six forty two and you're searching for 42 countif will return you two and if you're an APL programmer or a J programmer or an array oriented thinker um you've already solved this problem in your head guaranteed and uh this is exciting.

Bryce

So so in Thrust we implement it as a transform reduce.

Conor

Woo there we go that's uh ding ding ding. Which is which is awesome because this is exactly how you solve it in an APL. So in APL what you would do is you'd go 42 equals your list and that's gonna turn it into a Boolean array of ones and zeros. So it'll be 00001 00001 and then you just do a plus reduction. And in C or thrust uh you're just gonna do the exact same thing with the transform reduce. Note that this is the transform reduce that just has a single range so it applies a unary operation to transform the integers into ones and zeros or trues and falses and then you do a plus reduction.

Bryce

This is very similar to one of my favorite examples the parallel word count one where which you implement with transform reduce with a with a binary transform reduce and the idea we I'm sure we've talked about it before but the idea there is that as a transformation you you you take you do a binary transform where it takes two inputs and what you do is you look at the a left element like two consecutive elements at a time and you return whether that's the end of a word. And you do that by checking is the character on the left um uh a non-space and the character on the right is a space okay then it's an end of the word and so then that produces a uh an intermediate sequence of ones and zeros where each one represents the end of a word and then you just reduce that and it's it's so elegant.

Conor

Right. And and that algorithm that I think yeah we've explained you've explained that before the transform reduce that takes two ranges that are just using the zip tail trick that could be an algorithm um and I actually presented it in the same algorithm intuition talk not like a parallel version but it's easily parallelizable with the implementation you explained where it's called adjacent reduce. So basically exactly exactly similar to adjacent difference or or what should have been named adjacent transform or adjacent find where you're looking at adjacent elements and then at the end of the day for this we're just doing a reduction and doing basically a plus one whenever we see a a character and then a space um because that denotes the end of a word. Yeah it's a that's a great algorithm that shows up all the time.

Bryce

The thing that makes reductions so powerful is that it is a way to pass global information um uh efficiently like I want to I want to do something that requires me to know something about all the elements in this sequence you know uh uh that requires all of them to in some way to communicate uh and and a reduction is a super efficient way of doing that communication because that communication builds up over time. Uh what what like one of one of the things that uh in my previous job when I when I worked in HPX one of our fundamental tenets was to always localize communication and reduce really really really localizes communication because it it ends up localizing it down to two you know actors at once. And you know on sort of the the you know one of the points you made earlier about um you know how much more powerful language like APL can be for parallel programming than writing things by hand. Um I think you're really right about that and I think that there's I think that there's still revolution to come there. Um you know there's a lot of a lot of interesting research these days and a lot of interesting uh uh Things that have been put into production around these machine learning graph compilers that where they're these compilers where the underlying IR, the underlying operations that are supported are all fundamentally parallel operations. Now they're parallel operations that are sort of specific to the domain of machine learning, but I think that that sort of technology is applicable to just general sequence algorithms. So if you if you imagine an assembly language where every one of your operations is not operate on scalar data, but operates on sequences of elements and where it's all parallel. And um I I I the one of the nice things about this model where you express your code in terms of some known algorithms, some known corpus of algorithms, that is in in comparison to accelerating arbitrary code, accelerating a colle like a collection of calls to known algorithms is way easier. Because all you have to do is you have to implement those known algorithms efficiently. You know, the the the parallel APLs of the future. Who knows? Maybe you'll make one. Maybe it'll be you.

Conor

Oh, Bryce, you're just You've done this so that you can say, I remember back on episode 25 when I planted that seed, and I've already been thinking about this for like since I've fallen in love with APLI.

Bryce

When you started working at NVIDIA, do you remember what I told you you were gonna do? I told you you were gonna build for me the next parallel programming language.

Conor

That actually, if we're gonna be technical technical about it, that was even before I started at NVIDIA.

Bryce

That was before you knew that you'd started at NVIDIA.

Conor

Yeah, I think technically what happened is I I had left my job at Amazon in like mid-September of 2019. Um yeah, that sounds right. And then CPPCon was like in the third week of September, and I want to say I actually like signed my offer. No, I did sign it when I was in Vancouver. Um uh, which I can't even remember. I that was the week after CPPCon. But I remember distinctly being at CPPCon in like the gathering welcome room, or I don't even know. It was like it's the main area of that like lodge, and then we were sitting on the couch, and uh there was a couple people around, and you were like, All right, here's our code name project. Uh you already had come up with a code name for a project that didn't exist yet. And uh it's uh it's an exciting space. Graph compilers right now sort of they only exist in these you know machine learning uh applications, but uh I don't know much about them, but it definitely seems like there's a use case for like a more generalized graph compiler that it's not just you know linear algebra that's sitting on top of it, it's just it's a language. Um and yes, it's a going to be a constrained language, but that's basically what the uh APL family of languages are. Um and honestly, like when you I I'm not we've I've probably mentioned this before, but if you look at the popularity of uh the most popular Python libraries, like what's the number one Python library? It's numpy. And numpy is basically just a variant of APL. Half of the functions in NumPy get their names directly from APO. Reshape, uh shape. I don't know all of them, but uh it it's basically there's articles that have been written that uh talk about how NumPy is uh a ghost of Iverson, who is the individual who created the language. Anyways, I want to circle back too. You asked me what what should this so we're going full circle to like 30 minutes ago when you asked what should the name of this missing algorithm uh this and I'll and I'll I'll tell you why I think associative reduce is a bad name.

Bryce

Because one, um uh associative the fact that it's for operations that are associative is not the important part. The important thing is that it does not commute the end of the case.

Conor

Yeah, it doesn't require commutativity.

Bryce

Yeah. Now, but non-commutative reduce be a bad name too, because I think it's the more common case than reduce.

Conor

So And I guess maybe a question too is if if we could, you know, what should we name this missing algorithm? And on top of that, if we could name std accumulate, std reduce, and this lost algorithm, you know, carte blanche, if that's if that's the correct way to say that. Oh, and also I'm gonna just interject here. Um this I meant to say this earlier, and if I don't say it now, I'll forget. Uh there were two people on Twitter that I actually I believe came to the solution that we expl explained. Uh so Jean-Marc, I'm gonna mispronounce your last name, I apologize. Uh Borgette, it's B-O-U-R-G-U-E-T. Um, I apologize. And then also uh Toby Isaac, I believe, um both have a solution with this sort of summary object that's got four pieces of information, you know, the ones at the left, the right, and the max.

Bryce

Um so we weren't well well and and we have to thank Tony Lewis, who if if if Tony had not uh mentioned this at the end of our of our uh Zoom call, I would have totally forgotten. And we net this episode never would have happened. So thank you, Tony.

Conor

Yeah, thank you, Tony. This is uh and it's uh I think it's a really important. I hope folks, this is definitely gonna be one of our longer episodes, but um especially if I include the stuff about my sock drawer at the beginning. But uh so what do we what do we call?

Bryce

What do you think you'd name it? Um well there's fold. Like, but like C23 ranges are gonna probably use fold for something.

Conor

But I just finished telling Barry Revzin earlier a couple hours ago because he was asking me on the naming of uh the proposed C23 reduction algorithm, and I said, I think I'm gonna write a paper just like purely on the namings, uh naming of fold, because we already have std accumulate and reduce, and I don't think we're gonna How do you how do you feel about the fold?

Bryce

Like Barry hit wants fold with initial value to have a different name than just fold. And I want the Python thing where they're they have the same name, they're just overloads.

Conor

I honestly like I I don't know how I feel because I've looked at too many languages and like have forgotten, you know. I know Haskell does like fold, fold L, fold R, and then fold L1 and fold R1. Uh Barry just linked me uh apparently Rust used to call it fold first, and now they're they just finished renaming fold first, um, which I believe is the one without the initial value to reduce.

Bryce

And I think that's what a Wait, wait, whoa, whoa, whoa, whoa, whoa! How can fold first be the one without the initial value? Like that what I I I completely misunderstood those names because I seen fold first was the one with the initial value.

Conor

Let's open uh let's open Slack so I don't get this wrong.

Bryce

I told Barry to talk to you too, by the way. Um I don't know what I CCU in that email, but my my so so key key management and leadership tip for people quickly learn how to hand off emails and tasks whenever possible to someone else, even if that person doesn't technically work for you. Well, you well, you you gotta you gotta give me some name ideas for this new algorithm. I am gonna go make somebody implement this in Thrust. Actually, actually, there's a chance that that uh that the person who's impl who's gonna be implementing this, uh who is starting at NVIDIA soon is listening to this right now and is wondering, hmm, when he says I'm gonna make somebody go do that, does he mean me? The answer is yes. If you're starting at NVIDIA in my team in like two weeks, this will probably be a task that you'll do.

Conor

So I I still uh don't because I need to read the details and I will go and fix this in post. But one of the alternatives for fold first that was being suggested was try fold first, which almost definitely makes me think that it is the one that doesn't take an initial value because the try implies that you might fail, and the way you fail is if you have an empty list. So I'm I'm almost positive that like fold first is the one that means just use the initial, use the first element of the list as your initial value. And so yeah, uh Haskell, Haskell has fold L and fold R, and those ones takes it, those ones take initial values, and then they have fold L1 and Fold R1, which don't take initial values. A lot of languages, they just choose two different algorithm names, like fold and reduce, and you just need to know, oh, the reduce is the one that doesn't take an initial value. I think that's what basically ended up happening to Rust. And I don't know. What what I'm gonna do is I'm gonna go and look at every single language. Um and and then that's and that's the thing, is on top of like initial values or not initial values, there's these associative associativity and commutativity requirements.

Bryce

Yeah, I would be really it would be really interesting to see a survey of what other languages call these and w whether the associativity and commutativity is uh is respected in in the various names of those things. So yeah, go make me one of your pretty tables.

Conor

It'll be yeah, it'll be in the form of a paper. Maybe I'll make a YouTube video as well.

Bryce

Um honestly, I think that it I think that if if not for the fact that that we were going to use the name fold for the ranges version of accumulate, I would probably use the name the name fold for this.

Conor

Um I I feel like if I were doing this from scratch, um I don't know, there's a part of me that actually wants like uh the requirements of associativity and commutativity to be represented by the word like par, par underscore. Um, or like put that in a namespace so that like the parallel algorithms could have been like stdd colon colon par colon, um, and then we could have just used the same names, um, arguably.

Bryce

Um yeah, it's actually interesting. If you look at um libstdc's implementation of std reduce, not the parallel version one, but just the regular one, you'll see that even if you're not worried about parallelism, the redu like like they have a more efficient implementation because um uh uh they don't have to, you know, they don't have to avoid commuting and they can just associate the operations however they want. So um it's not necessarily inherent to parallelism.

Conor

So yeah, I I feel like there's like a space though for like just the calling the accumulate fold left and then having a fold right version just for symmetry, and then um having like parallel fold left and parallel fold right, and then having like parallel fold. And you're not explicitly pointing out that like, oh, the parallel fold left doesn't require uh that your operation be commutative, but that's implied. Because I think it's actually what's what's more important is the behavior. And honestly, like until you at least for me, until I got hit over the head with like commutativity and associativity like four different times, I could never remember which one was which. And actually, one of the things that helped is that in APL, there's an operator called commute, which basically swaps the order of arguments to a two-argument function. So if you uh like it's a very classical thing to do if you have a minus operation or you're trying to do a minus reduction on something, and you need to swap it, well, instead of writing some uh custom lambda or what they call a defunct in an APL, you just you apply the commute operator to the minus operation and then with a single character you swap the order.

Bryce

Um subtraction is a great example of something that of an operator that does not support uh uh that that's that's non-associative, that does not support, you know, be uh std reduce. Um uh you you could use it, it's just that like, you know, you you might get unexpected results. Whereas addition, you know, and I when I when I say sub subtraction, I mean like subtraction on the set of natural numbers. Um likewise addition on the set of natural numbers is a good example of something that that does support commutative that that uh sorry, I said associativity there, I meant commutativity for all of what I just said.

Conor

Yeah. I know that in um in uh in Q, which is uh array language, they have parallel versions of some of their functions, and they just prefix it with a P.

Bryce

Um so they have like each which I don't I think that that's I think that that's wrong though. I think that I think that that the these semantics are not about parallelism.

Conor

So you don't like the fold left, parallel fold left, and parallel fold?

Bryce

No, I don't. I don't I don't I don't think it's about parallelism, I think it's about commuttivity and associativity. But I think those are just words that are too long to put into the name.

Conor

But so you'd what what is your take on like parallel and left implying that you don't need a commutative operation and parallel with you know fold or whatever not require or requiring both of them? Um like you're like so you're saying that it really what's key is associativity and commutativity, but is there is there no way to name the algorithms that like doesn't make that explicit and overwhelm the user, or should we just expect that in 20 years parallelism is gonna be everywhere and it's just gonna be the same way that learning what std accumulate does and how um important that algorithm is, we're gonna expect people to know what whatever the different variants of these parallel versions are.

Bryce

So, as I often say, one of my goals is to normalize parallelism. Um and I I I just think that the way that the algorithm is executed should be completely divorced from the the the semantics that it expresses. Like uh you should like a std reduce and like this is why uh there is both a when we had to introduce a new like a std reduce because we couldn't parallelize std accumulate, we didn't just add a parallel version of it. We didn't just call it parallel accumulate. There is both a std reduce that takes an execution policy and one that doesn't.

Conor

Right, right.

Bryce

Um and I I think that that's absolutely essential that you separate parallelism from the semantics of the algorithm. There are some algorithms that you want specifically because they're more useful in parallel execution, but um I don't think that you should say that those are parallel algorithms.

Conor

Yeah, I'll have to I'll have to think. I'll have to think. I'll have to write the paper.

Bryce

And um my guess is that like one naming scheme that would probably be if if the if the naming scheme was like very clear, like it's like uh you know, I uh maybe non-commutative reduce isn't the worst in the world. That's actually the name of if you look in the wording for std reduce and for st in and for the scan algorithms, we actually have these things called generalized sum and then generalized non-commutative sum. So maybe non-commutative uh reduce isn't the worst word name in the world. Again, I think that it's actually more useful than than reduce. Um uh I'll boldly claim that.

Conor

I mean, it's is that even a bold claim? It's a it's a less restricted algorithm.

Bryce

Of course it's gonna be um uh stood reduce if you don't need if you don't need the freedom.

Conor

Right, right.

Bryce

It's uh um it you may take a big performance hit for it.

Conor

Right.

Bryce

Um like if if you if you if your operator is commutative, you may may take a big performance hit from from invoking the version of the algorithm that assumes that you can't commute.

Conor

That'd be actually I would I'd be interested to maybe I should go. That's if I ever come out of retirement from speaking, uh profiling this kind of stuff on a variety of problems, it would be in interesting to see what is the impact.

Bryce

Yeah, to explain why we'd have to do a whole separate episode talking about memory coalescing. And you know, we we've we've talked a few times about how to get Olivier on this podcast to explain to people what GPUs are, and maybe that's the way to do it is that we tell him, hey, because last the last time we talked to Olivier, she was like, that's such a big topic. You have to give me some parameters. And so maybe the parameters that we give him is we tell him, uh, yeah, come on and explain memory coalescing. Explain how like the world of memory traffic is completely different on CPUs and GPUs in terms of what's optimal. Um boy, this is just gonna be a really difficult episode for you to cut. There's no clear middle point. We normally like this.

Conor

We I don't think I'm gonna split this. I think I'm just gonna release it all as one because uh it deserves that.

Bryce

But like no the audience should understand that normally when Connor and I record, we record on Saturday mornings, Saturday mornings for me, Saturday afternoons for him. Normally we record for an hour and a half, and that becomes like three episodes. This is not that.

Conor

Yeah, we're at like what an hour and 15 minutes, and uh I really want to include the socks stuff, so it's just we're you're gonna be if you're if you've listened through.

Bryce

I only got an hour and five. I only got an hour and five minutes here on my on my recorder. So my my remember when we started this podcast, how long did we say episodes were gonna be?

Conor

Uh my goal was 30 minutes, and then it became like an average of 35, and I was like, nah, that's perfect.

Bryce

35 minutes is I thought that we said I thought that we said 20. Oh, yeah, yeah. It's true.

Conor

Because yeah, uh Magic Read Along is like roughly 20. It's like a long episode for them is like 30 minutes. Um that that was the goal.

Bryce

We never had an episode under 20 under 20 minutes.

Conor

No, I think our shortest ever was like 23, and that was because that was the episode on uh our impromptu episode on inclusive language that happened inception like because we ended up recording it in the midst of another episode. Um I'm sure if we had set out just to talk about that from the get-go, it would have ended up being 40 minutes easily.

Bryce

Yeah. Alright, well, we should probably shut up before this becomes uh uh unbearably long. But um, anyways, we will we will put the uh the godball with the uh implementation of this algorithm. Now, uh I have I have done some verification that it's correct, but um I I I do not know that I currently have any parallel uh implementation of this of the reduction that I need to actually test this. So uh uh but but but don't worry, I will soon have somebody put this into into thrust and then we'll be able to uh to play around with it.

Conor

Yep. Thanks for thanks for staying tuned in this long. Or, you know, potentially we're talking to nobody and everybody turned us off at this point. Um that's also possible.

Bryce

But uh this is this podcast's really more for to make us feel good than to than for the audience, anyways, right?

Conor

Thanks for listening and have a great day.