Algorithms + Data Structures = Programs - Episode 4: How Many Programming Languages?

Episode Date: December 18, 2020

In this episode, Bryce and Conor talk about how many programming languages you should learn, why Haskell and APL are worth learning, and how to get your "scan eyes".Date Recorded: 2020-12-13Date Released: 2020-12-18Ben Deane's tweetBen Deane's blog post "Six languages worth knowing"Michael Park's Advent of Code 10A in AWKConor's Advent of Code 10A in SmalltalkConors' Advent of Code 11A in APLHaskell SectionsBoost hana::flipC++ P1371 Patten Matching ProposalConway's Game of Life in APL YouTube VideoHaskell's mapAdjacentpandas Series.ffillthrust::inclusive_scanBryce's CppCon 2019 - The C++20 Synchronization LibraryIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

is at least partially underwater. And so I'm biking, and at one point I realized that my pedals are like underwater. I haven't seen my friends in basically all year. What are you talking about? You're seeing one of your friends right now. What am I, chopped liver? I don't see any of my friends in person. Proctor's like, hmm, should I really let this kid who's completely soaked into a room full of computers?

Welcome to ADSP the podcast, episode four, recorded on December 13th, 2020. My name is Connor. And today with my co-host, Bryce, we're going to be talking about how many programming languages you should learn, why APL and Haskell are worth learning and how to get your scan eyes. We have to read. We don't have to, but I would like to read some feedback. So I sent you a DM saying – you sent me a DM saying we've got to read user feedback. And I sent a DM saying is it good feedback or bad feedback? And I almost like – I almost hope it's bad feedback because I think that's going to be a lot more funny. But, yeah, let's read the user feedback.

I'm not sure if i've read all of the feedback uh that we've received i think i have but i haven't come across any that's that's uh negative um but sure we'll highlight well i'm not come on internet up your game we're not asking for negative i'm not personally asking for negative feedback but bryce uh bryce would would appreciate some but anyways uh pablo from linkedin messaged us saying started listening to your podcast and i thoroughly enjoy it listening to you and bryce talk so passionately revitalize my tough love for algorithms with a smiley face emoji can't wait for more episodes so i'm not sure what tough love means, but we appreciate the feedback. Not sure if you have any thoughts on that that you'd like to share, Bryce. Tough love. Well, I think

he may have been referring to the fact that, you know, we're very passionate about algorithms, but we also, you know, pointed out some of the holes and problems with some of the, you know, names and designs of some of the algorithms in C++. So maybe he's sharing the same appreciation for the problems. And we've got two more pieces. We'll limit ourselves to one piece per episode, but we're at episode number four here, so we're catching up. Ahmad, and I apologize if I mispronounce any of these names Ahmad said can't wait for episode 3

episode 2 was quite interesting first time I heard about the unique pointer array specialization pretty cool amazing podcast so kudos to you for pointing that out educating the masses and then the last one that I was going to read which clearly

I have moved away from. Awkward pause. I had it all lined up and now it's gone. So I'll find it next time but maybe I'll cut this part out too anyways when we started this podcast Connor was like we're not going to do any editing

it'll be nice and lightweight and every episode except for episode one we've been like oh we're going to have to make all these edits although I think only episode what was last week, three? Only episode three actually required some edits because of our... There's been pretty lightweight. The last episode was quite heavy, but they've been pretty lightweight.

It's mostly the first section that needs to be edited. Anyways, today we're debating. Let me adjust my chair. Get in debate mode. Lock the back so that I'm not slouching. What are we debating? We are debating how many programming languages should you learn. How many? Or whether you should learn more than one. Right. I think it was that. Yes. Whether you should learn more than one programming language. And

I will be taking the position of that you should learn more than one. At least a little bit. Well, I think it's really what the debate is. Should you learn a lot of programming languages or should you just focus on a couple of programming languages? And I think I'm going to be team fewer programming languages and you're going to be team more programming languages.

