Bryce

Oh, Connor's Connor's too healthy for his own good. Connor, Connor is like this crazy runner.

Conor

Pause. Uh I need to go put coconut milk. Or uh coconut milk and kale in this curry thing.

Bryce

And I just wanna wring his little neck. I'm down at zero indexing.

Conor

Yeah, this is just this is just a bit to put in the end of our podcast, episode one, recorded on November 22nd, 2020. My name is Carter, and today with my co-host Bryce, we're gonna be revisiting Student Transform Reduce and other unfinished topics from episode 0.

Bryce

The original question for episode 0. The original question for episode 0 was what is your favorite algorithm? Like favorite algorithm singular, and uh we have feature creeped way past that. I think um we covered uh like four algorithms in episode zero. So this is, I guess, part two. Um yeah, so uh yeah. So before we before we get into this, because we're gonna talk more about transform reduce, because that like this is this podcast is called algorithms um plus data structures equals programs, but it's really transform reduce equals programs. Um so we're gonna talk about reduce transform reduce, I'm sure a lot throughout this podcast, but today we're gonna talk specifically about it a bit more. But before we do that, we should explain a little bit about our our jobs and our background because that's sort of relevant to our passion for transform reduce. Have we started the podcast? Yeah, this is the podcast. This is the podcast right now.

Conor

All right, I had no idea we started. Uh so what are we what are we talking about now? We're explaining all right where we work. All right, you go ahead.

Bryce

Uh okay, so so well, both of us now work at NVIDIA. Uh that wasn't always the case. You didn't work at NVIDIA, and then I was like, Connor needs to work at NVIDIA. Um, but so I work at NVIDIA and I uh my team works on um what's called our C core compute libraries. Um and one of those libraries is an algorithms library called Thrust. So it is it's in particular, it's a parallel algorithms library. And uh for me, the reason why Transform Reduce is so exciting is because it is, I'd argue, the the most powerful of the C parallel algorithms. Um and we'll talk a little bit more about that later. But uh you should explain. So so I'm coming from this as the implementer of um the algorithm, whereas you are actually one of my users.

Conor

True. So also, too, before uh I start talking, uh explain to folks because I I um envision that over time, less and less of like I I assume at the start a high concentration or percentage of our listeners will be C developers, but over time that uh proportion will decrease as other listeners join. Uh so I started my career as a C developer. Um I spent a year at Amazon doing a bit of C, uh Java, Python, a tiny bit of Go, tiny bit of Pearl. Um, and now I'm back to doing C and a little bit of Python. Uh so what's your background? Have you been C from start to finish?

Bryce

Um so so in episode zero, we talked about how I uh flunked out of college and um uh started teaching myself to program in C to uh create a game, and then I uh I discovered Boost through the Boost uh uh the first algorithm I was exposed to was Boost algorithm split. And uh then I quickly got distracted from the project I was working on by just contributing a Boost, and uh then I needed a job because I had you know dropped out of college. My parents were not super thrilled about me just like sitting in their basement. So uh I knew this guy on IMRC, uh Hartmitt Kaiser, and I was like, hey, I'm looking for a job, and he's like, hey, why don't you come down to Louisiana? So then I somehow talked my uh uh my parents into uh buying me a one-way me, a 19-year-old, uh fairly sheltered child, a one-way ticket to Louisiana, and uh it that worked out pretty well. So I was there for a number of years, um working at uh Louisiana State University doing um uh high performance computing, um uh scient building um uh uh parallel runtimes for scientific applications that run on supercomputers. And I did that for a few years. I worked on this thing called HPX, and then I uh I went to Lawrence Berkeley National Lab in Berkeley, California, um, and I did some other uh HPC stuff. Um and uh then I came to work at NVIDIA, and throughout that entire time I have almost exclusively programmed in C. My old mentor, Hartmitt, he he used to say like there's like three acceptable programming languages C, JavaScript, and Python. Um and so that's basically all that I've ever really worked with. Maybe with the exception of I I interact a bit with Fortran. I have a weird passion for COBOL, in particular the history of COBOL. And um I write a lot of bash scripts, and uh I think Bash is actually like a pretty great programming language.

Conor

So we'll save we'll save Bash for a whole episode. We'll save the history of COBOL for another episode. Uh but do you know why uh Hartman said that those three JavaScript, Python, and C are the only three that you what did he say? The only three that are uh real programming languages, or the only three you need to know?

Bryce

