Algorithms + Data Structures = Programs - Episode 17: Special Guest Sean Parent!

Episode Date: March 19, 2021

In this episode, we have our first guest - Sean Parent!About the Guest:Sean Parent is a principal scientist and software architect for Adobe Photoshop. Sean has been at Adobe since 1993 when he joined as a senior engineer working on Photoshop and later managed Adobe’s Software Technology Lab. 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.Date Recorded: 2021-03-18Date Released: 2021-03-192013 C++ Seasoning2018 Generic Programming“That’s a lot of APL” tweet2012 C++Now Keynote: Now What? A vignette in three partsAdobe PhotoshopStepanov PapersAdobe Software Technology Lab (STLab)STLab on GithubAdobe RevelAdobe LightroomC++ 20 ConceptsC++ std::moveSTL SGI Implementation and DocsC++ std::findIntro 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 was making myself, I was making myself this very fine hot chocolate. My first Mac hack was probably 88, so I was working at Orange Micro. There were some technical difficulties with the hot chocolate maker and I had to debug it. Guess what? I got a fever. And the only prescription is Sean Parent. Welcome to ADSP the podcast episode 17 recorded on March 18 2021. My name is Connor and today with my co host Bryce, we are super excited to bring you a conversation with our first guest, Sean Parent. How is it going, ADSP listeners? It is just Connor recording a introduction slash prologue

before we hop into the conversation with Sean. Sean Parent, as many of you know, is a senior principal scientist working for Adobe. He's been at Adobe since 1993, with the exception of a year in 2009 slash 2010, where he worked for Google, which is where the infamous That's a Rotate story comes from. Before Adobe, he worked at Apple for roughly five years. And before Apple, he started his career at a company called Orange Micro. That's all I'll say about Sean's work history as I'm sure you'll hear a lot more about it from him as he will be a recurring guest on ADSP the podcast. The one thing I do want to add though, is that if you haven't seen any of Sean's talks, I can't recommend them highly enough. My two favorites are C++ Seasoning from 2013 and Generic Programming from 2018. Listening to Sean talk is inspiring. And a part of the reason

that I gave my first conference talk in 2019, Algorithm Intuition, is because of watching Sean Perrin's C++ seasoning from 2013. So at this point, I'm going to splice in a quote from his generic programming talk in 2018 because I think it's absolutely fantastic. And after that, we will hop into our conversation. Super excited to bring you this conversation with Sean Perrin. And Alex has this beautiful little solution in there for stable sort that builds it up out of all the other algorithms.

All the algorithms within the STL fit together like puzzle pieces. I saw this and I thought, who writes code like this? Okay, right? I mean, keep in mind here, I'm working with a bunch of phenomenal engineers, right? Great people. These are some of the top people in the industry. And I've never seen somebody who writes code like this. Okay. This is not like the code that Alex published in, in his paper five years before, right? He's clearly grown and had some time to think about it. So it's just this phenomenal piece of work. And for me, it was like, like, I want to write code like that. How do I write code like that? All right, we are recording our first episode with a guest. And if you've been listening up till now, you probably have a good idea who it is, the man, the myth, the legend, Sean Parent. How's it going? Hey, it's going pretty good.

So yeah, I've been actually listening to your podcast. I think I'm current, so I've listened to all of them. It was probably the highlight of my year so far when you tweeted out around Christmas the photo of you with a glass of eggnog with the caption, that was a lot of APL. So thank you for that. Yeah, you're an easy man to please i guess so sean do you do you remember your do you remember the keynote you gave at c++ now like 2014 it was a it was you gave a talk where you were talking about getting Photoshop or something of that nature running on an iPad.

And what I remember about the talk is there's one part where you're talking about what's the compute that you have available on the iPad. And like a small part of it is the serial processing power. And then there's a larger part of it that's the, you know, parallel processing power. And then you have the GPU. And yeah, it was just, I think it's my favorite of your talks. But anyways, I've been thinking about it a lot lately because i now obviously work at nvidia and work a lot on parallel computing and uh i just remember net like like in hindsight thinking that talk was really prescient yeah it's uh i use that slide that slides actually from from russell williams and it's it's not specific to the ipad it's actually uh an intel box that a few years ago he kind of broke down the numbers on but yeah if you look at where the compute horsepower is and in a

modern machine if you're just writing.25% of the complete compute capability of the machine. And most of the MIPS are trapped inside the GPU and increasingly now split between GPU and ML units. Yeah. Yeah, one of these days I'm going to, one of these days somebody at NVIDIA is going to teach me something about this machine learning stuff. Yeah. Yeah, definitely worth looking at. I mean, the, you know, my short summary of kind of modern machine learning is is