Yes. I will be arguing one of my favorite tweets of all time from ben dean where he tweeted it'll be in the it'll be in the show notes but he says learn computational paradigms and then lists off c++ lisp haskell small talk prologue fourth apl and it's this is actually from a blog post that he wrote, and later in the blog post, he also mentions Erlang. But I think those eight, feel free to leave comments on either the Reddit where we post this or on Twitter or somewhere or LinkedIn if you think that there's another language that represents a paradigm outside of those eight. But I completely agree. He ends his tweet saying, if you know these, just about everything else is variations. And I completely agree that learning one language from each of those paradigms is a paradigm shift.

It's going to completely change the way that you think about problems and that you solve problems. So what do you say to that, Bryce? Nothing. Well, I mean, I should say I don't necessarily, like, as... I've already won. He agrees. As a programming language designer, it would be... It would kind of be hard for me to say

that you should only ever look at, you know, a small number of languages. Because when you're designing a programming language, of course, you want to look at other programming languages to draw inspiration. You want to look at what, you know, what's the existing best practice? What's the prior art? But that's sort of with my hat on is somebody that's involved in programming language evolution. As somebody that's, you know, just working on building, you know, software libraries or software frameworks, in that role, I'm not, I don't feel very motivated to go and learn a whole bunch of other languages,

except when I really need to. Like the languages that I work in right now are the, we talked about in a past episode how my mentor thought there were three acceptable programming languages, C++, JavaScript, and Python. So I kind of know all those languages. I like to joke I write really bad Python. I also read a lot of Bash. Bash is actually a language that I kind of love. And I'm sure we'll talk about that at length at some point. And then more recently, I've been spending a lot more time with Fortran because Fortran's a very important language to HPC and I work on an HPC compiler

here at NVIDIA. But I've just never felt the motivation to go and learn every, you know, cool new language or, you know, languages that I'm not going to be using in my day-to-day work. And I just, part of it's just a matter of time management. You know, I've got so much stuff I want to do and I don't necessarily have the spare time to go and learn a language that I'm not, like, that I don't actively have a reason to use. Like, I've recently been going and relearning Fortran, not because I'm particularly excited about, like, not because I personally have a need to learn Fortran, but because I need to use it in my work. And, like, I think Fortran is actually a pretty cool and exciting language. And modern Fortran, in particular, if you look at modern Fortran versus like older Fortran, like it's a whole different language.

But it's just like I learned it because I needed to use it for my job, not because I had some desire to explore it. And I feel like there's so many things to learn within, you know, each different language. I'd rather specialize in a few languages, you know? Like, there's so much to learn in C++. I'd rather focus my efforts on really mastering C++ instead of going off and learning, you know, Go or Ling, APL, etc. So I think part of part of it is just like how do you find the time um yeah yeah i mean i feel like honestly this is a bad debate because like we very quickly have taken our extreme positions and like centered on something like we agree on uh so i'm sure

people think that i know languages very well but the truth is is like at one point i heard some people referring uh to me at a conference as like oh he's the haskell guy um and i was like what uh because i guess in a couple of my talks i had just i brought up haskell quite a bit but like i i am not a haskell expert by any means. In fact, like I got six chapters into real world Haskell and then got distracted. And like, that's the extent of my Haskell knowledge. And I've spent a lot of time like studying the prelude and like all the different algorithms

in a couple of the most popular libraries. But that does not make someone a Haskell expert. And same thing with basically all the other languages that I learn or that I know, I have some knowledge of, like, I would say I have a very surface level understanding of many of the languages that I can write like a simple solution to some programming problem in. So your comment, you know, mastering one language and just sort of knowing a few that you can like write scripts in is actually probably what I would advocate for. But I would say, you know, follow the advice of the pragmatic programmer, which says, you know, attempt to learn a language every year, every couple of years so that you do get exposed to sort of different paradigms. And I wouldn't say it's definitely not worth it to become like an expert

