Algorithms + Data Structures = Programs - Episode 203: Rotates All the Way Down with Sean Parent (Part 2)

Episode Date: October 11, 2024

In this episode, Conor and Ben continue their chat with Sean Parent about std::rotate, std::stable_sort and more!Link to Episode 203 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)TwitterADSP: The PodcastConor HoekstraBen DeaneAbout the Guest:Sean Parent is a senior principal scientist and software architect managing Adobe's Software Technology Lab. Sean first joined Adobe in 1993 working on Photoshop and is one of the creators of Photoshop Mobile, Lightroom Mobile, and Lightroom Web. In 2009 Sean spent a year at Google working on Chrome OS before returning to Adobe. From 1988 through 1993 Sean worked at Apple, where he was part of the system software team that developed the technologies allowing Apple’s successful transition to PowerPC.Show NotesDate Recorded: 2024-09-26Date Released: 2024-10-11ADSP Episode 202: Rotates All the Way Down with Sean Parent (Part 1)From Mathematics to Generic Programming (FM2GP)Elements of ProgrammingStepanov Papers (website)Stepanov Papers: Notes on Higher Order Programming in SchemeStepanov Papers: Class Notes & Videos - Incomplete Notes for Foundations of ProgrammingC++ std::rotateC++ std::stable_sortC++ std::stable_partitionC++ Seasoning by Sean ParentC++ std::nth_elementC++ std::sortC++ std::partitionC++ std::partial_sortFour Algorithmic Journeys Part 1: Spoils of the EgyptiansIntro 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

I had no idea that it was rotates all the way down. And so if you think about it, how do you get a stable sort in place? Well, that's a quick sort with a stable partition. How do you do stable partition? That's just rotate called recursively. How do you do a rotate? That's just three reverses. how do you do reverses that's just swap and so so we just built like some of the most complex algorithms in 20 seconds right it's really beautiful people should in general think about and there's multiple algorithms in that kind of sort hierarchy right so stable sort is at the top then sort and partition and then element you know there's a partial sort might be in there but

there's a there's a range of power there right and we should be picking the least powerful thing to solve the problem in general yes the fastest algorithm is usually the one with the with the fewest guarantees people tend to to use a shotgun where a scalpel would suffice welcome to adsp the podcast episode 203 recorded on september 26 2004 my name is connor and today with my co-host ben we continue our conversation with sean parent about stood rotate we talk about how it lays the foundation for stable sort, talk about many other algorithms and more. Interesting. So we've got std rotate and GCD.

They have an intertwined history. I'm not sure if you know this off the top of your head, because I have also not read, although a good friend of mine on top of you has also, I think he tried to read EOP and was a C++ dev for a while, but now is mostly using Python. And he transitioned very quickly to mathematics, from mathematics to generic programming and said that it was a much easier read, but also like more thoroughly enjoyable because of the the way that the content is given to the reader does that book cover the three different implementations of rotate or i'll have to

just you know i it should be i don't know if i can make it a 2024 goal but 2025 goal will be to get through all these videos read eop and read from mathematics to generic programming otherwise you know it's i can't can't have this happening again where I, at the end of an episode, am apologizing for probably only 80% of what we should have been apologizing for. We didn't know how little we knew. I mean, Bryce has less of an excuse

because he's purportedly read EOP. So I don't know, he dropped the ball there. I can admit more ignorance and say ashamedly that I haven't actually even finished it. So at least I didn't fail to recall it. I'm not sure which is worse. I mean, there was a time when if you went to C++ Now, the first thing you would hear would be read Elements of Programming. The first year I went to C++ Now was 2014. That was where i first heard about

elements of programming the next year when i went back i had read elements of programming so i was ready for c++ now in a sense yeah i yeah i think well i mean since you guys talk a lot about stl algorithms uh not always but if you're if you're trying to to research one of the stl algorithms where where it's it's one of the the ones that came out of the the steppanoff library right steppanoff and lee check eop first if it isn't there go to steppanoff papers and there's a oh i can find the exact links for you there's's a couple of near books. I think one of them is called Notes on Programming and one is called Programming as Mathematics. Those were drafts of what eventually became EOP.

They're in some ways more approachable. They're more algorithmic centered, less math, even a little less philosophical. When you say Notes on Programming, are you, because I'm pretty sure, at least when you say that, I think of the 88 page PDF that is written or the language used in it. I'm not sure if there's multiple, but one of them for sure is scheme. Is this the same thing you're thinking of? Because there's a chance then if that was a starting point for EOP, maybe EOP all this time, and it's my fault for not having fully read it,

