Conor

Wait, I gotta I gotta go get my Lady Great Tea, okay? I'll be back in uh and we'll talk about that. We'll talk about that in like 30 seconds, but I need my I need my uh my hydration. Maybe I'll gonna pick up a strawberry perrier as well, because you know. I'd offer you one, but you know, you're in New York, so bad choice.

Bryce

There's so much to unpack to that. So much to unpack, dear listener.

Conor

Welcome to ADSP the podcast episode 43, recorded on September 11th, 2021. My name is Connor, and on today's episode with my co-host Bryce, we talk about parallel scans and what the associativity requirement on binary operations actually entails, as well as NASA plants, Ramonadon numbers, and more.

Bryce

Oh see, I I bet I bet you expected me to be late, and that's why you aren't ready on time.

Conor

Um Well, let's let's talk about this, Bryce. You've been late 33 minutes once, 28 minutes once.

Bryce

You know, the the the group that I used to play Magic the Gathering with in uh in California, there may have been a few times where I was confused about whether we started at 6 p.m. or 7 p.m. on on Friday nights, and so I showed up an hour late. And so they they they of course never let me forget it, and they started using Bryce as a verb to mean late. You know, so somebody would be like, oh, I'm gonna be five minutes, or not as a verb, as uh whatever part of speech it would be. I'm gonna be five minutes Bryce. Um, yeah. Um wait, so so so you you just you just uh you just um indicated that I was missing out for having moved to New York, like but I'm closer to where you are, so it would be more practical now for you to send to share a drink with me than it would have been when I was in California.

Conor

Uh yeah, I guess that's true. That's true.

Bryce

Were you just suggesting that I made the wrong decision and not deciding to relocate to Toronto?

Conor

Maybe. Alright, here listeners. Uh usually I would mute this. This is the sound of a strawberry perrier being opened. It's it's gonna be it's gonna be magnificent. You ready? Here we go. Actually, that was pretty bad. I'm gonna cut that out. Or maybe I'll go get another. Maybe I'll go get another strawberry perrier later.

Bryce

My uh what, you're gonna re-record that? You're gonna redo that?

Conor

No, I mean these things are only 250 milliliters. I'm gonna pound through this in like 30 seconds.

Bryce

My stuff is here. Organized boxes. Well, all my boxes are here. I I do have a bed.

Conor

Yep. Our listeners are informed of uh all of your furniture and my furniture that for that matter. We're keeping our keeping uh the listener. Hey.

Bryce

Yeah, yeah, there you go. Good one. I I I I told Connor, I told Connor that uh we should start referring to our when we when we break the fourth wall and and talk directly to you, the listener, that we shouldn't talk about you the listener in the plural. We shouldn't say, you know, uh audience, you know, insert some fact about Connor here that I want to tell you directly or something like that. No, instead, I should directly address you, specifically you. Yes, you. Whoever's listening to this right now, because it creates a more personal experience for the podcast. I picked up that a lot of the big podcasts um do this.

Conor

Should we just assume also that everyone we talk about is a listener? So when we mention, like, you know, Tony's name, we just say, Hey Tony, how's it going?

Bryce

Uh oh yeah, of course. Of course. Because because either they're listening and they feel special, or they're not listening, and then we have a chance to to guilt them over it later.

Conor

Oh, yeah, that's a good point. Yeah, that's how we should grow our uh listener base is through emotional manipulation.

Bryce

Um it is it is what my people are known for.

Conor

So we gotta we gotta start things off by addressing the first ever ADSP, the podcast, Twitter poll, which was obviously if you're listening.

Bryce

I am unfamiliar with this.

Conor

It's uh when Bryce uh previously had said uh quote, any civilized person knows what a credenza is.

Bryce

Now I do know I do know what's happening.

Conor

I posted the question, so I wasn't sure if I should I should have posted it I have heard of or I have not heard of, um, like just a truefalse sort of thing, but I opted for like the balder dashed let's make up things. Um so I put four options. What is a credenza? A pastry, B, luxury car, uh C furniture, and D clothing. In last place, with 4.7% was a luxury car. And I should also give myself some credit that when I said it sounded like a Ferrari credenza, I think the reason why a bunch of people knew what this was is because they're Italian, and it's an Italian word, and uh luxury cars mostly come from Italy.

