@@davidmark1673 if I didn't already know how to calculate a p-value, I'm not sure I'd be able to just from that (although I'd at least know where to start looking). (Then again I mostly deal with Bayesian inference and rarely do p-values)
This is an awesome talk, with some great, novel information (at least to me). The name of the program, "Stabilizer" is humorous, as it is actually more of an "unstabilizer". Excellent work Emery. I would love to see a example program that demonstrates significant performance delta between memory layouts.
Wow. He went from theory, background knowledge, to full blown applied uses at a really nice pace. This is a great lecture for any student in software engineering. Love the reminders that certain optimizations can cause slowdown--as well as the reminder that rolling your own naive hash table can have disastrous consequences for performance (37:23)
All code and papers are linked from here: plasma-umass.org. To install coz on Debian or Ubuntu: % sudo apt-get install coz-profiler Papers: * "Stabilizer: Statistically Sound Performance Evaluation" [ASPLOS 13] people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf * "Coz: Finding Code that Counts with Causal Profiling" [SOSP 15 Best Paper, CACM Research Highlight] sigops.org/s/conferences/sosp/2015/current/2015-Monterey/printable/090-curtsinger.pdf * Mentioned during talk: "Producing Wrong Data Without Doing Anything Obviously Wrong!" [ASPLOS 09] Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter Sweeney users.cs.northwestern.edu/~robby/courses/322-2013-spring/mytkowicz-wrong-data.pdf Slides are here (Keynote): emeryberger.github.io/presentations/performance-matters-strangeloop2019.key Reddit discussion thread: www.reddit.com/r/programming/comments/d4k5x5/performance_matters_by_emery_berger_strange_loop/
This is the only helpful performance analysis talk I have ever seen. Spectacular work, and thank you for making the tools available. I think it'd be spectacular to integrate the layout randomization and causal profiling directly into the Rust toolchain, and I can't see why not. Edit: seems somebody has ported or begun porting Coz to Rust, very cool. :- )
It has all been written before, but in order to "feed the algorithm" let me just concur, this was to me an extremely interesting and in many ways eye opening talk. And the presentation was absolutely "spot on" for my preferences, clear and and to the point, with the perfect "balance" of overview and details, and then some humor for those of us who like that. In short(?) interesting, informative, educational and enjoyable. Best regards
One of the better talks on "Memory Layout" within a given program or application that has a direct effect on Performance. The jokes and puns are great! No more malloc! Run it as me and it's faster... lol! Great content!
This was a bloody amazing speech and great content. Now the coz-profiler just needs to be ported to macOS. If it works on Linux already probably isn't too big a leap.
I really like the causal analysis technique! I might be misunderstanding what "layout" is, but I was confused as to why you would randomize it every .5 seconds. It seems like this could wash out optimizations that are actually valid, e.g. optimizations that reduce the probability of cache misses, because out in the wild layout isn't being randomized all the time. It seems like the fact that you get unexpected distributions when only randomizing once per execution could be indicating that different codes do have different performance characteristics across different layouts, meaning that there are potentially useful code-level optimizations. An extreme example of this could be a data structure that monitors its own timing information and adapts to optimize latency assuming static memory layout, because then randomizing the layout could make that structure look way worse than a more naive approach that doesn't bias itself for any particular layout.
To me it seemed that the point of it is to eliminate any layout optimizations and look purely at the code and then on top of this you can add machine specific or runtime layout optimizations if you need them.
the randomization is to remove measurement bias, not to improve performance. you don't do this in the actual program, just while you try to figure out what other than memory layout ( = how the memory access is organized) influences your performance.
My understanding is that the layout is not randomized, but it's *outside of the developers' control*. So say the layout on your testing machine is just right to get a few small speedups, but you've got one unlucky customer whose layout causes a slowdown once a month or something. By randomizing the layout repeatedly during testing, you can avoid the random advantages and disadvantages and instead get a statistically meaningful test result.
Regarding 0.5 seconds: Isn't this already very long for this kind of test on modern computers? Using the right kind of algorithm, it's always possible to construct pathological examples that would require running the program for hours before you can compare the times without getting misleading results. But in practically occurring cases, half a second should be plenty, while also being short enough so you can try many iterations. Also, the program that adaptively changes its memory layout is reminiscent of a halting problem construction. That's more of a sophisticated denial of service attack against the performance test, rather than a genuine problem likely to occur in practice.
but the key here is that you can't tell if it's a code improvement of a layout improvement unless you use the stabilizer to randomize the layout. If you want to measure whether you did any optimization to the layout after the fact, just compare the non-stabilized layout to the stabilized one. Nothing is lost.
That stabilizer. Instead of randomizing every half second, you could randomize once per test. And then pick the best program. Super optimizing compiler.
One thing I'm wondering about: these causal graphs assume that no other variable changes its performance characteristic, right? So wouldn't it be possible that speeding up one bottleneck completely changes the shape of the graphs of all the other ones?
Right now, Coz tests the effect of a single change. It would also be possible to test the effects of two changes (or more), though this requires an increasingly large number of samples (testing pairs requires O(n^2) experiments, for example).
Great talk about performance. You illustrate quite well the struggle to optimize a program. I'm curious about all those real examples in you "Summary of Optimisations" slide. Do you have references about them ? (like specific thread or patch note ?)
I noticed once in a C++ project that changing the order of some of my very slow functions consistently improves their performance by 3%. Seeing that kind of made me want to give up coding
The working diagram of the program makes me think of Program evaluation and review technique/critical path analysis of all things. I wonder if the coz analyser is partly inspired by existing ways to "optimise" projects that utilise PERT/CPA. It's probably closely related, though I'm not proficient in any of those, so I could be way off. Good talk though! And very interesting.
First class work and presentation, with Prof. Berger's inimitable sense of humor. There are definitely statements made that I need to think about (I don't agree with them 100%, but ... Prof. Berger may well be right and I may well be ... well, "less right"). I think I will "start at the beginning" with: arxiv.org/abs/1608.03676 .
25:50 whats it all about with the "dash O1 up to dash O11" thing. I dont actually know what -XX means in the first place. Yould be glad to learn about from you guys!
You are telling the compiler (the program that translates you quasi human programming into 0 and 1s) to have a deeper look into your code and try to see if it can be made faster by exploiting some of the properties of the processor
A “causal profiler”, huh?… I bet that would be useful as a component to building a system that uses an evolutionary algorithm to create a program, or at least, to optimize a program. Specifically, the part that grades the performance score of a unique specimen of code, to decide whether it survives that generation. Then you just need a way to get the random code to do the thing you want, and to get it to avoid or fix bugs. Maybe I shouldn't say “just”, in that sentence…
It's not fully independent the execution time at time t depends on some state from time t-1 things like temperature which threads finished first branch prediction etc. So that means ur assumed normality is problematic because u basically Hand wave those away. I feel like directly testing normality and then doing the rest is best
Yes, but I'd love you to show me a modern system where literally disabling the concept of virtual memory would go over well. Cache would be even harder to disable, as it is likely hardwired into the processor, and might barely be changable by microcode.
No, because algorithms that take better advantage of caches etc. are the most important aspect of software. Thus if you would eliminate caches, you could have algorithms that never get cache hits be as fast as best dynamic programming algorithms that utilize caches optimally.
This was a cool talk but I think it should have included a description of what A prime, O3, O2, and all of these metrics are. They're mentioned but sound nuanced enough that I feel like I don't understand their importance.
O2 and O3 are just C/C++ compiler optimization options (GCC, Clang, MSVC, etc). O0 means no optimizations are performed, which is useful for debugging, and isn't bad in all scenarios, but sometimes has some really wonky performance effects. The higher the O level, from O1 to O3, the more mangled the assembly looks, but the more optimizations are applied. O3 has a reputation for not actually providing any benefit over O2, and this confirms that. Compiler authors didn't have tools like this to actually check if their "optimizations" were anything more than artifacts, and so they ended up being artifacts.
Where 'A' is the label identifying one version of code, 'A prime' is simply a label identifying the later version. This is an idiom carried over from mathematics, but otherwise the labels are arbitrary and are not significant beyond this presentation. '-O3' and '-O2' refer to compiler arguments for optimization levels.
The command `gcc main.c` compiles the file main.c into an executable i.e. a program that you can actually run on your computer. If you specify the argument `-O0` to the gcc compiler, then you're telling it to compile your code without performing any optimization whatsoever. "O0" stands for "optimization level 0". It will compile relatively quickly, however the resulting program will be relatively slow. The command `gcc -O1 main.c` is likely to produce a faster executable. GCC will optimize the code more aggressively with the argument `-O2`, and `-O3` represent the highest level of optimization. `-O9` isn't a thing. What could be expected is that more the compiler optimizes a code, the faster the resulting executable runs. However that's not always the case.
The -Ox flags are optional compiler flags that determines the 'optimization level' of some compilers (notably GCC: www.rapidtables.com/code/linux/gcc/gcc-o.html). Essentially, the higher x is in -Ox, the more tricks your compiler will try to apply to optimize your code.
14:00 "I guess I'll never malloc again" And everyone laughs as if it is absurd to even suggest never using malloc. It's called MEMORY POOLS! Yes, you can have dynamically allocated memory w/o using malloc. Just manage your own memory. AAA VIDEO GAME ENGINES ALREADY DO THIS, IT IS NOT IMPOSSIBLE TO ACCOMPLISH. Especially if the program you are writing is less complicated than a video game, which I can almost guarantee is the case.
But... You shouldn't use malloc anyway, you should use new and delete. If you're writing complicated software in C and it's not for a good reason, you're just punishing yourself. Also, if you ever find yourself using new and delete, 95% of the time you should re-evaluate your life decisions and use a standard library data structure instead.
No. The original code used a struct with pointers to functions and the dot operator to call those functions through the struct. The change was to call the functions directly.
It's a great presentation, great lecture, but this is a 1st year of University when doing Computer Science... So normally I'd expect anyone working as a dev to know this.
I want to find your magical school where they teach about layout and cache optimization in the first year. Seriously, I would. All of my courses barely got into optimization and hardware level items. If I didn't watch videos like this, I'd be a much worse developer. I always found it sad and hilarious at the same time that most of my friends never used or bothered to understand even the simplest of data structures in the standard library of languages we were using.
Hey Dr. Berger if you are still replying, in the graphic at 30:48 it looks like the virtual speedup is done by just putting other processes in a timeout where it completely stops for a while. Is this just an artifact of the graphic? It seems like this would mess with the analysis of competition for resources. Maybe I have the wrong idea in my head, but how can you stretch run-time in each piece in a way to make sure that processes that were happening concurrently before a virtual speedup are still happening at the same time?
Concerning O1, O2 optimization, fit in L1 and L2 cache is a big deal. If O1 binary happens to fit in L1/L2 and O2 does not, then the O1 binary could perform better than O2. The big thing today is that memory round-trip access time is a couple of hundred CPU-cycles. Try to avoid too much pointer-chasing code. Prefetch memory when possible. Note, Intel Core iX processors up to generation 9 have 256K L2. The Xeon SP lines have 1M L2 at 2 additional cycles access time. 10th gen Core have 512K L2. Be aware that Intel processors since about mid-2000 had cache line size of 64 bytes. Prior to that, it was 32-bytes. My view, too many software people have purist view of the world, thinking they can achieve great performance without consideration for the details of the underlying hardware.
I've never known anyone focused on performance who didn't care about the underlying hardware. Timur Doumler even has a talk called "Want fast C++? Know your hardware." Also. Most of the stuff you mentioned forms the basis of things like DoD (Data Oriented Design).
@@nyankers precisely. Focusing on hardware is only something you do for compute clusters, where you're running on bare metal, and therefore know exactly what is running where. Otherwise, your cache optimization could just make things worse on a different platform.
This was an amazing talk! Lots of counterintuitive things to correct in our mental models about performance, thank you for the knowledge! Haha, I loved the "eyeball statistics". Wonderful.
But we DO have magic! 1) Have set data to run through the program. 2) Run it through the program, saving the results of each individual process. 3) Run it through the program again, skipping different processes by copying pre-calculated results. You can even run the process halfway and only then copy the precalculated results. Anything from minor improvement to infinite speed is possible!
Reminds me of Z80 Assembly, you can triple the speed you index an array by aligning the array so that the base address ends in 00. Basically you only needed half the pointer to the array
41:33 a traditional profiler wouldn't have caught those things, how? Shouldn't the operations that make the program slow be the operations that cost a lot of time?
Is it necessary to have the --- in the coz command line? And if it is, is it necessary to name it exclusively with non-alphabetic symbols? It does not seem something I would have in an API if I want to make it intuitive/self-commented/discoverable/usable.
testing the speed of a piece of code by slowing everything else down seems like it would miss interactions between components. It seems like the ferret example required explicit knowledge of interactions in order to discover the optimization.
Think of it as running the application on a slower computer, everything is slower globally. However, since this is done virtually, you can virtually speed one component up independently. Since everything, but your isolated component, is running at the same global speed, relative interactions among those components should be preserved. You only need be able to isolate a specific component.
The graphs and analysis at 24:20 are flawed. The problem is that -O2 and -O3 actively optimizes the layout, to improve (static) branch prediction and separation of hot and cold code. By using randomizer you throw these optimizations out of the window, so obviously you are going to loose advantage of using these optimizations. The proper way to test is to keep benchmarks well designed, and run in extremal well controlled environment (keep noise to minimum), preferably in a cycle accurate CPU simulator with full cache, prefetch and branch prediction subsystems simulated accurately. Also another aspect is running enough repetitions, and not using average, but to use instead minimums (best possible performance, with removal of noises).
Also I think the point of it is to eliminate any layout optimizations and look purely at the code. The randomization is to remove measurement bias, not to improve performance.
I'm not sure what you're looking for. The technical paper describing Stabilizer and the performance analysis we conducted is here: people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf
Generally the higher you go, the larger the size of your program, so an -O3 compiled program can be a good size larger than -O1. While the execution speed very usually increases, you also may need to move a lot more instructions and data around the CPU and to and from RAM, which can get expensive at large program sizes. Going from 1MB at -O1 to 1.5MB at -O3 is no big deal usually, since you can store the entire thing in CPU cache regardless. Going from 100MB to 150MB meanwhile means a significantly more amount of time on waiting on RAM to transfer those extra bytes as well as more cache misses since the CPU has try to juggle and predict what portion of the program should be in cache at any point in time, since it can no longer store it all, and increasing size of the program just makes that prediction even worse. Also you have cases where under -O1 an entire function fits in L1 cache and under -O3 that same function doesn't and part of it is forced into L2, leading to the -O1 being much faster in execution despite using slower instructions.
This is definitely one of the best conference talks I've ever seen!
That guy just explained what the p-value is and how it works in just few seconds - that was an entire lecture at uni. Wow
It's much easier to explain when you don't have to calculate it.
@@abebuckingham8198 Because p values are notoriously difficult to calculate
It's much easier to understand when you already know what it is.
He did didn't he (professional statistician here)
@@davidmark1673 if I didn't already know how to calculate a p-value, I'm not sure I'd be able to just from that (although I'd at least know where to start looking).
(Then again I mostly deal with Bayesian inference and rarely do p-values)
This talk is incredible, great job to everyone involved.
This is an awesome talk, with some great, novel information (at least to me). The name of the program, "Stabilizer" is humorous, as it is actually more of an "unstabilizer". Excellent work Emery. I would love to see a example program that demonstrates significant performance delta between memory layouts.
Stabilizer, because it stabilizes mean results (by "destabilizing" test conditions).
The SQLite example surprises me a little. Indirect calls seems like something I would expect the compiler to optimize already.
Well, not through function pointers as in the SQLite example
Extremely interesting research and a great presentation, thanks!
Wow. He went from theory, background knowledge, to full blown applied uses at a really nice pace. This is a great lecture for any student in software engineering. Love the reminders that certain optimizations can cause slowdown--as well as the reminder that rolling your own naive hash table can have disastrous consequences for performance (37:23)
And on the flip side, the reminder that indirection can be surprisingly expensive.
I've never done anything with programming, but still understood almost everything Emery said. Great video!
That anecdote really summarizes the grad school experience. "As your advisor, the code just runs faster for me."
All code and papers are linked from here: plasma-umass.org.
To install coz on Debian or Ubuntu:
% sudo apt-get install coz-profiler
Papers:
* "Stabilizer: Statistically Sound Performance Evaluation" [ASPLOS 13]
people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf
* "Coz: Finding Code that Counts with Causal Profiling" [SOSP 15 Best Paper, CACM Research Highlight]
sigops.org/s/conferences/sosp/2015/current/2015-Monterey/printable/090-curtsinger.pdf
* Mentioned during talk: "Producing Wrong Data Without Doing Anything Obviously Wrong!" [ASPLOS 09]
Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter Sweeney
users.cs.northwestern.edu/~robby/courses/322-2013-spring/mytkowicz-wrong-data.pdf
Slides are here (Keynote):
emeryberger.github.io/presentations/performance-matters-strangeloop2019.key
Reddit discussion thread: www.reddit.com/r/programming/comments/d4k5x5/performance_matters_by_emery_berger_strange_loop/
This is one of the best talks I have ever seen, full stop
Enlightening talk and amazing results. If only coz existed for every language.
This is the only helpful performance analysis talk I have ever seen. Spectacular work, and thank you for making the tools available. I think it'd be spectacular to integrate the layout randomization and causal profiling directly into the Rust toolchain, and I can't see why not.
Edit: seems somebody has ported or begun porting Coz to Rust, very cool. :- )
Does anyone know what paper he's referring to around 10:35? I can't find it anywhere.
25:05 "You plug this into R with this awesome incantation" hahaha he's the best speaker eer
It has all been written before, but in order to "feed the algorithm" let me just concur, this was to me an extremely interesting and in many ways eye opening talk. And the presentation was absolutely "spot on" for my preferences, clear and and to the point, with the perfect "balance" of overview and details, and then some humor for those of us who like that.
In short(?) interesting, informative, educational and enjoyable.
Best regards
One of the better talks on "Memory Layout" within a given program or application that has a direct effect on Performance. The jokes and puns are great! No more malloc! Run it as me and it's faster... lol! Great content!
As a data scientist I take personal offence to the R slander, but on a serious note this was a great talk and I really enjoyed listening!
This was a bloody amazing speech and great content. Now the coz-profiler just needs to be ported to macOS. If it works on Linux already probably isn't too big a leap.
Excellent presentation. Eventually this stuff will be built into Visual Studio and us casual plebs will be guided into making code that isn't awful.
I really like the causal analysis technique! I might be misunderstanding what "layout" is, but I was confused as to why you would randomize it every .5 seconds. It seems like this could wash out optimizations that are actually valid, e.g. optimizations that reduce the probability of cache misses, because out in the wild layout isn't being randomized all the time. It seems like the fact that you get unexpected distributions when only randomizing once per execution could be indicating that different codes do have different performance characteristics across different layouts, meaning that there are potentially useful code-level optimizations. An extreme example of this could be a data structure that monitors its own timing information and adapts to optimize latency assuming static memory layout, because then randomizing the layout could make that structure look way worse than a more naive approach that doesn't bias itself for any particular layout.
To me it seemed that the point of it is to eliminate any layout optimizations and look purely at the code and then on top of this you can add machine specific or runtime layout optimizations if you need them.
the randomization is to remove measurement bias, not to improve performance. you don't do this in the actual program, just while you try to figure out what other than memory layout ( = how the memory access is organized) influences your performance.
My understanding is that the layout is not randomized, but it's *outside of the developers' control*. So say the layout on your testing machine is just right to get a few small speedups, but you've got one unlucky customer whose layout causes a slowdown once a month or something. By randomizing the layout repeatedly during testing, you can avoid the random advantages and disadvantages and instead get a statistically meaningful test result.
Regarding 0.5 seconds: Isn't this already very long for this kind of test on modern computers?
Using the right kind of algorithm, it's always possible to construct pathological examples that would require running the program for hours before you can compare the times without getting misleading results. But in practically occurring cases, half a second should be plenty, while also being short enough so you can try many iterations.
Also, the program that adaptively changes its memory layout is reminiscent of a halting problem construction. That's more of a sophisticated denial of service attack against the performance test, rather than a genuine problem likely to occur in practice.
but the key here is that you can't tell if it's a code improvement of a layout improvement unless you use the stabilizer to randomize the layout.
If you want to measure whether you did any optimization to the layout after the fact, just compare the non-stabilized layout to the stabilized one. Nothing is lost.
Excellent and engaging presentation with interesting research. Informative and entertaining. If only every conference talk was like this!
Truly amazing talk! Seriously great stuff!
That stabilizer. Instead of randomizing every half second, you could randomize once per test. And then pick the best program.
Super optimizing compiler.
Woah! This is a super awesome talk. Was not expecting as much as I learned.
if only someone would write a language where -03 picks the fastest data structures to use
i actually LOLed when i saw that hash function profile. and then immediately felt sad that nobody near me would get why this is funny 😂
what a brilliant talk - great content, super clarity, funny
Great talk, biased details about biased measurement layout awesome. The best statistics and performance talk. Crystal clear.
how insanely useful... I was thinking about the next steps for optimization. This came in at the right time lol
Very nice! Thanks for the share. I've been through a few pitfalls stated in the presentation.
One thing I'm wondering about: these causal graphs assume that no other variable changes its performance characteristic, right? So wouldn't it be possible that speeding up one bottleneck completely changes the shape of the graphs of all the other ones?
yes completely ! this is why i reevaluate after each changes. it's specially important when you are using threads
Right now, Coz tests the effect of a single change. It would also be possible to test the effects of two changes (or more), though this requires an increasingly large number of samples (testing pairs requires O(n^2) experiments, for example).
Great talk about performance. You illustrate quite well the struggle to optimize a program.
I'm curious about all those real examples in you "Summary of Optimisations" slide.
Do you have references about them ? (like specific thread or patch note ?)
Educational *and* fun! That was great.
I noticed once in a C++ project that changing the order of some of my very slow functions consistently improves their performance by 3%. Seeing that kind of made me want to give up coding
Superb talk.
Very interesting! Great video!
Eye opening, thanks!
One of those rare talks that's actually full with useful insights and lessons.
I'm not against people rolling their own hash thing at home though 😉
Awesome talk, really enjoyed it!
Extremely interesting and well-presented work!
30:00 Gahhhh! So obvious in retrospect. That, sir, is some fine lateral thinking.
Just really brilliant ideas and great execution wow!
Great speaker
Great talk!
nothing beats hardware talks and enjoying christmas
Have a Great Christmas everybody🎅
Wow awesome talk, thanks
Fantastic talk!
So basically what you're saying is "you can't reliably measure performance anymore"
The working diagram of the program makes me think of Program evaluation and review technique/critical path analysis of all things. I wonder if the coz analyser is partly inspired by existing ways to "optimise" projects that utilise PERT/CPA. It's probably closely related, though I'm not proficient in any of those, so I could be way off.
Good talk though! And very interesting.
First class work and presentation, with Prof. Berger's inimitable sense of humor. There are definitely statements made that I need to think about (I don't agree with them 100%, but ... Prof. Berger may well be right and I may well be ... well, "less right"). I think I will "start at the beginning" with: arxiv.org/abs/1608.03676 .
Super interesting!
25:50 whats it all about with the "dash O1 up to dash O11" thing.
I dont actually know what -XX means in the first place.
Yould be glad to learn about from you guys!
You are telling the compiler (the program that translates you quasi human programming into 0 and 1s) to have a deeper look into your code and try to see if it can be made faster by exploiting some of the properties of the processor
Am I right to think that both tools are C/C++ only? How easily can the approaches be applied to other languages, programs and systems?
There is a version of Coz for Java called JCoz.
Does this work for java?
There is now an open-source version of Coz for Java! I hope to integrate the tools going forwards.
github.com/Decave/JCoz
No, but lookup 'JCoz'
pretty neat
A “causal profiler”, huh?… I bet that would be useful as a component to building a system that uses an evolutionary algorithm to create a program, or at least, to optimize a program. Specifically, the part that grades the performance score of a unique specimen of code, to decide whether it survives that generation.
Then you just need a way to get the random code to do the thing you want, and to get it to avoid or fix bugs. Maybe I shouldn't say “just”, in that sentence…
It's not fully independent the execution time at time t depends on some state from time t-1 things like temperature which threads finished first branch prediction etc.
So that means ur assumed normality is problematic because u basically Hand wave those away. I feel like directly testing normality and then doing the rest is best
Did these performance optimizations get implemented in these projects?
What is-o2 or 3
BMP didn't even exist in 1984 !
27:40 wait does that mean the profiler in Unity engine is not good ?
9:40 why is it magic number?
So how muny function get an adress before reach heaps
Yey optimization!
Couldn't you "stabilise" your program during performance testing by disabling the TLB, cache etc on the test hardware?
Yes, but I'd love you to show me a modern system where literally disabling the concept of virtual memory would go over well. Cache would be even harder to disable, as it is likely hardwired into the processor, and might barely be changable by microcode.
No, because algorithms that take better advantage of caches etc. are the most important aspect of software. Thus if you would eliminate caches, you could have algorithms that never get cache hits be as fast as best dynamic programming algorithms that utilize caches optimally.
This was a cool talk but I think it should have included a description of what A prime, O3, O2, and all of these metrics are. They're mentioned but sound nuanced enough that I feel like I don't understand their importance.
O2 and O3 are just C/C++ compiler optimization options (GCC, Clang, MSVC, etc). O0 means no optimizations are performed, which is useful for debugging, and isn't bad in all scenarios, but sometimes has some really wonky performance effects. The higher the O level, from O1 to O3, the more mangled the assembly looks, but the more optimizations are applied. O3 has a reputation for not actually providing any benefit over O2, and this confirms that. Compiler authors didn't have tools like this to actually check if their "optimizations" were anything more than artifacts, and so they ended up being artifacts.
Where 'A' is the label identifying one version of code, 'A prime' is simply a label identifying the later version. This is an idiom carried over from mathematics, but otherwise the labels are arbitrary and are not significant beyond this presentation. '-O3' and '-O2' refer to compiler arguments for optimization levels.
Great talk!
Are there python versions?
What does -09 mean?
The command `gcc main.c` compiles the file main.c into an executable i.e. a program that you can actually run on your computer. If you specify the argument `-O0` to the gcc compiler, then you're telling it to compile your code without performing any optimization whatsoever. "O0" stands for "optimization level 0".
It will compile relatively quickly, however the resulting program will be relatively slow. The command `gcc -O1 main.c` is likely to produce a faster executable. GCC will optimize the code more aggressively with the argument `-O2`, and `-O3` represent the highest level of optimization. `-O9` isn't a thing.
What could be expected is that more the compiler optimizes a code, the faster the resulting executable runs. However that's not always the case.
11:49 what does that mean?
The -Ox flags are optional compiler flags that determines the 'optimization level' of some compilers (notably GCC: www.rapidtables.com/code/linux/gcc/gcc-o.html). Essentially, the higher x is in -Ox, the more tricks your compiler will try to apply to optimize your code.
Ugh. Why mess with janky hash functions when your CPU gives instruction level hardware support for cryptographic hash functions?
14:00 "I guess I'll never malloc again" And everyone laughs as if it is absurd to even suggest never using malloc. It's called MEMORY POOLS! Yes, you can have dynamically allocated memory w/o using malloc. Just manage your own memory. AAA VIDEO GAME ENGINES ALREADY DO THIS, IT IS NOT IMPOSSIBLE TO ACCOMPLISH. Especially if the program you are writing is less complicated than a video game, which I can almost guarantee is the case.
But... You shouldn't use malloc anyway, you should use new and delete. If you're writing complicated software in C and it's not for a good reason, you're just punishing yourself. Also, if you ever find yourself using new and delete, 95% of the time you should re-evaluate your life decisions and use a standard library data structure instead.
You still have to write code to access the memory pool, thus your layout would still change, that's the essence of what it meant
Your tool should rather be called "UN stabilizer", as you randomize everything.
So this is just a memory layout fuzzer..
41:15 soo added inline?
No. The original code used a struct with pointers to functions and the dot operator to call those functions through the struct. The change was to call the functions directly.
No, this is direct call vs indirect call.
It's a great presentation, great lecture, but this is a 1st year of University when doing Computer Science... So normally I'd expect anyone working as a dev to know this.
I want to find your magical school where they teach about layout and cache optimization in the first year. Seriously, I would. All of my courses barely got into optimization and hardware level items. If I didn't watch videos like this, I'd be a much worse developer. I always found it sad and hilarious at the same time that most of my friends never used or bothered to understand even the simplest of data structures in the standard library of languages we were using.
Hey Dr. Berger if you are still replying, in the graphic at 30:48 it looks like the virtual speedup is done by just putting other processes in a timeout where it completely stops for a while. Is this just an artifact of the graphic? It seems like this would mess with the analysis of competition for resources. Maybe I have the wrong idea in my head, but how can you stretch run-time in each piece in a way to make sure that processes that were happening concurrently before a virtual speedup are still happening at the same time?
Oh also your work is awesome. I mean a really novel idea and just so thorough. Wow.
Yes
Concerning O1, O2 optimization, fit in L1 and L2 cache is a big deal. If O1 binary happens to fit in L1/L2 and O2 does not, then the O1 binary could perform better than O2.
The big thing today is that memory round-trip access time is a couple of hundred CPU-cycles. Try to avoid too much pointer-chasing code. Prefetch memory when possible.
Note, Intel Core iX processors up to generation 9 have 256K L2. The Xeon SP lines have 1M L2 at 2 additional cycles access time. 10th gen Core have 512K L2.
Be aware that Intel processors since about mid-2000 had cache line size of 64 bytes. Prior to that, it was 32-bytes.
My view, too many software people have purist view of the world, thinking they can achieve great performance without consideration for the details of the underlying hardware.
I've never known anyone focused on performance who didn't care about the underlying hardware. Timur Doumler even has a talk called "Want fast C++? Know your hardware." Also. Most of the stuff you mentioned forms the basis of things like DoD (Data Oriented Design).
you can only focus on hardware if you control the hardware
@@nyankers precisely. Focusing on hardware is only something you do for compute clusters, where you're running on bare metal, and therefore know exactly what is running where. Otherwise, your cache optimization could just make things worse on a different platform.
Amazing talk!
I'm not even a programmer and enjoyed this presentation. I wish I had teachers like him!
This was an amazing talk! Lots of counterintuitive things to correct in our mental models about performance, thank you for the knowledge! Haha, I loved the "eyeball statistics". Wonderful.
Did you guys try using Coz to enhance the performance of its own code?
Excellent talk. Informative, engaging, clear.
Amazing idea slowing everything down!
But we DO have magic!
1) Have set data to run through the program.
2) Run it through the program, saving the results of each individual process.
3) Run it through the program again, skipping different processes by copying pre-calculated results.
You can even run the process halfway and only then copy the precalculated results. Anything from minor improvement to infinite speed is possible!
The best talk I've ever seen. These tools are incredible and I learned a ton. Great job!
What an excellent talk with an awesome presenter; going to look more into this, kudos!
Is there any interest in automatically tweaking layout to optimize runtime?
Reminds me of Z80 Assembly, you can triple the speed you index an array by aligning the array so that the base address ends in 00. Basically you only needed half the pointer to the array
41:33 a traditional profiler wouldn't have caught those things, how? Shouldn't the operations that make the program slow be the operations that cost a lot of time?
Is it necessary to have the --- in the coz command line? And if it is, is it necessary to name it exclusively with non-alphabetic symbols? It does not seem something I would have in an API if I want to make it intuitive/self-commented/discoverable/usable.
testing the speed of a piece of code by slowing everything else down seems like it would miss interactions between components. It seems like the ferret example required explicit knowledge of interactions in order to discover the optimization.
Think of it as running the application on a slower computer, everything is slower globally. However, since this is done virtually, you can virtually speed one component up independently. Since everything, but your isolated component, is running at the same global speed, relative interactions among those components should be preserved. You only need be able to isolate a specific component.
Great presentation, great material. I've enjoyed watching it a lot, very educational, thanks!
Great presentation and even if I never use there software I’ve an idea how to looking my own performance work and how certain limits work. Thank you.
bottleneck does make programs slower if you have a bad scheduler or workload distributor.
The graphs and analysis at 24:20 are flawed. The problem is that -O2 and -O3 actively optimizes the layout, to improve (static) branch prediction and separation of hot and cold code. By using randomizer you throw these optimizations out of the window, so obviously you are going to loose advantage of using these optimizations. The proper way to test is to keep benchmarks well designed, and run in extremal well controlled environment (keep noise to minimum), preferably in a cycle accurate CPU simulator with full cache, prefetch and branch prediction subsystems simulated accurately. Also another aspect is running enough repetitions, and not using average, but to use instead minimums (best possible performance, with removal of noises).
You can set up what Coz is allowed to randomize.
Also I think the point of it is to eliminate any layout optimizations and look purely at the code. The randomization is to remove measurement bias, not to improve performance.
11:42 that's a bit (read: quite a bit) bigger than I anticipated.
I couldn't find anything about dedup, what is that?
And did SQLite change the code to yours?
Holy cow, this guy is GOOD!
Could someone point me to a good talk or resource where the -O1, -O2 performance cost thing is explained?
I'm not sure what you're looking for. The technical paper describing Stabilizer and the performance analysis we conducted is here: people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf
They appear to be compiler optimization options. clang.llvm.org/docs/CommandGuide/clang.html#code-generation-options
It's referring to a compiler option, I know it from gcc but probably something similar in others.
www.rapidtables.com/code/linux/gcc/gcc-o.html
Generally the higher you go, the larger the size of your program, so an -O3 compiled program can be a good size larger than -O1. While the execution speed very usually increases, you also may need to move a lot more instructions and data around the CPU and to and from RAM, which can get expensive at large program sizes. Going from 1MB at -O1 to 1.5MB at -O3 is no big deal usually, since you can store the entire thing in CPU cache regardless. Going from 100MB to 150MB meanwhile means a significantly more amount of time on waiting on RAM to transfer those extra bytes as well as more cache misses since the CPU has try to juggle and predict what portion of the program should be in cache at any point in time, since it can no longer store it all, and increasing size of the program just makes that prediction even worse.
Also you have cases where under -O1 an entire function fits in L1 cache and under -O3 that same function doesn't and part of it is forced into L2, leading to the -O1 being much faster in execution despite using slower instructions.
Is there a similar tool for Python?