maybe it mentions APL because famously the notes on programming that I'm thinking of implements Reduce and I think all the other algorithms in Scheme. And it mentions, that was the first time I had heard a reference to the fact that Stepanov borrowed the name Reduce from APL and basically said that's where he first saw that algorithm. Yeah, let me see. Links, of course, dear listener, will be in the show notes. I also, sadly, even though I have referenced in both podcasts and talks, the notes on programming, have not fully read that 88-page PDF.

I have read through some of it. Right. So if you go to steppingoffpapers.com, and then the two things I'm referring to are under Class Notes and Videos, there's a section that says, Incomplete Notes for the Foundation of Programming Course Taught at Adobe, May 2004. And there's a pdf for that and if you open that pdf it's uh the title of it is foundations of programming i think volume one linear structures and so that was the start of what was going to become come EOP and then Alex was having

a difficult time kind of completing that that work partially because he just is somebody who goes off on a lot of tangents and so Matt Marcus jumped in to help and so if you look the next thing on the page is steppinganoff and Matt Marcus notes for the Foundations of Programming course, 2004-2005, and it's split into three sections, mathematical preliminaries, generic programming, and the partition algorithm. And those three sections sections form the complete draft of a book. Okay. So we had finished the draft of the book. And there were a number of things that Alex wasn't happy about. Alex and Matt got into a bit of an argument over the direction and how things should be shaken out. And Alex actually pulled out of the effort and said he was going to go do it himself. And so he started again, page one, a rewrite. And

soon after he started, Paul McJones joined him. And so it was that effort that led to EOP. But the notes for the Foundations of of programming and Alex's notes before that cover most of the algorithms that are in the classic STL in a fair amount of detail with all the proper references, right? It's not like, you know, Alex invented this stuff. There's very little in STL that's new. It's collecting other people's work and putting it into a generic form it's the generic aspect that's the new aspect of it well uh sorry actually i want i want to ask you is so stable sort is new right stable sort in knuth edition 2 was listed as a research problem i believe yeah it's a problem that took in place stable sort

yeah in situ stable sort is is alex's big algorithmic contribution there and that's um in older versions of the art of computer programming which is knuth's book uh uh it was listed as an exercise and the exercises have a difficulty problem and i forget what the scale is it's like like five or something is is basically it's a knuth scale m50 is ringing a bell for some reason i think that's like the take a grad student and give them a couple of years to solve it something like that yes so it's basically an exercise with no known solution. And stable partition in STL is an in-place solution and depends on rotate. So it's really quite amazingly trivial once you understand, which is, you know, if you want to do a stable partition for the reader, what that means is you've got some predicate that's going to return true or false.

And you want to reorder your sequence so that all the true guys are first, and then all the false guys follow. But the relative order of everything in the true bucket and everything in the false bucket doesn't change. And you want to do that in place with some reasonable complexity. And so the algorithm is, well, if you imagine somehow magically, what if our sequence was stable partitioned on half and the other half was stable partitioned on half, and the other half was stable partitioned, just somehow magically. And I wanted to combine those so that the whole was stable partitioned. Well, what you want to do is you want to take

the two adjoining parts in the middle and rotate them. And now the whole is stable partitioned. And so then you can just keep recursively dividing each half until you get down to just one element, in which case, how do you stable partition one element? Well, you're just returning the partition point, which is you're just going to return... Whether or not it satisfies the predicate plus its place.

Yeah. Right, plus its address. So that's trivial. Once you recurse all the way down, now you can build it back up by just rotating. Okay. And that gives you an n log n complexity algorithm for doing an in situ stable partition. And so, you know, an in situ stable partition gives you an in situ stable sort. And so if you think about it, how do you get a stable sort in place? Well, that's a quick sort with a stable partition. How do you do stable partition? That's just rotate called recursively. How do you do a rotate? That's just three reverses. How do you do reverses? That's just swap. And so we just built some of the most complex algorithms in 20 seconds, right? It's really beautiful.

And people say that the STL algorithms are not composable. They're incredibly composable. So in fact, almost every algorithm that's in the original STL, the reason why it's there is because it was a building block for stable sort. So that's it. That's the beauty. I had no idea that it was rotates all the way down. In the back of my head now, I've been thinking where it's almost unfathomable that I've made such a big deal. At one point, I actually wanted to get the APL rotate symbol as a tattoo.