Like in his mind, like those are the three the three acceptable programming languages. Like like if you knew those three programming languages, like C wasn't the answer for all problems. He he admitted that. He was first and foremost a C person. But it wasn't always the answer for everything. And so if it wasn't the answer for something, then you should do that thing in either Python or JavaScript.

Conor

I see.

Bryce

And uh I don't I don't particularly know the rationale. I mean, uh Python uh it's a nice language. Um it's very popular in data science and in HPC, so maybe that's why. Um I don't know about JavaScript. I mean, I guess it's you know, if you need to deal with some web technology, it's uh it's it's one of them.

Conor

Okay, so to summarize, you're basically start to finish C with a little bit of uh bash, Fortran, COBOL in the midst, and I'm the more of the polyglot one um or polyglot developer, I should say.

Bryce

I I take it back, there is one common theme between all those languages, and I'm and I suspect it's part of the reason why my my mentor Hartmet liked them all. All of those languages are Python, C, and JavaScript, they're all fundamentally multi-paradigm languages. Um they're not purely functional languages or purely imperative languages or purely object-oriented languages. Instead, they support multiple different paradigms, um uh which gives you, the programmer, a great deal of freedom in how you write and structure code. And that was something that I think was always valuable to Hartmet. He is somebody who um, you know, if he goes and looks at a problem, he'll come up with a solution for it which um combines the power of functional programming, um, object-oriented programming, and you know, the efficiency of just writing low-level imperative code. So I think that's what he probably liked about all those languages.

Conor

Yeah, that's a good point. Multi-paradigm. I prefer multi-paradigm languages because then I get to write code the way that I want.

Bryce

So before our um before our tangent into the uh the three acceptable programming languages, according to Hartbit Kaiser, um, we were pointing out the fact that I am a implementer of uh a C algorithms library, and you are uh are now a uh consumer. So uh why don't you explain a little bit about where you come from?

Conor

So, yeah, in in a nutshell, uh I work for a team called uh Rapids. That's all capital letters. Um you can At NVIDIA. Yeah, at NVIDIA. Um and this is uh this is sort of a newer uh kind of team for NVIDIA in that we're entirely open source. So Thrust um is obviously an open source library, uh, but I I think that's probably the first open source or like the major, at least the the first major.

Bryce

This is the first open source library at NVIDIA. It is funny that that both you know NVIDIA is a company not historically known for open source, but both you and I work at NVIDIA, and we both pretty much spend 100% of our time working on open source code or on open standards.

Conor

Yeah, so the the Rapids team like from the from the bottom up uh was built to be like a remote open source team. So all of our development happens on and through GitHub. Um I rarely have to like log into VPN because my my day job is like uh working on PRs and issues that are posted on uh the Rapids uh project. So specifically, I work on QDF. Uh the Q the CU stands for uh CUDA and DF stands for data frame, but Rapids is a number of uh projects, not just QDF. But basically what Rapids is designed to be is a end-to-end data science pipeline that runs on the GPU. Um and each of the projects or repos within Rapids sort of targets an existing uh library that exists in sort of the data science ecosystem, um, but that doesn't run on the GPU. So specifically, uh QDF targets or tries to sort of maintain parity with a Python library called Pandas, which is extremely popular. Uh so if you're a Python dev, I'm sure you've heard of Pandas. I believe we have QML, the ML in that repo stands for machine learning. Um, that targets ScikitLearn, if I believe. Um and then there's a ton of other repos and projects, Q Spatial, QGraph. Um I won't go through them all, but it's a super, super exciting team. Um I absolutely love the work that we're doing there. Um we I write in C 14. We should be upgrading to C17 uh in the next I don't know, year or so. I think we it depends on the case.

Bryce

And it it plays well into your background too, because you you actually like originally were schooled in actuarial science, which is a good fit for data science.

Conor

Uh yeah. I I went to school to study actuarial math, and there is a lot of uh sort of finance applications, I guess, that leverage data science. I would say though, um a lot of the work that I do is sort of abstract, um, with with no like with no specific domain in mind, um, which I actually love uh because I really care more about like code quality and like the code that I'm writing than I do actually on like the product that's being built at the end of the day. I think it's awesome that there's a lot of um like national labs and um a lot of like really really big corporations that need to crunch a ton of data that are leveraging this library. Um but at the end of the day, like I am at heart like a library writer. I'm not like an app developer.

Bryce

