Bryce

If I'm going somewhere and there's ducks, I will stop what I'm doing to go and like interact with the ducks. What like when we talk about Transform Reduce, I'll be able to talk about how I met you. Oh, is this is this a PG-rated podcast?

Conor

No, no, no, no, no. We're allowed to say whatever we want.

Bryce

The the most important thing, and you gotta leave this part in, the most important thing is that our podcast has to be better than JF and Chris's podcast.

Conor

That'll be the opening, that'll be the opening clip. Have you have you listened to their podcast? I'm not listening to their podcast. Welcome to episode zero of ABSP, the podcast, recorded on November 14th, 2020. My name is Connor, and with my co-host Bryce, today we're gonna be talking about what our favorite algorithms are. Hey man, how's it how's it going?

Bryce

It's uh it's pretty good. I just woke up, had myself uh had myself a bagel that I like napped in my couch for uh for a half an hour. Was that got on to talk with you?

Conor

Was that intentional mentioning bagels in like the first 30 seconds of our first like inaugural episode of this podcast?

Bryce

I I mean it is a meme with me, but uh but yeah, but yeah. So uh what's this podcast about?

Conor

It's gonna be about algorithms, data structures, and anything and everything we want to talk about. So for those of you that don't know, uh this podcast is gonna be modeled after one of my favorite podcasts called Magic Read Along, which is just two guys uh you know hopping on what sounds like a phone call, uh chatting about something's programming related, some things not, and uh hopefully it's entertaining for those that are listening.

Bryce

Yeah. It's funny, uh the that term algorithms plus data structures equals programs, uh it was actually one of the first things that my mentor, Hartmittyser, uh uh told me about. Uh and I don't think he ever mentioned the book to me, but he just he just said something to me in a moment of like programming is just algorithms plus data structures. And and Hartman was this um this uh East German guy with this uh he had a real character to him, so he just said it in such a way as if it was just this fundamental truth of the universe. And uh something I always really took to heart.

Conor

When did when did you learn that it was uh a book? So also for those that aren't aware, uh that what Bryce just said is the title of a Nicholas Virth book that was published I don't even know what year, probably in the 70s. Which at some point both of us was would read. Full disclosure, I don't think either of us ever read it yet. Uh we just thought it was a great podcast name.

Bryce

Yeah. I think I first learned about it when you told me about it. And I think prior to that, I my only exposure to that title was Hertmet having mentioned it to me, and I think I had no idea that it was a book. I just thought it was a wise thing that he told me. Interesting. Yeah, that algorithms plus data structures equals programs. Yeah.

Conor

So what are we gonna be talking about today? We've got a question in mind. What's that question?

Bryce

That question is what is your favorite algorithm? And and I thought that the answer to this question was gonna be really easy because I thought both of us were gonna say the same algorithm. The algorithm, in fact, that brought us together, which is transform reduce or map reduce. Um and and I I I should now I should give the story of how I met Connor. Um so it was, oh God, what year was it? Was it 2018?

Conor

Uh technically the first time that we we talked was in 2018, yes.

Bryce

Was but was that when you gave the talk at the user group?

Conor

Uh the first time I spoke at the uh Bay Area C user group was in January of 2019. But I s I I I moved to the Silicon Valley in on August 5th uh of 2018, and then I believe it was like August 8th or 9th, I went to my first C Bay Area user group.

Bryce