Bryce

Yeah, and Germany. And Germany, not to offend our German state. Did you capitalize credenza in the poll? Because if you didn't, then obviously people would be like, well, yeah, it can't be a luxury car because otherwise it'd be capitalized.

Conor

Oh, yeah, good point. It was not capitalized. I uh I done messed up.

Bryce

All right, all right, so that was four. What was three?

Conor

Uh in third place was clothing at 11.2%. I really should have, instead of putting clothing after the fact, I realized I should have put bicycle, but that's okay. In third place in third place with 21.3% was pastry. I'm not sure if that says more about people thinking it's a pastry or people thinking that if this is something about Bryce, it's a pastry. Um that means that uh in first place with 62.7% was furniture, so that means what is that, 37.3%?

Bryce

I'm pretty sure that you just that that you switched the place ordering that system that you were using in between the second place and the last one. Because you said in third place was pastry, and then in first place was Oh, my bad.

Conor

Yeah, so fourth, fourth was luxury car, third was clothing, second was pastry, and uh first was furniture. So yeah, a grand total if my math is my math is correct, uh 37.3% of people are uncivilized. So I think you owe the listener 37.3% of the listener an apology, bro.

Bryce

Yes, I I I I just want to say, dear listener, um, I'm I'm really glad for the uh 67% of you that are civilized.

Conor

63. 63%. Well, you're not rounding up to two-thirds there, buddy. You don't get to do that. Also, this doesn't make it doesn't work if we're referring to the listener with a poll where how many people responded? It's like 10. Oh, 169. Wow, that's uh 13 squared. That's pretty good.

Bryce

Why do you know that? Why do you know that?

Conor

Uh doesn't everyone well, I don't know. Like mathers, I just assume have like all of their uh their squares.

Bryce

Why did you I I like how you not only knew that, but you felt the need to just share it with the world right now.

Conor

I mean, how often do you come across the number 169? You know?

Bryce

I don't know, but I have a feeling that somewhere you have some spreadsheet where you've written down every time you've come across the number of things.

Conor

No, no. It's just like like I've never come across like the number 343 just like as a figure. Um, but that's like my one of my favorite numbers. That's 7 cubed.

Bryce

What are some of your other favorite numbers?

Conor

Well, we already took well, 42, 1729, 4104, anything that's a Ramadan number.

Bryce

Uh yeah, I'm so I'm so bad when I write uh when I write tests. There's a surprising number of tests that I write where the value 1742 or 3.14 is used as uh as as some value um for testing purposes. Like uh if you if you look through a bunch of uh you know tests in a code base that I've worked on and you see those numbers, it was probably me that did it.

Conor

Yeah, that's uh it's uh yeah, a lot of times when I'm just messing around, 42 and 1729 are the the numbers that I that I throw in.

Bryce

Why 29?

Conor

Or 1729. So uh 1729 is the first Ramanajan number. What? Which is what is I cover I covered this in a CPP con talk, which means Bryce doesn't watch my talks. Um also uh Stefan Lowaid uh in the same CPP con of 2019, he snuck a bunch of 1729s in, which I pointed out uh in in in the same conference at my talk that was later in the week. So there's a movie called Well, Romanajan is a famous mathematician. Yeah, I knew that. Um and there's a movie called uh is it the man who knew everything? Something like that. Um uh Dev Patel plays Ramanujan. And uh it's all they're also known as taxicab numbers, but they're numb they're numbers that are uh expressible two different ways as the sum of two cubes. Um so there's this famous anecdote from history where Roman is getting out of a taxicab, um, and his advisor, I'm not gonna remember his name, um, there's Littlewood, and then there's one other guy. Um and he says, Oh, that's he remarks, that's not uh really intriguing number, and then Roman goes, What are you talking about? 1729, it's it's a number that is expressible two different ways as a sum of two cubes. And it's so it's it's uh ten cubed plus nine cubed, and I believe uh I can't remember, one cubed plus uh thirteen cubed, maybe something like that.

Bryce

Why why taxicab?