if you think about you know what we write on machines are just functions and and we typically come up with some equation for the function but any function can be approximated and so if you have something where you don't know what the function is, but you can feed enough material to a machine learning system, it can learn to derive an approximate function. And so, you know, that's kind of all machine learning is, but it does change things. If you look at image processing, say, take Lightroom, the Lightroom auto button, which, you know, kind of auto-adjusts all the sliders. That used to be a very carefully hand-tuned algorithm and trying to look at, well, you know, statistically,

how would we want to balance highlights and shadows, and what about this kind of image, and what about that kind of image? And the approach now is to just get a bunch of experts and have them correct a whole bunch of images and do a really good job and have the machine learn what they do. And that's the auto button these days. So you've worked on Photoshop. What are all the things that you've worked on in Adobe?

You've worked on Photoshop, Premiere? I have not worked on Premiere. So at Adobe, I started at Adobe working on Photoshop and then we launched an internet division. This was way back when Netscape was really hot and everybody needed an internet division. And so I ended up working on a shared component about the only surviving piece of that is something called XMP, which is a standard for metadata and how metadata is embedded in documents so that you can pull it out. From there I did a stint in Adobe's ATG, which is their advanced technology group, or was at the time, a research team.

And I was doing, that's where I started research on something called property models, which I still, is still something that I continue to work on in my, what little spare time I have. While I was in ATG is when Adobe hired and then fired Alex Stepanoff and that led to me and then hired him back and the hiring him back led to me managing him and together we formed Adobe Software Technology Lab which spun out of our research team and so we formed Adobe Software Technology Lab, which spun out of our research team. And so I ran Adobe Software Technology Lab for eight years. And, you know, we wrote the book Elements of Programming. We created Adobe Source Libraries. We did a whole bunch of stuff internally as part of that effort.

And when STLAB fell apart, I went to Google for a year, worked on Chrome OS, came back to Adobe to work on Revel, which was a consumer version of Lightroom for, we shipped it for iPhone, iPad, and desktop and it was a precursor for Lightroom Mobile. It was running the same imaging engine that Lightroom runs and so I pivoted from working on Revel just before Revel was cancelled to start Lightroom Mobile and so I did Lightroom Mobile and then got the imaging engine going inside the browser. So that was Lightroom Web. And then after doing that, a guy named Dave Howell walked into my office one day and said, could we just put Photoshop on the iPad?

And I said, I think I know how I would do that. And that launched the effort to put Photoshop on iPad. So I did Photoshop mobile. And Photoshop mobile is somewhat of a larger effort. You can probably read the tea leaves if you look at people we're hiring these days. But part of that was taking the Photoshop codebase and turning it into a library that contains kind of all the interactive logic. So you can't just do batch processing with it, but you can attach a UI to this library and put Photoshop in other places. And so recently I've been doing some work putting Photoshop in other places which haven't shipped yet. And right now I'm

putting together a white paper and maybe looking to hire somebody and get back in the research side of things a little bit. I've got an idea for a potential product that's a little bit long I've got an idea for a potential product that's a little bit long lead and is going to require a little research to feed into it. Spicy. So when did you first meet Alex? Did you know Stepanov before you became his manager?

Yes, yeah. So when I was working in Adobe's ATG group, one of my colleagues there was an individual, Larry Macenter. And Larry had worked with Alex at Bell Labs years ago and was friends with Alex and Larry invited Alex to give a talk at Adobe and at that time Alex was vice president at Compaq computers if you remember who they were they made kind of you know portable PC devices and Compaq was getting bought out by hp and so alex had been in hp research before but now he's a vp at compact going through a transition to hewlett packard and so alex came in and gave a talk on stl and afterwards i went up to him and told him hey enjoyed the talk and a fan of your work on STL.

And it was a wonderful talk. And he asked what I did. And we started chatting about at the time I was researching property models. And he said, you know, that's actually interesting. So we ended up going up to my office and talking for like four hours. And I gave him a demo of property models, and we just chatted. And at some point in that conversation, he said, he said, you know, I've really missed being an engineer and doing engineering. And I said, well, why don't you go back to it?

Like, what's stopping you? And he just kind of laughed and shrugged it off. And, you know, we wrapped up our talk and he went away. And about two weeks later, he gave me a call and said, you know, I gave a lot of thought to what you were saying. And I would like to go back and be an engineer. And is there a position at Adobe? And I tried to get him a position in Adobe's research organization, but failed. In fact, the exact quote I got from our then CTO was, we don't need another C++ person like you.

