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)
@@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)
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 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.
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!
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 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.
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
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).
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.
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
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 ?)
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
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.
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?
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
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.
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!
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.
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.
19:00 on average A' is faster however the closer they get the more it depends on the random layout wether they are faster. Why dont you just build the app 30 times on the client with randomized layout and see what works the best?
Besides that it would just not be practical, even if it had some impact. Just think about building an application 30 times for a single client in a single deployment... if it takes an hour to compile you have 30 hours of compile time. Your next hotfix is probably less than 30 hours away. Since every change of code could impact performance you would need to redeploy after every change and compile again for 30 hours. The Software would have more down than uptime!
I guess the only "optimization" you could do in that area, is to compile with optimal layout in given directory, for given user etc. and just never touch it. It might be beneficial, but I don't see it getting popular as presented method let's you tackle more important issues.
'-O' is a common option for optimization level in program compilers. The argument '3' indicates optimization level 3. Lower numbers mean the compiler will do fewer or less radical optimizations.
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.
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.
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…
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.
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 .
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.
Sadly both null hypothesis significance testing and the p-value are significantly flawed and the descriptions given in the talk are also wrong. A p-value of 26.4% doesn't mean that 1 in 4 runs will show a random effect. The p-value tells you how probable it is to generate data in some range GIVEN the null hypothesis is true. Yes, you read right. Calculating the p-value already assumes the null hypothesis (no difference) to be true. To conclude from a low resulting probability that the assumed null hypothesis is wrong requires mental gymnastics that frequentists seem to be experts in.
For academic purposes, comparing different algorithmic strategies, this is gold honestly. I'm very happy i found this tool and I'll use it in my master thesis, because just running your implementations x times for graphs is nice but not too sound... Basically i don't really want to spend too much time on the implementation of the algorithm, i just want to make sure that my theoretical conclusions are correct and that they are not *in all cases* nullified by an underlying process of caching or accessing that i haven't considered
This is definitely one of the best conference talks I've ever seen!
I'm not even a programmer and enjoyed this presentation. I wish I had teachers like him!
Extremely interesting research and a great presentation, thanks!
This talk is incredible, great job to everyone involved.
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.
I've never done anything with programming, but still understood almost everything Emery said. Great video!
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.
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)
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.
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
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).
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!
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/
25:05 "You plug this into R with this awesome incantation" hahaha he's the best speaker eer
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.
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.
Excellent talk. Informative, engaging, clear.
That anecdote really summarizes the grad school experience. "As your advisor, the code just runs faster for me."
The best talk I've ever seen. These tools are incredible and I learned a ton. Great job!
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!
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
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.
What an excellent talk with an awesome presenter; going to look more into this, kudos!
Woah! This is a super awesome talk. Was not expecting as much as I learned.
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.
Amazing idea slowing everything down!
Truly amazing talk! Seriously great stuff!
what a brilliant talk - great content, super clarity, funny
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!
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 interesting! Great video!
Superb talk.
Eye opening, thanks!
Very nice! Thanks for the share. I've been through a few pitfalls stated in the presentation.
Did you guys try using Coz to enhance the performance of its own code?
That stabilizer. Instead of randomizing every half second, you could randomize once per test. And then pick the best program.
Super optimizing compiler.
Educational *and* fun! That was great.
Awesome talk, really enjoyed it!
Great presentation, great material. I've enjoyed watching it a lot, very educational, thanks!
Holy cow, this guy is GOOD!
Just really brilliant ideas and great execution wow!
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).
Extremely interesting and well-presented work!
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 😂
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.
Great talk!
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
Great speaker
Wow awesome talk, thanks
Fantastic talk!
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 ?)
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
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.
Great talk! 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.
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?
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
Super interesting!
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.
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 😉
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.
30:00 Gahhhh! So obvious in retrospect. That, sir, is some fine lateral thinking.
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!
27:40 wait does that mean the profiler in Unity engine is not good ?
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'
9:40 why is it magic number?
Too bad the stabilizer project seems to be dead. Anyone knows an updated version for llvm18+?
nothing beats hardware talks and enjoying christmas
Have a Great Christmas everybody🎅
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.
Did these performance optimizations get implemented in these projects?
What is-o2 or 3
I couldn't find anything about dedup, what is that?
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.
19:00 on average A' is faster however the closer they get the more it depends on the random layout wether they are faster.
Why dont you just build the app 30 times on the client with randomized layout and see what works the best?
I explain this in the talk: any tiny change can easily erase those gains -- even running the code in a different directory or with a different user!
Besides that it would just not be practical, even if it had some impact. Just think about building an application 30 times for a single client in a single deployment... if it takes an hour to compile you have 30 hours of compile time. Your next hotfix is probably less than 30 hours away.
Since every change of code could impact performance you would need to redeploy after every change and compile again for 30 hours.
The Software would have more down than uptime!
I guess the only "optimization" you could do in that area, is to compile with optimal layout in given directory, for given user etc. and just never touch it. It might be beneficial, but I don't see it getting popular as presented method let's you tackle more important issues.
pretty neat
Yey optimization!
What is the meaning of the "-O3" in this presentation? Edit: Rather, what is the significance of it, and how does it apply to the development process?
'-O' is a common option for optimization level in program compilers. The argument '3' indicates optimization level 3. Lower numbers mean the compiler will do fewer or less radical optimizations.
@@obviouslynot85 Also -O9 isn't a thing, that part was a joke.
And did SQLite change the code to yours?
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
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.
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.
Is there a similar tool for Python?
Great talk! I saw there is a version targeting Java available so that gives me hope that some day we will have it for dotnet as well.
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…
11:42 that's a bit (read: quite a bit) bigger than I anticipated.
So how muny function get an adress before reach heaps
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.
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.
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 .
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
Great talk!
Are there python versions?
Sadly both null hypothesis significance testing and the p-value are significantly flawed and the descriptions given in the talk are also wrong.
A p-value of 26.4% doesn't mean that 1 in 4 runs will show a random effect. The p-value tells you how probable it is to generate data in some range GIVEN the null hypothesis is true.
Yes, you read right. Calculating the p-value already assumes the null hypothesis (no difference) to be true.
To conclude from a low resulting probability that the assumed null hypothesis is wrong requires mental gymnastics that frequentists seem to be experts in.
It means 1 in 4 runs where the null hypothesis is true will show those random effects.
bottleneck does make programs slower if you have a bad scheduler or workload distributor.
I love the idea of the second tool. Perhaps I underestimate the first.
For academic purposes, comparing different algorithmic strategies, this is gold honestly. I'm very happy i found this tool and I'll use it in my master thesis, because just running your implementations x times for graphs is nice but not too sound...
Basically i don't really want to spend too much time on the implementation of the algorithm, i just want to make sure that my theoretical conclusions are correct and that they are not *in all cases* nullified by an underlying process of caching or accessing that i haven't considered
Ugh. Why mess with janky hash functions when your CPU gives instruction level hardware support for cryptographic hash functions?
So basically what you're saying is "you can't reliably measure performance anymore"