Conor

Because he th because Ramanujan was getting out of a taxicab where the taxicab number was seventeen seventeen twenty-nine. Um and that's where the that's where they got given his name.

Bryce

Um That wall behind you needs like a a picture or it's something. It's it's sad right now. It's sad and lonely.

Conor

I mean, I will give you that it is lonely in my place. I wouldn't say it's necessarily sad. Uh I've got I've got like eight plants. I've got like a little garden, a greenhouse in my my my apartment's basically a few.

Bryce

I am no plants. I'm very I'm very, you know, like some people some people move to New York and they're like, oh, like there's you know, I I I miss having like a place to go outside. I miss having the backyard. That's not me. I'm very happy in my sterile apartment that has nothing living in it aside from me.

Conor

Yep. It's uh I don't know. You should get some NASA NASA plants. Oh, it's NASA. Java Java, uh, NASA, NASA. Um the NASA approved plants that like uh they they clean oxygen at like a super Did you freeze or are you just very still you're not just very still?

Bryce

I'm just very still.

Conor

Um anyways, enough about plants. We also, so we have to talk about we have to talk about the associate so this this is gonna get a bit technical. I apologize to listeners for if this becomes really boring.

Bryce

You don't apologize to listeners now, do you?

Conor

Uh yes, we apologize to you, the listener. We gotta be the only podcast where there's two co-hosts and one pings them, hey, hey, we gotta stop referring to them in the aggregate. We gotta use singular. Let's let's connect with them more one-on-one. And then it becomes just meta because the first episode we're recording, 30% of our discussion is like, no, no, no, Connor, what do we talk about? We talked about that. There's only one listener. You hear that? He's listening or she's listening, or they're listening right now. There's only one of them. Um I stay all right, here we go. So what happened? CF, C E A F. It's gonna be a big deal. Combinator-enabled algorithm fusion. It's gonna be the foundation upon which potentially a programming language will be written in the future.

Bryce

Is this the programming language that when you started working at NVIDIA, I told you you were gonna write, and you gave me an incredulous look and did that thing where you giggle and laugh?

Conor

That uh, as far as I can recall, never happened. I'm not sure what you're talking about.

Bryce

There were witnesses.

Conor

Giggling is not something that I believe I'm capable of.

Bryce

I I'm I'm I'm gonna spare you, dear listener, from me repeating the story again of the time that Connor giggled at the mention of Sean Parent. But continue.

Conor

Okay, okay. Uh that's fair. Um But, anyways, I posted I posted so actually what happened is on the most recent, or was it two episodes of ArrayCast Ago, um, at the tail end of it, I had mentioned the possibility of like building an array language that uh took advantage of the fact that if you built it up of primitives and you knew all the properties, algebraic properties of the primitives, like if whether they're associative or commutative, you could like fuse your operations down to whatever, the bare minimum of what needed to be done. And then on top of that, if it was like a reduction at the end of the day, you would know that the like combination or composition of all those binary operations, you'd know the associativity or commutativity of it. And then let me get his name right, Troll Henriksen, I believe. Trolls Henriksen, I apologize if I'm pronouncing incorrectly your name. We went back and forth on Twitter a tiny bit, and so Trolls is uh the I'm not sure if he's the creator, um, but he is working on the Futhark language, which is like a GPU slash Haskell slash sort of functional programming um language. And basically at one point he asked for some example code. I posted that example code, and then his response was that operation is not associative. And let me find that.

Bryce

And show me this operation.

Conor

And and so what I thought was that basically the binary operation had a pair as the left argument of the binary operation, and just a single element of for the right argument. So it's not it's definitely not commutative. And based on his definition, it made sense to say that it wasn't associative, but it was the same pattern that we had when we were solving that maximum consecutive ones. And the way we solved that was by creating a function object in the form of a struct that uh that overloaded the function call operator like three or four different times for dealing with the different cases of do I have sort of that information like information struct and a single element, or do I have two like information structs on the left and right? Um so it dealt with the cases of like, am I doing my first little pass on a chunk of the array and building up the information and then doing like the down the down sweep and the upsweep? But like, does that not qualify as associative?

Bryce