To put this in context a little bit, at the time, there was this belief that Adobe would at some point rewrite all of their applications, either in Java or in Flash, as safer languages. So I never thought that that would ever happen, and certainly I've been proven correct to date. But I did manage to find Alex a position in one of our shared technology groups, and unfortunately it was a really bad mismatch. This was kind of generally a mediocre team. There were some strong individuals on the team working on a legacy component that just needed a bunch of bug fixes and maintenance. And Alex came in and was of

the opinion that you know basically all of this is wrong and needs to be rewritten from the ground up. And the engineers on this team don't have a strong theoretical education. So I need to start by teaching the engineers how to code. And then we'll start rewriting this product. That went over about as well with management as you would expect and and we tried hard. We tried to make the classes very relevant and you know I helped Alex with his classes and Alex was getting increasingly frustrated and and at one point I told Alex I said you

know if it gets to the point where you're going to quit, please call me and we'll see if there's something else that, you know, see if we can make something else happen. And he said, no, no, no. He thought that this project was important and he was willing to stick it out and there was no way he was going to quit. And about two weeks later, he called me up and he goes willing to stick it out and there was no way he was going to quit. And about two weeks later, he called me up and he goes, guess what? And I said, you quit. And he's like, no, they fired me. And so I went to my then boss, who was Greg Gilley,

and a lot of respect for Greg and said you know Alex was fired and you need to to make that not happen and hire him back into your organization and Greg said I can't do that politically because he was you know fired in a different organization and it makes the management chain in that organization look bad if I then just turn around and hire him back. And I said, well, at least do me a favor and take Alex out to lunch. So Greg took Alex out to lunch and came back and called me into his office and said, damn you, I'm going to hire him back.

But here's the deal. You're going to manage him. Had you managed people before Alex? So, yeah, I had been an engineering manager on Photoshop for a while fairly early on during Photoshop 5 timeframe and when I had done the stint with when we launched the Internet division I was managing a shared technology team in that organization. So I had done some amount of management.

But I'm going to bet that Alex was a bit different. You know, yes, Alex was a bit different. My wife will sometimes refer to me as Peter Pan because I have a habit of collecting the lost boys, is the way she puts it. You know, when I was running Software Technology Lab, myself included, almost everybody on the team except for Alex were kind of refugees from our advanced technology group and so kind of, you know, misfit individuals. Even when I was engineering manager on Photoshop, my management philosophy has always been that, you know, you kind of want to align your goals with where the company is going,

but you want people to be working on what interests them. And sometimes that means not taking a straight line path to what the corporate goals are. It means you'll run a bit on a tangent. But if you have your people working on things that interest them, you'll end up going further faster than if you just force people to stay on target and walk a straight line. So I'm a relatively hands-off manager when it comes to the individuals. I try to just make sure that I'm communicating with them well and know what they're doing and know what they're working on. Largely the role then for me of being a manager is conveying that information up,

making sure that management is aware of the value of the team and that things are going well in that regard. I just realized we should probably explain to our audience who Alex Stepanov is because some of our listeners are not going to be C++ people and won't know. Right, so who is Alex Stepanov? Right, so Alex Stepanov, best known as the creator of the STL, the Standard Template Library, which is part of the C++ Standard Library,

which was very unique and revolutionary at the time that it became part of the C++ standard. It didn't look like any other library in that time frame. And part of that was inventing the notion of concepts, which are now a formal part of the language in C++20. So Alex wrote the early papers and coined the term concept. You know, Alex's history, he's quite a brilliant individual. He was born and raised in Moscow, was a Ph. the 70s and found his way to the US worked mostly in research organizations in GE labs Bell labs, HP labs, doing research in software development. And it was his stint at Bell labs that got him interested in C and C++ languages. And then he developed the standard template library at HP Labs.

So I didn't know Stepanov was kicked out of Russia. I had not heard that before. Are you allowed to elaborate or shine some light on what happened there, or is that something we don't talk about anymore? You know, I've gotten the story from Alex, so apologies if I don't get all the details correct here. And that gave him access to foreign diplomats who were visiting Moscow. And he would smuggle information to the foreign diplomats and was arrested twice by the KGB. The first time he was sentenced to military service, and the second time they... it was more of punitive measures. And the third time he was caught,