in a language from every single one of those paradigms. It's worth it to become an expert in maybe one or two or three, and then just sort of have like no, have a surface level understanding of like in broad strokes like you know how does this language deal with polymorphism like how does this language what do they do for their type system you know um do they have like a dsl for insert this or insert that um well but so like for i think it also might be that you and I are like slightly different types of programmers. And that might also drive our different levels of interest in other languages. Like you're really very much an algorithms guy. You get very, you're very passionate about going out and solving algorithmic problems.

And like that's something that you can go and do in, you know, whatever language. Like I've noticed you've done some of the Advent of Codes. Okay, you should tell me what Advent of Code is. I've seen that you've done some of them on Twitter and APL. I have no idea what it is. So very quickly, and this is anyone that wants to can hop in and start solving them. I was talking to Michael Park at the Bay Area C++

virtual user group meeting on Wednesday, this past Wednesday, and was chatting with him and then somehow looped him into starting Advent of Code. He did his first solution in awk, I believe, which we should probably do an episode on at some point. But he's been like changing languages every day. I think the last one he did was in Rust. Anyways, Avent of Code, it's a little programming problem contest, sort of. If you're like in the top 100, it's a contest.

If you're not, then it's just something fun to do, which I am not in the top 100. It's just something fun. Where every day for 25 days from December 1st till Christmas, they release a problem at midnight Eastern Standard Time. And the problem comes in two parts. And I think the idea is that progressively it gets harder from day one till day 25. And a lot of people use it as sort of like,

they take it as an opportunity to get more familiar or to learn a new language. So they choose a language that they don't program in day to day. Not everyone, like I know Tristan Brindles, he's solving them in C++. Barry Revzin I've seen has been solving them in Rust. I've been solving them in a combination

of small talker apl depending on uh what what the problem is and this is the thing i will say about advent of code is that i typically don't get very far because a lot of the problems are super heavy on like parsing the input and i half the time can't be bothered to like just parse input like the problem itself is quite easy. It's just, you have to extract some information from like strings and especially like, you know, years past,

I'd never done it in any other language other than C++. C++ is infamously not a good language for like parsing strings. I've noticed a lot of like coding competitions, like some of the ones that I've seen at various conferences tend to be very, like, string-oriented. And, like, I have a theory that the reason for that is that it's easier to engineer sort of self-contained challenges where your inputs are all just strings. Like, there might be interesting algorithmic problems where the inputs aren't strings, but, like, that requires a little bit more setup. Like, if you've got more complex data types, et cetera. Whereas like strings are fairly easy to set up. But like, I agree with you, like if the problem just like boils down to like either parsing some input string or formatting

some output string in a certain way, that's just like not super exciting to me. Yeah. And that's the thing is some of them aren't like there was a really cool problem the other day that boiled down to basically like you have a list of numbers. If you sort them, you're guaranteed that all the differences will either be one or three. So like figure out how many differences of one there are, figure out how many differences of three there are, and then multiply those two numbers. And if you live in algorithm land, you can very, very nicely just go sort, pipe, adjacent difference, pipe frequencies, pipe values, pipe multiply, and you're done. And if you don't live in algorithms land, then you're gonna have a bunch of for loops, and it's gonna look super messy. So like problems like that, I think are awesome that like,

and all you're doing is parsing basically integers. So that's super fine. But other ones, they give you a sentence that's space and comma delimited, and you need to pull the last two words in three different partitions, and it's just irritating. Anyway, so Advent of Code. How did this come up? Or you said you saw me in APL. Why?

That's the question. Why? Why? Because, yeah, why do I love learning other languages? It starts with Haskell. When I learned Haskell, my mind was blown in that I had been learning the algorithms and seeing a little bit of functional programming and that you can pass, you know, function objects or lambdas to algorithms to customize the behavior. So you can take a simple accumulate and change how it works. And that's very powerful.

Okay, but you can do that in C++ too. So that's what I'm saying. You can do that in C++, but it's limited to what you're given a set of algorithms in the algorithm and numeric headers. And you can write your lambdas. But you're limited to the extent of how many algorithms you get. You get like whatever, 100 plus or minus.