Well, so so I'm looking at your Godwalt example here. Which um which operator are we talking about? Is it the one in the K function or the K2 function or the scan reduce lift function? But I wonder whether maybe him and us are working from a deaf different a different uh definition of what associative means.

Conor

Um if you look at uh either K2, yeah. Um K2 is the easiest because it's not split into that scan reduce lift thing. So basically what what we're looking at, just so that we're not just randomly talking about some gobbled example, is we're looking at three different solutions to Caden's algorithm. And um Caden's algorithm is a solution to solving the maximum uh subarray sum problem. So if you're given a uh list of numbers that are negative and positive, what's the longest contiguous sequence of elements such that it maximizes the sum of that uh subarray?

Bryce

So just do a proof. Like just you you you you you you took a you must have taken a uh class in college where you did proofs, right?

Conor

I took discrete mathematics, uh but yeah. Here, let me send you the tweet that trolls sent.

Bryce

Um I think that's the easiest way to um to think this through is to just sit down and write out a proof. Um maybe we can even do that now. So you know, essentially you you you um But that's the thing.

Conor

I think I think his point is that so if you click that tweet, it'll it'll bring you that I sent it in the chat. It it says how can F of X so F that takes two parameters where the first one is X and the second one is F of Y and Z be the same as uh if you switch the F of X or F of F of X and Y, comma Z if they have diff they have different types.

Bryce

But that's the thing is like he's he's going along the same logic that I'm going along. That that that statement that he has there in his tweet, um that's what you want to to prove. Um you know, just just just take your um take your operator and plug it in and see what happens.

Conor

Well, so so that's why I'm getting back to the maximum consecutive ones problem. So if you haven't listened to that, that was a couple episodes actually, but the one where we really dive into it and then it's called the loss reduction episode 25. I was gonna say, don't you recall that like in that function object, like you we have overloaded the function call operator.

Bryce

And and that that's that's where the disagreement between us and him comes up. So keep he's asking, how can f of x, comma f yz be equal to f of f xy comma z if y comma z has a different type than z. Yeah. Um and then he asks, maybe we are using different definitions of associative. And I think he's right that we are, because in in our thinking, um uh overloading, you know, F could be an overloaded function, right? That F could take um uh it could take either you know a pair as the second argument, or it could take um uh a scalar element.

Conor

Um but I Isn't that cheating? I feel like that's cheating, is that like so like is isn't aren't we bending the definition of associative then?

Bryce

Yes, uh I mean I I think it's hard to say.

Conor

Um uh I think isn't this in the ISO standard? Like, do we define what we mean by associative and and I don't I don't think so.

Bryce

I mean it it's real it but no the question isn't what we define as uh associative here. Um the question is what do we define as an operation? Like what do we define as F? If if we say that F is only a single overload, then yeah, this couldn't be um associative. But if we say that F is an overload set, or if F is a function object, um then sure, this this could be um uh associative. And I I think I would even argue from um from like a mathical grounds, I don't see any reason that you couldn't define uh uh a function this way. Um you know that there's there's there's no reason to restrict yourself to uh uh just a to to to requiring that um that the second parameter is just a single type. Um and in fact I would I'd go a step further. Um one of the tricks that I used in that maximum consecutive ones uh in a couple of my little prototypes was relying on implicit conversions. Um so this reduction that you're doing, it's a reduction over uh what, like uh a pair of int, and then what's the data type? This is the data type like int for the input sequence?

Conor

Yeah, basically it's it's a pair of ints, and one of them represents sort of uh internal scan that we're doing, and then the other int represents a maximum value over that scan, which the point is is that like when you have a scan followed by a reduction. You don't actually need to do the scan in terms of like writing to a linear amount of memory. You can just fuse those into a single reduction.

Bryce

So, you know, one way that you could implement this operator is you could have one overload that takes um pair and then you know pair events and then int. Um, and then you could have one overload that takes pair of ints and then pair of ints. But you could also pick some sentinel value, you know. Um what what is what is the second pair? Like in this pair of ints, what what are the two things, what are the two values that are represented?

Conor