they escorted him to the border, stripped him of his papers, he and his wife, and said goodbye. So, yes, he was, I believe it was Austria. He was stuck in Austria for some amount of time, and he had friends in Sweden. So he was trying to get permission to leave to Sweden, and just because of the bureaucracy, he couldn't make that happen. And one of his contacts said,

you know, you need to contact the U.S. And apparently the U.S. was like a Russian mathematician. You want to come to the U.S.? Yep, we'll make that happen. So this was in the middle of the Cold War. And so that's how he ended up in the U.S. Well, Connor's dad is also a journalist So that's how he ended up in the U.S. Connor's dad is also a journalist and apparently a fairly well-known journalist in Canada.

That is true, yes. Didn't you want to tell me, Connor, that you used to have people who would look at your last name and their faces would pale and they'd be like, are you related to whatever your dad's name is's name yeah this is a super random anecdote that probably our listeners uh won't care about um one time at a party um when i was in university yeah i met one of my my ex's friends and they said oh hookstra that's uh you're not related to gourd which is my dad's name, are you? And I said, oh, yeah, that's my dad. And then she was just like, can you get me a meeting with him? And I was like, for what? And she's like, I work for Fortis, which is like an oil company.

And they were like, it would be, oh, my goodness, like the people upstairs, like there's flags, red flags. They get raised whenever, you know, he sends out a story that has anything to do with us. And anyway, so it's he was an investigative reporter. So if you were doing anything sketchy in Canada, you'd be afraid of the sky. Yeah. Yeah. So I just think of him as like my dad. But to people that work at oil companies and to politicians, they're they're always there's a bit of concern i think when uh when and i'm glad that there's probably like zero overlap between everyone that i'm talking about right now and the people that listen to this podcast but anyways um yeah well don't worry i think it's pretty

unlikely that he's going to get kicked out of canada for sure yeah but that is crazy that um i did not and that's it's so weird to think that Stepan, like we all, or at least I, we think of him as sort of like the father of the, you know, standard template library. And, you know, worked at Adobe for a number of years, that at one point, he was being sort of chased down by the KGB. And then at some point, they said, bye-bye uh i mean i i really kind of think of him as not not only the father of the standard template library but also also sort of the the father of a lot of what we consider to be you know modern c++ library design um you know a lot of a lot of the um a lot of the fundamentals that we take for granted about how you should build a C++ library come from work that Alex either did or Alex inspired. Yeah, I think that's definitely true. I think, unfortunately, you know, I'm going to say this because I'm working on a standards proposal right now. I just finished a couple pages for John Lagos's upcoming book. But I'm working on a standards proposal to try to fix the postconditions of a move from object in the standard,

which I think are badly broken. But in kind of digging through why the postconditions for a move from object are badly broken, it, you know, I realized that one of the key ideas from STL and concepts which was about the domain of an operation, has been all but stripped from STL. And the requirements in the standard right now, even though we still have the requirements tables where we define things like, you know, what equality comparable is or what less than comparable is, and now they're called things like you know CPP 17 equality comparable. We have all the tables there as STL requirements but they're no longer actually used as requirements. So if you look you know

if you if you just search the the standard for the the CPP 17 equality comparable requirement it's never used as a requirement for any of the algorithms or containers right stood find doesn't require that the value type is equality comparable anymore where it did in the old old STL documentation. Instead there's just a couple of types within the standard library that satisfy the requirements that you know they guarantee they satisfy the requirements of of a quality comparable as my example here. But that's you know what value does that have if nothing actually has the requirement, right? I have a type that satisfies these requirements that nothing

actually requires. So, I think over time the semantics of the standard library have kind of been stripped away, and what we're left with is works as coded. When I write std find, it's defined as it applies equal equal to each of the elements in the sequence until equal equals returns true. And at that point, equal equal is just a predicate it's not it's not actually searching for for an equal element yeah this has been um this is actually a problem i've i've become intimately familiar with um because i did a lot of work on the algorithms when we were adding the parallel versions of the algorithms, we came to realize that a lot of the specification of the requirements for some of the algorithms, notably the numeric ones, but some of the others as well,

were sort of underspecified or didn't really capture all of what the requirements were. And in many cases, they didn't, you know, we didn't have concepts in the language when we first introduced them and we didn't get them in C++11. And so because of that, the current corpus of algorithms, the ones that have been there since, you know, since the start are not specified in terms of concepts, which is unfortunate. Eric Niebler likes to say that concepts should come from algorithms, right? That you write the