Um Yeah, we're we're both we're both fundamentally framework people. Um you know, I the one of the analogies I like to use is that um, you know, software is sort of like a library. Um uh there's people that write that author the books, um, the library authors, and then there's people who come in and read the books and and use knowledge from the books to build actual concrete things. Um that's people who build, you know, end applications. Um and then of course there's you know the people who define the languages that uh for that you use to write the books, um, which we also do a part of because a large part of you know what we do um is uh or a large part of what I do, less so you, um, is work on uh programming language standards. Specifically, I spend a lot of my time on on the C standard. Um but uh but you know this um uh the data science world is actually sort of a good um intro into why we both think transform reduce is so awesome.

Conor

So before before we do that though, I just realized I went on a uh ramble of you know uh rapids and why I think rapids is awesome and failed to mention how that makes me a consumer of thrust, um, which is the connection. So uh rapids is heavily built on top of thrust. Um which is fantastic because when I came to NVIDIA, and even still now, uh I do not consider myself like a GPU computing expert. Um I'm not like uh anywhere near like the top of the distribution when it comes to writing like CUDA kernels. Um but most of the time we're not writing CUDA kernels in Rapids. We're just leveraging the work that's already been done in Thrust. And so if you're familiar with the STL algorithms, you basically just instead of writing STD, you just write thrust colon colon and you're programming on the GPU. Fantastic. Um so yes, that's how I'm a consumer of or Rapids is a consumer of Thrust. But yes, back to Transform Reduce.

Bryce

Well, and and like let's say here's a data science problem. Let's say that you've got um census data, let's say, US um census data, um, as one big data set, and you want to um count some property of that data set. Like, for example, you want to determine how many people are over 30, 30 years old um uh in this huge data set. Well, one way you can do this is with transform reduce. So in that case, your transformation function is a uh function that takes um you know a record uh for a person in this data set and uh returns true if um uh that person is older than 30 um and false otherwise. And then your reduction operation uh just you know adds adds up uh uh all the trues and uh into some integer value. Um and you probably are using some big int type uh if your data set is you know really truly large. Um and uh uh this is um uh uh a good approach to to implementing this because transform reduce is inherently something that uh that we can easily paralyze. Um the transformation uh is embarrassingly parallel, and redu then the reduction part, well, we we we know how to paralyze reductions. That's a fairly well-known um uh science, and it can be done fairly efficiently. Um and so so that's one really good example um of how uh you can use transform reduce any time that you need to count a property.

Conor

So so here's a question. Uh you know, while I'm listening to you explain that, you've got uh some record, you're either turning that record, you're turning that record into basically a one or a zero based on some property, and then you're just adding up those ones and zeros to get a total count. Um in my head, and I'm sure in uh some of the listeners' heads, they're thinking, why not just use a std reduce uh or a std accumulate uh where you know your accumulator is the total count, and each element uh that's being passed into your sort of binary oper reduction binary operation is try d doing the transform and uh the reduction at the same time. So it's taking the record and going, you know, using some ternary expression or if an if statement, you know, if uh greater than 30 or whatever your age is, add one, otherwise add zero. Um and this is something that I misunderstood that you there's a reason that that actually doesn't work when you are parallelizing uh your algorithm. You can't just take a std accumulate that's doing that reduction and change it to a std reduce. Do you want to explain why that is?

Bryce

Well, yeah, because um uh in that case, that that sort of reduction that you're describing, um uh that reduction depends upon uh uh things happening in a sort certain order, right? It it it it it depends upon a um a left fold, right?

Conor

Uh correct.

Bryce

Yeah. And and um uh a parallel reduc reduce um uh cannot be constrained in that way. Um if if you always have to fold from the left, then you can't actually really parallelize things, right? Because um then you know the second the second reduction that you're doing in the set is always gonna depend on the first one, and the third one will always depend on the second one, etc. etc. And so the algorithm becomes inherently sequential. Um and so you need to uh like a parallel reduc reduce cannot make that guarantee. Um and uh and thus um uh something that might like be a very natural way of writing the code um sequentially doesn't necessarily lower well to um uh a parallel implementation.

Conor

So yeah, another way of like wording that is uh you have to adhere to like the two properties of the reduction operation for both std reduce and std transform reduce, which is that they both need to be associative and commutative. And in the binary operation that was doing the reduction using a stdd reduce, when your first element uh is the total count, which is some sort of integer or big integer type, and the second element is like your record type, like there's no way that's gonna work. So you can say yes, you'd need a fold left for that. Another way to say is like you don't have an associative and commutative operation. Um so you need the transform from the transform reduce to like uh modify uh the data that you have such that the reduction that you do doesn't depend on order or isn't uh commutative or associative, or is commutative and associative. So in this case, we're turning our record into just an integer or a big integer, uh, which then when we have sort of like the running sum and a one or a zero, it doesn't matter what order you add those up, you're always gonna end up with the correct answer at the end of the day. Which is like it's a super important insight, which I didn't have for, I don't know, a number of weeks.