And then I had this whole plan to like reveal it during a talk. Anyways, I have a very, very soft place in my heart for the rotate algorithm because i feel like it that was like watching that talk however many years ago you know almost it's like you have these inflection points in your career and uh that was like a big one and now here we are four years later episode you know 202 of this podcast where rotate has come up this many times and i feel like we only on this podcast had touched like the tip of the rotate iceberg, but not only just on this podcast, like also in the conference, like circuits, like there is this beautiful talk that I may give in the future, or maybe someone else will beat me to it.

That is just titled stood colon, colon rotate that like talks about like these implementations and talks about elements of programming, unless if maybe in the hundred hours of content of the four algorithmic journeys, these algorithms are talked about. Cause like similar to your C++ seasoning talk, Sean, where you have those beautiful animations building up to what you ended up calling gather, you could show basically the exact same kind of animations talking about the rotate algorithm, but I have in the thousand plus talks I've watched in the last N years,

I've never seen that in any, not just C++, but there's also some Swift talks out there by Dave Abrahams and Doug Greger and other talks in different languages. I've never seen anything touches on this. So yeah, what's going on? How come this talk doesn't exist? Or maybe it doesn't.

It just hasn't come across my radar. I don't know one quite like that that exists. But yeah, I think if you did like title of talk stood rotate and you can get into kind of the algorithmic beauty and then the uses, both the uses inside of STL and things like slide and then gather. Ben's example of picking up one element and putting it somewhere else. Actually, when you said that, I was like, that's not a rotate.

And I was like, oh, no, that is a one rotate. This is overwhelmingly the most common use case I've ever seen for rotate. People do this all the time. Arbitrarily rotating blocks or ranges ranges that's a useful building block but but in application code 90% of the time you want to take this element and put it somewhere else yeah i'm not sure that a rotate lies behind that animation but any i can think in like a multiple apps on my phone where you'll have a, basically some form of a playlist or some form of a list. And then you have like a hamburger thing that you

can touch and like drag the UI thing. Even if there's no rotate in the code behind the scenes, cause you're actually doing a little bit more, right? As soon as you touch it, I guess, technically you're just doing repeated one rotates on two elements, but you can drag it up and down. And that is effectively at the end of the day, if you're not showing that animation, that's a one rotate on that sequence whenever you're doing that kind of. And I think that's not that far removed from the gather example that Sean shows where I think you kind of talk about what if you're in like an email inbox or something like that and you you select two things and or I can't remember if that was your exact example but it is something to do with that well my exact example I was working on Chrome OS and and and I was doing my very first code review at Google and somebody made a change so that you could Chrome OS has a view where you could could could see all of your windows as kind of these little slices on your screen, and you could reorder your windows. And you could only drag one, right?

You could drag one and put it in. And that's the code that I was reviewing. And the code, I show all the code in my talk, It's this morass of loops. It's like this 1800 line function or something like that that's doing all of these loops. And a bunch of them are conditionalized like, oh well

in this case we do this loop, in that case we do this loop, in this other case we do this other loop. And I was like, whenever I do code review the first thing I look at is what are the loops? What in the world are these things doing right and i tear through it and they're doing a one rotate and they're doing it by erasing the one element and then erasing the next element and and reinserting it into the new slot so it's like this quadratic erase and assert mess okay and so it's really slow and and the only other piece of it was you needed to find the position right you user clicks somewhere you

need to find the position and and so so i went went and said okay like the start of this is a find if followed by rotate and if you read all of the rest rest of it, it's basically just another rotate, which is what gather is because you're rotating. Depending on which way you're moving, you're rotating one direction or the other, right? It's the same three arguments, just a different permutation of the same three arguments. So I'm like, this is just find if, rotate. That's all that's happening here. And that had led to a big argument. And I finally convinced the, uh, uh, the author of the code that, that yes, that's what his code was actually doing. I mean, the first thing was, he's like, no, that's not at all. You don't understand my code, right? My

code is doing way more than that. And I'm like, it's doing that, right? It's doing a lot more work to do that, but right. Right. So I finally convinced the author, but then it was still rejected from the code review because my mentor, who was overseeing, since it was my first code review, said that it was too tricky and nobody knew what Rotate did. And because of that, that code landed in the Chromium open sourced effort because Chrome OS is open sourced under Chromium. And that's why I was able to put the code in my slides. Okay?

