In this episode, Conor and Bryce chat with Ben Deane and Tristan Brindle about which algorithm is the most fundamental of all algorithms! Link to Episode 131 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Twitter ADSP: The Podcast Conor Hoekstra Bryce Adelstein Lelbach About the Guests Ben Deane has been programming in C++ for this whole millennium. He spent just over 20 years in the games industry working for companies like EA and Blizzard; many of the games he worked on used to be fondly remembered but now he’s accepted that they are probably mostly forgotten. After getting more interested in modern C++, in the teens he started giving internal company talks and then talks at various conferences, spreading ideas about types, algorithms and declarative and functional techniques. Tristan Brindle a freelance programmer and trainer based in London, mostly focussing on C++. He is a member of the UK national body (BSI) and ISO WG21. Occasionally I can be found at C++ conferences. He is also a director of C++ London Uni, a not-for-profit organisation offering free beginner programming classes in London and online. He has a few fun projects on GitHub that you can find out about here. Show Notes Date Recorded: 2023-05-16 Date Released: 2023-05-26 ADSP Episode 130: C++Now 2023 with Ben Deane & Tristan Brindle! C++17 std::reduce zip_fold_while (No Link) scan_while What Do You Mean by “Cache Friendly”? - Björn Fahller - C++ on Sea 2022 b-tree Valgrind C++Now 2023: Composition on Tiny Embedded Systems - Luke Valenty CppCon 2016: Jason Turner “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17” Thrust Docs unfold (A tutorial on the universality and expressiveness of fold) C++20 std::views::iota Haskell iterate Catamorphisms Anamorphisms J cut Recursion Schemes Hylomorphism C++ thrust::counting_iterator C++ thrust::transform_iterator C++Now CppNorth
Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.
Transcript
From the show. Tap a time to play from there.
ConorYou're ruining my clickbait, Ben! So the question is, what do we call this algorithm?
Ben DeaneWhat do we call this one algorithm?
ConorYeah, what is this? Is there an umbrella term for scans and folds? Scaffold. Oh man, we've now we've got scanduction and we've got scaffold. Welcome to ADSP the podcast episode 131, recorded on May 16th, 2023. My name is Connor. Today with my co-host Bryce, we continue the conversation with Ben Dean and Tristan Brindle and discuss what is the one algorithm to rule them all.
ConorAnyways, all right, wrapping now, finally, part one, part two, which is what the real reason we've collected this algorithmic minds, is to talk about the title of this episode will be One Algorithm to Rule Them All. And this idea came out of the interview that we had with Tristan, where we were having a discussion of what is the quote unquote, you know, root algorithm to rule all algorithms, or what is the most sort of fundamental algorithm that all other algorithms can be implemented in terms of, or is does there even one that exists?
ConorWe're gonna talk about that for the remainder of this recording. So I think maybe what we should all do first, without any explanation, one by one we'll go around and we just get to say the name of the one algorithm and we'll go from there.
BryceOkay, cool. I'll go first. Reduce.
ConorAlright, Bryce says reduce. We'll go to Tristan next. Zipfold while zip fold while. We'll go to Ben next.
Ben DeaneI'll take the side that that I that I reached out to you about. Scan while.
ConorAlright, so we've got reduce, we've got zip fold while we've got scan while.
Ben DeaneNow that I'm actually coming around myself, reaction from Tristan.
ConorI think I think I'm I think I'll also say reduce, although my mind can be changed.
BryceGood man.
ConorBut uh I think I think reduce is where it's at. Alright. Now who wants who wants to respond first to I feel like Tristan has thoughts on what Ben said and Ben has thoughts on what Tristan said. Well, zipfold while seems like a bit of a cop-out.
Ben DeaneIt seems like just jamming together some other time.
Tristan BrindleYou're absolutely right, right? Because um that's that's precisely what it's precisely what it is. But also um your answer is kind of the same as mine. It's real similar, yeah.
BryceWhat I don't I don't know what either of those two things are. Somebody somebody explain. And I can't.
Ben DeaneZipfold is is transform reduced. Or is that is could it be alternative? With multiple.
BryceOkay, but transform reduce is just reduced.
Tristan BrindleOkay. So hang on a second. Right. We we we know what it we know what a fold is, right? We we you uh have some uh accumulator, and as you iterate over the sequence, you uh you update this this accumulator in your you have some function that returns this new value, um fold or reduce or standard accumulate. And then we can have a short circuiting version of this that is uh fold while. Right? Um and in that case your your function returns two pieces of information, it returns your updated accumulator, and it returns like whether to continue or not.
Tristan BrindleSo that might be a pair, or you can return an optional, however you do it, or you can use now parameter, but it has to return these two pieces of information. Right?
ConorYeah.
Tristan BrindleSo that's like fold a fold while it's a short circuiting or a version of fold that can short circuit. Doesn't have to. Um and then you can do you can do yes, a sort of cop-out version that can take uh multiple sequences at one time and have an NRE predicate. Um and then you can you can say you can argue that that is more general because you can have it, you know, uh specialize it for the unary case as well.
ConorRight.
Tristan BrindleUm so that was that is my my the root of all the root of all algorithms because the zip version you can use to implement things like mismatch, unequal, and adjacent find, and probably others, but those are the ones that come to mind.
BryceSee, I I think we all just answered the same way.
Tristan BrindleYeah, I was gonna say reduce, but like some of you just said a fancier reduce than the Well you asked what was the what was the the most basic version the the version of it from which everything else can be.
BryceRight, but we asked we didn't ask for the most generic, we asked for the the most basic, and the answer is reduce.
ConorNo. I mean I think there are some subtle Ben, you're gonna say something now.
Ben DeaneUm I was gonna say I I I think ultimately this question is sort of ill-formed. It's interesting to think about, but it's not useful every day. Um and I and I think one of the points of algorithms is to be multitudinous and have lots of different formulations. So, you know, trying to implement all the algorithms in terms of one is is interesting as a pedagogical exercise, but not much more. Um and I do think we've said basically all the same algorithm.
Ben DeaneUm in my case I said scanwhile. I I implemented scan while once as a as a one-function interface to a to a map.
ConorAs a one sorry, say that again?
Ben DeaneAs the one function, the pretty much the one function interface to a map. A map being like a C ⁇ dud map? Yeah, something with that interface. Um so something you can iterate, actually it uh think of an ordered map. Right? So um something you can iterate and you can take you can take as long as you as long as you like, and when you're, you know, it's uh it's scanned while so it takes Interestingly, Tristan said like I don't know how you formulate it, Tristan, but in my case I formulated it with a separate predicate.
Ben DeaneYou seem to suggest that the the one function returned both the the fold uh the folded value and the and whether or not to continue.
Tristan BrindleUm that was my sort of uh yeah, my way of doing it would be uh to have so you pass it one one function that returns you the two pieces of information. Um various ways you could return that information, but it uh I guess you could do it with having two separate perhaps it yeah, perhaps it's more general to have two separate functions, one of which does the accumulation and one of which decides whether to continue or not.
Ben DeaneWell, I I yeah, I mean I think they're equivalent, it's just a case of in my case it seemed obvious to to put the predicate separate in the API. Um I did. But yes, it it it it goes down a sequence, it does a scan, it stops when when you want it to stop. Either, but either, you know, and that could be uh that you could have a pre you can have a predicate that works on the accumulated value, or you can have a predicate that works on the sort of depth index you've scanned to.
Ben DeaneRight.
Tristan BrindleOkay.
ConorAnd what's interesting about if we ignore the zip part of the zip fold while and we just compare fold while versus scan while is kind of what you're talking about, Ben, is that it's not really useful to think about implementing like you can you can implement every algorithm in terms of those two, but there's trade-offs for each one, right? The scan while you're gonna always be building up a linear amount of you know space depending on what you're doing. And then if you're trying to implement a reduction in terms of that scan, that's kind of wasteful uh because you don't need to materialize all the first zero to n minus one values.
ConorYou really only want the last one. Whereas with a fold, um, you can implement folds obviously directly, which is avoids the problem with implementing a fold in terms of a scan while. But then if you want to implement a scan in terms of a fold, depending on the copying semantics of your accumulator from iteration to iteration, like I remember in one of your talks, Ben, you actually talked about how the you know they changed some requirements in C 17 or 20, would actually make which made it possible to avoid those copies.
ConorSo if you were building up like a string by doing concatenation, you could actually do it uh non non or non-suboptimally. So you could I think you could do it optimally in certain cases.
Ben DeaneWell in 20 in 20 accumulate was changed to move the accumulated value through the computation. Right. And that's probably what you said. I mean accumulating strings still incurs temporaries and allocation and that sort of thing. But it's just that now they get moved instead of copied, so it's slightly better, but I still wouldn't recommend that use case.
ConorYeah. So, you know, you can implement a scan in terms of a fold and a fold in terms of a scan, but there's trade-offs in each one, which is why you would probably argue you don't want to do those the same way. Like definitely in in Thrust, we do not implement our reduce or r scan in terms of one or the other. They are two fundamental algorithms, correct, Bryce?
BryceYeah. Um and I mean if you I I think that the fun the fundamental difference is the um the shape of the the output, right? And so there will always be an inefficiency in doing one in terms of the other.
ConorYeah.
BryceThat that that if if that reduce gives you back a single thing. You know, a single final value whereas a scan gives you back n things. So if you implement the reduction in terms of the scan, um then you will have computed or stored or s or kept around more information than you needed. You only needed the last value of the that scanned array, but you you had to build up and keep that whole thing around.
BryceSo it may be storage inefficient, it may be compute inefficient. On the other hand, if you implement the scan in terms of the reduction, um then you have to build up your output array sort of on the fly, and that's gonna potentially be inefficient. You can't just allocate it all uh a priori.
ConorSo the big question is the two NVIDIA employees don't have a suffix underscore while. So Bryce, I'll ask you, how do you, you know, the the critic would say you can't implement short circuiting sort short circuiting algorithms.
BryceSo how is how is how is reduced possibly because I think Yeah, yeah, but but see I'm thinking I'm thinking about in terms of parallel primitives. And in parallel, like like um if I'm doing something like uh you know a find if um it's just more efficient, or it's less efficient, but faster. Something we've talked about before, um, to simply not short circuit.
ConorYeah, that's the same thing I would say. But if David Olson was here, because I've said this before in a meeting, David is a fellow NVIDIA that works on on MVC.
BryceYeah.
ConorAnd he works on compiler stuff as well. Uh he heard me say that and was like, well, that's uh oversimplification. He says, it depends. And um actually, didn't we get a request to talk about I can't remember the name of the algorithm implementation where you do successively so like if you're trying to do a if you're trying to do something like a find if or a short circuiting algorithm, the way to do it, an implementation on a GPU or something in parallel is to just choose different values of N.
ConorAnd so you do like a full-blown reduction, but only on the first 10%. And then if you don't find if you don't end up short circuiting in that first 10%, then you try the next 20% or something. I can't remember if you start from the 10% mark to the 20% mark.
BryceFor a sufficiently large data set, it it may be correct that short circuiting is um gonna be faster um on modern parallel hardware, but like if I'm doing if I'm if my reduction is that like I'm doing you know, search in like some text and it's like you know, gigabytes upon gigabytes of data, and I'm gonna be loading that onto and off of the GPU or whatever my parallel processor is, um then yeah, like short circuiting might matter if I'm like searching for something in like a hundred or like a 200 gigabyte, you know, input.
BryceUm I just I don't think that's the common case. Um and it definitely slows down the common case uh having to do uh short circuiting um in a parallel computation because that means you're doing some sort of either some sort of branching or some sort of uh uh work dispatch logic where you're not actually queuing up all the work at once because you're gonna launch some of it and then wait. Um and like that's one of the problems with what you just described, is like if you if you do, oh, I'm gonna do some of this computation and then see if I got an answer and then launch more, then it if you're on a system where your work and queue times have a have a long latency, um, which tends to be true about GPUs.
BryceGPUs are bandwidth optimized, not latency optimized. Um not in queue, there you pay a penalty for not in queuing your work as early as possible. And it's not just the penalty of um of how long it takes to send the work to the GPU. That's actually come down a lot in recent years. Um it's just the fact that that first chunk of work may uh happen so quickly, and then whatever logic you're doing on your CPU, you know, those are cycles where you're not using your compute heavy resource.
BryceUm like there's not really there's not really much point in having you know the the the world's most powerful processor in your system if you're not utilizing it all the time. Um and and so I I I do think that that sort of speculatively uh computing is is is the way to go. Um you know, m maybe the maybe the best way to do it would not be to launch a piece and then wait to see whether you get a response, but instead just split the work up into multiple chunks and encue them all at once and then to cancel um later if um uh if you find the result.
BryceUm and that may be a a better approach because then you don't have to necessarily have the work um uh uh check for completion or anything. It's like you just you have like this cancellation case. Um but uh I don't even know how one would structure that on um on our platform. Um you know, whether whether there's no graceful way to cancel some out some outstanding submitted work that does not require the work to um uh have built-in support for cancellation.
Ben DeaneI think it's important to say also that so so yes, so all of that kind of I don't know, strategy of parallelism um and and whether or not to actually short circuit, uh I think is important, and but in some sense it's an engineering choice, and and the the the formulation of the function, scan while or fold while that's an ergonomic choice, right? That's that's the user wants to use this function because that's the way they think about it, and that's that's the eventual result they want to get out, right?
Ben DeaneAnd if they can do it in one function, you know, otherwise it would be you know having to deal with a scan and then I don't know what a find and and a maybe uh something else. So I think there is hopefully we can have our cake and eat it and have the ergonomic function that uh but but yes, obviously you don't it it is frequently faster to do the work rather than as as Bryce just said, stop, branch, re-enqueue, whatever.
ConorIn the in the parallel context. If you're sequential, it's always well. Is it always? I think it's always. It's always faster to just stop, right? If you're going left to right or right to left.
Ben DeaneIt depends. Um if you a branch every loop might not be faster.
BryceIt depends on what you mean by by by serial. If you mean single-threaded, um no, it may not be faster because a vectorized version of the algorithm may be faster.
ConorUm I is vex is vectorized fall under the category of serial though?
BryceBut that's why I said single-threaded. You may have a single thread, like that's what I think a lot of people would think of as serial. And by that I mean. Yeah, but nobody actually writes code like that. I mean even if you write code like that today, every m mm- I was gonna say, like, people write code like that, but that's that's just what you're calling. Every modern major processor, you're not getting performance out of it if you're not um vectorizing your code.
BryceAnd and so you you're just the per you're leaving a huge chunk of performance on the table if your code isn't being vectorized. Um and so if if if you're calling something like a like a reduction or a find if um on any modern uh uh processor, and by modern I mean like last 20 years, it's not not really even modern anymore.
Ben DeaneWell, every any desktop or server processor, I mean the the target that my target doesn't doesn't do vectorization like that at all.
BryceYeah, yeah, yeah, yeah. Sure. But but but the the major the majority of us are programming on uh on a on a desktop server or mobile processor, all of which are fundamentally parallel uh computers. I mean, I mean i uh obviously i if it you know above a certain uh a certain problem size, yeah, short circuiting is gonna be faster. But I think in in the in the common case problem size, it it may it may not be.
BryceThis is like the whole like should you use like a you know a like a a stood map, like a red black trees type data structure, or do you just want like a flat map that's just like basically a fancy vector? Um and in a lot of cases you just want the flat map.
Ben DeaneYou want the uh machine sympathy is the the term that Matt uses.
ConorYeah, there's a great talk by Bjorn Fowler. Um I'll find it. I can't remember the title of it. It's I think it's called Cash Friendliness or something in the title.
BryceHe's given it a couple times where I thought for a moment I thought you meant cash like money. And I was like, what?
ConorNo, no, no. C-A-C-H-E. Uh and he I think it starts off by just like he finds some performance problem, and then he ends up kind of like, I wouldn't necessarily call it yak shaving, but he ends up going down a rabbit hole where he ends up ultimately, well, I kind of ruined the talk, but he ends up, you know, re-implementing a bunch of stuff and then discovering that what he did was something called a B tree that was just basically like a modified type of tree that had like way better um uh cache locality, and so it ended up being way more performant than like this theoretical uh different type of data structure that they were using.
ConorAnd uh I found that super interesting. And he did it all with, I can't remember if it was Val grind or grind or however you pronounce that, but he he showed like all the cache misses and whatnot, and that like uh sure they teach you this theoretical, like you know, big O notation performance stuff, but at the end of the day you're actually running stuff on hardware where it's a much different story.
Ben DeaneThat's interesting, because if I'm not mistaken, B trees were invented for storage, right? They're optimized where there's a the big latency difference between you know between pot between successive layers uh accessing successive layers of the data structure, I guess. So in particular, you know, like that last layer could be on a spinning disk.
BryceYeah.
Ben DeaneUm so it's interesting you know the multiple layered, you know, cache and memory that we have in modern architectures makes Big Special.
BryceThe spread between mean memory latency and cache latency um uh has increased in recent years, and also as processors have gotten faster that you've become a lot more susceptible to notice that spread and latency. You know, it's it basically it's compute has come but compute has become so cheap in recent years. that it's essentially free. You know, when when every when every processor can do maybe for you, Bryce.
BryceWhen every uh CPU or GPU can do uh tons of uh uh you know multiplies and ads per cycle um and like like then to to be able to like fully utilize things uh you need to be able to feed enough data and sort of the the this there's this now this very narrow window for um how much data you need to move um to actually be able to to fully utilize your uh your central processor.
BryceWell I'll say central processor then.
Ben DeaneSo on the other end of the spectrum I would like to add an addendum to the talks at C now um my my friend and colleague Luke Valenti gave a talk um about composition on on tiny embedded systems and just to give you an idea of what is meant by tiny he was live coding and indeed building on a breadboard um he was driving an LED with a with a tiny microprocessor with with 1k of program memory and 64 bytes of RAM in C plus plus 20 and that talk was that talk was awesome.
Ben DeaneThat talk was awesome for a couple of reasons one just just to see that you can use C20 on that kind of system two the audience were on the edge of their seats because it was really you know very sensitive to Luke actually getting the getting the wiring correct as well lots of things that could go wrong but it all came off and it was brilliant.
Tristan BrindleI remember Jason Turner's talk CPP on with the Commodore 64 but he's gone and done it with a thousand times less RAM is uh still using C20 is amazing.
BryceI do think that the trends that we see in the high end of processors do have a long tail effect on all processors in general. Like you may be more compute constrained on a um you know a small DSP or a small embedded processor, but you're less compute constrained than you used to be. And the the what's really changed has been the ratio of compute to uh memory latency and throughput. Like compute latency and throughput compute latency has gone down quicker than memory latency and compute throughput has risen quicker than memory throughput.
BryceAnd that has narrowed the window of um uh like what you need to like how many compute operations you need to do per byte of memory that you move to fully utilize things. And so that you know maybe maybe at earlier points in our history we were spending more time waiting for compute but these days most processors are waiting for waiting for memory to be moved somewhere.
ConorSo the question is what do we call this algorithm?
Ben DeaneWhat do we call this one algorithm?
ConorYeah what is this is there an umbrella term for scans and folds scaffold oh man we've now we've got scanduction and we've got scaffold a scaffold while like that I mean I I sort of put them in different categories anyway because a scan gives you back uh like it's a it's a sort of lazy uh like a range adapter right like it as you ask for each element of the adapted range it it goes and it fetches the the previous element and so that's it's almost a separate category to me anyway.
Tristan BrindleThese range adapters are a different category from the eager algorithms like fold or you know the hundred or so other ones that will you know iterate over the whole range and give you back some result.
BryceThey're sort of I I think I I I disagree. I think that you're you're describing this from the perspective of one particular implementation strategy or technique. And and I I think that you could implement a f a fold lazily just like that and the lazy way that you're describing implementing a scan would be horribly inefficient on certain on certain platforms and in certain architectures. In particular if you're doing the scan in parallel you can't do that lazy thing. So I think that both of them can be expressed either lazily or eagerly.
BryceAnd I do think that they're the same family of things.
ConorI haven't ever tried to do a parallel scan so I I'll uh oh well we can we have a whole episode already talking about but if you think about in your head the um the compute pattern for uh a scan and and a reduction uh can I think about it not in my head this is a podcast and uh your your head is gonna have to be where where where this goes but um if you think about it it it it is the same shape um uh you it it is fundamentally the same shape it's just it's just a question of like what are the results that you're getting out of it um I don't know I I agree like so I was I was trying to search because I thought at one point on the thrust documentation they bucket their the algorithms and the thrust what documentation yeah very funny thrust.github.io slash doc and uh link in the description and I thought at one point it had the scans under the so like the under algorithms there's searching copying reductions reordering prefix sums and transformations so I'm not sure if prefix sums is new but I thought at one point I saw the scans under the reductions header which always bothered me and I have this like one table of fundamental categories and there's maps there's folds or reduces and then at one point I like kind of put scans but like scans are in between like maps and reduce uh reductions like they're like maps in that they give you n values back or you know plus or minus one and they're like reductions in that they carry state whereas maps don't so they're like they're like a map that carries state but I don't know I've never made my mind up like I I do feel that they're different though.
ConorBut also kind of now that we have this like fold while versus scan while it'd be nice if like I don't want to call it a stateful algorithm underscore while like I was just going to say you could use scan to implement a map.
Tristan BrindleYou could see look at a map as a special case of a scan.
Ben DeaneAnyway definitely I was gonna say I mean I think I think we're overly aggrandizing this with the one algorithm to rule them all because it it's not even one algorithm to rule most you're ruining my clickbait Ben We're very much thinking in the model of like okay these are algorithms that work on a single sequence a linear sequence a one dimensional sequence and and we're talking about reducing or you know all the things that encompasses within that frame but but you know we're not talking about unfolds folds and unfolds can be viewed as different sides of the same coin and implemented in terms of each other and we're not talking about graph algorithms which is a whole you know we're talking about one dimensional algorithms in a sense or possibly fixed dimensional algorithms.
BryceWe're not talking about but you you you can build you can build you you build a lot of the other stuff on top of reductions.
Ben DeaneWhat is an unfold uh an unfold is um the simplest example of an unfold that we have in C is probably IOTA so rather than going from a sequence and producing a value you're going the other way around you're going from a seed value and you're unfolding it into a sequence. Sure the unfold in Haskell is called iterate right iterate is one of the yeah a a general form of unfold.
Ben DeaneSo iterate takes a seed value and a function and uh it gives you back the sequence of x and then f of x and f of f of x etc.
BryceYeah that makes sense.
Ben DeaneAnd IOTA is is that same shape just where the function is the increment function.
BryceI was just thinking about how how would you express scans and reductions mathematically and I think mathematically you would define both in terms of summation would be the the underlying operation. There's a reason it's called prefix sum. So I do think that they're both of the family of summation algorithms.
Tristan BrindleSorry I was just going to say if you does that mean that um something like a a split or a group by or something like that where you go from a sequence of T to a sequence of sequences of T, is that also a kind of un uh unfold operation? Or would is that a different category then?
Ben DeaneI mean in a sense it could be I I guess I would say yes.
Tristan BrindleI wasn't familiar with the with the term unfold so I I'm just trying to get it straight in my head.
Ben DeaneYeah it is used in it's more normally used to to go from a you know talking about the one dimensional case to go from a seed to to a to a sequence but but yes I mean so reduce is called reduce because it reduces the number of dimensions by one right in the data. And if we think about the reverse of that as an unfold then you if you're increasing the number of dimensions by one then as well as going from zero dimensions to one dimension you could also go from one dimension to two dimensions, I suppose.
Tristan BrindleOkay.
Ben DeaneUm but it's super useful for things like oh I saw a talk at uh at LambdaConf back in the day about uh about tournament design. Right? You're designing a tournament for some game or sport and you're um you can express that algorithmically with an with an unf with a sort of unfold. Don't ask me the details because I've forgotten it but go find the talk.
ConorLink in the description yeah we're gonna I remember at the time we'll find that talk uh understanding it but um you know lack of use has meant that it's gone out of my brain the thing I was gonna say about um unfolds is that for a long time in my talks I used to refer to I used to mention that reductions are known as catamorphisms in category theory and that unfolds or or folds are known as catamorphisms and unfolds are known as anamorphisms and for a while I used to refer to all of these splitting algorithms like chunk chump by uh adjacent uh slide etc the ones that we all the range adapters that we got in C23 and these all already exist in languages like Haskell etc I used to refer to those as anamorphisms which technically they are but anamorphisms aka unfolds are a a larger umbrella term that I did not mean to use I meant purely the ones that are going from a sequence of values to like a sequence of sequences.
ConorI did not mean like iota and iterate and I don't even really think about two dimensional ones to like three dimensional ones. I like I was purely talking about you know you have a sequence of values and you want to chunk adjacent equal ones and so I've started referring to those as just like splits in in the J language that category of algorithms is known as cut which I've maybe is growing on me.
Ben DeaneI think a useful a useful search term also is recursion schemes. I've seen that used to refer to catamorphism anamorphism and the combo of a catamorphism and an anamorphism I'm not sure which way around either way either way is called a hylomorphism I believe. A hylomorphism just a generalized data structure transformation.
ConorYeah I tried to understand it and I think I did briefly for like a day and then you exp you gave me some example that helped but uh it's never stopped.
Ben DeaneYeah. I only remember it because I think of it as like going high and then low again. Expanding and then reducing.
ConorBut yeah unfolds are very are very useful. And what I I can't remember what uh we went back and forth via email and then it was about iterate. And then I was saying one of the most common patterns is actually like a transform after an IOTA like in both array languages and even in the last team I work on Rapids we have we use thrust heavily and they've got fancy iterators and they've got an IOTA iterator that's called counting iterator and then they've got a transform iterator and it really should be the other way around IOTA's a bad name uh I disagree.
Ben DeaneI love IOTA and Ben has a guinea pig named IOTA so sadly no more oh no last year I'm sorry to hear that rest in peace iota guinea pigs are great but they only lost some somebody somebody clip uh uh Connor saying rest in peace iota and uh put it on the internet use it against him no no um I still have min element okay this they is she he getting up in age uh she's they're all she's because you can't mix sexes with guinea pigs it's bad times poor guinea pigs can you fix a guinea pig?
Ben DeaneI don't think you can fix a guinea oh yeah you can although and it happens usually it's best to leave them alone if you can but um you can fix them and especially if they become prone to cancer later in life which guinea pigs don't nearly so much as something like rats.
Tristan BrindleYeah but yeah anyway I I'm learning about I'm learning about you know category theory I'm learning about rodents this is uh this is awesome.
Ben DeaneOh well the the cool fact about guinea pigs is that uh like humans they can't make their own vitamin C. You know but unlike almost every other mammal you could name um and so when scientists were trying to figure out what caused scurvy um they I now I don't know whether they noticed that guinea pigs also get scurvy or were they just lucked out but they were anyway they chose guinea pigs as their lab animals and that's the reason we call just generic lab animals guinea pigs now.
Tristan BrindleInteresting.
Ben DeaneWow look at that. Which guinea are guinea pigs named after uh someone told me I think it was Papua New Guinea, I'm not sure.
BryceAlright well before we wrap things up um see I okay so so I uh uh a final I I I I feel like I shouldn't have said reduce earlier because you all said reduce I should have said for each I should have said for each or transform which is actually the most fundamental thing like 99 or let's say 95% of code out there is for each.
ConorYeah because they don't they don't know the algorithms I maybe it still only on linear sequences right only on something you can define a linear traversal.
Ben DeaneWell let's just as like sure but just assume that no because because with like a for each you can feed it in a sufficient uh iterator that can do a nonlinear traversal like like you i i it it's it you combine it with you know some fancy iterator arrange I think we're using different terms of different uh definitions of linear but uh but I mean what do you what do you mean by l by linear here? You just give it you can't you know I mean you can have a two-dimensional data structure like a like a map like a red black tree.
Ben DeaneThe implementation but you can still define a l a l uh a linear iteration. I mean you know you can a flattened iteration I mean I mean I mean something it will start at the beginning and when it comes to the end it will stop okay sure. Something that will without without a nested hierarchy it it can traver you know like you can have a pre-order post-order in-order traversal of a tree right that's that's a linear traversal in the sense that it visits every element.
BryceYeah that's yeah yeah I'm not I I'm not saying like like a for H that like necessarily visits well it depends on what you define as the element right you could you can you can you know instead of feeding it in a sequence of every element in the data structure you can feed it in a sequence of just the elements that you selected or things like that.
Ben DeaneSure. I mean yeah the algorithm itself is a linear algorithm it happens to be working on an iterator that that encapsulates the nonlinearity okay that's that I I I I I acknowledge your point.
BryceI acknowledge your point.
ConorWell no wait I was gonna say I was like before we wrap things up and then you interject it Bryce I said we were the the last thing we're gonna say is is there anything Tristan Ben things we want to randomly mention, plug or just say to the listeners?
Ben DeaneYeah attend your local meetup. If you don't have a local meetup and for whatever reason you you can't start one or find one consider the Denver meetup which is a hybrid meetup and now having said that our very next one will not be hybrid as it happens. I was gonna say one of the best meetups out there because it's arguably the best in sense of well in whatever sense in North America.
ConorYeah and many many well known speakers and good talks that I've seen in the past including Ben of course. Tristan you've got a you've got the local London meetup as well.
Tristan BrindleWe have we have run by Phil Nash um which is uh excellent and anybody who's in London uh it's not a hybrid but the talks are recorded and uh Phil puts them up on the the YouTube channel afterwards there's that's someone got in there before you Bryce sorry there's uh just this other podcast host that I like better so uh but can Connor and I have this exciting you know this exciting little bit of travel that we're gonna do which I think will be a pretty unique experience this road trip in the p the pot on the road yeah which will be crash I probably it should probably be a lot more planned than it is currently planned.
ConorNo it's all good we got the flights that's all that matters yeah and you got the car you got the car rental uh yeah and Cody you're gonna be driving is that right is that what I'm gonna be driving he's gonna have the mic but you're gonna be driving and podcasting.
BryceOh absolutely we're gonna at least record one or two podcasts while driving we're definitely gonna get pulled over by the Slovenian or no no that's not illegal that's not that can't be illegal that's not illegal we're gonna get pulled over for driving erratically your tombstone is gonna say killed the environment so yeah you're gonna fly back across the Atlantic for two days and then fly back to Europe again. Yeah I I want to be home to see my family even if it's just for a couple days.
Ben DeaneDo you offset your carbon footprint somehow Bryce Nope question which conferences are coming up for each of us? In particular is there a chance Tristan that you and I will be attending the same conference this year at all?
Tristan BrindleI don't know on my radar I've got uh C1C and CPP North where uh you will be oh great well yes.
ConorThank you so much to Tristan and Ben for coming on the podcast to talk everything about algorithms. We look forward to seeing them at a future conference. Be sure to check the show notes in your podcast app or at adspthepodcast dot com for links to anything that we mentioned in today's episode as well as a link to the GitHub discussion for any comments, thoughts or questions that you might have. Thanks for listening. We hope you enjoyed and have a great day
In this episode, Conor and Bryce chat with Zach Laine about C++26 Reflection vs CRTP, AI, kids & more. Link to Episode 313 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP:...
In this episode, Conor and Bryce chat with Zach Laine about the C++26 contracts fiasco. Link to Episode 312 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...
In this episode, Conor and Bryce talk with Zach Laine about his career and the career changes he has made. Link to Episode 311 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials...
In this episode, Conor and Bryce talk about Bryce's next chapter and where he is leaving NVIDIA for. Link to Episode 310 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The...
In this episode, Conor and Ben chat with Jason Turner about default construction in C++. Link to Episode 309 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...