And you can't do anything nice, like really nice. So like if I want to add, if I want to create a unary operator that just adds one to a number, the spelling of that in C++ is bracket, bracket, paren, auto, e, n, paren, brace, return, e, plus one, semicolon, brace, paren, you're done. That hurts my soul a little bit. C++ did an amazing job getting lambdas into C++11, but it hurts my soul a little bit. Then I went to Haskell. First, I learned the lambda syntax, which honestly isn't a lot better, but like the equivalent of that in Haskell

is paren slash e arrow e plus one n paren. So still not super elegant, but it's a lot shorter. And then I learned about something called sections in Haskell, which are basically terse lambdas. So if you take a binary operator like plus, and you just put parens around it, so three characters, paren, paren plus, and paren, that is a binary operator that adds two things together. If you insert a one on either side of the plus, so if you have paren plus one and paren,

you then change that binary operator that does plus to a unary operation that just adds one. So like in three characters, I defined a binary operation. And in four characters, just by binding a value to either side of the binary operation plus, I've created a unary operation. And, like, that's just syntax. Like, you really haven't learned anything at that point. Yeah, are you, like, being charged by the character or something?

You know, it makes me a lot happier. So that's the thing. It makes me happy. Like, when I learned about sections, like, I was just like, oh, my God, goodness. Like, this is amazing. But then, like, you start to learn about ways that like you can manipulate these things. So they have like, we technically in Boost HANA have a template metaprogramming function called flip, which they have the equivalent in Haskell.

So like if you need to flip a binary operation that's like not associative or commutative so that it applies the arguments in the reverse order you can just like compose a function in Haskell called flip with that binary operation and you're done like in C++ unless if you're like doing something in template metaprogramming land and you have access to boost hana there's there's no way to do that like the only way to do that is to wrap your function inside a lambda or there's a couple ways to do it but the simplest way is to wrap your binary function in a lambda and then like reverse the order that you're passing your arguments uh to that function which is irritating um but like in other languages you can just compose

a a function called flip with your other function and you're done um and like that's just that's just like the tip of the iceberg and so like as i started like going down the haskell path it just it just the way that they um you know the way that they had pattern matching like that was the first time i'd really seen like pattern matching in a language was when i learned haskell like i knew it was coming in c++ and later on i would read, you know, Michael's paper. But like seeing how Haskell dealt with pattern matching and guard statements is just extremely elegant. So it just changed the way that like I saw that problems could be solved. And then I stumbled across APL. And if like, if the difference from C++ to Haskell was an order of magnitude, the difference from C++ to APL

is like two or three orders of magnitude. Like the solution that I most recently solved for Advent of Code had to do with basically, they say picture a grid that represents an airport waiting area. So there is a sequence of chairs, which are represented by the character L. And then there's everything else in between that's a period.

It's just empty space that you can walk around. And it is, honestly, it's a spin on the Conway's Game of Life problem. I won't attempt to explain, or do you want to, well, let's stay on topic. Let's finish the problem, and then you can attempt to explain Conway's Game of Life if you want. I can attempt to explain it? If you want. Other than that, otherwise we'll just link a YouTube video. But anyways, Conway's Game of Life, famous problem.

This is sort of a variation of it where it says each iteration of people sitting down, if every adjacent possible seat to them is empty, then that seat becomes taken. And if there are four or more people sitting adjacent to you, then that person gets up and leaves. So those are the rules of like, if you start off completely empty, the second iteration, every seat will be filled. And then the third iteration, any seat that has four or more people sitting next to it will become empty. And then it just sort of repeats. The way that you solve this in APL is like, is mind blowing. Like modern APL actually has something called a stencil operator, which specifically takes like a N by M region of your two dimensional thing.

It's like a popular trick and like NumPy like libraries. But like the old school way of doing it, it's honestly going to be so hard to explain but it involves a bunch of rotates you know Sean Parent's favorite algorithm for the win where basically you're creating a 3x3 matrix of the original matrix so you have a matrix of matrices