Bryce

And if and if you if you don't uh know what you know associativity or commutativity means, um here's a simple um mental test that you can use to um uh think about whether a reduction uh in your code um is going to be paralyzable or not. Um if that reduction is has heterogeneous types, um so the left hand side is a different type than the right hand side, that probably means that um you are doing some stateful reduction into one of those two types. You know, the the left hand side um has some accumulation of uh uh the running state um of the algorithm. And that that means that it's not an algorithm that you can or that's not a a pattern that you can uh paralyze.

Conor

Yeah, that is a good way to think about it.

Bryce

Yeah. Um so so another thing we should talk about um is uh the Rity of TransformReduce. Um so uh actually the first the first proposal I ever wrote on the C committee was adding um a binary transform reduce. Um C's uh sequential version of transform reduce inner product um uh uh takes two input sequences and the transformation function that it applies takes one element from each of those two input sequences. Um and uh the parallel version, we didn't have that. The parallel version uh we were just going to ship uh transform reduce, um just one form of it that took only a single input sequence. Um and I wrote this paper saying, hey no, it's actually really useful to have the binary one. Um You can do very cool things with it, like a word count algorithm, or something like doing a dot product with this binary transform reduce that takes two input sequences. And one of the common things that users of the Thrust library that I work on do is something that I uh I think you've come to call a zip reduce, where what if you have three input sequences or four input sequences, etc.?

Conor

Yeah. Zip reduce is one of the names that I mentioned in a couple of my talks. Um I think that TransformReduce at the end of the day is uh the correct name because as you point out, um there is both a version that takes a single sequence or a single range and one that takes two sequences or two ranges. And in the single range version, you're not doing any zipping operation. Um but internally I think of uh the two-range version as an algorithm called zip reduce. And in fact, that is exactly what it's called in certain functional programming languages, like Haskell, the two-range zipping and sort of transforming algorithm is called zip width. Um which I think is uh it's great that they highlight zip. I'm not sure about the width, uh, but definitely I like the zip.

Bryce

Um yeah. And we don't we don't uh or we we have we did not in the original C algorithms have an algorithm like zip, although now we have that with uh with ranges, right?

Conor

Uh it is proposed in the uh you know a plan for C23 ranges paper. Um so depending on uh how well you do getting stuff through Lug, um it might end up in C23.

Bryce

Yeah, we should we should explain. I uh uh I am the chair of the C committee's library design uh group. Uh so uh my ability to uh uh manage a standardization process can have a very real impact on whether or not we're able to get cool stuff into the next revision of the C standard. Uh but it's but no pressure or anything. Yeah, no pressure.

Conor

So a question, it sounds like actually. I always thought um this this came up in I was on CPPCAST last week, and this came up that uh I had mentioned that transform reduce was sort of the revamped uh parallel version of uh the STL algorithm inner product. Um and I pointed out the the two differences, one being that you know there's tighter restrictions on uh transform reduce and that uh transform reduce also takes uh a single range, whereas inner product uh you can only take two ranges. Um and so I had always thought that transform reduce was actually just like an evolved version of inner product where they added the extra single range, but it sounds like if you're writing a proposal to add the two ranges, that transform reduce uh started out as just like an entirely like it was designed as an algorithm on itself, not as an evolution of std inner product. Do you know if that's the case?

Bryce

Yeah, so um uh so the the C parallel algorithms are based on the thrust library that I now work on. But at the time that they were being standardized, I worked on this parallel runtime called HPX and didn't work at NVIDIA and wasn't particularly familiar with uh uh the thrust library. And uh the thrust library had introduced transform reduce, and I think the mentally the model there was it's an extended version of reduce. It's a more efficient thing to do than to do a transform, uh to do yet a transform uh followed by a reduction. Um and uh I think that's why it takes only a single input sequence, because reduce only took a single input sequence. Whereas um in HPX, we always thought of it as naturally being the parallel version of inner product. Um although I should mention uh Thrust does have a parallel version of inner product um uh under the name inner product. Uh and that may have been a part of it too, that the original plan was for transform reduced to just take a single input and for inner product to take two inputs, but for there to both be a um sequential and a parallel version. Um and this is actually one of the big design questions about the parallel algorithms. Um should we have parallel versions of the algorithms with the same name, even if the parallel version cannot provide the same guarantees as the sequential version? And in some cases, in most cases, we said no, if the parallel version requires fundamentally guarante different guarantees, then we should give it a new name. And that's why in C we have both accumulate um a sequential algorithm that does reductions, um, but in a certain order, um uh and reduce a uh uh which has a both a sequential and a parallel version, but makes no guarantees about the ordering. And uh uh requires uh commuttivity and associativity.