Um and yeah, I'm gonna say it was 2019 though, because that was when we really met. That was when we really got to know each other, was when you gave that talk. So so for those who don't know, um uh I live in the Bay Area, and um a few years ago I sort of became one of the main organizers of the Bay Area's C user group, although um I've since uh stepped away from that role because uh I have no free time. Um but uh at the time I was still, you know, w one of the main organizers, and um, you know, we're always looking for people from the community to give talks. And I don't remember if Connor approached me or I approached Connor. But um Connor came to give this talk and I still I still think it is the best talk that Connor's ever given. Uh and he gave this talk about um uh I think it was at the time it was still called Algorithm Intuition. And if you want to see a version of this talk, um the best version I think would be to go watch the uh the version at C ⁇ now 2019, which won like best speaker and best talk, and it won a bunch of awards. Um and it's essentially it's a it's a talk about um uh uh uh some of the C algorithms. Uh I think primarily it's a talk about um a particular set of the C sequence algorithms that are near and dear to my heart, um uh some of which are the the known as the numeric algorithms. And during this talk, one of the things that Connor was particularly excited about, and Connor's a very excited speaker, one of the things he was particularly excited about was TransformReduce. Um TransformReduce is an algorithm that i if you're not a C person, you might know it better under the name of mapReduce. Um so the idea is that it it it's an algorithm where it takes an input sequence of items and then it takes two operations that it applies to them. Um one of those operations is a transformation which uh takes uh some function and applies it to each one of the elements. Um and then um the result of that transformation gets fed into a reduction operation. And a reduction operation um is just an operation which takes two inputs and it produces a single output from it. So for example, plus is a reduction operation. Plus, you take two inputs, you know, the two things that you're gonna add together, and it produces a single value as the output. Um and it's a very powerful, it's used a lot in data science. Um and so I I I I had to say, you know, the thing about Connor's talk that really that really built our friendship was I just thought it was like the best talk ever. And this was at a point in my career where the bar for a talk to impress me was really high. Um like, you know, I'd sometimes there'd be talks and I'd just feel like, ah, this is this is good, but not like great. But I I'd I'd come to have this intuition about like what was truly a great talk. And Connor was sitting there and giving this talk, and I just thought, boy, this was great. And one of the reasons I thought it was great was he was talking about all the things that I would talk about when talking about these algorithms. And Connor didn't know it at the time, but I had been the person who'd written the the like specification in the language for a bunch of these algorithms, and Connor was talking about a bunch of the problems and the limitations with them, and I was like, oh my god, this dude gets it, and I was so excited. And he mentioned at some point in that talk that transform reduces his favorite algorithm, and I had given a talk a few years ago about how transform reduces my favorite algorithm, because it's so powerful, it's so versatile, there's so much stuff that you can do about it. But I think that we've determined that neither of us actually think transform reduces our favorite algorithm, is that right?

Conor

Well, I'm actually I'm I'm curious to hear what you're I know when we spoke about this uh topic uh a while back, uh, that was your initial thought, and then I said, oh well, at the time, inner product or transform reduce was my favorite algorithm, uh, but I don't think it is anymore. And that's not because I don't love it. It's still, you know, it's an amazing algorithm, it's still my top whatever N. Um, but yeah, I think I have a new one now, and I guess maybe you have a new one too.

Bryce

So uh Yeah, well, no, no. I want you go first. You go first. I just I just said a bunch of words. I want to hear, I want to hear what your your new favorite algorithm is.

Conor

Well, so first I should say that even before uh you know, so inner product for for those of you that um you know are less familiar with C, because I imagine we're gonna have some non-C developers listening in over time. Um Inner Product is the C11 name, sort of the precursor. It's not identical because the constraints on the transform reduce, which is a parallel algorithm, um, are slightly different. Uh but I sort of first learned of transform reduce by the name Inner Product, and then I thought to myself, wow, this is a really bad name. And then like a couple weeks later, discovered the C 17 version, was like, oh my gosh, this is a way way better name. Um and that's the case with most of the C17 parallel algorithms. Uh but before inner product, probably my favorite algorithm was std partition, um, which I don't think I've ever said in a talk or anything. Uh I just loved it because it was a linear runtime algorithm that had sort of the behavior of a sort. I think of partition as like a predicate sort. You pass a predicate and then you sort everything that adheres to it at the beginning and doesn't adhere to it at the end. Uh, but it's a linear runtime, which is super, super nice. Um so I went from partition uh to inner product to the renamed version transform reduce uh to then a new algorithm which exists in uh very few languages uh called outer product. Um and in fact, um the product quote unquote family of algorithms I'm just a huge fan of. Um so so in that family exists inner product, otherwise known as transform reduce, uh Cartesian product, uh which is sometimes just known as product in languages like Python and Ruby, and uh outer product. And I also wish that there was an algorithm that I have yet to discover called triangle product, which I mentioned in my CPPCon 2020 talk, uh, but we're not gonna talk about that here. So outer product.

Bryce

Woo! Why aren't we gonna talk about that? I want to know what triangle product is.

Conor