where each of the 9 matrices that makes up the outer matrix is, has a one rotate applied in every direction to the original matrix. So like the top left has like a one rotate to the left, the top right has like a one rotate to the right, and then you can imagine like rotates in both directions so that, uh, you have the diagonals anyway. So you end up with like eight different, uh,

rotated versions of the initial one. And if you just do like a summation across all of those original, uh, or rotated matrices, you end up with like a matrix that represents the number of adjacent, uh, seats that are actively um being sat in and like i would never ever in a million years like think to solve it that way um and

unless if i was like learning apl and like learning the apl way to solve things anyways i will end my digression does it but do you do you does that knowledge like you don't you don't write apl code in your day job no um well so i will say uh what the one main thing that was so awesome about that story is when i got the code to work like i i literally like i let out like a yelp of excitement um when i got that code working like it felt it was amazing i i know that uh yelp i've heard that connor yelp before it was like because i honestly i had didn't know how to do conway's game of life and apl and i was working walking through a tutorial and i was like i honestly don't even know i was just typing in like one zero negative one rotate and i'm watching all these numbers pop on my screen. I did not understand it. By the end I did.

But your point is, you know, okay, that's great. You've learned to think differently. Like, but you're not writing an APL day to day. So like, what's the point? The point is that like, it has like, I thought I had good algorithm knowledge when I learned Haskell. Like I, it was pretty good when I was learning C++. Then I went to Haskell and then I had good algorithm knowledge when I learned Haskell. It was pretty good when I was learning C++. Then I went to Haskell, and then I had a bunch of insights. For instance, adjacent difference. It's a terrible name. It encodes the default operation of minus into the name of the algorithm. I had that realization because in Haskell, there's an algorithm called map adjacent. Our map is called transform. So the equivalent sort of translated back to C++ name is transform adjacent. And so then I thought like,

oh yeah, that makes sense. And the Haskell version doesn't come with the default binary operation. You have to specify it. And like when I saw that in Haskell, I realized, yeah, we messed that up in C++. We should have just called our adjacent difference adjacent transform and not encoded a default binary operation because you lose sight of the fact that you can do other things with adjacent difference. One of the things I highlighted in my very first talk is that you can calculate Fibonacci numbers with adjacent difference because it's really adjacent transform. And if you substitute the minus for plus, you have a Fibonacci generator. Based on if you feed the inputs incorrectly. And so like I learned things about C++ from Haskell.

And the exact same thing happened for APL. Like I've learned a ton about algorithms. Like really, arguably, APL should be I've learned a ton about algorithms, like really, arguably APL should be called the algorithm programming language, not a programming language. But I think that's what it actually stands for is a programming language. Yeah, it stands for a programming language based on a 1962 book that Ken Iverson, the guy that wrote the language wrote, honestly, they didn't know what to call it. It was originally called Iverson notation.

And then he wrote a book about it called A Programming Language. And then in the 60s, IBM was like, hey, we could probably implement this. And then they started implementing it in like 66 and 67. And then at that time, like they didn't have a name for it. And like they were trying to figure out a good name for this language. And then at some point, someone walked in and was just like, about we just call it apl after the book and then everyone sort of shrugged their shoulders and said okay um anyways this is supposed to be a debate now i've just started talking about i'm gonna maybe modify my answer to you should have at least one person on your squad like connor so that you have somebody that has all this knowledge that you can uh

you can extract for your purposes but uh see for me for me it's just like I mean again maybe it's just a difference in like what we do um I don't spend a lot of day-to-day time like writing algorithms anymore or even like writing code I'm doing more like architectural stuff. Um, and so maybe it's just because we're like, we do different things, uh, that it's, uh, it's more valuable for you than for me. Um, yeah, it's just like, I don't know, I don't know where I'd find the time. Um, and, uh, it's certainly, I, I could see it being very interesting and exciting to go and learn a language like APL. I'm just not sure that it would do anything useful for me. Plus, I've already got you who's learned it.