Conor

Interesting. So I actually did not know Thrust had I'm staring at the docs right now. We'll we'll put it in the show notes, but inner product. So inner product is a parallel version of the STL inner product without the uh requirements on the binary operations. Um is that that's correct?

Bryce

Yeah, that's right. Yeah.

Conor

Interesting. Um Yeah.

Bryce

So I I I would argue that um that is something of a historical mistake in Thrust, that we probably didn't really mean to do that. Um uh but it's you know, it's a little bit too late to fix it now.

Conor

Do what specifically?

Bryce

Have both inner product and transform reduce or oh no no to have the to have a a parallel inner product under that name was probably a mistake. Um because we don't have in Thrust an algorithm called accumulate that's parallel. Um we don't have in Thrust an algorithm called IOTA that's parallel. Um out of recognition that those algorithms were um like the name, those named algorithms in the standard library were inherently sequential. And so the when we introduced those into our parallel algorithms library, we gave them different names so that people would not associate the semantics of the sequential one with the semantics of the parallel one. There's other algorithms like transform um where there is no difference in guarantees um aside from guarantees around race conditions between the sequential and the parallel version. Um and uh those guarantees around rate race conditions being essentially, you know, okay, if you're if your transformation function um uh your transformation functions need to be thread safe. Um uh but there's no big difference like hey, you know, the accumulate supports, non-commutative, non-associative um uh uh operations, whereas you know, reduce doesn't. Um and and so uh you know there's a lot of power in names because names associate semantics with them. Um and I think it was probably a mistake for us to use the name inner product, which has an association with um uh those guarantees that std inner product makes, to use that name for a parallel algorithm that doesn't make those guarantees is probably a mistake.

Conor

Interesting.

Bryce

Yeah.

Conor

Well, I feel like we've gone over time once again, and I feel like you're probably right. There was a third topic we were supposed to, because we were we were supposed to revisit all the stuff we said we would talk about in episode one, and then we just sort of like.

Bryce

Oh, yeah, yeah.

Conor

I can very quickly wrap up this episode by just saying that if you recall from episode zero uh what outer product was, um, to recap basically a Cartesian product where you take two lists and you uh generate all possible uh combinations of the elements of those two lists, uh except a Cartesian product just produces a flat list, whereas outer product uh produces uh a matrix with the dimensions of uh the lengths of your two lists. Um a triangle product basically uh avoids the duplicates. So if you imagine yourself with a matrix, uh just looking at the upper triangular matrix of that sort of matrix that you started with is what triangle product does. Because a lot of the times when you're using outer product to perform some binary operation on pairs of elements from two lists, you don't actually want to do uh the operation uh twice for you know the pair at index two ten. Um you don't want to also repeat the operation for the uh uh pair of elements um at 10.2, which is basically the same elements just reversed. Um obviously if your binary operation uh is something like minus uh that's not associative, um you're gonna wanna you're gonna want to perform that in both directions, but for something like multiplies or plus, uh you don't actually need to do that. And you can save yourself like uh twice as many computations. So a triangle product is basically just an outer product that only takes the upper triangular of the matrix, um, which is a common pattern in array-oriented languages. Uh, but as I mentioned in episode zero, I have not found an algorithm uh in any language that does this kind of thing. But probably our listeners are thinking it's super niche, um, which it is. But when you want it, it's irritating to have to compose it yourself. Um, and I've run into it many times. So I think with that, we talked about transform reduce more comprehensively. We actually talked about where we work and what languages we've worked in, and we talked about triangle product. Anything else we need to mention before we call it?

Bryce

I think we should call it.

Conor

Alright. And are we gonna be are we gonna be releasing these on Fridays or Tuesdays?

Bryce

Uh I think that's uh I'm gonna delegate that decision to you.

Conor

Okay. Our first one was released on Friday. Uh we might release this one on Tuesday, because apparently Tuesdays might be better than Fridays for some reason.

Bryce

Um Yeah, there's some data to that effect.

Conor

Alrighty. With that, thanks for listening. We'll see you in the next one.