concepts that a particular algorithm needs. But unfortunately, that's just not how the, that's not how the specification is structured today, although we've gone a long way till it's fixing that with ranges. Yeah, I, you know, I think things are improved in ranges, although we don't, in C++20 anyways, we don't have much in the terms of algorithms with ranges. I haven't looked at what's going on with C++23, you know, where we where we might get more. But yes, it is it is very unfortunate and it's been you know, kind of this this this I

think this, I think, thing that has happened over time, this weakening of the concepts, because people want to say, well, look, if I call find, and find is just this loop, and I call it with my equal equal, it does what I want. It may not do, you know,

it may not be completely legal, but what I want happens to have the same structure. And the way things are defined right now, it's perfectly legitimate to call std find, say, where the value you're looking for is a NAND. And that won't actually find anything, but it's completely legal as far as the standard's concerned, because you can call operator equal on all the things. So even if you're looking for an and in the sequence of NAMs, you can call it, it won't find it.

Where in, say, the HP or the SGI STL, the early versions of STL, and even in the early versions of the standard, that would have been undefined behavior because you were violating the preconditions for find. And over time, the preconditions have been weakened. And along with that, the semantics of the operation have been weakened. I think a part of it is also we often at the surface,

we think about concept requirements as being syntactic, but there's also semantic requirements too. And it's often difficult or impossible for us to enforce the semantic requirements, but it does not make them any less important. Yeah, yeah. And that's the point. It doesn't make them any less important. Yeah, yeah. And that's the point. It doesn't make them any less important. And the whole idea, you know, with concepts was they've never been particularly checkable because for the most part, you know, they rely on existential qualifiers, right? You know, for all or for any, you know, I'm sorry, for all or there exists, right, right, right, right, some element that satisfies this. And so there's no way short of doing a proof that you can validate that that's

met. So the idea with concepts was to say, we can still have the strict semantics. And what we do is we just associate those semantics with a name. If you use this name, then you have to guarantee that you satisfy these semantics. And if you do satisfy those semantics, then the operation works as specified. But yeah, so over time, those semantics have been stripped away. So like I said, stood fine no longer requires equality. It only requires that operator of that, you know, a lot of these concepts, a lot of the concepts or things you want to say I want an invocable that can take a single parameter that is an integral. So not a particular instance of an integral type, but something that satisfies the integral concept. There's not really a way to express that in the concepts that we have

today. Instead, what you can say is you can say I want something that satisfies invocable with this particular integral type. But that problem of sort of, I think often in the C++OX model, it was called archetypes. It's very hard to check for that, to check, hey, does this thing satisfy the invocable constraints for anything that satisfies this other set of constraints yes yes and uh yeah and and where this you know the the damage that i think this has done with with move is in the old a you know hp and and and sgi st. For people who don't know, the STL was originally developed in HP Labs and so the the very first prototype of STL was done at HP Labs and then Alex moved to SGI and so one of the early popular standard conformant implementations of the STL came out of SGI. So you can still

find the docs for that online. Somebody scraped them from the SGI website when SGI took them down. If you look at the at the old docs and even the the old versions of the standard, there was this notion of the domain of an operation. And basically what that said is that the concept, you know, say a concept of a quality comparable, only has to hold for the values that are reachable through the arguments to the function. So if you're talking about stood find, equality didn't have to be defined as total for all possible values of the arguments passed, only for the values that were reachable, you know, within the range of where you were finding elements. And that's how Alex kind of dealt with NANDs and double precision.

So, you know, less than is required to be a strict weak ordering. Less than on floating point types is not a strict weak ordering if you consider NaN. And so Alex just took NaN out of the domain of the operation, right? And being outside the domain of the operation doesn't mean that it has undefined behavior for a specific type. It just means that in the use of the algorithms, it no longer satisfies the precondition for the algorithm. And so that's how things like NAND got dealt with. In the case of MOVE, because now the domain of operation still appears in the standard, but it only does for operator equal equal on input iterators, which is like really weird. It's been like stripped every place else and now there's just one section

where we talk about domain of operation for equal equal for input iterators. The reason why that affects move is basically what happens is when I move one object from one location to another location, the value that's been moved from is only required to be in an unspecified state, and that unspecified state has to be removed from the domain for most of the other operations. And basically, my proposed wording is to say, you know, it's removed from the domain of all operations except for being used in the left hand side of assignment and destruction. Right.

Right. But it's a challenge because domain of operation isn't used anymore in the standard. That's where we'll end Part 1. Tune in next week for Part 2. Have a great day.