Uh well, these things are supposed to be like 20 to 30 minutes. Um but yeah, so well, I'll explain outer product and then triangle product is just a slight variation of it. Um but so if you're familiar, so we've discussed inner product, aka transform reduce. Uh Cartesian product, uh, for those of you that aren't familiar, is basically um in the simple case, you're taking two sequences or two ranges, uh, but in the more complicated, you can take up to n. It's a variadic number of sequences. And basically you create all possible combinations of each of the elements in that list. So if you have two lists, A, B, C, and then uh the second list is one, two, three, you create uh the pairs of elements, uh a1, a2, a3, b1, b2, b3, and c1, c2, c three. Pretty straightforward. Um so you end up with like uh if you have two different length lists because they don't need to be the same length, you end up with n times m uh pairs or tuples of elements if you have more than two lists. Um so a Cartesian product, if we think about it just in sort of the two uh list or sequence or range case, um, you can actually visualize that as a two-dimensional uh data structure, like a matrix. Um so in the case where I had A, B, C, and one, two, three, instead of just a Cartesian product gives you back all of the pairs in a single list, outer product gives you back a list of lists or a range of ranges. Um you end up with basically a matrix that has each of these pairs. Except instead of getting back pairs similar to inner product or transform reduce, you specify a binary reduction operation that is applied to each of those pairs. So if you have an outer product, typically now the ABC123 case doesn't make sense, but if you have the numbers, you know, one to five for each list, you can apply the multiplies binary operation, and then your resulting table is a multiplication table. Um and this is extremely uh useful in uh the array-oriented uh programming paradigm, which of course uh is where the first time on the uh ADSP of the podcast, I'll be mentioning APL. Uh we can start potentially a drinking game for our listeners every time I mention APL, um, which is my favorite programming language, but um outer product, it exists um in basically every array programming language, APL, J, uh Julia is probably the most popular array programming language that people have heard of. Um Haskell also has an outer product. Um but I think other than those, those are the only languages that I know that have outer product, but you can do um very, very cool things. And and uh just to add, if you have Cartesian product and you don't have outer product, you can do a Cartesian product and then call another algorithm called chunk, where you just pass the length of the first sequence and then chunk your uh list, the resulting uh list from your Cartesian product to get basically the equivalent of an outer product. But that's my favorite algorithm. I absolutely love it. Um and maybe C29 ranges will get it. Uh we'll see. What is what is your uh favorite algorithm now though, Bryce?

Bryce