This is the thing. As I was going to say, you guys can all, or I apologize. I said guys. Everyone can just watch the future talks that I will give that will just be condensations of everything I learned in language X and skip the learning part, although it's probably not the same. But yeah, I mean, definitely it's job dependent. I happen to work on a library that is heavily built on top of algorithms, the thrust algorithms. And a lot of the times it's figuring out how do we implement another algorithm in terms of like the existing algorithms.

So like having a strong knowledge of algorithms is like very important for the work that I do day to day. Like for instance, the other day, I thought this was awesome. A colleague was implementing something called forward fill. So in a data frame, I'll use the pandas and our Python API terminology. So you have a series, which is basically just a column or a vector, if you will. And we have an algorithm called replace nulls. So you can have, it's basically like a vector of optional data.

So you can either have, you know, optionals that have the values or ones called replace nulls. So you can have, it's basically like a vector of optional data. So you can either have, you know, optionals that have the values or ones that are null opt. And so there's an algorithm that we have called replace nulls that goes through and you just specify a value and anything that's a null value, they replace with that value. There's a variant of that algorithm called forward fill, which instead of specifying a value, you just take the preceding value, the which instead of specifying a value, you just take

the preceding value, the preceding non-null value, and replace that with the null value. So for instance, if you have 1, null, 3, null, 5, a forward fill will replace the first null with the preceding 1 and the second null with the preceding 3. So you end up with 1, three three five so the question is for the listeners and for bryce do you know what algorithm that is not off the top of my head no so we'll give we'll give the listeners uh a couple more seconds well it's it's some sort of a JSON algorithm, obviously. Or I'm guessing it's some sort of a JSON algorithm because you've got to look at the last element.

So you need some sort of stencil where you're looking at multiple elements at the same time. Unless you've got some sort of stateful thing where you're storing what the last element was. But I don't like such things because they're harder to paralyze uh yeah so if you were guaranteed i think that um you only ever had uh nulls that were you didn't have like a sequence of nulls one one after another, that would definitely work. You could do an adjacent transform, a.k.a. what we call an adjacent difference,

and that would work. The problem is what happens if we take our original example and get rid of the middle three and you have one null, null, null, five. If you're doing it sequentially then you're still fine because you you know you you replace the the first null and then it becomes a number and then you by the time you get to the second null you know the thing on its left has been which was a null has been replaced with a with a one already yeah i think actually that would work. Is that defined behavior? Yeah, yeah, yeah.

If it's a sequential algorithm, yes. I mean, if we're talking parallel, then things get a little bit more complicated. In some ways, this reminds me of stream compactation, which is an algorithm where you want to go and find like runs of numbers of the same value and compact them to, or you want to go find runs of elements of the same value and compact

them to a single element. Yes, encoding is what that's classically referred to. Sorry to keep everybody hanging, but the answer to the question or problem is to use something that in Thrust is called an inclusive scan.

Yeah, that was actually my first intuitive thought was that kind of sounds like a scan. But then my second thought was that might be inefficient because you don't need the sum of everything, right? Well, so that's the thing is classically a scan, the default operation of the scan in C++ is partial sum. So basically a scan is a transform that just carries state with it. And classically in C++, the default operation is std plus, which that means that like at every point in time, the state that you are carrying is the rolling sum of all of the elements that you visited so far. But you don't actually need to carry like state that is the sum of everything. There is something called a scan max um or a scan min which all it does is

carries a single value that represents the minimum of the values you've seen so far and so in this example when you're scanning all you're doing is basically scanning with the previous element um and then you basically have a ternary operator where you check like uh is the current element null uh if it is just use the previous element that is the state that you're carrying return that otherwise just return the current value and the way that that works out is that if you end up with consecutive nulls it will always be returning the last previously non-null value yeah this also kind of reminds me of of group by algorithms.

But yes, I'm not surprised to hear you say scan because that was the first thing that jumped out at me. But the thing is, I initially thought scan and then I wasn't certain that it actually worked

due to the sort of case with the extra nulls and I couldn't see it. But what's beautiful is that I think this is like, I think identifying min scans, max scans, you know, plus scans, those are all pretty easy.

