Optimising Code - Computerphile
Vložit
- čas přidán 26. 05. 2024
- You can optimise for speed, power consumption or memory use & tiny changes can have a negligible or huge impact, but what should you optimise and most importantly, when? Dr Steve Bagley has an example!
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharanblog.com
Thank you to Jane Street for their support of this channel. Learn more: www.janestreet.com
It’s always cool to compile two versions of the same algorithm to assembly, and see they’re identical
Hardly the case. Unless we are talking about shuffling the code around, inlining constants, or factoring things out of a loop.
Not hardly the case because by default the compiler will apply all the optimizations by default. Unless you make significant chances, it makes sense
@@KilgoreTroutAsf Yes, a modern compiler can and will do *ALL* of the above.
That is it's job.
@@christopherg2347 Modern compilers truly are mindnumbingly impressive
@@TheArrowedKnee They are written by people a few levels smarter then me with a more understanding of the hardware then I could ever learn.
They are no different than a library as far as tools go.
For others not to waste their 10 minutes of their life:
In 3:58 the text encoded in binary is "OK so this isn't strictly speaking the same text as the stuff on the left. Oh well :) :)"
In 5:17 the text encoded in binary is "Right, are you really converting all this binary back to asci? Well done you! - Sean"
Well done you!
Well done you!
i cant help but notice the binary in the background
@@mellowyellow7523 I also decoded the brighter part of it, but my computer accidentally plugged off before I could save the decoded content.
I have not even noticed the second text, got to "RIGH" on the right and somehow thought I had made a mistake, because it seemed unpronounceable, so I typed it into an online binary translator.
One fun thing in optimization is the work that Kaze Eamanuar is doing on the N64. To make a long story short - he's optimizing for speed BUT one of the biggest bottlenecks for the N64 is RAM access. The CPU doesn't have direct access to the RAM, so when it requests a read from RAM it first goes to a local cache and if that page of memory isn't cached, it has to request the (essentially) GPU to copy the entire page of RAM into the CPU's local cache. This goes for both data and instructions which go to separate caches. What he's found is that one of the best ways to get good performance out of the N64 is to get your code to fit into (and be aligned into) a single page of memory. If you can do that, the CPU will hum away happily at 93MHz (which was a lot for the time!). But if you keep calling functions that are located in different pages, you'll frequently have to stall the CPU to wait for those pages to be moved into cache.
Yeah I love his videos. Discovered him last week and I binged them all. I don't know why but it's so satisfying for me to see how far you can go with efficiency and how much performance you can claq back from code work alone. Absolutely amazing.
Kaze is awesome! Love when he deep dives into optimization strategies.
Pretty sure you and I watched the exact same CZcams video on how N64 graphics work.
yeah...now the same approach is used by data oriented design.
Something very similar was done in the days of the BBC Micro and the iconic game, Elite (published 1984). The 6502 has something called page zero, the first 256 bytes of RAM, which can be accessed very quickly with short instructions. There are also similar benefits to your code if it can fit inside 1 memory page itself. Elite used some incredibly cunning memory access algorithms involving these 2 optimisations which have only relatively recently been properly documented. It is, of course, far from the only 6502 software to use these speed-ups, but it is notable for getting a 3D space flight sim and universe sim into 22kB.
1:36 The quote "premature optimization is the root of all evil" is severely misued nowadays as an excuse to write very slow or just plain bad bad on the first (and often only) pass.
The quote was initially said to discourage developers from inlining assembly inside their C applications before they even had an MVP. But nowadays it's an excuse for developers to write poor, unefficient code that becomes the architecture of application, making meaningful changes require a large refactoring.
If you can write good, fast code from the start without going overboard into inlined assembly, what excuse do you have not to?
Premature pessimization is the root of all evil
Quotes are the root of all evil.
optimizing the proof of concept you've finished and had well documented itsnt premature in the slightest, and lacking any optimization makes people associate you with adobe. I think adobe either missed this part or wanted to be associated with itself.
Eh, it’s still true though. Remember being lectured by my advisor in my job when I spent hours having an O(n^2) algorithm and I wanted to make it O(n), and my advisor said that quote and was like, look, it needs to work first, then we worry about that difference
As someone who has to teach juniors to optimize games, these are the types of optimization that are the least important and is very rare that you actually bother with.
The part he scoffed at also kinda glossed over a very important part, the reason you don't just write it "right from the beginning" is because you don't only do trade offs between speed, memory and battery, you also do it against maintainability, which these kinds of optimization ruin and is the thing you should be optimizing for while writing it the first time around.
Also, by far the most important optimizations are choosing the correct algoritm, data structure and architecture. Those optimizations are almost never premature and can give speed ups of many orders of magnitude compared to the micro optimizations shown that might give 2x at most.
Exactly, he brushes off premature optimization then goes straight to prematurely optimizing memcpy, one of the most optimized routines in the crt. Real world implementations of memcpy do everything he mentioned and much more.
Yeah it makes me twitch when people do the premature optimization quote. Getting the basic memory layout of your data right from the start is important, as it will be hard to adjust that later.
Was looking for a comment like this. To write fast code you need to consider your data from the start not afterwards.
Yeah he didn't even mentioned SIMD, or how to break dependency chain, to give the CPU more room for speculative execution, or how to optimise the cache line usage, by using a DOD design, those are where the bottleneck usually occurs, if you look at what the cpu is doing most of the time in poorly optimised software the CPU is waiting to get data from the cache.
but is a beginner video. kinda need a few hours to delve into to that stuff.
- Optimise fo CPU speed
- Optimise for memory usage
- Optimise for power consumption
- Optimise for maintenability
- Optimise for Developer time
Make your educated choice !
Personally: Wait until you are in testing so you actually see what needs optimisation.
luckily these aren't all mutually exclusive
Glad someone high up in the comments mentioned optimising for dev time, too. Sometimes you're not just trying to make something run a bit more efficiently, you're also trying to finish the next piece of software sooner to bring someone that benefit sooner.
Maintainability first, that actually cuts down on bugs so it rolls into developer time then you can take your pick (or spade or crowbar as preferred).
CPU speed can buy with money
memory size can buy with money
power consumption is not a concern on non-battery device
Now make your choice on:
- Optimise for maintenability
- Optimise for Developer time
A note on the idea of not optimizing until its working. For context, I write embedded C for microcontrollers in time-critical systems that have safety requirements (aerospace and such). With that in mind, the software architecture needs to be designed with some degree of optimization in mind, but that aside, I agree, we not optimize until a functional block is complete. The biggest benefit we have in doing this is readability and maintainability; it is just as important that a piece of code can be understood as it is that it works. I have worked with a lot of legacy code that was written without oversight and focused on hand-coded optimization from the start. The result is code that is hard to follow and is prone to mistakes when it is picked up by another developer.
The most fun part, is when you get into arguments about what "readable" means. 😅
One huge trick John Carmack taught:
If a piece of code is written poorly and you know it. But at the moment the input size is so small that it doesnt matter.
Give it a nice living comment with for example assert.
Example:
You have an array of unsorted numbers and you want to find if 3 numbers add up to zero. The 3-Sum problem.
And your first approach takes O(n^3) instead of the optimal O(n^2) its fine go ahead.
Then put down: assert arr.length
It's also helpful to just make the program first without thinking anything of optimization, because when you have it finished (or w.e part you're working on) changes you make afterwards while trying to optimize, you'll already have the ability to test that immediately, with whatever code you've already written.
yeah that’s exactly what’s said in the video
You say that like he didn't say it six times in the video.
Modern compilers are pretty insane. Writing benchmarks is difficult because compiler may realize what you're doing and optimize your payload away.
That is actually really funny lol. They just optimize too well beyond our human understanding.
@@atomgutan8064 Its still very much understandable by humans, if anyone had that much time to spend. The problem is nearly every CPU is different these days. They have different sets of instructions or extra instructions. They have different timings for the individual instructions. Some have advanced caching and jump prediction. So the problem is it would take a human a vast amount of time to fully understand all the ins and outs of a single CPU - but your software many deploy to many different types of CPUs! The companies who write optimizing compilers hire bunches of people to specialize in such things and embed that knowledge into the compiler these days.
Also remember that since CPUs are so much faster these days (GHz) and there is lots of available memory a compiler can use vastly more resources to find the optimal code than was feasible years ago.
@@atomgutan8064 They are actually very obvious and easy optimizations, which is why it can be a trick to stop them.
Maybe you want to test some algorithm with a fixed input for consistant speed results, but the compiler is like "Hey these inputs are all constant values so the result is never going to change, I'll just substitute the final answer for the entire algorithm and print it to screen."
The solution isn't that complex though, just fetch the inputs at runtime from a separate file or pipe them in from stdin, this way the compiler and optimizer do not know the values and must assume they are truly variable.
The sheer subtile effect of
v = *ptr;
vs
v += *ptr;
in benchmark loops is a good reminder of your need to pay attention.
I am reminded of a story I was told about a Fortran compiler being written in the 1970s for a brand new computer (the DG Eclipse). They spent lots of time working on getting all the optimizations they could in. They had run lots of incremental tests as it was developed, but the first big test was writing a large Fortran program which had all the types of coding it was supposed to optimize and then running that through the full compiler. The problem was the compiler produced a resulting binary that didn't compute anything, until one of the other engineers (the one I heard the story from, _not_ working on the compiler) remarked, "your program as written produces no output, so the optimizer noticed that _none_ of the code was relevant and optimized it all away!"
Remember kids, you are only allowed to quote Knuth if you are going to profile and optimise your code later. If you don't, it's just an excuse for writing sloppy code.
YES! Almost no one profiles and optimizes later anymore. And because of teachings like this very few write decent code that isn't horribly slow with terrible algorithms/data structures. This Knuth quote really needs to die, it was for a long past time when people actually cared about machine instructions and loop unrolling.
"Make it right before you make it fast." (P.J.Plauger)
I was taught this in one of the first classes in my CompSci course back in the 70s.
@@clickrick Because it made sense i the 70s. And because even with that said there was a baseline of reasonable quality (aka "making it right") that was just expected. Newer developers don't have that same quality baseline, they write inefficient, unscalable and unmaintainable garbage and use quotes like this as justification. If professional coders back in the 80s write code that was this poor, they'd be unemployed.
Always optimise for debugging.
Someone is going to have to fix your code at some point - always write the code so it is easier to step through and fix it.
this eally depends on your field of work
nobody is going to look through my code that computes solar magnetic energy - people just import the function and get their number
if they want to know what happens inside they can check the formulae in my article
@@jakeezetciassuming you've implemented your formulas correctly in your code. I might want to inspect the code itself.
True! You want to optimize for readability and maintainability too.
If only compilers had a super-optimiser pipeline to magically take readable & debugable code and turn it into the most optimized code possible in release build mode...
Code is ran more often than it is read, more often that it is written
Optimize for user experience, then for readability, then for yourself
Software can be and most often is magnitudes more complex since 1974 when Knuth wrote that. I would go so far as to say optimization in software means something different now than it did then since we can do a lot of optimization without writing assembly or messing with the hardware. You could make a wise optimization choice before you even start writing by choosing a package or library with no dependencies, for example.
In other words, optimization can't be considered a single step of the process anymore. I can't fathom waiting until I'm close to finishing a project before thinking about efficiency
Where did find "until I'm close to finish"?
Why in blazes are your testing your code that late?
I am disappointed that he didn't even mention the memory alignment problem. At best, off alignment access is a significant performance hit. At worst, it fails. I don't know if any current computers have the limitation, but I have worked on computers that require all access to be aligned to the data size.
He'd better told the people to just call memcpy.
Quite a number of really good comments here calling out how this video covers all the wrong things and is off base. Glad to see so many people understand that and are willing to speak up.
Very interesting video, Can't wait for the next one!
Nice. Although he missed a few points.
Copying 4 at a time is good, but it also introduces potential alignment issues. Some processors can only access larger chunks of data at natural alignments. And for many that can handle unaligned accesses, the unaligned access is slower.
Another thing missed. The basic copy loop was like
while(i < n) {
*p++ = *q++;
i++;
}
That increment of i is mostly wasted effort. By that, it's just to keep track of how many bytes have been copied. Additionally, comparing the pointers directly is pretty easy. So how about.
limit = p + n;
while(p < limit) {
*p++ = *q++
}
Now we've eliminated the increment of i and instead are simply using the unavoidable increment of the pointers themselves to handle the loop. So with his ARM example, we now have 3 opcodes per byte instead of the 5. Of course, the optimizations illustrated in the video can also be used as well.
Just watching the video, I can see two obvious (but mutually incompatible) optimisations (in terms of number of instructions per loop) before trying loop unrolling:
- rather than counting up until R2 matches R3, copy R3 into R2 before the loop (if you want to preserve the original byte count for some reason) and use a single decrement-and-compare-to-0 instruction rather than the separate increment and comparison instructions.
- rather than having a separate loop counter at all, calculate what the final value for one of the pointers should be and compare that pointer with that value.
Steve Bagley is one of the most underrated people on the Internet.
Not based on this video. This is completely wrong, focuses on extremely outdated things and would be useless in a real world development situation.
it's funny how we go back to paper on Computerphile videos lol; always cool to learn these concepts Dr. Steve's way.
There was a missed opportunity here. Based on the example, I was expecting you to circle back to the point about making your code correct before optimising it. This code fails for a certain case of overlap between src and dst; it has the potential to overwrite your data before you've had a chance to move it.
That's what memmove is for ;)
Thanks for the great critical questions by the cameraman
I am usually concerned with optimizing for reliability, maintainability, and testability. Performance means little when code is fragile, because running code is generally faster than crashed code. Walking that line between writing compact (performance and resource optimized) code and clear code is an art form in itself.
I agree with you.
Broken code has either a time complexity of infinity (it doesn't run or never finishes) or memory complexity that is effectively infinity. Not optimised code is always less in both dimensions.
I think everyone in the comment section has to remember: this video is meant as a general introduction and understanding of the necessary rules and purpose of code optimization, NOT code optimization for C (using GCC, gdb, and ASSEMBLY)
These notes are meant to apply to code optimization for, say, Rust, golang, python etc etc, so while memcpy might make optimization via manual control easier - Python, Rust does not have memcpy
This uses manual approaches to fully understand the flow, not the tools
I had a job once that I described as being the final optimization pass of the compiler. In the mid-70s a friend of mine (Rodger Doxsey, bio on wikipedia) was one of the PIs for an X-Ray astronomy satellite (SAS-3). Once every 90 minutes they got a large downlink of data from the observations in that orbit and had to analyze it quickly to decide if they wanted to change the orders for the next orbit. The problem was the analysis was all done by Fortran code written by astrophysicists, and the data was all packed in 4, 5 and 6 bit fields in larger data words. So, as the first real Computer person to look at the code, the first optimization was to just know how bit arithmetic worked and improve the Fortran in the inner loop a bunch (and, IIRC that halved the time it took for the program to run). But then I looked at the generated assembly code and realized that by better use of the machine code bit shift/mask features, it could be improved much more (IIRC, a factor of 5 this time). They were very grateful for the extra time that gave them to think about what the data actually meant.
speaking on unrolling, one of my favorite C "techniques" for doing so has got so be Duff's device, which makes clever use of some C language features to implement loop unrolling at runtime, similarly to as shown in the video
its not loop unrolling that duffs device gives you, its a jump table that duffs device gives you
It's barely readable and obfuscating. Just use memcpy which will do that anyway. memcpy does not copy 1 byte at a time if it can get away with it. If memcpy does not do that (check the assembly output) you can write a much more readable version using inline assembly anyway.
@@styleisaweaponTechnically it's a simple jump table that takes care of N mod 8 iterations on data before N div 8 iterations on the rest of the data.
Nowadays, it's reversed when you let the compiler optimize the loop using SIMD instructions.
🤮
while I agree that its "barely readable" saying "Just use memcpy" tells us you only think duffs device is for memory copying which is such a gross ignorance that maybe, just maybe... hush@@kierengracie6883
My favourite topic. I love beautiful and aesthetic stuff, and efficient. Sometimes beauty and magic don't go well together, sometimes it does (there are people like people who work with standard libraries that say, generally the simpler the solution, the better it is). Then you see matrix multiplication optimization.
Sean's question about isn't it better to design it well at first is great in my opinion to draw out the difference of good design vs optimization. Because at times optimization is definitely not "good design" in terms of let's say readability. And the implementation details shouldn't really be part of the design talk I don't think. For the general idea etc yes, but the optimizations come up from seeing what the actual code is like. Like Sean Parent's classic "that's a rotate" speech in GoingNative2013.
I think the good way to explain compiler and optimizing is that the compiler can only optimize it as much as you allow it to: if you keep a layer of mystery to everything in the code, the compiler can't deduce what is behind the curtains and has to consider the worst case possible. If you write it smarter, the compiler can just look at the code and see "oh you declared that const, that constexpr, you made loops or avoided loops where I can just write them off and skip calculations, just saving the answer" etc. I.e. if you give compiler enough information about your code (don't go declaring types where you should allow the compiler to deduce them), it can do magic tricks that you couldn't even imagine trying to do clever bit manipulation tricks. The compiler WILL outsmart you if you give it an opportunity. But for example deciding which type of pointer you give, which kind of virtual functions you make, how you pass your pointers or pass by value/reference, that will improve things manually. And using vectors and STL algorithms. Remove loops and branches. Remove unnecessary copies and allocations. And don't lock the compiler forced to do something unnecessary by being very explicit. Don't make an int pointer to be smart because the pointer takes more resources. Of course these apply more to C++ than C, they're obviously different beasts.
Matt Godbolt has a fantastic demonstrations with his Compiler Explorer about how you shouldn't try to outsmart the compiler, but work with it. Jason Turner's Commodore 64 game in C++17 is also an impressive demonstration of 0 overhead abstractions and compiler magic. Bjarne Stroustrup also had that article about linked lists vs vectors and how despite a lot of all kinds of testing, and despite being a very unintuitive result, vectors came on top almost always. And switch magic...
I feel like a game Human Resource Machine" gives a great introduction to programs and optimization.
Your video is complementary to the game itself.
Power is usually solved by also solving for performance. The less cycles something takes the less power it uses. The less time it runs the less power it draws over time. After that it is more efficient to configure the hardware to run at a lower power level than try and make the code use less power. If you need to use one core vs 64 cores during some low power situation then you could use code for that. However, if you need 1 core out of 64 all the time it is best just to adjust the hardware to that need.
Performant code tends to also solve other issues. Performant code is usually smaller less lines. Less lines means less chances for bugs. Also makes it easier to maintain and use in the future because there is less to understand for someone new. Less lines also usually translated to less machine instructions in most cases. This means it tends to make fitting in memory easier.
Granted your compiler flags can also make this change but if it is smaller to start with it will also end up smaller in most cases with the compiler flags set to whatever.
The ARM has the ability to read multiple words into and out of memory/registers which could also be used to improve cycles per byte of a copy routine.
I think another point at 2:05 from your question asked is that who knows the “way” to build something. It’s hard to build something the right way at the start because you are trying to write your mental abstractions of your program ideas into actual code
One other optimization that you could do before loop unrolling, is getting rid of the counter (i in the pseudocode). Have one line before the loop calculate the address of the last byte to copy (src address plus i). Then in the loop you don't have to do i++, just compare the src pointer to the calculated last byte to copy. If the source pointer address is equal to the last byte to copy, exit the loop. For the copying four bytes at a time version, that would make it one byte per instruction.
I've arrived at the same conclusion by experience. While coding multiple migration scripts, that must be ready to use as soon as possible. Soon enough I realized that first, I had to make the code work and do the job, and then later do the optimisation. At least you know where you could optimise. Otherwise you will not being optimal and will loose precious time.
Other types : complexity, understandability, portability(cross platform)
Testing.
Sometimes the debug libraries _contain_ errors , thus causing problems determining optimizing and validating.
Bugs errors and slow downs can also be encapsulated(built-in) in the compiled versions of libraries as well.
Do you need to optimize? CPUs our general way to compute things. What if you don't need a computer at all what if you could just look up the results. Generate a table once look it up after that. What if there's a shortcut computation? There's a shortcut computation is probably also a shortcut lookup. If you need to have more precise results that's the time to make more precise lookup tables
How important is it to be optimizing the first place. Are you doing trillions of operations and you need it in a fraction of a second well yes. If you're doing one operation every year well who cares
@@Wyld1onefor some problems tables are a great optimization. For others the table would require a memory device larger than the observable Universe. I have worked with both cases.
@13:52: The computer scientist and the mathematician square off. The mathematician answers "you've got a problem with odd numbers", recognizing that anything indivisible by 4 is indivisible by 2, twice. The computer scientist replies "you've got a problem with odd numbers or numbers that are not a multiple of 4", missing that their added comment was included in the original criterium. It's a great reminder to me (computer engineer) to try taking time to process what the other person said before replying.
"Optimization" - optimization for readability and understandability should be first goal.
The best thing to optimize for is readability and maintainability. I've seen people write "optimal" code before, which was ~20% faster than baseline, but at cost of maintainability. These days, for most applications, maintainability is key.
Also, regarding "the right algorithm": Caching is so often overlocked. Trading off memory usage for execution time can be extremely valuable, especially if the computation is expensive or requires IO.
Hard disagree
@@elpapichulo4046 Would you mind stating why?
At an enterprise level there's another optimization layer which is the human element; maintenance, reusability, and extensibility. There are times in our projects we often forego true computational optimization for readability or ease of use of a certain API. I think from a business standpoint that usually comes first (fortunately or unfortunately) because it affects the amount of resources required to solve a problem, especially given the higher order languages that already either have some optimizations built into the compiler/translation layer or, on the other end, are so abstracted away that computational optimization isn't possible. Not to say this isn't still thought about, we consider O(n) daily even if we don't directly solve for it, it's just either second nature or not worth the additional engineering time.
Optimizing those human items is often not in direct conflict with performance optimization. There is no need to make a poorly commented confused intertwined mess when making a better list of instructions; that tends to be a sign of someone that really doesn't know what is going on just throughing things at the wall to see what sticks. At the other end general overly verbose codebase bloat usually hurts all types of optimization, human and machine.
Absolutely
"When I was working on Visual Studio Tools For Office we did comparatively little making the customization framework code _run_ faster because our tests showed that it typically ran fast enough to satisfy customers. But we did an enormous amount of work making the framework code _load_ faster, because our research showed that Office power users were highly irritated by noticable-by-humans delays when loading customized documents for the first time. "
"Which is faster?", Eric Lippert, "Part the fifth: What is this “faster” you speak of?"
@@christopherg2347 Which in essence IS optimization for loading. We have made similar decisions in iOS development to actively avoid dynamic linking because it bloats application launch times. There's newer functionality that allows for dynamic linking during debug builds and then merges those libraries into a single (or multiple depending on how configured) binary which makes release builds take longer but launch times much faster.
But again that's a different kind of optimization, sometimes we'll write code and abstract away several layers of an operation to make it more testable. Does this make it run slower in production? Possibly? At a scale above a few nanoseconds? Probably not, so we don't even think to optimize for runtime performance in that instance, we optimize "for stability" instead by ensuring test coverage is there. That ultimately saves support time, saves our maintenance time, and would hopefully save consumers' time by working the first time. Even 30 seconds having to relaunch an app from a crash is more time (and bits) burned than a slightly less optimal but unstable piece of code.
My first Software Engineering lecturer (30 years ago) taught me this motto "Make it work, Make it better"
Your definition of optimal reminds me of the definition for recursion in the Devil's DP Dictionary. Recursion: noun, see Recursion.
When we wrote code for USAF in the mid-90s, each of us were assigned, beyond our workstations, the least powerful computer in use at the base.
Everything needed to run properly on that lowly PC; "It runs on my PC" would get you chastised severely.
I learned to write tiny code; now I can write verbose code, and the compiler does the hard work.
memcpy will most likely beat any hand-written attempt you write since it has already been highly optimised for the platform you compile it to.
You would have been better explaining other optimisation methods like caching recent results, using loookup tables, avoiding branches if possible, utilising the cache, etc. Also stuff like don't calculate the length of a vector if you can can use the length squared, etc.
It's probably more as an example in the video, but there are a few times when memcpy is better handwritten, namely when it's a known-to-be-small byte count and the compiler still calls libc (since that call takes some time, especially if there's a cache miss)
Yeah not calling sqrt when just comparing lengths of 2 vectors probably saves a lot of time when you have to do collisions.
@@kwzucompilers inline functions like memcpy with optimizations on specifically to avoid that. Small sizes or remainder sizes presumably are optimized out when inlining as well...
@atomgutan8064 square root is a unary operation that takes one clock cycle. It's literally as expensive as integer addition. The only penalty is the extra clock cycle each for loading and retrieving from the x87 FPU. You should probably learn square root algorithms before talking ignorantly about how expensive they are, when they aren't.
@@gregorymorse8423 It's even faster when you don't use sqrt though... fastest code is no code.
You can compare lengths of 2 vectors by comparing the magnitude squared.
When it comes to collision you should probably partition your space so you don't compare every object to every other one as well.
The sight gags are always appreciated.
As a programmer who usually codes in assembly... gosh compilers are really stupid sometimes. A lot of the time you have to write the code in C using weird builtins like \_\_builtin_ctz or SIMD stuff, and it'll be as good as in assembly, but those are the kinds of optimisations compilers do miss. And in the case of older or embedded architectures, you can really save a _lot_ because these architectures are hard to optimise for.
But it makes sense that compilers aren't perfect btw. We're at the point where adding more optimisations to compilers will noticeably slow down compilation times. It's a tradeoff.
I can highly recommend the Article "Which is faster?" by Eric Lippert.
After a giant like Knuth, he is one of the biggest authorities on the matters of programming.
i'm not that impressed by Eric Lippert honestly. it's probably his bad takes on the StackOverflow website, that gave me a bad impression
Great content, thank you!
About the bit of using the compiler to optimize your code.
Most times it's not a matter of badly compiled code but a bad approach to the problem.
Say a function needs the first million prime numbers... You wouldn't calculate the first million prime numbers on each function call.
You would store a table of the first known million prime numbers somewhere so they can be looked up as they are needed. I.E, not CalculatePrime(N) but rather FetchPrime(N)
No compiler i've heard of can figure this optimization out for you. It can only make the CalculatePrime() function run faster. It can't re-design your program to fetch a prime from a table.
The best example of optimization i can recall is that of the game Factorio. Their code was optimized but it wasn't enough. They had to consider where the resources they accessed lived in the memory, was it in slow RAM or fast CACHE memory? And they re-designed their code such that as much as possible was living as close to the CPU core as possible as they needed it.
Apparently, no amount of compiler optimization could do this for them even though modern processors are supposedly good at organizing what can live in cache vs RAM. They changed it so when something existed in cache, they did everything they needed to that memory in one batch and only then would discard parts of that close to CPU data that they knew they wouldn't be needing for a while. Especially as it came to path finding and fluid network calculations.
97% means it does not apply in 3% of the times.
Plenty of other games had no such issues.
bro is using a literal notepad as a texteditor, absolute chad
The main optimisation is, in my opinion, the readability. Comments are free at run time when the compiler has removed them. Comments are prceless at 4am when things have gone pearshaped.
Actually comments may avoid that 4am phone call altogether by forcing you to actually think what you are doing when writing the program.
you should always check the pointer location before copying memory....i know that's not part of the video explanation, but it's necessary to know which direction to copy the data. For example, if you have an array of 1000 bytes and you are copying from position 2-1000 into 0-998, left to right will work.....but say you are expanding the array and copying the data from 2-998 to 4-1000, well then you have a problem because you from position 6-1000 will have a corrupt data of position 2-3 repeated nonstop. In this way, if the write position is higher in memory than the read position, you have to add the count to both positions and subtract with each loop, working backwards.
Two other optimisation targets you might consider:
1. Optimise for stability - particularly in programs operating in real-time environments like transaction processing or process control… avoiding technologies that can lead to memory leaks etc.
2. Optimise for maintainability - for long lived code that may be maintained by a separate team the ability to perform thing’s simply and correctly, without any tricks or nooks and crannies will be more valuable in the long term.
Those aren't optimizations.
In the second assembly program, shouldn't add instruction have #4 at the end?
Begin a life long Z80 coder, these techniques are quite familiar. I don't know if using the stack pointer is feasible for fast data transfer on a modern CPU?
these are more optimizations that a compiler can do behind the scenes. most application programmers are concerned with picking the optimal algorithm. no compiler (afaik) is going to optimize which type of sort is best for the data you have.
17:25 for any one wondering, its str r5, [r0] instead of [r1].
The quote from Knuth also applies to databases: over-normalization.
Would you be able to make a video explaining what virtual cores are please?
This saying, not optimising too early, was said at a time where programs were mostly small algorithms implemented in C. It doesn't apply to a bigger system, especially with asynchronous and latent operations, where you really have to think about optimisation early enough to not create an unoptimisable mess. For instance if you use OO you'll never get the performance you can get with a data driven approach.
I love seeing people call this out. I've been saying this for a decade and for a long time no one else seemed to be saying such things.
Regarding OO, everything has its place. OO is really excellent at dealing with complex inter-twined data that needs to adhere to certain rules. Trying to do such things without OO can be a nightmare. But if you're dealing with vast quantities of simple data OO can add a lot of overhead just from allocating, deallocating and fragging your memory. Right tool for the job.
One optimisation strategy I use for my backend-heavy Django website is to make it fit into a Raspberry Pi 3! This way, I am forced to optimise it for speed as well as memory (the Pi has under 1GB or usable RAM).
that's a pretty cool strategy. i've been interested in doing the same with my applications. i think there is a lot of deep stuff to be learned that way, depending on how far you go
And what remains when you take out optimizing from programming?
The never ending process of decoding business requirements and translating them to code.
I consider myself lucky if optimizing is part of the business requirements, because I found it an enjoyable puzzle, but sadly that's a rare opportunity.
Good. Always make it part of the business requirements, factor it into your estimates. The more you spend thinking about how to write good, optimal code the better you'll get at coding and the less time such things will take you later. Its a skill and if you exercise that skill you'll be a better coder than most others.
Seeing that old printer paper brought back some memories.
Solving the right problem is my professional mantra because a good solution to the wrong problem is a waste of them.
That said, Z80 assembly tweaking is a hobby when coding for the ZX Spectrum.
An experienced assembly programmer would never count upwards, but always downwards. It saves you the comparison instruction, because decrement always includes a test against a zero result. It's not even counterintuitive - just do not call the variable n, but numBytesStillToCopy, or so. However, modern optimizers can detect and eliminate superfluous upward counters.
@8:25 that program has a flaw when they source and destination overlap partially. It will overwrite the bytes it is going to copy later.
Thank you!
ARM assembly is so nice.
I’d have thought that divide by 4, where 4 is a constant, that the compiler would optimise that to a shift operation for us?
For most modern CPUs it's less likely to be needing ASM optimization, lacking cache utilization is the biggest bottleneck in most cases.
Until we have like 512MB+ L3 caches on consumer CPUs, which on the other hand isn't too far into the future, at least for desktops! =P
When we finally get 512Mb caches, bad programmers will already have figure out a way to use an extra 2Gb of memory for a simple quicksort
That might unfortunately be the case, yeah... @@KilgoreTroutAsf
@@KilgoreTroutAsf Which is avoided by using a existing implementation, instead of prematurely optimizing a custom one.
Premature optimizing is definitely what I struggled with the most at first in software development.
You were learning. Nothing wrong with that.
'Premature optimisation. They say it happens to 4 out of 5 programmers 😉"
@@christopherg2347 Yeah it happens to roughly 5 out of 4 programmers. Hold on, it seems I swapped a couple of variables somewhere, dang it this code is completely unreadable!
@@Takyodor2 "The two hardest problems in programming are: Cache invalidations, naming things and off-by-one errors."
@@christopherg2347 🤣 I love that one!
Do not worry, the editor guy, I read the covers👏🏻
Always write readable/maintainable code first. If performance is an issue, profile and optimize.
Also sad there was no mention of CPU magic like branch prediction/speculative execution, instruction pipelining, cache effects, etc.
Optimizing for "lower number of instructions" may sound reasonable but is hardly the right metric on modern hardware.
1. Make it work. 2. Make it work right. 3. Make it work fast.
It may not optimize this code unless you say restrict, due to potential aliasing.
Nowadays, rather than getting on the CPU instruction level, much bigger speed benefits are generally by optimizing memory layout of the data structures used. And that can be done on a higher level than CPU instructions. What good is to save 4 instructions taking a few clock cycles, when you have a cache miss and wait for hundreds of cycles on a simple read from the main memory... Not optimizing for CPU cache usage / hits (several levels) and prefetch is the biggest blind spot of videos like this one IMHO.
And on ARM(and some other archs like RISCV as well) you can want to write your loop to count down to zero instead of counting up to the loop count. As they would have decrement and skip if zero flag instruction which would be faster than load value from reg, compare two register and make decision about branch. RISCV even has an r0 reg dedicated to storing 0 value. But again does all these fancy optimization make a real difference if you do it in places which are not hot spots in your code? Probably not.
Sometimes you're optimising for development time rather than code performance
Does the data still have to be aligned to loads/store 4 bytes at a time? Back in the day, that was also a limitation of doing it 4 at a time
No, but it's faster if it is. There are operations for aligned and unaligned data. The aligned one will almost always be more efficient and take less time
thanks alot
you're welcome
My best tip is to make it readable. You don't need the code to be efficient, but if you can tell where anything is you can fix it when necessary.
What happens if you move four bytes at a time 1000 bytes from address 59049 to 65536?
Profiling before optimization saves a lot of time because then you know which parts are slow and need to be faster
The fact, that you write a program in C, C++ etc., is in itself an optimization. But it's not a premature optimization. So the hard part here is discerning a premature from a non-premature optimization. Maybe for this, there aren't hard rules, but you wouldn't write a sofware renderer in python, when you write a game engine, and later optimize it to OpenGL/Vulkan and C++.
You can also optimize for readability and testability.
Usually when you optimize for speed you are also optimizing for power usage. Race to sleep.
2:06 Much what Cliff Harris says on Positech Games when he was optimising his game.
The memcpy function has been aggressively optimised for decades. These days, it won't even run in userspace, but do all the work in the kernel;. With modern architectures it can be written to use DMA, and quite possibly to not do any copying at all, via the MMU. In general, as long as you haven't made a completely boneheaded algorithm choice, the compiler's optimisations will be better than yours.
Sean, of course we can read the book titles 🙂
1) write readable code
2) make sure it works
3) if possible optimize it
Only if needed and only after profiling it.
I would say "3) Optimize only actual issues revealed during testing"
I like how what you call “pseudo code” is actually just compilable c code.
2:20 He is right, it's better to make the program modifiable. If you just make it work but the code is a bloody mess, you are going to have to re-write a lot of code when you finally get around to trying to optimize it. Meaning you not only develop the same program TWICE, but now you also have to replicate how the program you've written horribly works in the new optimized version minus the slowdowns or resources expenses.
Premature optimization might the the root of all evil, but badly written code is like trying to find a way to divide by zero.
EDIT: I personally tend to do "budget programming" and by that (a term i just made up myself) i mean that every feature of my program has a budget. It can take 10 ms to execute, but not more than that or i will most definitely have a frame drop on my target hardware at 60 FPS since it will coincide with everything else that eats another 6.666 ms.
Or this feature must not use more than 100 mb of RAM, since the rest of the program only uses 100 mb of RAM in total. I don't want runaway memory usage this early on because re-factoring later to use less just means i've wasted my time developing the first example and have to redo everything anyways.
I've never concerned myself with power usage because i am not developing for phones or laptops or server farms etc.
It's all speed and memory usage and in some cases, network latency/bandwidth.
I plan ahead of time what my goals for performance are and if a newly added feature misses those goals, i optimize them right away. As developing on top of those unoptimized features will just mean i have to change/refactor more code later on anyways to meet the goals.
It's as if i include execution time and resource usage into my unit tests.
The quote "premature optimisation is the root of all evil" is the root of all evil. The quote is outdated and lacks important context from the original passage, and is used by people to excuse writing bad code. It is far better to practice doing it correctly the first time than it is to adopt the attitude of "good enough, we'll fix it in post". Looking at the software industry, there's hardly a pandemic of optimisation going on. Efficient code is an exception not the rule, and that holds the world back in many ways.
Can you do an episode on distillation as it applies to neural nets? I’d really appreciate that. TY!
As a pythonista, I simply MUST stress, that "readability matters". Optimising for readability is a thing (not necessarily the same as PEP 8).
The mindset of "Oh its just a 0.1 secs and it only gets run once" is why we have to wait dozens of seconds (yes thats a lot computers are FAST) for programs to start
Optimising code for speed IS optimising for power. Software that executes a task faster allows the processor to sleep for longer and that reduces power.
I like to optimize code for readability
You know I once cut a whole documentary using ffmpeg?
Sean was wise. Premature optimisation is evil. But so is unoptimisable architecture. Fundamental structure matters a lot
Optimising `memcpy`! Traditionally you don't want to ever do that, but I actually wrote a fast 32-bit ARM `memcpy` for the GBA that uses 12 registers for a whopping 48 bytes copied per iteration when in ideal conditions
Each iteration is just 4 instructions:
```arm
.Lloop_48:
subs r2, r2, #48
ldmiage r1!, {r3-r14}
stmiage r0!, {r3-r14}
bgt .Lloop_48
```
I had to set the CPU mode to FIQ to free up the stack and link registers for an extra 8 bytes to copy per iteration
I agree with him, but if I can do a lookup from a hashmap rather than doing some goofy nested loop then I'll write that optimization rather than do it the slow way first.