So my favorite algorithm to understand it, uh my favorite algorithm actually tells the story of the start of my career. So it's actually like perfect for our first podcast. And my favorite algorithm, um uh I will I will say it's a specific implementation of the algorithm, because that leads into the story, which is Boost Algorithm Split. Um and this, and the reason well, one of the reasons that this is my favorite is this was the first algorithm the fur the first time I was ever exposed to Boost. So back in 2010, um I was a fresh college dropout. Oh, okay. Technically speaking, I didn't drop out of college. Technically speaking, I flunked out and they kicked me out for if we're if we're being correct about things. And um it was because I was bored with school, and I um I played a lot of text-based games called MUDs when I was a kid, and I started learning programming to create my own MUD engine. Um, and uh I was I didn't know anything about programming before I started this. I was working with this guy uh who uh was a programmer, and we were doing it in C, um, which was sort of novel because a lot of MUDs were written in C. But he was like, Yeah, we should use C. It's more modern, it's better. And um uh so I I I first got exposed to the standard library um in this project, and then there was one place in this mud engine where he was using Boost, and it was he was using Boost um uh algorithm split. And and what what that split algorithm is, is it's just a basic tokenization algorithm. So um you give it an input sequence um and then you give it a some set of tokens, and it takes the input sequence and it chops it up um uh using those tokens. So like you know, if you had an IP address um and you wanted to split it out into the individual numeric components, your token would be a period. And then what you know, if I had the IP address uh 127.0.0.1, um, and I fed it into this tokenization algorithm, it would give me back four components. The first component would be one two seven, the second one would be zero, the third one would be zero, the last one would be one. Um and I don't remember exactly what we were using it for in this little mud engine. I think we were using it to perhaps we were using it to like um uh separate out um commands entered into the mud into into their constituent components. But um it was my first exposure to Boost, and I seem to recall I found some sort of bug in the algorithm. And so I went to the Boost people and I was like, hey, here's this bug, I had this fix for it. Um and then I very rapidly got completely sidelined from my little game project into contributing to Boost. Um and I th I if I recall correctly, what happened was I was my use case got more and more advanced, and then somebody was like, you should use Boost Spirit. And then uh I started talking with the Boost Spirit guys and I started contributing to Boost Spirit. Um and at the time, uh uh you know, one of the main contributors to Boost Spirit was one of its creators, Hartmitt Kaiser. Um and so I got to know Hartmitt, and uh uh after you know, some period of time, uh Hartmit and I got talking about, well, I was I basically approached him on IRC and was like, hey, I need a job, because I was like a 19-year-old college dropout. And he's like, why don't you buy a one-way plane ticket to Louisiana, come down here and work for me? My parents, of course, absolutely loved this idea of me uh of me getting on a plane and going off to some stranger that they'd uh never met. My mother thought he was gonna be an axe murderer, and uh that was the start of my career. Is your mom gonna listen to this podcast? Oh, she'll probably listen to this podcast, yes. Uh yeah. Um but uh but I think it's a very cool algorithm, and one of the reasons why it's a very cool algorithm is it's a very common thing that comes up for um a lot of programmers. Um even if you're not doing anything like that complex, I think it's I think tokenization is a fairly common thing to come up. I mean, even just if if you're just like writing some like a command line scripts, like it's a very common thing that you do where you're like, hey, I have this, you know, this input sequence and I need to divide it up in some way. Um and uh it it also uh it sort of leads into some interesting discussions about uh uh efficiency. You know, one of the reasons that we introduced string view into C17 was to uh allow you to write an algorithm like this more efficiently. So let's go back to that example of parsing an IP address. Let's say that I've got a string that stores some IP address, um, a std string specifically. Um and uh I want to split that std string up into its constituent components. So a std string is an owning string. You know, it owns it owns the memory for the string that it points to. So if my API for split is that it um takes a std string in and it returns a vector of std strings, well boy, that is not efficient at all, is it? Because then what I'm doing is I'm taking this one initial input string, and uh for each one of the constituent components, I have to make a copy of that that piece of the string and stick it into the vector that I'm gonna return. And so one of the canonical examples for for why C C17 string view is useful is split. Because if I have a string view, what a string view is is it's a non-owning view into some other string. So if I if I have one string that's my input string and I want to split it up into you know the constituent components, string view is perfect for this because the string view is non-owning, it can just refer to the piece of the string that it uh that it um uh refers to. Um and that the storage for that string is owned by the original input. Uh and so instead of returning a string view, you can return a vector of string views or perhaps even something better than a vector. And um uh this is act it's actually even more interesting uh uh because uh just coincidentally uh this week um uh what one of my other jobs is I'm the chair of the C ⁇ Committee's library design group. And we got a paper this week um talking about improving um string splitting in C. So C ⁇ 20 introduced ranges, which is a more powerful iter idiom for um uh composing algorithms than our previous idiom, which was iterator-based. And uh one of the things that's introduced in C20 is a uh uh uh a ranges view called split view. But there's kind of a little bit of a problem with split view. Um and this paper tries to address it. The problem is split view in C20, you can you give it some sequence and it gives you back um uh a sequence of sequences. The issue is what type of iterators that sequence of sequence gives you. So uh my understanding from the proposal is that today um the uh iterators that you get back um from split view only provide for the forward iterator guarantee. And this is problematic because almost all of the string APIs expect contiguous iterator. So suppose that you're taking C20 split and you want to do Something like a parsing IP address. And then you want to call the C library function A2I or the more modern version from cars to convert each one of those IP constituent components to an actual integer type. But you can't do that because the iterators that Split gives you are not the correct type of iterators to feed into from cars. And they're not the correct type of iterators to turn into to give to a to I because a to I expects actual, you know, pointers. So there's this proposal. I'm sure we can add a new. Yeah, we'll put it in the show notes. Superior string splitting is the name of the paper. Here, I'll see if I can find it. But uh this proposal essentially aims to fix this problem. Um here, here, I got the paper number. It's P2210 by Barry Rebson. Uh and that IP example is like the first example in the paper. So if you go and and look at that paper, you'll see immediately what I mean. Um and this proposal uh uh attempts to remedy that in C to make um uh the split view a lot more useful when working with strings. Um and and the the other the other algorithm, which is you know, I think sort of combined with this, is the algorithm for um uh joining a set of um strings with a delimiter. We've all probably written this at some point. You know, you have like a um you have a vector of strings and you want to insert a comma in between them. And I'm sure we've all written the the naive form of this where you've just got some for loop and it just does like, you know, if I'm the first one, then don't insert it, etc. But you can probably tell me if there's like what the name of that algorithm is. I don't even actually know what the name of that algorithm is in like, you know, all the cool kid algorithm languages.