Uh the first value in the pair is the maximum. So like you see how we're doing a dot first at the very end. That's our actual result that we're collecting. And then uh the second value is the running sum that's sort of being floored at certain points in time.

Bryce

Um basically so if you if you were doing if you were if you wanted to take just a single element and construct one of these pairs from it, you could do that.

Conor

Yeah, you would basically you would just add it to the second one and then you would set it as the first one as well, because that's gonna be the maximum at that point in time. Unless if it's negative, um of course.

Bryce

So then instead of instead of defining your operation as a associative operation over the set of like ints in the set of these pairs, and having this problem of dealing with heterogeneous types, you could just think about your operation as being an operation that only operates on these pairs, and that you would just convert those, the ints, to the pair.

Conor

Just do a transformer.

Bryce

Or yeah. And like like like, you know, you could one, you could actually do this in your implementation. You instead of using std pair, you could implement your own little struct type that has a constructor that takes a single int, and it's a um, it's not an explicit constructor, so that it will actually implicitly convert. You could do that. Um, but my point is really more that like this is a theoretical exercise that I think demonstrates that the operation is indeed associative, um, and it can be associative over a single type if you make that single type this collection of pairs. Um, I do see his point, but I I I do think that he's wrong. I do think that this is an associative operation, and I think that um uh in the worst case, you could explain it as an associative operation over these, you know, these pairs.

Conor

Right. But like I from him looking at the code where you see that it's they're not both pairs, the binary operation has a pair on the left and an element on the right. It's definitely like when he asked the question, I was like, yeah, he seems right, but I know that we worked through this in the previous maximum consecutive ones, and we did that by overloading the function call operator. Yeah. And then my question was like, so either either we're like we've taken the word associative and sort of redefined it for our own sake, or um you're allowed to call that op like if the operation can do different things, that is also a valid in terms of it being associative. Either way, I'm not sure which one's right, but this is for you, uh, or not sorry, Henrik, Henriksen, trolls Henrickson. Uh yeah, that's I guess the the answer. Do you do you have a sense of whether which one it is? Like from what do you think the mathematicians are saying? That we're we're like uh we're speaking blasphemy right now.

Bryce

I'm not sure. Um I'll I'll say this. I think um overloading is such an intuitive part of C. Um I I I feel like somebody would clip that because uh overloading, of course, can be a fairly complex um aspect of C that can be hard to understand. But when I say it's intuitive, what I mean is it's a tool that we reach for so frequently that we take it for granted and that we don't perhaps even think about um the um all the implications of that. And let me let me take explain it a step further. Um when we as C programmers talk about a um uh an operation, either you know, an operation that's defined as functions or maybe it's defined as a customization point object, but like a named operation, like um std reduce. Let's use this as an example. We think of that as a single entity, right? That's a single thing. Um maybe we even say like it's a single function. Um and I and I just I I consciously avoided saying the word function when I was just describing that there. Um because I didn't want to um uh to add confusion to it, but in reality, the named thing std colon colon reduce is uh actually multiple different overloads. Um uh it's it's it's multiple different function definitions. Um that's how you implement it. And and another interesting aspect of this is that in some cases, when especially when you're dealing with um uh defaulted parameters, you have the choice where you could either say, I'm gonna implement this function with a single overload that has defaulted parameters, or I'll implement it with you know multiple overloads um uh uh without the defaulting without the defaulted parameter. And the there the distinction between the two isn't really observable. And in fact, we give standard library implementers the freedom to pick which of these um uh to pick to choose to do this um either with more overloads or less overloads when they when they can, when they have defaulted parameters. The point I'm getting at is that we we think about an overload set as being like one contiguous entity. Um and that's not you know that's not always the case. Sometimes different overloads um have different functionality. Um we try to avoid that. We generally think that that's not good design. Um in fact, one of one of my key library design rules is that all of the uh overloads of a function should have the same semantics, the same general semantics. And likewise, all of the specializations of a of a class template should have the same semantics and the same the same set of member functions and the same interfaces. Um because uh we're going to think of those things as being a single entity. But there's other ways in which overloads can be quirky too. Different overloads can return different things, um uh which can sometimes be surprising. Um the parallel overload of for each returns void. The scalar overloads return the function object. The parallel versions, of course, can't return that function object because that function object um uh it may have been stateful, and like that's the reason why the the the scalar version of um or the sequential version of for each returns that returns it, is because you might have passed in some function object that was gonna accumulate some data and then you want to get it back later. Well, we we couldn't support that in the parallel version, so um we didn't, and we didn't return you the function object because there wasn't there was no reason for us to do that, because there was nothing useful you could do with it. But that's a little funky to have a operation um under one name that has two different return types, and likewise um you can have you know a variety of different parameters that a single named operation can take, um of a variety of different types. And I think we perhaps take it for granted that operations work like that in C. And maybe this fellow, um coming from a sounds like a more Haskell background and a background from other programming languages, maybe in his mind a named function or a single operation should be something that has a cons uh you know the same signature. And so maybe that's what what was bothering him.