Like whenever you need to see those, like in my first algorithm intuition talk, when you have to calculate like the mountain range, which is basically identify the maximum and then do a plus scan from both sides. It's pretty easy to see that. But like this is a non-classical scan i would say like in my opinion that is it is definitely a scan um but unless if

you like spent if unless if you're mark harris and like you spend your your days thinking about like he he said like once you have your scan eyes this is mark harris uh the pick on my team um he was like once you have your scan eyes, you see it everywhere. And I thought that was like a great quote because I don't spend like a ton of my time thinking about like scans. So I wasn't convinced. But when I presented this in like a lightning talk meeting or more accurately, one of my colleagues, Michael Wang, presented it. And then like a couple people immediately when I was like, what's the algorithm? They were like scan, scan.

And because they just they have their scan eyes. If have your scan eyes you see them everywhere um yeah i think this is awesome i'm pretty sure that my adjacent uh transform approach works if you only care about doing this sequentially but if you if you care about doing this in parallel the problem is if you've got like if i've got like one no no five um and let's say that i i divide i divide that four element input sequence into two element chunks each one that's given to a separate thread that second right chunk is going to be null five. And I guess the more nefarious case would be what if you had one – no, no, no. That's the sufficiently nefarious case. In that case, the second thread doesn't know what to do. But I also think – no, I can't really do it with a transformer.

Yeah, I guess it's got to be a scan if you're doing it in parallel um but if you're doing it in in serial um i think uh just like an adjacent transform would work fine if you just if you know that you're always um marching serially from left to right yeah i i think we're getting close to the end but but I'll link what Bryce just said makes sense to me. But I'm guessing to a lot of the listeners, sort of the parallel versus serial when it comes to like adjacent transform versus scan. There's like a subtle thing that he's relying on. And we can try to explain it in a couple of sentences here. But there's a one of

your best talks i think i think it's called the c++ 20 synchronization library from cppcon 2019 i believe at the end of that talk that's where you give like a visualization of inclusive scan with like the upsweep and the downsweep yeah and that that is like i'm not sure if you recall, but the first time we went to, and this probably deserves a whole episode to its own. When you drove to San Francisco and we went to the Michael Park hosted, we were at Mesosphere, I believe. In that car ride on the way to San Francisco, I think previously at like a different time I had asked like I don't understand how a scan can be done in parallel like a reduction is pretty straightforward you can visualize the tree reduction and you know you just add the numbers that make sense but like a scan inherently when you visualize a scan it's carrying state and like anything that carries state it is not intuitive

like how you can make that work in parallel and And then you explained to me in that car ride and I was enlightened. And if you recall, we missed a certain turn that we had to take like three or four times while I was in the deep part of the explanation. But you had the aha moment in the car. Yeah, that was that was hilarious. Yeah, we were so we were talking about the the scan and then yeah a few minutes later wait did we take the wrong ah and then yes some uh colorful words were shared and then i was i was less concerned about us getting there on time than i was about you understanding the power of a parallel scan and i think too i i you were trying

to like get back on the right highway and I was still asking questions. And at one point you were just like, all right, we got to take a break. We got to pause the scan talk. Yeah. We've got to.

And, and that, that version of scan that I showed isn't even the most efficient scan algorithm. Cause that, that was still a two pass algorithm where you didn't upsweep in a downsweep. Whereas the, the modern state-of-the-art, the scan algorithm that we have in Thrust is a single-pass algorithm.

But it's much trickier to explain. There's a whole paper written on it that my colleague Dwayne Merrill wrote. We should link all that stuff. Yeah. Maybe we should leave. We'll leave the explanation of inclusive scan in parallel, maybe for the next episode, maybe that's what we can talk about. Implementing counter and less intuitive algorithms, parallel algorithms, we can try and explain

that stuff next episode. Spicy. All right, anything else we want to highlight before we hop off here? I think that's it. I think it's a good one. All right, everybody. Thanks for listening, and we'll catch you in the next one.