Conor

What's the variant that you just described?

Bryce

It's the one the like like where where it inserts a comma in but in between every every element, but like not it doesn't insert one before the first element or after the last element.

Conor

Uh that that depends on the language, but like typically that is called um is it it's doing the concatenation as well, right?

Bryce

Right, right. It's also doing the concatenation.

Conor

Typically that is like there's several different names, but yeah, join. Uh concaten or flatten typically don't take a delimiter. I know in Haskell there's an algorithm called interspurse, which is the same thing as join, uh, but like minus the concatenation. So like if you have a list of elements, it will just insert uh in between every element uh the new element that you want there, but like doesn't join them, so you still end up with a list of elements. Um but I think typically what's it called?

Bryce

It's called intersperse.

Conor

Intersperse, yeah. There's there's two different inter algorithms. One is uh interspurse and one is interleave. And uh little C trivia fact, if you've watched um uh Eric Niebler, who is the author behind the Range V3 library, which was the work that was sort of done to show um what C ranges could look like. Uh in his calendar talk, I believe it was CPPCon 2015, but I plus or minus one, uh, he shows an algorithm for transposing, which is just a composition of chunk and interleave. Uh interleave being where basically you have n different sequences and then you take one element at a time from each one uh so that you reorder them that way. Um and then you go and take the second element from each algorithm, uh, so on and so forth. But um, yeah, join I think is cla it's a classic name for it. Um interestingly, the join that we got in range of C20 doesn't take a delimiter. Um so in the current C23 uh proposal for sort of extending the range algorithms and or uh adapters, I should say, and views, um, we've had to propose join width, because unfortunately, the way we design join uh doesn't enable us to extend uh the interface such that it can take a delimiter, so we now need two different algorithms for that, which is this gonna be another example that you're gonna show in a talk where you're gonna have a list of what every programming language calls it, and it's gonna be the same for every programming language, and then you're gonna have you're gonna have what C calls it, and it's gonna be different. Uh join is not as consistently named um as some other ones. So like the classic example that Bryce may or may not be explicit implicitly referring to is the fact that C calls uh what every language calls map um std transform uh because we accidentally already chose map for our uh ordered associative containers and ordered um yeah.

Bryce

So that that and this and this this is a real problem. Like like people think that names might not matter, but I I bet you, you know, the first half of this talk we talked about transform reduce. And I bet you that a lot of our audience would have not really known what transform reduce is, but if we said, you know, we did say map reduce, you know, if you say map reduce, a lot more people know that because that's what that's what it's called in every other language. Um and like it's not only that, it's not only that transform is called map in every other language, it's that map reduce is a specific paradigm. So our mistake of calling map transform then led to this other mistake of the common paradigm of map reduce not being called map reduce in C.

Conor

And the problem also exists in reverse. So I had heard of MapReduce and the whole Hadoop uh, you know, you know, uh at scale doing this kind of computation, and I think MapReduce, you know, uh became very popular at Google for a while, or maybe still is. Uh and I thought that was I thought it was different than what trans, like I learned transform reduce and like never made the connection until I started learning functional programming. Um and so like yeah, it's um it's both a problem for C developers uh relating things to you know in other languages or paradigms, um, and also for you know software developers coming to C. Um but yeah, naming naming is hard.

Bryce