Conor

Um but uh I I could see, I could see even even coming from a like similar background, but you're like I I'm not a a trained mathematician, so I'm not sure in the world of mathematics what they consider like the definitive definition of associative. And um I wouldn't be surprised though if um many mathematicians saw that, you know, the pair on like not even just type A on one side and type B on another side and said, well, clearly that's not associative.

Bryce

Um I I think if you looked at the math definition, yeah, I think if you looked at the math definition, it would have to be associative defined on some set of objects, and that set of things shouldn't be heterogeneous. Um but I'm not really sure. Um because it uh the the the the definitions of associative in the math world that I'm familiar with work like that, but it's possible that there are more complex definitions of associative uh that do have a notion of you know heterogeneity. But I I definitely think that at the very least you could define the set of objects that this operation operates on as being those pairs, not the ints and the pairs. And then you've solved your problem.

Conor

Right. I uh we should put I feel like we should put a disclaimer on the our website. We do have a website, by the way. We never mention it, but it's uh ADSP the podcast.com. And maybe we should call it the title of this episode. Like surprise, uh, we are not mathematicians.

Bryce

I I I have a math degree. I have a math degree.

Conor

I studied actual science, which is like in in the math world, but uh but um you know I feel like we're too Bryce has just runoff to go get something, but I'm gonna continue to talk. But uh I feel like we're we're two developers that are math inclined, but you know, we're talking about the definition of associativity and opining on it when really we should just have a math person on and uh we should have a we should oh ADSP should have like a like so if you study pure mathematics, um you or maybe you should maybe uh Lisa Lippincott would be great for that. Yeah, she'd be great.

Bryce

I think you should narrate what I'm doing, by the way.

Conor

Alright, I'll start doing that. So Lisa, you probably don't listen, but if you are listening, uh would you want to be our math consultant and every couple well a couple we will accrue our math questions and then have you on every once in a while. Um and also, too, Lisa's got a crazy fascinating story. It'd be awesome to have her on, just for her to I'm sure she has some crazy stories similar to Sean. Um so yeah, narrating. I don't actually know. Bryce has got a package that's or it's something he's wrapped up. You can hear in the background, he's got scissors. There's a 37% chance he's gonna stab himself.

Bryce

Um these are very nice scissors, by the way. These are of course they are.

Conor

I'm sure they're imported imported from Italy. They've got mahogany handle a mahogany handle. The fact the fact that even Bryce has to clarify that his scissors don't have mahogany, uh mahogany handle is like the perfect summary of uh so so this um this actually I uh this didn't come in the stuff that that just arrived yesterday.

Bryce

This this traveled with me, but this is my Louisiana State University diploma. And uh can you read that?

Conor

It says uh Louisiana State University and Agricultural and Mechanical College on the nomination of the faculty of the College of Science has conferred upon Bryce Alexander. Whoa! I didn't know you had a second middle name, Adelstein Lelbach. Actually, I think I did know that. Um the degree of Bachelor of Science with all the honors, rights, and privileges of that degree appertaining. You gotta move it up a little bit.

Bryce

Oh yeah. Wait, wait, shit. It it it doesn't say that it doesn't say what my paper was. Crap. Well I am showing you I am sure that's a good idea. I had a major in applied mathematics.

Conor

Thanks for listening. We hope you enjoyed and have a great day.