The Mature Optimization Handbook(facebook.com)
facebook.com
The Mature Optimization Handbook
https://www.facebook.com/notes/facebook-engineering/the-mature-optimization-handbook/10151784131623920
12 comments
This is really fantastic. It's highly readable, with a good mix of high-level headiness and practical advice. At a relatively early stage startup many of the techniques are overkill, or simply out of reach, but it's nice to peer around the corner and get an overview of the approaches and problems of performance at the next order of magnitude of scale. And the fundamental lessons of each of the optimization anecdotes are applicable, even if the techniques aren't.
The first few chapters in particular are a nice introduction to reasoning about performance, and the availability in multiple formats is also nice!
The first few chapters in particular are a nice introduction to reasoning about performance, and the availability in multiple formats is also nice!
>At a relatively early stage startup many of the techniques are overkill, or simply out of reach, but it's nice to peer around the corner and get an overview of the approaches and problems of performance at the next order of magnitude of scale.
I wouldn't say that they're necessarily overkill or out of reach, but things to keep in mind as you're designing and building your software. Making sure that you can measure and instrument your code can save a lot of grief later on, even if it doesn't make sense to be doing those measurements right now. The flowchart is absolutely true: You can't prove that it's fast without measuring it.
I wouldn't say that they're necessarily overkill or out of reach, but things to keep in mind as you're designing and building your software. Making sure that you can measure and instrument your code can save a lot of grief later on, even if it doesn't make sense to be doing those measurements right now. The flowchart is absolutely true: You can't prove that it's fast without measuring it.
yes. the clarity of thought really comes through in the writing. nicely done!
Great quote from Knuth/Dijkstra:
I believe that by presenting such a view [on the proper use of goto statements] I
am not in fact disagreeing sharply with
Dijkstra's ideas, since he recently wrote the
following: "Please don't fall into the trap of
believing that I am terribly dogmatical
about [the go to statement]. I have the
uncomfortable feeling that others are making
a religion out of it, as if the conceptual
problems of programming could be solved by
a single trick, by a simple form of coding
discipline!" [29]. In other words, it, seems
that fanatical advocates of the New Pro-
gramming are going overboard in their strict
enforcement of morality and purity in
programs.I had a practical introduction to the dangers of inappropriate optimisation when working in machine vision years ago. I was in a lab that had a mixture of algorithmic researchers and computer engineering researchers, specifically chip design. Now this was back in the early 1990's so we were getting excited about being able to do anything at near frame rate (25 fps). On our typical hardware (Sun SPARCStation 1/2) getting Canny edge detection [http://en.wikipedia.org/wiki/Canny_edge_detector] to run at 25fps on a 512x512 was a challenge.
The group had a very effective technique for estimating depth from stereo camera systems called PMF. Now this was an edge based algorithm, that used a lot of 'high level' (at the time) data constructs; you do Canny, calibrate an align to the epi-polar geometry, search and compare edges under various criteria, create lists of matches, etc. It was accurate, which is what mattered but slow. Now one smart guy in the group worked out that you do achieve the same outcome using a very different approach (known as stretch correlation) to achieve a similar result that on the right hardware would run much quicker. Well to cut a long story short the algorithm got written (worked well) and then someone went off and designed and built the specific hardware, including a chip optimized to run the algorithm. Frankly it was incredible it worked considering this was a couple of PhD students and our access to fabrication was, well typically British shall we say, which lead to yield problems. However, by the time it was all up and running we had moved a lot of development onto Linux on some nice shiny new Pentium PCs (133MHz!) which had little trouble running the original PMF algorithm almost as quickly and more stably than the purpose built chip.
Now in some respects this was all fine. We were a University whose purpose was to teach and some smart people learnt how to design chips and develop algorithms, all good. However, the intention was also to create something of practical value and in this it failed. It failed because people forgot Moore's law and that today's optimized code is tomorrows cranky old, cryptic ball of mud.
I apologise if I'm just reminiscing here but I wanted to share.
The group had a very effective technique for estimating depth from stereo camera systems called PMF. Now this was an edge based algorithm, that used a lot of 'high level' (at the time) data constructs; you do Canny, calibrate an align to the epi-polar geometry, search and compare edges under various criteria, create lists of matches, etc. It was accurate, which is what mattered but slow. Now one smart guy in the group worked out that you do achieve the same outcome using a very different approach (known as stretch correlation) to achieve a similar result that on the right hardware would run much quicker. Well to cut a long story short the algorithm got written (worked well) and then someone went off and designed and built the specific hardware, including a chip optimized to run the algorithm. Frankly it was incredible it worked considering this was a couple of PhD students and our access to fabrication was, well typically British shall we say, which lead to yield problems. However, by the time it was all up and running we had moved a lot of development onto Linux on some nice shiny new Pentium PCs (133MHz!) which had little trouble running the original PMF algorithm almost as quickly and more stably than the purpose built chip.
Now in some respects this was all fine. We were a University whose purpose was to teach and some smart people learnt how to design chips and develop algorithms, all good. However, the intention was also to create something of practical value and in this it failed. It failed because people forgot Moore's law and that today's optimized code is tomorrows cranky old, cryptic ball of mud.
I apologise if I'm just reminiscing here but I wanted to share.
Very cool to see this on HN. :) I developed a 1hr class in March or April for Facebook's "bootcamp", and kind of just kept going, collecting in war stories from smart folks around the industry. If you have any questions or want to suggest a topic to add, fire away.
Thanks. I especially loved the story about the delayed-feedback-causing-oscillations issue.
Is it possible to share some of the details of "postmortems" of large-scale systems in more detail? This would really help academics who are interested in working on techniques to diagnose such issues. Perhaps log files, history of monitored metrics, etc.?
thanks,
Is it possible to share some of the details of "postmortems" of large-scale systems in more detail? This would really help academics who are interested in working on techniques to diagnose such issues. Perhaps log files, history of monitored metrics, etc.?
thanks,
That's an interesting idea. Normally it goes the other way round. Facebook has a fellowship program, and often collaborates with academia, but usually in "data science", not systems or perf. If you are interested, msg me. Maybe something can happen.
Histograms instead of averages!
Optimizing code is really the closest thing to experimental science in programming, because it really is a purely experimental exercise.
Restricting your variables is important, because you can't be sure exactly which change resulted in the improvement if you made a dozen changes(which is why threading is sometimes dangerous, because, like jwz's famous regex quote, it tends to turn one problem into many).
You're going to see things that don't make any sense, even if your gut says differently. This point is hammered home quite a bit. I've seen a case where removing what I thought was dead code reduced performance by a measurable amount... I still can't explain that one.
Restricting your variables is important, because you can't be sure exactly which change resulted in the improvement if you made a dozen changes(which is why threading is sometimes dangerous, because, like jwz's famous regex quote, it tends to turn one problem into many).
You're going to see things that don't make any sense, even if your gut says differently. This point is hammered home quite a bit. I've seen a case where removing what I thought was dead code reduced performance by a measurable amount... I still can't explain that one.
You can't know what to optimize without taking into account how the application is going to be used. And even knowing that, profiling and cost/benefit analyses are the ultimate guide. I think the best rule of thumb is to not worry too much about optimizing everything on the first pass, but be careful not to cut off future optimizations and prematurely lock in poor performance. I always like having my options open.
Great topic!
It reminds me of the times when I found out about the wonders of profiling my applications, where I could clearly see where the bottlenecks were (the 3%).
This also reminds me about the endless discussions about which <insert here a programming language>'s function/method was faster than the other and why you must change your code immediately to save a tiny fraction of a millisecond </irony>
I haven't read the book yet, but I believe the key to a mature optimization is knowing clearly what needs to be optimized. There is no way to know it if you don't measure it. But the thing is that you may be measuring the wrong thing. If you focus on a class, for instance, without the entire context, you may be trying to speed up the wrong piece of your application. Make sure you measure the entire flow, from the user clicking something to him seeing the response. Sometimes you will find that what needs to be optimized is not even your code.
I haven't read the book yet, but I believe the key to a mature optimization is knowing clearly what needs to be optimized. There is no way to know it if you don't measure it. But the thing is that you may be measuring the wrong thing. If you focus on a class, for instance, without the entire context, you may be trying to speed up the wrong piece of your application. Make sure you measure the entire flow, from the user clicking something to him seeing the response. Sometimes you will find that what needs to be optimized is not even your code.
To add a bit of counterbalance, I tried to read a few pages and couldn't help but think in petto "what a loong string of platitudes".
"How a program works and how it performs are very different things." -- Yes, yes... That's also the case for many random x and y.
"By all means, use your brain and your training to guide you; it’s good to make predictions. But not all predictions are good." I didn't find a translation for "La chèvre et le chou", which means keep the goat and the cabbage and is ironic. So yes, predictions are sometimes good sometimes not that good. A very many random x also comply to this proposition.
And so ooyawnnn.
But to have a little positive note, some quotes are fun, I actually enjoyed this troubling Mise-en-abîme[1] "I once generalized from a single data point, and I’ll never do that again!"
[1] Not lucky today, it seems to not have any English translation either, interested reader can wikipedia it or tell me wrong.
"How a program works and how it performs are very different things." -- Yes, yes... That's also the case for many random x and y.
"By all means, use your brain and your training to guide you; it’s good to make predictions. But not all predictions are good." I didn't find a translation for "La chèvre et le chou", which means keep the goat and the cabbage and is ironic. So yes, predictions are sometimes good sometimes not that good. A very many random x also comply to this proposition.
And so ooyawnnn.
But to have a little positive note, some quotes are fun, I actually enjoyed this troubling Mise-en-abîme[1] "I once generalized from a single data point, and I’ll never do that again!"
[1] Not lucky today, it seems to not have any English translation either, interested reader can wikipedia it or tell me wrong.
Dammit. I was hoping no one would see through me.
It's hard to remember to practice those platitudes day-to-day, which makes them worth repeating. You must register your predictions beforehand in order to avoid hindsight bias. You also have to avoid getting attached to them. Programmers very often commit map-v-territory mistakes, asserting how a thing works as if it were an observation of how it performs, and so on.
If all this is old hat to you, well, congrats! But it's not to everyone. And keep reading. It gets more practical after Ch 2 or 3.
It's hard to remember to practice those platitudes day-to-day, which makes them worth repeating. You must register your predictions beforehand in order to avoid hindsight bias. You also have to avoid getting attached to them. Programmers very often commit map-v-territory mistakes, asserting how a thing works as if it were an observation of how it performs, and so on.
If all this is old hat to you, well, congrats! But it's not to everyone. And keep reading. It gets more practical after Ch 2 or 3.
This is a really cool resource. Thank you Carlos and Facebook.
"Carlos Bueno, an Engineer at Facebook, doesn't let data push him around."
Hilarious!
Hilarious!
Someone might mention that the ebook (PDF, ePub and mobi) is provided free in the link.
[PDF] http://carlos.bueno.org/optimization/mature-optimization.pdf
[Mobi (Kindle)] http://carlos.bueno.org/optimization/mature-optimization.mob...
[ePub] http://carlos.bueno.org/optimization/mature-optimization.epu...