Well, and that sort of gets to you know the one of the reasons why I didn't explain really why I like Transform Reduce so much, but the reason is, you know, uh you're you're much more an algorithms guy than me. I'm more of a system software sort of guy, but r really my s my expertise and specialty is in parallel programming and concurrent programming. Um uh and uh w you know one of my jobs at NVIDIA is I'm the the team lead for Thrust, which is our parallel algorithms library, our implementation of C17 parallel algorithms. And I think Transform Reduce is the most useful of the parallel algorithms. I'll I'll maybe I'll temper that a little bit. I'll say that reduce is one of the most useful. Um and I say that because in our implementation, um we implement many algorithms in terms of other algorithms. And uh the the algorithm that the most number of algorithms are implemented in terms of is reduce and transform reduce. Um, you know, there's things like uh uh the extrema functions, you know, m min element, max element, um count if, etc. All of those are implemented in terms of reductions and transform reduce in uh in our parallel algorithms library. Um and uh in general, it's just a very useful parallel algorithm.

Conor

Yep, there was a talk given by, you know, moving outside the parallel world, uh a talk that Ben Dean gave, I believe it was at 2016 CPPCon called uh stddaccumulate an algorithmic empire, where he showed that of the 90 algorithms across a couple headers, uh 77 of them with a little bit of sort of uh bending and twisting were implementable in terms of std accumulate, which is what the C11 uh standard calls basically std reduce. Once again, slight differences on restrictions uh due to the parallel nature of the reduce algorithm, but um yeah. You start to see reductions everywhere. I remember when I listened to the first uh LambdaCast podcast where they were talking about sort of maps, um reduces and filters, and they were talking about how like there's catamorphic functions and anamorphic functions. Catamorphic functions are the ones that do reductions. Anamorphic is exactly split, so it's when taking a list and you end up with a list of lists. So like chunk, split, uh group by, they're all versions of anamorphic ones. But like these categories are just everywhere, and that like once you learn them, everything starts to look like a reduction. Um I think there's a paper called Beautiful Folds where they show that like basically everything is implementable in terms of a reduction.

Bryce

Yeah, I I have this great um this great uh diagram that I made that shows the dependencies between you know which algorithms are implemented in terms of other algorithms in our parallel algorithms layer. Uh and I I just I just shared it, I just shared it with you on my screen, although it's not great for the podcast audience.

Conor

I was gonna say, now you know what this means. We're gonna have to start uh screen capturing and putting these on YouTube as well, because now our listeners are gonna feel left out that we're staring at our screens and they're not.

Bryce

Plus, you you need you need you need the pictures, like the video evidence of how excitable we get. But um, yeah, it's really fascinating some of the things that are implemented with reductions in Thrust. Like um uh so find if is one whole family of algorithms that we implement in terms of reductions. Um uh in parallel algorithms, oftentimes um uh short-circuiting algorithms or algorithms where you can give up early, it doesn't make sense to do those um in our implementation.

Conor

Well, give up is uh is a bit of a misnomer. Like it you've already found your result, so you can stop iterating.

Bryce

Right, right. You can stop iterating, but in the case of like something that you're gonna GPU accelerate, it's actually more expensive to make an algorithm that's gonna stop uh that's gonna be efficient than an algorithm that's gonna be fast. So yeah, so so so making an algorithm that's gonna stop as soon as it finds um the result is gonna potentially be slower than an algorithm that just uh uh exhaustively searches the entire um input sequence. So we implement find not find if in terms of reduce, and then we implement um find if not in terms of find if. And interestingly, we implement partition point um in terms of find if not, and we implement mismatch in terms of find if not. Um uh so so essentially we implement mismatch and then equal uh in terms of reduce. And and mismatch is an interesting one because I know that's one of your that's one that's an algorithm that's also near and dear to your heart. So maybe you can talk a little bit about mismatch.

Conor