Nice. So that's kind of the whole arc. And my point there is, once you realize that that's a one rotate, then if you want to do multiple selection and select a range, that's still just a rotate. And if you want to do a disjoint selection, it's stable partition. But stable partition is just recursive rotates. Right.

So once you realize what you're doing is a rotate, you can do multiple selections in your ui okay trivially yeah because it's all built from the same stuff because it's all built from the same stuff if your code though is is looking like like well if it's at this position then i'm going to erase this guy and insert these guys and and otherwise i'm going to erase this guy and insert those guys if that's how your code's written first you're going to go horribly quadratic as you try to extend it to more to more elements but you're also never going to erase this guy and insert those guys. If that's how your code's written, first you're going to go horribly quadratic as you try to extend it to more elements, but you're also never going to figure it out. The complexity gets too high to think about it in those terms. So my pet peeve right now is applications that don't support multiple select, or if they do support multiple select, don't let me drag the selection around. Right?

Drives me insane. And it's ubiquitous. All right. I know we only have a couple minutes left because we have a hard stop. We have to let you go, Sean. But maybe in the last couple minutes, a final question. And it might be hard to answer now. So if there's no answer, maybe we can all just think about it and see if we can come up for answers next time. I, just in the last 60 minutes, just during this recording, realized that the one rotate is actually like the most common use case of a rotate.

That's like lying in plain sight. But until you, someone says it or you notice it, I do kind of like, you know, I have a soft spot in my heart, like I said, said for for rotate but you do kind of think of this like oh whoever needs like a four rotate it doesn't come up that often but a one rotate when you think about it from like what's what is that doing that comes up all the time are there other either stl algorithms or algorithms outside of the stl that have these obvious like in plain sight use cases that, you know, might, I might be missing or folks might be missing. Cause like, I think stood sort, you know, algorithms like that, it's obvious what you use those for, but potentially I'm guessing that there are these other kinds of uses in plain sight that until you see it, you might miss. Do you have any of those

off the top of your head or? Yeah, I think, you know, my, my other favorite algorithm that gets missed a lot is nth element. I was going to say the same thing. Least appreciated, the most underappreciated algorithm ever. Yes. So nth element, I mean, it will give you a median. It will give you, you know, so it's very useful if you're trying to gather statistics on things. It will give you unsorted top n.

Yeah, if you need the top n elements out of something, or not just the top n, if you need a window of things, you need things, you need elements 30 to 50 out of a sequence of a million. How do you get that without sorting the whole sequence? So nth element is going to be a piece of that answer. It also partitions, it leaves your sequence partitioned. And so that's a very useful property that can be exploited. And so if you're trying to gather a range of statistics, like if you're in graphics and you want the, you don't just want the media and you want like, like what's at the 10% mark, the 40% mark, the 50%, the 90%, right? You want to sample a set of crust of ranges. You can do that by starting at the nth element

for whatever element is roughly in the middle, and then recursively partitioning, yeah, with nth element. And you can gather a set of statistics very quickly from a large sequence of numbers. So it comes up a lot. It's one of the most underutilized. And a lot of times where I see people sort, it's like, oh, you didn't need to sort. You know, you just needed nthelmin. Right.

Yeah. People should, in general, think about, and there's multiple algorithms in that kind of sort hierarchy, right? So stable sort is at the top, then sort and partition, then end element. Yeah, or partial sort might be in there, but there's a range of power there, right? And we should be picking the least powerful thing to solve the problem in general. Yes. The fastest algorithm is usually the one with the fewest guarantees. And so think about what problem you actually need solved and then select accordingly. And, you know, it's just like the number of times I see people reach for a map when sort and lower bound would have been the obvious better choice.

People tend to use a shotgun where a scalpel would suffice. Wow. This has been absolutely phenomenal. We'll do this again at some point because this was amazing. Links for everything we mentioned in the show notes. And I know, Sean, we have to let you run. So we'll say thank you. And until next time and to my new co-host as well, Ben.

Yeah. Thank you, Sean. Hey, thank you both. Be sure to check these show notes either in your podcast app or at ADSP, the podcast.com for links to anything we mentioned in today's episode, as well as a link to a get up discussion where you can leave thoughts, comments and questions. Thanks for listening. We hope you enjoyed and have a great day.

I am the anti-brace.