03 May 2017: Amdahl's Law

okay this song is not going to play today that makes me a little sad that's alright oh there's a new table here change something in the matrix okay so today first of all congrats on those that are done with assignment three a couple new names up here recently so a couple more days actually you know you can keep submitting on the leaderboards as long as you want leaderboards don't know anything about the deadline so so yeah hopefully we'll get a few more people up here over the next couple days of course that still they did click outside of here happens okay today we're going to talk about um Dells law we're going to finish talking about performance and then at the end of class I'll start talking about the paper that you guys are going to look at for Monday so it's a reminder there is no class on Friday we will have all day mega office hours going on in and around Davis hall for finishing up last push on assignment three and then Monday Carl will talk about the rest of the paper that we introduced at the end of class so you guys haven't read it yet I just sent it out today but please look at it over the weekend hopefully I can sort of encourage you inspire you today to actually look at the paper because this is a fun paper to read the lessons are timeless some of the examples have gotten a little bit crufty the paper was written a long time ago but there's a lot of good advice in this paper some of which we've talked about throughout the semester but Lampson does a nice job of organizing it all together and presenting it well ok any questions on Carl's what Carl talked about on Monday sort of the start of our discussion brief discussion of performance in benchmark Carl was excited about sharing some of his own experiences with performance testing with you so hopefully you got something out of that ok so let's talk about statistics so once you've actually picked a benchmark to run and figured out how to measure things about the system that you care about at this point what you actually have to start doing is analyzing the results and this is a place where computer scientists can get into trouble can I talk Thanks yeah there's only one right answer to that question so collect results start computing some statistics and I mean how many people in this room enjoy math really why that's not the response I was expecting yeah hands down up here how about how many people enjoy statistics okay still something wrong with you guys somebody was to come into class demented people um maybe you guys are coming because you're waiting for me to talk about math and statistics well today is the day you guys never to come to class anymore anyway I'm definitely in computer science because I was too dumb to do other things I want us to do right which included at one point physics and then math well I guess math was first maybe in physics or Secor but whatever that's why I became a computer scientist because it was better at it so I don't particularly like maths or statistics but these are really useful tools like other things that we do we build system so we have to learn how to use them on the other hand our approach to these things that's not necessarily always ideal so averages for example like I want to summarize a data set hey I'll uh run the experiment a few times well first of all I have to have a data set so that's kind of the first thing actually on a on a on a bad day I just run the experiment once get one number move on you know because clearly that number is exactly right on a good day I might run the experiment a few times see a little bit of performance variation and try to summarize that data set using some sort of summary statistic like an average which is a fantastic statistic about 10 percent of the time and other 9% of the time is a miserable terrible statistic and if I'm you know feeling really frisky that day you know like I've got some extra time you know something good happened to me in the morning I drank a couple of extra espressos or something I might actually put some air ours on the graph so people have some idea about the variance in the underlined data set so we're going to talk today about some of the right things to do right ways to approach this process particularly once again so we're at the point where we're we know how to measure things about the system and we know the things that the system is going to do while we're measuring it so we figured out how to you know measure things given the limitations that Carl talked about Monday and we have some sense of what this workload should be what are the benchmarks we're going to run that produce behavior that we're interested in studying so this is something I always thought my PhD students and I think this is really a important part of this process that people don't always do the first thing before you start writing experiments is is make predictions about what's going to happen in the scientific method people called this a hypothesis I know we're computer scientists right well they say about science any science that has science in the name it's not an actual science right political science the social sciences in general this is true and I didn't say this don't blame me but you're a computer scientists right so you feel the need to emphasize to people that you do science what that means is that you don't formulate hypotheses before you run experiments so why don't we try doing that and actually this is really this is really an easy thing to do so before you produce a graph of a form of a hypothesis it doesn't have to be like 3rd grade science you don't have to write hypothesis : bla bla bla bla bla draw on the whiteboard a picture of the graph that you think is going to result from this particular experiment and and that's your hypothesis now then you collect results graph the data and if the graph has a shape and features that match your original hypothesis then something about your understanding of how the system behaves has been validated this is always a good thing to do because this is a way to help build your intuition you know a lot of particularly when you build computer systems computer systems takes a lot you know building computer systems if you guys have discovered takes a fair amount of time and energy and so something that you build up over time is an intuition about what things are going to work because we can't always try stuff trying things when you build big systems sometimes take years if that thing doesn't work out that's time wasted and so having some intuition about what's going to happen how systems are going to behave and what are general good design ideas is something that comes with time but is worth trying to build up so make a prediction I just said you can compare graphs you know compare your sketches of what you thought the graph would look like with the actual grass themselves has anyone actually ever done this at college have you taken a class where you did experiment just curious okay are you guys like this is these are computer engineers over here this is like them when they make you to chemistry or something like that yeah there we go okay yeah like other fields do this it's not a weird thing you know I run a chem experiment once you start doing what we're talking about you know benchmarking and experimenting with systems this this is important and it's not something that we necessarily always talk about enough in the context of computer science okay and then you know when we talked Carl talked on Monday about various tools that you can use to experiment with systems predictions are also good ways to validate models and simulators so if the simulator doesn't match up with your intuition and produce results at least along the lies that you predicted then there may be a bug in that system that you need to fix okay understanding your data once you have data working with that data understanding that data you know Oliver in our department works a lot on data cleaning thinking about how to take the data and massage it into the format that you want and then mine it for information one of the biggest mistakes people make is that they in my opinion is that people are drawn to computing these sort of summary statistics too soon why do so for example when I talk about summary statistics I'm sorry have other things like means medians standard deviations things like that these are single numbers that are designed to summarize an entire set of data how many people have computed one of things these things before in the last few years okay how many people did that when it didn't involve like a grade in a class okay it's a few heads that didn't go off yeah so no there's there's deep explanatory power in some of these statistics when they're used properly they also can be really misleading if they're used improperly and there are assumptions about the underlying data sets that are implied in the ability of some of these statistics to actually effectively summarize the data that you're trying to use why do people tend to compute these so quickly it could be a data set you know first thing you do is is compute if I give you a data set a lot of things a lot of you the first thing you would do or if I said compute one interesting number about this data set you would probably just compute an average right why yeah it's a good representation of the data it's a representation of the data it's easy it's actually pretty easy you know there's a very easy mathematical definition of average that I can compute you know even if I you know even if Excel makes me vomit in my mouth a little bit it will probably help me to do this if I poke it in exactly the right way and it also avoids doing things like actually graphing datasets that's complicated I don't want to do that but but some of these things looking at full data sets before you jump to summer so just this is actually really important so let me give you the canonical example of this these two experiments these two data sets produce the same mean and median so if I computed the median and the mean of these data sets common summary statistics I get the same result now clearly there are different things going on with these two data sets you know what's like you know it clearly they look different once a one hump camel the other is a two hump camel but other than that what is like if you were a computer systems person and you saw a data set like this let's say that this is like the page fault handling time for your VM like what's what's the difference between these two or what's a difference what's one direction at that second data set that has two clusters and it starts the Lee doing yeah yeah there's something else going there's two different things going on here you know maybe this is one of the code paths in your VM vault handling and and this is the other code path maybe you didn't know that there were two code paths so this is useful information maybe you thought there were three code paths and it turns out there's actually only two because maybe there's some dead code in there that never gets run because one of the corner cases you thought to handle never happens or didn't happen when you ran this particular benchmark so trust me I mean there is nothing that's going to make you feel Dumber then you know going to somebody like your boss in the future and presenting them with these high-level summary statistics and then having to go back a few days later and be like actually whoops by the way that data actually looks like this and it turns out that there's this completely unexpected thing going on in the data so that I didn't realize this makes sense graphing data I mean don't ever compute summary statistics on reasonable sized data sets before you look at the data in some way histograms like this are a nice way of looking at larger data sets if you have small data sets just you know plotting them out a scatter plot or just looking at them you know what's another you know I thought it would at some point when you know I was thinking about new classes to teacher I thought it would be fun to teach about it you could teach a whole class on misleading statistics well it's an example anyone have a favorite yeah what's that starting an Access Oh in accidents oh yeah you see that all the time right ever seen graphs where it's like it looks like there's been this huge change in a variable and then you squint down at the access and it turns out axes axis how do I say that axis you really mess with me I think I'm saying it wrong right you look down at the scale let's put it that I can avoid the word and yeah the scale starts at like five million right but anyone else but but favorite statistics people talk about like highly misleading statistics what else poor statistical practice oh come on I mean you guys how many people here follow sports like there's a fair amount of numbers in sports these days right and of course you know some of the movement in sports like baseball is away from these statistics that are really misleading on certain levels a batting average for example yeah well Tom Brady wins a lot of games so that's just okay okay yeah yeah well so if you don't play baseball for example something like a batting average has been considered to be a four so just like because it doesn't include times where the runner got on base without actually being given a chance to hit the ball this is where this stuff gets weird my favorite is average income in the United States yeah look at the average income who cares what the average income there's some people over there making billions of dollars that are dragging the average way over in that direction I'm serious that people talk about oh you know the average income the United States went up all that means is that Bill Gates made ten times as much more money right like Bill Gates affects the average way more than I do what's a better statistic for a data set like that median the median is an underappreciated statistic you know someone said before said the average is a good way to describe a data set almost never true actually averages are a good way to describe data sets that have a particular distribution to them a data set what's so nice about a media if I told you the average of a data set what do you really know about the dataset very little all I know is that if I add it up and divide by the number of members in it I have this if I tell you the median what do you know about that data set half are bigger half are smaller so they give you the median income in this country you know that half the people in the country make less half the people in the country make more but it's a useful thing to know about a data set not the only thing you might want to know obviously again both these data sets have to say median and mean so the median is not a you know using medians it's not a magic you know thing that's going to save us from looking at the underlined data itself okay outliers what's an outlier yeah so a weird data point it's like most of my data points are over here and then there's one data point that's ten times larger ten times smaller what do people like to do with outliers yeah ignore them all right whoops something must have gone wrong right something must have gone sunk that just happens sometimes right like sometimes you know the Sun doesn't rise at the time that you think it's going to rise it's like an outlier day and it's ignore it you know just go on with your life yeah so outliers are tricky I mean it is possible I'm not saying that you have to at all costs preserve outliers in your data set but it is possible that outliers are real they could just be some sort of noise in the system you know you ran an experiment at a time where somebody else was hogging the machine it was consuming all of the system resources right I would argue that's not a particularly well designed experimental environment but that can happen but outlier sometimes can represent behavior that you really really need to understand some sort of corner case in your code some sort of very very poor interaction between differences some components and and here's the thing so I think you guys have probably figured this out by now by some magic of the configuration of the universe test 161 when we run it on the server exposes lots more bugs than it does when you run it locally right and this is the case of a general sort of law of the universe that says whatever the worst thing your software can do it'll do it when you give it to the client and say that it works right that's the point at which it'll start to act up and there's actually some reasonable reasons for that they're going to run it with a different configuration they're going to provide more load they're going to use it in some way that you didn't understand or expect but it's also just sort of you know the you know one of these laws of the universe so if you see something like this when you're testing a system this is also sort of like those race conditions that you guys run into when you're testing your kernels you know I've been helping people in office hours and they'll hit a race condition like this and they'll start immediately like shut down the system and start I'm like you we're gonna see that bug again it's gone you know like they're only gonna hit that bug once every million times of course again when you run it for grading we're going to hit it once out of one times so but don't stop like you have valuable information like this is a really really critical moment just leave it alone take a deep breath you know start debugging don't stop and hope it doesn't happen again it won't write again until we graded okay so understanding outliers and data is relatable okay any questions before we go on this is sort of about data analysis all right so now we're going to I mean in terms of like material in this class that has significant deep life implications that people tend to ignore that that you know if there's advice that I can give you to take out in the world that's going to improve your life not just in the computer programs that you write this is probably the best stuff coming up here in the next ten much ten slides okay um does law how many people heard of IM dole's log okay good we're going to talk about it again because we should talk about it more so once you've measured things once you understand data remember we're talking about performance improvement here making things go fast deciding on what to improve is the next step what part of my code am I going to try to rewrite in order to make it faster now even if I thought I should work on the slowest part of the code which is not true this is really hard to do and again I think by now you guys have been developing iOS 161 all semester you may have started to see some of these patterns emerge in your own behavior so for example how many people here have just known that a certain part of their code has a bug in it like if there's a problem with your code you just kind of know where it has to be you know it's in that janky thing I wrote at 3:00 in the morning you know that's got like ijk and ellas indices I did see this in someone's code by the way they know who they are four level page tables yeah like the part that has no comments for 300 lines of code you know the part where I decided to stop using the syntax I use everywhere else like the part where I didn't put great statements around my bear if statements because I thought why bother right you know I've only got a certain number of keystrokes Jeff said that so I'm going to just stop using brace statements braces yeah like we have this intuition this happened to me all the time when there's bugs in my code I'm like oh I know where that bug is you start debugging you know and it turns out you're wrong even if you in nan types you have data in front of you that should have led you to some other conclusion but the problem is you were you're nervous about this one piece of code because you don't understand it fully or you forgot what it does or your partner wrote it and you're like hey it has to be the problem and so you start looking there and sometimes you rewrite it and sometimes you spend time you end up trying to you end up wasting time cleaning things up and stuff like that in the meantime the actual problem you're trying to solve is somewhere else you know and so programmers frequently approach performance evaluation performance improvement in the same way they say okay I'm going to work on this one product Co because I know it's the slow part now that's where I did a linear search through this array and I mean now that's going to have to be the part that's low okay but let's come back to talking about hamdullah slaw so so here's an example I've got two functions in my code one is called foo which takes five seconds to execute sorry five minutes execute and the other is called bar which takes five seconds execute so which function is slower not a trick question foo is slower food takes you know sixty times longer to run and bar so clearly I should start working on foo right away right okay somebody has trained you guys a little bit better than in the past so that's good progress is happening in the world so what two things do we need to think about here yeah yes so the first one and this is one I think you guys have probably been told them for how much does foo matter how many times is food being executed maybe foo was some sort of recovery in your file system that only gets run when the file system crashes now I'm not saying that that's not an important time we talked about journaling and why people do that now to speed the process of propping up file systems that have crashed however if we're trying to improve the common case then code that only runs in special circumstances is totally irrelevant there's something else to think about here this we can measure you know this I can run tests that I can run benchmarks that can figure out how much is foo contributing to the performance of the system there's something else though here that that is a little bit more intuition driven and that is how much slack is there in foo how much can I really get out of this right if I worked on foo for an hour how fat much faster am I really going to be able to get it to go and and this is not something that your benchmark is going to be able to tell you this is something that you're going to have to use other information to figure out you might have talked to other people on your team and say hey has anyone ever tried optimizing this and when everybody on the team is like yeah I did it yeah I did it yeah I did it I did last week you know they're like okay I'm not there's no slack there right unless they're really terrible programmers in which case I would find another job first before you optimize this code anymore so how hard is it going to be to do this you also look at the code I mean if Foos like two lines of code you know that are calling into some library that's provided by somebody else's you don't have control over them good luck right I mean it may just be nothing that you can do so but because we're talking about performance improvement and how to use benchmarking and analysis we're going to talk about significance but again difficulty matters so so here's the statement of our dolls law and we'll look at several statements at this so sort of the most mathematical which is that the impact of any effort to improve system performance is constrained by the parts of the system not targeted by the improvement it's kind of weird right and that this isn't my favorite formulation of this so I have a couple more what this means is that if the rest of the system remember when you work on improving the performance of something you're working part of a system usually the rest of the system is staying the same that's what this this law this formulation of the law is saying I can only get the system to go as much faster as the contribution of the part I'm working on because everything else is unchanged so going back to our example if I can reduce the execution time of foo from 5 minutes to 1 minute or reduce the execution time of bar from 5 seconds to 4 seconds what should I do this is more obvious right what's a right we're still stuck here we still don't know what to do right I mean and and this is this is where the human psychology starts to play a role okay because you're going to feel better about yourself at night if you work on food right you're going to be like no honey I made a piece of code today five times faster now hopefully the person that you care about doesn't care about that sort of thing they're like whatever let's have a beer the but you know the improvement to submit it's like oh yeah I spent all day working on this stupid piece of code and only got one second faster that's just not as glorious right unfortunately it still doesn't matter because if you know as Stephen pointed out if the program doesn't ever call who then all of your glorious victory has been for naught right I remember once at Microsoft like reading this totally gnarly nasty piece of code that had to do with weird page table structures for really large memory architectures and then starting to scratch my head and wondering like I just felt like I felt like I was on a wrong path and so what I did is I ran the preprocessor over the Windows kernel code that I was looking at and that file vanished right so for the for the types of machines that I was working on that file didn't even get compiled in right so that was great I'm glad I wasted those few hours of my life right I remember that experience I remember nothing else about the coat so so again I mean in this case and and you know because the in this case the improvement to Fuu is so dramatic you really have to push these numbers pretty hard to get this to happen but this happens okay when I worked at Microsoft I worked on a desktop performance group the first time I worked there I we had people on in the same unit that worked on server performance and the server performance people spend a lot of time thinking about these hot paths so the server performance people can find one instruction that they can get rid of on something like the page fault path the system call handling path they all get several months off and they go on vacation I'm not kidding because these code basket hits so often and usually they're pretty tight already and people spend a lot of time working okay so this is this is my more colloquial formulation of on dual saw which is ignore stuff that looks bad there may be parts of your code that you don't like there may be algorithms that you don't like maybe data structures that you don't like that you think are embarrassing and bad and they may be but no one cares what they care about is whether or not stuff works and goes fast and so if you fix the parts that are going to cause things to go fast the thing that's doing the damage the parts of your code that are actually causing the entire program to feel slow that's what's going to eventually make the most difference and again this is something that you can apply to your life you know most of us spend a lot of time optimizing things that don't really need to get optimized right so you know take the fix that fix the thing that's causing a problem all right and then this is so this is another corollary to on dualsaw which I think it's really interesting that's also important which is that performance improvements to a particular part of a system have to be part of a process because the longer you improve a particular part of the system remember I'm dolls law the rest of the system's not changing so even if you're working on 20% of the problem you can only make the system 20% better at some point you have to loop back start over run your benchmarks again analyze your data again and pick the next thing to do you know people get I've seen people get really wedged into improving one particular thing about a system and they're totally missing the bigger picture it's like that thing stopped mattering a long time ago you you won you made it better now stop you know go back and pick something else to work and of course again there are there are sort of deep psychological reasons that people do this I understand this piece of code really really well and I know everything I want to do and I've got this whole checklist of improvements I'm going to make and it turns out that I actually already fixed all the things that were a problem but think about all the new cool things I can do to this and just don't do that you know at some point stop take a break go back to square one start running experiments again and take the next thing to work all right any questions about this okay so what we're going to start talking about now and Carl will pick this up on Monday so this is this is one of these classic papers this paper is old fun venerable written by a very famous computer scientist this paper contains a variety of hints as he puts it and Balan Epson is very open about the fact that these are suggestions some of them are self contradictory there is no internal consistency some of them tell you to do one thing and other ones tell you to do kind of the opposite of that other thing and taken as a whole these expressed a lot of different tensions that exist in improving the performance of systems one thing that Butler Lampson is very correct about is that systems are more difficult to both understand and improve than algorithms okay systems contain algorithms they use algorithms but systems themself you know the design decisions that you guys make when you figure out how to factor your VM system that's not exactly an algorithm I mean it is kind of I mean at some level if you really want to go there everything's an algorithm but systems as a whole are more complicated to think about analyze and improve then then then algorithms and one of the things about Lampson does early in the paper is he talks about why this is the case so for example the external interface is less precisely defined this is this is pretty particularly when you're building systems for actual people to use an algorithm frequently has a very very specific thing that's supposed to do sort an array of numbers you know take two sets and figure out what members are common to both of them things like this systems the external interface particularly if it's a human interface is subject to change and less precisely defined so this is one of the challenges systems have a lot more internal structure to them than algorithms do systems have subsystems to talk to other subsystems I mean you think about something like Twitter me Twitter probably consist of you know dozens of different components that are talking to each other rather than you know one single piece of code or single sort of piece of pseudo code or single approach how to get things to work properly is frequently less clear now for certain types of systems there are you know certain constraints for example if Twitter didn't deliver tweets for several days that would be a problem so certainly Twitter and other types of systems have constraints about things that they have to do but the overall design success of some of these systems is a little bit less clear okay so Butler Lampson you know wrote this paper because he had accrued wisdom from working on a variety of different types of systems and this is probably the in my opinion the weakest part of the paper at this point in time because you know 40 years ago and by or 30 years ago by and some of the examples of from this paper are sort of great computer history lessons and so actually hopefully he won't bother me he won't mind me teasing him about this but this is a great paper for card will talk about right now Monday because Carl may have actually used some of these systems so you know Butler Lampson doesn't claim that these are original hints these are things that you know a lot of system designers apply sort of naturally his goal is just to colors they're collecting together in organizing well I can't ask you to active and read the paper so but learn Ebsen organizes the hints into three categories so one is and these are three things that you think about when you build computer systems one is does it work does it do the thing that was supposed to do this is probably the most important feature of any computer system no one really cares how fast an operating system is that dun doesn't run user programs yeah you know no one would care about the performance of Twitter if you couldn't send tweets that wouldn't be interesting so until the system works you know the other two things are sort of irrelevant so getting systems to work once systems start to work then speed becomes interesting and you can substitute speed for resource consumption today at the time this paper was written cloud computing was not a big thing so now you know big cloud computing providers big big companies that companies that build big systems think not only about how well they work and how well they perform but how few machines they can be run on you know because that affects your bottom line the fewer machines I can run things on even if you know so for example if you went to Twitter and you said I have a to to improving your computer system that will allow you to use half as many machines but will only increase the delay of a tweet by half a second they would probably do it I shouldn't put money on that but you know all these companies are making trade-offs between performance and the amount of machines they have to rent not of Rackspace they have to use stuff like that capital costs associated with maintaining these big data centers so fault tolerance final thing he talks about is does it keep working how does it recover from failures what are the failure models how are things allowed to fail okay and then in each part of these tasks there are three sorry and each part of these goals there are three parts of the process so part one is ensuring completeness so for example with functionality making sure that the system does everything that it's supposed to choosing interfaces so this is a task that affects all three of these so how fast does it go sometimes has to do with what are the interfaces that you've chosen to build between various parts of the system and actually designing the implementations themselves so you know making sure that you've done everything you need to do figuring out how different parts of the system are going to talk to each other and then figuring out how to implement the parts of the system that you now now need so I mean how many people had to design an internal interface when you did assignment 3 I hope that you guys don't know what I asked you so how many people wrote their entire VM system is inside vm fault just one big function okay Gus is laughing so at least one person huh yeah I mean I hope like you guys wrote some little helper functions did anyone write a helper function okay there we go so fine you use an interface maybe you didn't think about it that way phew okay good I feel better yeah I mean you may not have thought about this way and unfortunately they had to not have designed it very carefully but once you start to refactor your code and write helper functions essentially what you're doing is creating little internal interfaces that you're using and it's usually better to think about those interfaces beforehand spec them out talk about them you know make sure that everybody on your team understands how they're supposed to work but sometimes they just sort of emerge next that's all that's okay - all right so here is a summary this is a figure that's actually drawn from the paper of all of the hints let's see here and some of them end up in multiple categories so you know that this end-to-end principle is connected through you know several different places let's see here it's a good idea again divide-and-conquer cash answers so Karl is going to pick up with these on Monday does anyone have any questions about these before we stop for the day I know it's a little bit of a short short lecture so so again this paper is rich with useful hints about how to build computer system so please look at it over the weekend of course after you finish the sign of three point three we'll have office hours all day Friday good luck wrapping up a Simon three you