Well, so we're we're we're getting close to when we've got to wrap this up, but definitely I'll I'll say a little bit about mismatch. But first, partition point. I recently, so in uh the follow-up to the talk that Bryce mentioned at the beginning, Algorithm Intuition was another talk with a very similar title, but they're completely different talks, better algorithm intuition. I point out that there are five uh binary searches in uh the algorithm header. Most people are familiar with at least three, um, at I would say at least one, the one is being binary search, and then there's two other flavors, lower bound and upper bound. Um and then there's a fourth one called equal range, which is basically a combination of lower bound and upper bound. But there's a fifth one that very few people have heard of, um, or have heard of, but don't realize that it's a binary search. Um, and that's partition point. Um and this has come up recently twice in like code reviews of people asking, I need like a binary search, but that looks at two elements at a time, so it takes a binary predicate and finds the place where the element on the left returns true and the element on the right returns uh false for like some unary predicate, which you can then sort of fold into a binary predicate. I recently, the reason I'm going on this little tangent here is I recently discovered that we actually have a section in the uh C ISO standard for binary algorithms, binary search algorithms, and partition point isn't in it. Um it's in the section next to partition. Um because there's partition is partitioned and partition point. Um so even in our standard, we don't acknowledge that uh partition point is the fifth uh binary search algorithm. Um but anyways, yes, and mismatch uh mismatch is the generic version of adjacent find, and adjacent find is the generic version of is sorted until, and uh is sorted until can be used to program or to to code um is sorted. Um so that was like a relationship that I had found. And interestingly, in the same talk that I just mentioned, Better Algorithm Intuition, um, I thought that this was amazing. I'm not sure actually, Bryce, if you recall, uh we had um you know, non-alcoholic beverages and what is that bar called? Uh Shannon's at the top of NVIDIA. Um that was the time when I had made this discovery um that adjacent find uh was implementable in terms of what I had then called the most uh you know the worst named or the most poorly named algorithm in the C algorithm header. And I was scared to tell anybody because I wanted to be the first person in a talk to say, oh my goodness, look at what do you think? And so I I did this game where I said, What is is sorted implementable in terms of? And you said is sorted until, and then I asked what's in s is sorted until implementable in terms of uh and then I think you got it, Jason Find. And then I said, and there's one more, and you couldn't get it. Uh uh, but no one got it, and so then I told you stood mismatch, and I was super excited. Um, I asked Sean Parent this, uh, and when I asked him what is is sorted until implementable in terms of, he skipped over at Jason Find and went straight to std mismatch. Um so in in my talk I call it the Sean Parent uh game because um everyone should aspire to be as knowledgeable about your algorithms as he is, um, because he he just knew it off the back of his hand.

Bryce

So one one of these episodes we will talk about you and your fanboy love for Sean Parent.

Conor

That's that's fine. We can do that. I mean, that's an appropriate topic. Uh everyone should be uh a fanboy of Sean Parent. Um I mean he he single-handedly can like him and Kate Gregory, basically. Uh he started sort of the the road to my public speaking. Um and then Kate Gregory, I stole the title of my talk um from her CPP cast episode. I think it was 30. Um but yeah, like when I when I see Sean's talks, like they they are so inspiring. Um and they just make they make me want to like inspire. I hope that like someday I can inspire people like the way that like Sean inspired me. Um yeah, his C seasoning talk, his generic programming talk when he talks about how reading Alexander Stepanov's code was just like mind-blowing for him. Like that's that's just like so awesome.

Bryce

My favorite of his talks was I think his C ⁇ Now, 2014, uh keynote, where he talked about um he talked about um essentially porting uh porting some Adobe app to run on the iPad and talked about um sort of the fundamentals of where you can get performance on modern processors and how you have to turn to parallelism and how you have to turn to accelerators to get performance. And uh as somebody who's in that field, I just thought it was it was just a super inspiring talk. Um and uh I mean I and that at the time I was really in the HPC world, and Sean is Sean is not somebody who's an HPC programmer, and I was really awestruck with how how many of the things that he was talking about, like he was talking about getting performance on an iPad. An iPad is not an HPC platform, but the way in which he was talking about it was just as applicable to um uh how you get performance on the world's largest supercomputers. And I was just like, wow, this guy is this guy knows his stuff.

Conor

Yep, Sean is uh Sean is an inspiration.

Bryce

Yeah.

Conor

And maybe with that, maybe we should call it right there. That's the final line of our our first episode is Sean is an inspiration. Um and yeah, I think with that we'll just say uh thanks to everyone that's listening. And anything else you want to say, Bryce?

Bryce

Uh no, no, I'm good.

Conor

If you uh if you have a favorite algorithm and you want to share it with us, uh go follow us on Twitter at ADSP the podcast and let us know what's your favorite algorithm.