BigO = Performance! And other lies programmers tell themselves!!
Vložit
- čas přidán 19. 05. 2024
- Have you ever analyzed your algorithm and found out that it runs in O(n^2) and thought to yourself, "man I'm a crappy programmer...". Well, you are! But not for the reasons you think! If you think Big Oh = performance, boy have I got news for you. In this video I try to dispel this fallacy that programmers have assumed, that Big Oh complexity equates to performance.
My Benchmarks: gist.github.com/ambrosiogabe/...
Yea, there's probably issues with the way I timed this and stuff. I don't really care. It's simply to illustrate a point, which is this is all utterly worthless and I wasted my time to try to illustrate that Big Oh complexity means absolutely nothing in terms of profiling your code.
--- Music ---
Note: I would provide links to these songs,
however CZcams Studio doesn't provide an
easy way to find these links
Accordian: By Andrew Huang
Tis the Season: By Nate Blaze
Web Weaver's Dance: By Asher Fulero
And...
Hall of the Mountain King by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
Join the Discord: / discord
Follow me on Twitch: / gameswthgabe
---------------------------------------------------------------------
Website: ambrosiogabe.github.io/
Github: github.com/ambrosiogabe
Here are some books I recommend if you want to learn about game engine development more thoroughly. I do not profit off any of these sales, these are just some books that have helped me out :)
My Recommended Game Engine Books:
Game Engine Architecture: www.gameenginebook.com/
Game Physics Cookbook (Read this before the next physics book): www.amazon.com/Game-Physics-C...
Game Physics (Ian Millington): www.amazon.com/Game-Physics-E...
Game Programming Patterns (Free): gameprogrammingpatterns.com/
My Recommended Beginning Game Programming Books:
JavaScript Game Design: www.apress.com/gp/book/978143...
My Recommended Java Books:
Data Structures/Algorithms: www.amazon.com/Data-Structure...
LWJGL (Free, but I haven't read this thoroughly): lwjglgamedev.gitbooks.io/3d-g...
I think a part something a lot of people also miss in the big O notation ist that it just describes the growth rate and not where it starts. O(1) could mean the algorithm will take 10 seconds while O(n) could mean it will take 0.1*n seconds. Clearly for n>100 the first algorithm will be faster but everything
Not just where it starts, it also hides a constant factor. O(999*n) is the same as O(n). So you can't compare algorithms like at 2:40, the O(n) line could be much steeper
@@WilcoVerhoef Constant factor describes where it starts really. You both are talking about the same thing.
@@doktoracula7017 I think you're right, but the constant factor (b) does not describe "where it starts", a constant term (a) does.
O(a + b × f(n))
@@WilcoVerhoef depends on the function. For exponentials for example a constant factor does determine where it starts, 10e^x starts at 10 because e^0 is one.
But I definitely agree in general.
This is why some of the most optimised code contains multiple algorithms for the same thing - it starts by checking how large the input is, and then chooses which algorithm to use accordingly.
"Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy." - Rob Pike
I generally agree with your point, but I'm also glad that people brought up what they did. As someone who frequently contributes performance patches to MC mods, it's quite common to see mods that tank FPS because they didn't consider someone would use their mod in a mod pack that automates it and scales the process x1000.
Thanks for the input Final Spartan! I'm trying to learn to be more receptive to this type of feedback, because you're 100% correct. I could only gain performance from implementing something like this, and it's definitely good to hear about use cases that could cause my original implementation to blow up :)
@@GamesWithGabe what a short and sweet completely valid and complete discussion
This is a completely valid point. What happens if your code gets reused in a way you didn't intend?
Crafting in the GUI those few microseconds are indeed completely fine, but scale that up to thousands of automated crafting tables that use your code to craft items every tick. Now your code that "runs in a few microseconds" is the reason that the TPS is tanking in someone's factory.
Assume that you're in the 3%, and optimize from there. Slow your CPU down to the lowest clock it can go to simulate a potato PC. There will be users who will bring your code into its limits, and they will thank you for doing so.
@@benedani9580 You can't assume all of your code will be used like this. Perhaps the person modding the game to make it part of the 3% should be the one to add the optimization?
@@muschgathloosia5875 That is fair - and this is why (well maintained) open source software is simply superior. No work needed on the original developer's end, besides accepting a pull request.
The worst part is when developers try to optimize code in high level languages, but it just leads to the compiler not being able to self optimize the code. I've seen it
those are fun moments, some knowledge is required to know which types of optimizations makes sense. there's a lot you can do in terms of optimizing code in high level languages properly also
This is also correct. For a very small piece of code that needs speed, i can just change programming language instead of wasting time optimizing every single lines / block of code hoping it works faster.
Which is why you should know low level language and it makes me annoyed that most languages try to cut ties with lower level. I want to be able to dive right down to assembly if need is big enough
@@jakubrogacz6829 it is extremely unlikely you will NEED to dive down to assembly, and all you would be doing is making the worst, most terrible to maintain codebase imaginable.
@@NihongoWakannai not really true, unless you don't count SIMD intrinsics as assembly. using those is one of the best optimizations you can do (instant 4x or more speedup in a loop), if you can figure out how to use them
I mean, the best optimization is to make the code run less, not run faster.
As if your code did the crafting recipe check every single frame, with the "slow" algorithm, it would be horrendous and THEN using a faster method with hashtable or similar would maybe prove useful.
But there is no need to check the crafting recipe if it hasn't changed, so the best optimization is to only do the check whenever the player adds/removes an item from the crafting menu. (which is what I assume you're currently doing) So yeah, no need to optimize that at all, unless like you said you end up with a 6.5 GB file of crafting recipes, but then you have a different issue than the algorithm being a bottleneck. (due to ram, diskspeed and search times)
Like most people only look at the time complexitiy of an algorithm or piece of code when optimizing, instead of looking at how often it's running.
Yup. If there were 6.5Gb of recipes, just caching a few would definitely help more than working to improve the algorithm.
running it each frame wouldn't matter when there's only 300 recipies
caching is where the bugs are though
@Михайло Шевченко That's why you reuse the implementations of smarter people. Also this is only true if you need to do cache invalidation afaik.
The algorithm may end up being used in unpredictable ways.
Perhaps crafting is automated in the future, or multiplayer support us added or whatever and for whatever reason instead of one recipe being checked you got houndreds or thousands.
Perhaps a mod adds factory crafting or whatever...
Or perhaps it turns out that the code may be reusable in something completely different, might not even be this game.
If this is coded well the first time around it won't need work later and can more easily be reused.
I remember watching the crafting section and thinking "well that isn't efficient" but then realised any solution would only make it faster by a matter of nanoseconds at which point it doesnt matter anymore. Sure, people will say "BUT ITS STILL FASTER" - yes, and?
@@poetryflynn3712 You are thinking in extremes... Not everything is about optimization and certainly a lot of thing need to be optimized. Please don't get carried away by this way of thinking or you will go nuts
@@poetryflynn3712 I think the point is, programming, as any other art forms as you said, doesn't have the purpose of its own. The task gives it a purpose. Music doesn't have purpose being grand and giving feeling of excitement, BUT main theme of Star Wars does have that exact purpose. Video games as of themselves don't have purpose of giving criminal experience with guns in city environment, BUT Grand Theft Auto does. Programming doesn't have purpose of using system vulnerabilities for stealing private data from the servers, but hacker programs do.
Art is tool for expressing your ideas in some medium and have any purpose you give it.
Embeded systems?
@@poetryflynn3712 as a software consultant, I need to be efficient with my time as well.
Would you as a client pay $100 for me to optimize the crafting table to save a few microseconds? No, absolutely not.
@@capsey_ I agree with you
Feels like this guy (that you're replying to)
has gone down the unfortunate path of nihilism :(
Another thing Big O never really considers is actual hardware limitations/implementations. While theoretically more operations takes longer, you could have an algorithm that is O(N log N) still execute faster than something that's O(log N) because of cache-locality and various tricks CPUs use for properly lain-out memory structures.
This isn't really a problem with big O notation but with the model we implicitly use (at least most of the time) to estimate running times: RAM or random-access machine. RAM simply isn't a good model for modern CPUs for the reasons you mentioned. There are more realistic models, which for example measure the number of cache misses (in big O), but these aren't as widely used.
Thats kind of the purpose of Big O notation. Time is thought of as a pure software construct rather than a physical one
Could you come up with a real example of such an occurrence?
Man, I've had one case where I spent 2 days optimizing an algorithm to bring it from O(n^2) to O(nlog(n)), only to find that the new algorithm always ran a bit slower in practice, even for giant datasets. On paper the new algorithm was faster, but it had to shuffle a lot of data around in order to minimize the number of steps, which turned out to be so stupidly memory bandwidth intensive that it could never even outpace the simple brute force algorithm.
Basically, big O does not tell the whole story, and may not account for how much work the system as a whole needs to perform. As an extreme example, you could make a search algorithm run in O(1), by making it check every possible indexable value, every single time, regardless of the size of the dataset, and not returning the result until it has gone through its entire dance. Now you have an algorithm which ALWAYS takes 2 hours to run on your system. It's O(1), and absolutely awful!
@@fnorgen If the new algorithm had to shuffle data around, it almost for sure wasn’t truly lower order big O.
A proper big O evaluation takes into consideration CPU/cache cycles, but just program loops.
I completely agree. And i have to admit, i have a tendency to try to write the most optimised code possible right from the start and this causes me to lose interest or makes it hard to debug like u mentioned
optimizing is good. premature optimizing is bad
@@pvic6959 except if it's the 3%
@@whannabi even in the 3% there is usually no need for premature optimization
@@whannabi You never really know where the 3% is until you profile your code, at which point it's not premature anymore.
You are acting like you have to implement your own version of everything from scratch all the time. In many cases, using the correct algorithm is often even easier than using a "simple" algorithm. For example, to do his way, you have to write a loop, then write a comparison function, and then check at the end if the recipe was found. If you are using c++, just store the data using std::map. Your efficiency goes from O(n) to O(log(n)), and it will handle the searching and comparing for you. All you have to do is reference the element and then check to see if it was found.
Thank you now i cant get bullied by coding elitists telling me my algorithm can be slightly faster
@@greyshopleskin2315 use open bsd
@@whannabiuse gentoo
@@Mindroix use
@@greyshopleskin2315 use lfs
Oh no, you absolutely can. Nothing can stop an internet user with a need to feel superior
I was waiting for the constant to be mentioned throughout the video! Because even if an algorithm has good O(n) complexity it easily can have so big constant, that usually it will work slower than the algorithm with worse O(n) complexity
Yes the constant is also an important consideration! I overlooked it in this case since it wasn't very relevant in the performance of the two algorithms :)
A "good O(n)" algorithm is one with a small constant though
@@GamesWithGabe I'm going to expand on this and say there are a few constants to pick from. Don't forget there is also the fact that these algorithms aren't strictly O(n), O(n!), etc. They tend to have a much more complicated functions. something that is O(n!) may actually be 2n! + 3n^2 + 2n +4 whereas another algorithm may be O(n), but actually be (2^1000!)*n + 3000!. So, for almost any appreciable n, the O(n!) will be faster.
@@GamesWithGabe You missed the opportunity of saying “constants are important factors” :p
That's how you get galactic algorithms :)
I just love the music going on. It's chaos and its amazing
Also remember that if you maintain clean interfaces in your code, it will make it easy to replace slow code with fast code if and when it's necessary to do so.
You forgot to mention that Big-O notation only shows changes, and not absolute values. An algorithm may be O(1), meaning it is constant, but the constant speed is 50 seconds, while another algorithm is O(n!), but for small numbers, it runs under 1 second.
Exactly. O(1) does not necessarily mean that it will be faster than O(N).
@@JamshadAhmad yeah, like most newbies miss the "hash" part of hashmap, which means you need to actually HASH value, which is not most fast thing to do.
A few things I'd like to add:
* Performance per operation is more complicated than just "one operation per cycle". Modern CPUs can often perform multiple operations on the same cycle, but a lot of them take multiple cycles to complete. Some operations, like addition, typically take only one cycle to execute, whereas division often takes about 10 to 20 cycles to execute, and a cache-missing memory read typically takes about 100 cycles to execute. You also have to factor in the number of CPU cores, as well as the fact that you're probably going to share that CPU with a bunch of other applications.
* In addition to the above, it's also worth considering that the CPU will briefly enter a power-saving mode when there's no more work to do. If your app is running fast enough for a good user experience but you can still improve overall performance by 10%, then that 10% might save a bit of laptop battery and/or save a notable amount of energy when thousands of users are running that same software.
* Performance and maintainability can often go hand-in-hand, as the key to both often stems from understanding the problem's nature, and when they don't align, a bit of decoupling is usually enough to avoid compromise. To use your crafting recipes as an example, I'd probably still use a hash table simply because I like the interface, even if the added performance is insignificant in cases like this. When I'm using, say, a few thousand look-ups per frame, that added performance becomes a nice bonus.
* Even though I disagree with the point about "CPUs being more than fast enough" (If they were, that would just mean that the user is wasting their money), I still think the point about non-critical paths is important. It really makes no sense to optimize something that only occasionally needs a few microseconds from a single core. Better to spend that time optimizing the chicken's AI so you can make that 53.694-population chicken farm run smoothly.
I agree, but with a caveat to the last point. If optimizing something takes only a couple minutes to implement, then why not implement it? If the optimization is low-hanging fruit, you don't waste anything from grabbing it. You aren't going to waste any of that chicken farm optimization development time by implementing a trivial swap from a list-based lookup to a hash-based lookup.
It's a cost-vs-benefit exercise. As long as the cost is lower than the benefit, then it's generally a worthwhile effort, especially if it's an as-you-go type of optimization.
@@Abion47 That's definitely true, too. If you've already got hash maps, using them will probably not take that much more time than implementing a linear scan.
@@Abion47 I would add to your comment that there exists 2 optimisation parts
The ones that are simple optimisations (look up tables for crafting for example), those require usually small modifications
The ones that are heavy optimisations (SIMD, compilation programming...) which can destroy maintenability while still being easy to implement
The first one are low hanging fruits, the second ones can be pure poison outside of critical path
@@Abion47 I think similar to what you mean, you should always try to write the best code you can, so no lazy programming, but you shouldn’t then optimise unless you need to.
Agree with both the general sentiment of the video and the specific case. However I would argue that your case is actually just good use of Big Oh. O(n) should be obviously acceptable for this use case, but it's easy to imagine how if your recipe algorithm was somehow O(n!) say, then you'd have a terrible spike each time you'd craft. In my opinion Big Oh should be always thought about but never obsessed over (except for in such critical sections). It's all too easy to take your argument too far, leading to terrible performance (especially in terms of potential performance). The middle path is, as always, the way.
Yep, I definitely agree. I showed O(n!) just to illustrate that as long as your dataset is < 3 elements, then even O(n!) doesn't matter. Basically just pay attention to your requirements, and as you said, the middle path is usually the best way :)
lmao i was literally thinking of yandere sim dev and how this is probably how he rationalizes the 100-check if-else statements to direct game logic. when you continuously use logic like this in a game, performance will definitely take a hit. like....
@@Patrick-pu5di Yeah, if you have one isolated situation where performance is not very good, and you don't reach it very often, fine. But if there's one poorly optimized thing everywhere, those small inefficiencies will add up and potentially cause an awful experience.
Absolutely. Also be mindful about "hidden" O(n)s that can turn an otherwise O(n) algorithm into an O(n^2). There is an example from GTA Online which had horrible load times of up to 6 minutes, because otherwise innocuous function called strlen() inside it for every few characters parsed. What should have been a linear scan turned into an O(n^2) scan. This can happen if you don't pay attention to your datastructures for example. (If your algorithm does deletions in an array, for instance. Or has to find elements in a list. Those operations inside your O(n) algorithm loop will turn your loop into an O(n^2)...)
If your dataset is small enough, it won't matter, but you need to accurately understand your complexity class to make the judgement call on it. In a non-hot loop a linear O(n) algorithm will usually be fine to millions of elements. An O(n^2) algorithm will be fine to thousands - tens of thousands of elements (because this turns into millions - hundreds of millions of operations). In a hot loop you might have to forgo the O(n^2) algorithm if you can, unless your dataset is very small. But again, you need to know that your algorithm is O(n^2) instead of O(n) to make a reasoned decision on it.
Absolutely. While I agreed with just about everything he said, his obsessing about how fast computers are kind of grated. Yes, modern hardware is bonkers, but developers still manage to bog down my computer on a regular basis. Even with modern hardware, code speed does matter.
That's definitely something I've learned. The most important things to optimise are things that run many times per second, not the things that happen on comparatively rare user interactions.
Earlier this year I implemented a priority queue (well, a multithreaded task excecutor) that literally sorts the entire list whenever an item is added. At first I thought "this is gonna terrible", but in the end it actually ran pretty well, to my amazement.
Well, until I had tens of thousands of elements being added to it, then it became a bit of an issue.
What was your solution
@@chuffrey445 I still don't have one lol
I'm rewriting the whole project and haven't gotten to that part yet.
Binary inserts are a mans best friend
@@bluesillybeard could just use a standard binary heap, or you could also just keep the list sorted the entire time and use a binary search to find where a new element should be inserted, that way you go from O(n * log (n)) to O(n) insertion time
@@sayaks12 The reason I resorted the list each time is because the order of the elements would constantly change. The elements order doesn't change that quickly, and since it's entirely fine for them to be processed in a slightly wrong order I'll use something like a binary tree and sort everything by their initial value.
Big-O being more theoretical than always being a good reflection of true performance is one of the things that should be pointed out to you the first time you study about Big-O.
I think people need to fully understand what Big-O actually is, it is evaluating the performance from a mathematical perspective, almost completely removed from hardware.
I had a discussion with some people about achieving O(1) by running the algorithm on an FPGA, they couldn’t get past the fact that it would be limited by hardware and you can’t get infinite sized FPGAs, I bring up the fact that it is similar with CPUs, you can’t get infinite RAM or storage and apparently that isn’t the same thing. So they dismiss FPGAs because you can’t get infinite sized FPGAs but then hardware doesn’t matter when talking about CPUs somehow. Essentially according to them, hardware and what is realistically possible to implement matters when talking about FPGAs or similar systems but hardware doesn’t matter in the slightest when talking about the same algorithm run on a CPU.
I don’t know why they think that way but I think it probably stems from misunderstanding and lack of thinking.
Absolutely brilliant video! When I was a junior developer I suffered with premature optimization trap. This video perfectly finishes my whole journey of effort to finally not doing that (although I still try to optimize things to be "fast enough" when building them)
Bro really made an entire video to prove a point. Respect, and keep doing what you're doing, I love your videos.
I partially agree. Skipping easy optimizations like this is fine while isolated, but compound this system many times for a game application and you'd be leaving ms on the table you didn't need to. Every game hits a critical performance moment where devs need to reiterate the codebase and juice out a few more frames. If a little focus on performance is kept while prototyping the refactoring can focus on critical slow downs with a little more breathing room in terms of performance. In the long run, in my experience, this cuts down on refactoring and shaves off weeks if not months of development.
But this isn't the only case for streamlining development. Getting the team on the same page in terms of architecture, 'code smell' to an extent, and documentation wears the crown.
Juicing out a few more frames, yes absolutely worth the effort put into it. Optimizing a codepath that runs very very rarely on a very small dataset, not really necessary
This is a great comment, I completely agree
@@voxelrifts the issues arise when your use case of it running rarely becomes a "near every frame" case.
It's not unusual for Minecraft mods for example, to add hundreds of recipes, and fine, brute force with no impact sure, but what about when the "meta" in mods is to automate everything? Then you can easily find yourself in a situation where that once every minute or more execution becomes once every second, once every few frames, or worst case, many times per frame.
In this case, the video holds true for sure, and if there's no intention to open up for Minecraft levels of modding, then yeah, it's a pointless optimisation.
Lots of people here are claiming "elitism" in the comments featured in this video (disclaimer, I'm one such example). Those comments aren't all made by elitist snobs or pedants, but may very well be made by those who were, as in my case, asking about the optimisation from a more "what if," viewpoint. Why not optimise this system, as it's the kind of system that gets heavily modified and utilised in other, often unforseen areas in other similar titles (ie. automation mods). Never was it intended to be a criticism or snobbery.
@@MechanicalMooCow what you said is absolutely correct. If I came across as overly arrogant I apologize. I did not think the original comment was "elitist" at all, in fact quite the contrary. As for "why not to optimize the system", get something done and get it done as fast as possible is a viable strategy. Especially if going slower doesn't really benefit you much
@@voxelrifts no we're good, I'm just saying there's a few general comments talking shit about people that bring up optimisation 😋 ultimately though yeah, in my projects, personal and professional hardening is something done after sprints. No point optimising a project that is stuck in development hell facing constant refactoring. It's a far better, and profitable route to get a system in place and then optimise when absolutely required. That obviously doesn't hold true for all systems, and what does and doesn't get properly designed before creating the system is a skill only the more experienced software architects develop with decades of practice and exposure to the best and worst code bases
This video is amazing, I love how you explain everything with great examples. It's very informative and funny, keep it up!
I had a great time balancing this lately, for a render queue sort of system I was building. I had it so that a given renderer instance would collect calls to render and batch all the vertices/indices from the calls into one object to minimise draw calls. At the start, I set up a basic queue system, with pointers to each node. This was (obviously) because the time complexity for adding new calls would just be O(1) as adding to the end of a queue is a simple operation, as opposed to a vector/array where its O(n) to reallocated and copy each element. However, when I started adding more calls I ran into VERY large frame drops for 5000+ objects, likely due to the strain of having to heap allocate 5000 nodes every frame. So, what I did to solve my issue was make it so each node in the queue contains a preallocated array that can fit up to 96 calls, and so is contiguous in memory. (I picked this number by graphing in excel for increasing array sizes per node).
So I balanced the time complexity of being able to slot calls next in the queue, with the fact that for small amounts of reallocations an array takes less time to add to and read from, which is dependant on modern computers being fast. This one optimisation of the data structure sped the code up by 17 times.
When writing new code, priorities should be:
1. Correctness
2. Expressiveness
3. Performance
Only when you achieve the first 2, would you start working on the third. That being said, in the author's example I feel using a hash_map would have been the more expressive and idiomatic choice while maintaining the correctness and improving the performance. So I would have chosen that data-structure for the job nonetheless. Best to keep in mind that while using hash_maps gives you O(1) search, it will be slower to create than a plain vector and have less cache locality, so if one needs to for example iterate over the items, then a vector would probably be a better solution.
Yes, and it would still not matter.
Performance is very much contextual. There will be situations where it matters a lot -- to the point where it trumps expressiveness or even, in a sense, correctness (e.g., various approximations and simplifications that physics engines use that are "good enough" in terms of accuracy but are very fast and scalable).
But in a great many cases, performance really isn't a factor you need to worry about at all, and thus would not even be on a list of priorities.
@@nathansmith9597 I'd define correctness a bit differently. What you are talking about is precision, which indeed is often sacrificed for performance for good reason. But the program is still working correctly and as intended. A program not being correct means it doesn't work as intended and that is always the first concern no matter the context.
You are correct about expressiveness often trading places with performance though. Sometimes it can't be avoided (I sometimes write Assembly or use compiler intrinsics, which is not very expressive). Still even in these domains we can strive to follow best practices and try to use idiomatic conventions to make our code more expressive.
@@juliuskoskela452 That's fair, correctness in the sense of not having bugs is definitely top priority.
I guess the only point I would want to make is that I think your first two priorities are different from the third in a meaningful way.
Avoiding bugs and being as clear as possible to human readers are, in my view, "abstractly good" qualities of code, meaning you should always strive for them when writing code. (I mean, we could come up with contrived and silly examples where they don't matter, but practically speaking you always want your code to have those qualities.)
Performance, on the other hand, is worth consideration, but whether it is actually an objective is very contextual. And even when it is an objective, you probably want to gather benchmarks and figure out some threshold you want to clear based on the situation, rather than just having a "more performant === better" mindset.
At the same time I do think this video might bend the stick too far in an "anti-performant" direction?
I think the famous maxim attributed to Knuth, "premature optimization is evil," is not the same as saying "optimization (usually) doesn't matter."
The key word, which is easy to underappreciate, is *premature.*
If you're coding something that you know will be time critical, isn't it a waste of time to implement a slow algorithm first that's correct and expressive, only to change it for a faster algorithm?
While working on my unreal project I have tended to err on the side of caution, trying to avoid conditional statements, trying to squeeze out bits of performance wherever possible. When the time came to benchmark and find bottlenecks I found out that the game would run at around 500 fps if it was up to the cpu. My optimizing obviously didn't hurt, but aside from a handful of critical and frequently run functions I could have spent that time better. Especially when I had to go back and add those conditional statements to a sizeable chunk of the functions again to avoid rare crashes.
At one point I had to make my level generation algorithm considerably slower, and was concerned about it. When I asked a friend to playtest they told me honestly that they didn't notice that starting a level took any time at all. Even a noticeable lag might not be anything to worry about if it is associated with a button press and a discrete change of game state, as the player subconsciously skips over that transition in the first place.
Although it is insignificant at the end of the day, it is good practice to think of a better way to solve a problem. Not because it is useful in the particular case you're working on, but because with enough practice, optimized code automatically becomes your default code. It's a good habit to learn.
I agree!
When you start out as inexperienced programmer then optimization might seem like a huge effort whose outcomes are usually not worth the additional development cost.
But once it has become a habit, the cost of writing optimized code drastically decreases to the point where it doesn't make much of a difference anymore.
And it also becomes easier to read optimized code when you have used a similar optimization trick yourself dozens of times before.
Of course optimization is not only about Big-O, since simpler algorithms are often faster for small datasets that those optimized for O.
It's also about getting a feeling for how expensive certain operations are and being able to estimate how how large a data structure would get or often a part of code is likely being called (possibly use caching so it's called less often).
And then there are also advanced topics like CPU cache locality and memory management in general.
You should have mentioned that many faster algorithms are significantly worse in memory usage. In your 6.5G example, a hashmap approach that maps words to their locations would use an amount a tremendous amount of memory that I think for most programs would be unacceptably high.
Would it really matter? If you have 6.5G different information then your information a lone takes a tone of memory, also there are a lot of hash algorithms that don't consume a lot of memory
@@Void-pb2sj yes it matters, not (only) for memory consumption but rather for memory access. You can have a blazing fast algorithm and still get poor performance if it needs a lot of data scattered across your hardware.
@@Void-pb2sj Great question. The reality is that there may very well be a clever way to not use too much extra memory on this example, but I believe you'd have to at least exceed 6.5G of memory usage during construction of the map. There may be a clever way to construct the map by reordering elements perhaps... But now it's not so simple as "just use a hashmap", is it? :)
The general truth remains though: many algorithms must make a trade-off between speed and space. One of the most classic examples used everywhere in computer science is cache size.
I should add that YSC beat me to mentioning something else that can be very important: memory access. Contiguous memory layouts and access patterns can sometimes be better than theoretically faster algorithms purely because they can e.g. live in the CPU cache or not need to spill to disk, etc.
I think the moral of the story is that generally, you can't just rely on making your asymptotic runtime faster. As programmers, we must balance a wide variety of things when considering performance and getting work done.
casey muratori has an awesome series on optimization (search for: Refterm Lecture Part 1 - Philosophies of Optimization).
he makes an interesting distinction between optimization (profiling, counting cycles, etc) and non-pessimization (not doing obviously slow things) - watch the vid for a better description.
in your case I'd agree that going with the linear search is a very good solution: on top of the points you've made, i'd add the value of simplicity. if you're going to use a hashmap, you have to define a hash function - that's more code you have to maintain (eg: if you change the way recipes work).
if we're talking hot path (every frame) though, i'd be more careful with throwing away "a few microseconds". they add up more quickly than you'd think. and once you have lots of code that's slow, there's nothing obvious left to "optimize". everything is slow - death by a thousand cuts. this is where the principle of non-pessimization comes in. but of course there's trade offs. going with the simple solution first is almost always the best way to start.
and finally: don't forget that memory is slow. yes, the cpu can do billions of operations per second, but only if it has the data it needs. random reads from memory can have latencies of around 50-200ns - that's only 10s of millions of operations per second! yes, there's caches and pre-fetching and whatever, but there's also cache pollution. and that's why i'd say do the simple thing first. there are too many factors that influence performance. and we haven't even talked about compiler optimization.
I absolutely agree with your points and appreciate your insight leddoo! +1 on Casey's refterm lectures too, I wish he would do more videos like those haha.
I do always try to think of how my code is being used in context as well, im not sure where that falls into in Casey's rules for optimization. Like you said, if I have a piece of code in a critical path that's being hit every frame, I absolutely consider using a smarter algorithm. For example, in that same video I talk about using buffers for the multiplayer data. I store that data in a sorted fixed size array and use a binary search for the insertion and lookup since it's being hit every frame, potentially multiple times a frame.
I think everything is a tradeoff, and that's one of the main things I try to highlight with my videos. It's never as simple as it seems unfortunately.
But once again, great response and thanks for taking the time to give some input :)
First of all, good message in the video :)
There are some things I want to mention:
- BigO is the worst case run time, not best case, not average - worst case, so its never telling you anything about "performance" in the common sense, because that would be average
- People who dont study it correctly might be thinking that BigO solves everything, but like you kinda said in the video, you need to THINK before you apply any concepts - would you for example use a poor algorithm in your rendering or for any large scale operation that happens each game loop cycle - that would be impactful - a simple crafting recipe matching cant even be measured.
- You might have a calculation mistake though with the atomic operation, the algorithm, the iteration, the lookup cannot be counted as 1 or 2 atomic operations, therefore the comparison in the video might be a lil off
- Side note: implementing hashing might even reduce performance for smaller datasets, since it adds complexity first ;)
Summarizing, if the dataset is big AND its used very very frequently, you should think of using BigO to think about improving performance - any other time, its just not worth your time :D
PS: what I think is funny: O(n) is usually considered a good and average fast algorithm xD
I appreciate the great insight as always Juyas! I definitely did do some hand waving with the cycles and atomic operations haha. It's always more complicated then it seems :)
And I thought O(n) was pretty good too lol. I mean sure I can reduce it to O(1), but I figured it really didn't matter that much because it wasn't being hit frequently. I've already rewritten it so many times for the benchmarks though that I may as well use the faster version now XD
@@GamesWithGabe talking about efficiency, spending this much time with it and even making a video about might not be efficient as well xD
But I like your videos, so I don't mind xD
"The dataset will always be small and computers these days are fast anyway" - is exactly what gets us poorly performing software these days. Some optimizations are an unnecessary overkill for sure, but is implementing a hash table really that much harder?
Exactly.
I really liked your calm way to explain your side, I'll probably watch now 80% of your content regularly.
nice video. but it's important to note, cycle in CPU is not always the same as atomic operations, for example division or reminder can take few cycles depending on input and CPU architecture. Better measure for this is FLOPS
I was one of the ones suggesting the change. (But I said "It could be better" :) ) Sorry, but I've been dealing with developers all my 40 years and you will be surprised how few will understand that in this case, the optimization was superfluous..... They will grab to the "early optimization is the root of all evil" like mad while using the reduced data set we provide in QA envs, just to blow out on production with the full thing.
So not all people are this clever, so in this simple cases, I tend to ask for the highest.
This case was not "exceptional", for me the hash table is not an optimization, is just the best data structure for the task at hand. And is not that much hard to implement as an iterator (I think hash implementation may even be simpler).
Hey no worries! I was hesitating about including any of the comments in this video because I know a lot of them were in good faith like yours! There were a few rotten ones that got under my skin and I made this video because of that.
Using a hash map isn't that big of a deal, but I was analyzing this algorithm in context, which is its only run when a user adds or removes something to the crafting table. It's definitely not in a hot path, and honestly it's easier for me to code the linear search then to implement the proper hashing algorithm and comparison operator in C++. I think this is more of a fault with C++ because it makes me as a developer more inclined to just use an array since it's so much simpler than trying to get a dumb hash map set up properly haha.
@@GamesWithGabe hey, you included me too, but don't apologise. These comments we make are all public, and just like any decision you publicly share about your project opens up to criticism or query, every comment we make is also fair game. Appreciate the leaving out names and being respectful. It's one of the reasons I keep coming back to this channel and enjoy what you do. You're a far better engineer than me, and my original comment wasn't intended as critique, more a genuine question, so I apologise if it got under your skin. On the plus side, your video is a perfect response and correct for most cases for sure.
I've been programming for near 20 years now, and have constantly fallen into these kind of traps, and preoptimisation is a big one. Videos like this are useful to everyone, beginner and professional alike.
Thank you.
@@MechanicalMooCow thank you for the understanding! It's always very humbling to expose most of my code and thinking in videos like those devlogs. I tend to get defensive, but I'm trying to also learn to accept criticism :). You definitely didn't get under my skin (I was kind of thinking of one comment in particular about that haha), and I do appreciate and value valid criticism like this. I'm trying to learn to be more receptive, and learn from the countless other developers that have other experiences and wisdom that they can share with me :D
Hash table consumes memory, this can lead to worse performance in some systems, I think is in fact a matter of "what-you-want" rather than just "the right tool for the job" in this case too
Now its my time.
Especially on modern Hardware, there are factors with much more impact than a "slow" algorithm.
Cash locality is often way more important than big Oh notation for performance
@@Me__Myself__and__I oh jeah, in some circumstances you can gain double the performance bei doubling your memory usage 👀
Something that sound strange, but it's all due to better cache line usage.
Totally agree. It's crazy how many algorithms are in the class of "basically instant runtime" on a GHz processor. I've come across such an example recently, an algorithm that voxelizes a triangle mesh, at resolutions of several billion voxels. My first implementation of the naive ray-cast check-odd-number-of-intersections algorithm took >1h on the GPU, scaling O(N^5). With optimizations (bounding box, use GPU L1$), I got the same algorithm down to 15min. And then I changed the algorithm itself, to be only O(N^4). Suddenly, runtime was only milliseconds. This transition from minutes to basically instantly is mind-blowing every time.
I think something that some people might not think about to much when they want to optimise is the complexity of refactoring code. They would rather spend a lot of time to optimise algorithmic complexity, which would really only give them minor improvements.
Of course, if you have time and you see an optimization you know you could easily implement (as long as it actually matters for the runtime of the code in a meaningful way), sure go for it.
I'd put big asterisks on that.
Optimizations for clarity should take priority. If you can make something a bit better without sacrificing clarity - fine. But opaqueness is how you get unmaintainable messes - and programming is about trade-offs - not hard rules - and I put clarity of intent above almost everything.
And the bigger the code the base - the more you should optimize for clarity. Can a juinor dev read your code and understand what is going on? Unless it's mission critical ( Physics, AI, etc ) , clarity matters alot. Especially in UI code. That turns into spagetti very quickly. UI is large numbers of sparsely accessed methods that need to communicate with each other only rarely, and also needs to change the game state in a way that is often quite dramatic. It must be extremely reliable, because wonky UI is extremely annoying. And it must be extremely readable - lest you or other developers spend valuable hours debugging wacky race conditions.
I have a lot of programming experience in C, C++, and Assembly. And I agree with you! You are right in a lot of situations! So, the reason I personally recommended a change to your crafting system is because I have developed about 7 games and 3 game engines, and it’s usually something like that which can cause a surprising issue later on. Tech debt grows incredibly fast, and you need to make sure you take the time to remove those issues if they are simple to remove, even if you are an individual programmer. Sure, you only have about a 6 ms deficit, but what about once you reach the need for variations of an item? What happens if you have other small ms long optimization losses? What if these issues add up over time and eventually cause issues that become more extreme due to other circumstances? How would if hurt netcode? I understand why you might be frustrated by the huge number of responses, but it’s a principle to follow because you need to make absolutely sure that you take care of even the smaller tech debt elements, so that these unexpected issues do not appear later and cause you much more pain than you intended.
This issue is a huge reason why a lot of major AAA games suffer massive performance hits and need such complex systems to run. It’s a combination of disregard for small programming optimization practices and intense graphical requirements. They add up over time and you need to make sure as a rule and a practice that you keep things optimized, even if you have to rewrite things AFTER you got them working.
Just my thoughts. Glad you did the tests but it sadly does not change my opinion of the issue. Love your content a ton either way, and it doesn’t make you a bad programmer imo it just makes my programming ocd activate hahaha.
While all your criticisms are perfectly valid for something that runs every frame, the crafting system Gabe showed doesn't. And it's quite simple to switch from a linear brute force to a hash table but it would only be necessary if you see a performance hiccup
I totally agree with both you and voxelrifts! At this point I've rewritten this algorithm several times over so I may as well change it lmao.
But to your point, I do continuously rewrite my systems as the requirements change. For example, my chunk rendering started out as a single threaded, allocate memory on demand type of system. I was accidentally allocating 32GB of RAM because my vertices were so bloated, so I reduced it to around 1GB of RAM for the same amount of vertices. Then chunks would lag the game every time they started to load/unload, so I created a multithreaded system to handle the creation of chunks. This fixed the lags, but introduced a new problem with random stalls when I would have to transfer a bunch of data to the GPU. So I revised the algorithm to take advantage of OpenGLs persistent mapping to allow me to allocate a fixed size amount of VRAM and split it up into buckets to allow me to avoid fragmentation and any new GPU allocations. I determined a bucket size based on the real number of vertices that I was using on average for my chunks at the time.
Basically, I do revise my algorithms as I work on them and the requirements change. The crafting wasn't a problem at this time, so I didn't feel the need to change it haha :)
And I do appreciate the ocd coding. I also feel the same way watching other programmers on YT and at work 😅
@@GamesWithGabe yeah that absolutely makes sense! I just am explaining my reasoning, and all. I totally get why you would not do it in some places and would in others, I just tend to do it in unneeded places at times. Great work though!!
I think this is a bit of a skewed view of things, AAA studios need to worry MUCH MORE about problems with readability and code maintenance, because they are dealing with hundreds, sometimes thousands of people on projects, if you've ever worked in a group with 5 people know how complex it is to manage integrity (at least initially) and maintain standards, enforcing readable coding is almost always better for software, even if it costs more in terms of performance. There are other problems with this, such as the centralized structure of an enterprise, and other priorities besides final optimizations, which cause this loss of performance, but programmers already do a great job of optimizing using features such as uncompressed assets and other subtle techniques, these monumental AAA works would simply be unrealizable if we were only focusing on performance. For an indie dev, this is even more crucial, that he develop the features he needs and not focus on over-optimizing his product rather than actually creating something useful.
You sorta have a point, but the thing is I think you create more technical debt by optimizing everything than only optimizing things based on profiling. Most of the time optimizing code is going to make it less readable especially if you need to resort to something like making calls in assembly. In this particular example it's a bit silly since you're not really writing the algorithm yourself you're just going to call from the std library, and you can easily just swap out the exact algorithm being used with another variant if profiling shows that issue has become a critical section/too slow. If it costs us extra time to make a more optimal solution (eg: 3 days of inventing a new algorithm) or it makes the code harder to understand or read and we haven't profiled the first initial solution yet, we're wasting our time and effort and creating more technical debt. The best solution of course is to stick to an optimal route if it doesn't make it more complicated (eg: a hash isn't more complicated - especially if you're just using a std library one and implementing it takes about as long as a for loop). If someone has to go back and try to understand your code 6 months later and you've made it difficult or obtuse to understand you've just caused a lot of technical debt as the other programmer now has to understand your madness and waste time on it (and they may just end up deciding to erase that section and start from scratch since it's just simpler and easier than trying to understand your madness).
So in conclusion optimize only if at least one of the following is true 1) there's no extra effort 2) it makes your code more readable/easier to understand 3) you measured and profiled the performance and proved that what you're currently doing isn't fast enough to meet the needs of the project.
Now I understand what Big o is lol
Well, the point is that, just because a computer is fast enough to run the worst sorting algorithm possible in less than a second doesn't means that it is okay to let it do that all the time, because the great majority of systens are concurrent, so we're playing against OS, I/O and even gpu time slices. So no, it is not nice to let the CPU strugle just because it has enough horse power for that single isolated task
Great video. There is a lot of hype around big O. As someone with a PhD in CS I can tell you that I only learnt how useless some "optimal algorithms" were in the 2nd year of my PhD. With modern hardware, lots of software optimisations are just cheap flex for the githubers.
Haha yes. I would add, it's cheap flex for the githubbers, or absolutely critical for the people working on Google search 😅
Honestly I feel like this video is just a way to rant and talk shit on people who don't know any better, and I love it. I'd just call them shitters and say "Don't care didn't ask." but this video makes you the bigger person.
Incredible example, thank you so much
You are correct in almost everything in this case, young programmers usually overestimate the need for optimization in almost everything, and it is a pain to make them mentally develop themselves in this sense. I believe that game-dev is an area where optimization is especially important compared to other types of programs that don't need to run constantly, but even in that area the importance of readability over performance must exist, and of course your code works.
There are other special cases as well, of course, like making your games more inclusive of people with less powerful hardware, but even in those cases, unless the person has a processor incapable of supporting their own operating system, optimization shouldn't take too much of your time and code.
Another one I have not seen mentioned is web servers. Web servers need to be fast. It only takes 1.5s. Yeah, and that 1.5s was on top of 6 other calls, and people were only willing to wait 0.75s in total. Computers are fast. People are used to it. They will not wait.
@@da3dsoul
It's silly to worry about optimizing on web servers, except for the most low-level stuff, massive data processing, frameworks and tools. For the overwhelming majority of a conventional server, you can use practically any language without worrying too much about performance (of course, you can't be pig either), because simply most of the response time will be divided between the transmission latency of the data on the network, and mainly, the time of access and query to the database. Therefore, more important than optimizing your server code is creating an efficient data caching system, knowing how to deal with asynchronous queues and, if possible, using CDN's.
At last, worry more about creating an amazing product that makes a difference in people's lives and making money with it, than reducing the latency of each call by 10-30ms for much more work and going up the maintenance costs.
@@diadetediotedio6918 false.... assuming you built your database correctly. 10-30ms is my expected database round trip. I don't build static websites, where you would be correct. Static websites can generally be built by laymen these days. I'm a developer, so I build things that actually do work. In the case of most things I build, it is large data processing: business analysis, dashboard statistics, aggregates. Anything I build could easily hit the point where a poorly designed query could make the difference of multiple seconds, especially since many people are expected to use a server at once. If your request takes half a second, then you necessitated a server-side request queue, which will only ever cause poor response times. Web servers need to be fast because everything they do needs to be done 100,000 times
I agree with the idea of the video. I'll add a personal anecdote as a long time modded Minecraft player. Starting in the last few years, we've had to have mods that optimize the crafting code in Minecraft because with mods (and all the addition recipes that come with them), executing crafting recipes could take almost a full second or longer each time. And there is a lot more crafting done than in the base game as well depending on the modpack, which nearly makes it unplayable sometimes.
Obviously this isn't the original intended use of Minecraft's algorithms, but people utilizing systems in unexpected ways via modding can end up can end up exposing "unoptimized" code :P
You could argue that the car breaking down isn't the manufacturer's fault when you put in an incompatible engine.
But you have a good point about users using software in unpredictable ways.
Thanks for sharing your anecdote! I like hearing how other people are using software, and I think that's definitely the most difficult piece of writing a good API haha. Figuring out how users will use the API and creating the hard limitations of an API are super hard :)
Wasted more time, CPU cycles, memory, effort and energy making this video rather than fixing the code 😊
Props for providing the full Knuth quote, and not the most popular and often misunderstood part.
Great video! I definitely need to look into profiling.
I‘d add that when you choose a List/Array over a HashMap despite the „worse“ complexity for lookup, it should „at least“ give you some other benefits in return. Maybe you also need to do other things than lookup, like accessing the first or last element, where lists are more ergonomic. Or you do it to reduce memory footprint, or because it’s actually faster for your small dataset, or for simplicity, or whatever.
But when you have a collection of things just to look them up, I find that using a HashMap is conveying that intent better, thereby improving readability. I don‘t know whether that‘s the case for the recipes in your example, but if it is, I‘d personally prefer a HashMap, because I only see advantages. But a list is fine as well.
I'm not saying you should optimize this specific part of code because I haven't seen it. But telling that it's okay to leave unoptimized code until it's a problem is generally a bad idea. It's easy to ignore it because "it's only a few microseconds" until you got yourself deep into development, and you have so much code that you don't even know where to start optimizing. It's especially important when you measure performance on your PC.
Good example is Yendere Dev:
In most functions you can say "But those unnecessary if statements take only a small fraction of a frame", but at this point there is so much such bad functions that the whole game runs poorly. A project that should run on Pegasus can struggle on new machines.
The lesson should be, it's important to have in mind optimizing your code, especially if optimization is quite simple to implement. In big projects, those bums add up. But at the same time, know when optimization would take too much time to be worth implementing.
I did not see the code, so I am surprised that comparing 6 recipies took longer than computing the hash :D and by the way 2s for user action is too much :D I would optimize it anyway but not right away, because as you said performance is not a concern for it until some crazy amount of recipes.
My two favorite algorithms are linear search, and bubble sort, because of simplicity of debugging, and most funny moments are when they reliably defeat more complex algorithms :D (compilers are good at optimizing them, because they are simple :D )
Another benefit from implementing simple algorithm first is that it can be used as a reference implementation. Later if more fancy algorithm is required its output can be checked against this first implenentation. This technique simplifies debugging fancy algorithms greatly as inputs can be random and there's no need to manually pick inputs for unit testing and calculating output by hand.
This is such a quality and unique content for game programming, love it.
Also note that in order to reduce the algoritmic complexity you most of the time create overhead, take for exemple sorting, Insertion sort is in average O(n2), and compare it with radix sort, which is O(n): in big array sure radix sort obliterate insertion sort, but on small arrays, like 10 elements, insertion sort is actually faster most of the time. That's why most of the highly optimized sorting algorithm are actually just some batching for insertion sort. the best implementation of quicksort is to fall down to insertion sort once the array is small enough, because the overhead of taking a pivot, moving everything ect is actually greater at this scale than doing some kind of simple brutforcing.
I think the important take away here is that if you actually are serious about optimizing your code, you need some idea about which code paths are hot and which are cold. If there is a triple nested for loop with hundreds of iterations per loop, then saving even a single cycle in the inner loop is a huge benefit, but then again it only really matters if it's something that's being run every frame. Taking that hit on a single frame isn't gonna make much difference.
Bro made a whole essay to defend his crappy code lol
10:41 lol. I've seen some who on the one hand focus (almost pathologically) on premature optimisation, and on the other allocate in the hotpath. YAGNI is definitely relevant when it comes to optimisation, especially in cases unsubstantiated by benchmarks
In my opinion optimization is important, but it should be something you do after the code is working
The order I develop in is:
1: considering large scale architecture,
2: coding it and getting it to have almost functionality
3: edge case testing/bug fixing
4: optimize
5: edge case testing/bug fixing
I think the important thing about optimization when you’re first writing stuff is just to make sure it’s not obviously terrible
If you’re writing someone and every single function is like O(n!) yeah it’s probably not a great things simple cause it shows you don’t really know what you’re doing, but as long as you know how to use data structures well and know some basic sorting/searching/etc algorithms that are decently fast and use then as your natural first go to I think it doesn’t matter that much and any other optimization you could make can be done later after you have working code
First :), I really want to stress that people should make more time on those tiny details that go unnoticed, but are the real game-changers, I do know that optimization is good, I once was paranoid about my slow c code and used `-Werror` and `-Wall -Wextra` and many more stuff and It got so to the point where it started showing warnings libc itself and i used werror so I could not do anything about it :(. I used a hundread-ish many args to make an http library that I wrote compile down to under 1kb, I had to write my own asm and use syscalls, because if I used libc I was paranoid that file-size may increase and performance might go down. I completely stopped focusing on performance from then and just allocate **100s of megabytes** for no use at all. I am either on the paranoid abt performance side or don't even care side. This behaviour is bad I do not recommend it. I is very difficult to write programs when you are so on the extreams.
Exactly, finding the balance is key.
Striking a healthy balance is definitely the hardest part of programming haha. I feel you there :)
I wrote a program to check for duplicate files it took just over 2 1/2 days to finish running.
After some slight alterations to the process I reduced the amount of unneeded work done in the comparison loop down and it finished running in 12 minutes.
Prepare for unforeseen consequences
And here am i, working in deep learning, where my algos can run for literally days heheh
every speed up here is valuable
lmao honestly as a data scientist it's the opposite. Loading the models and libraries is by far the slowest part of our code, so optimizing the rest of it ends up being pretty superfluous. Of course I hope the people writing the models and libraries we're using are optimizing them, but as a result there's very little of *our* code that can actually impact performance in production.
@@sparksbet I work in research and usually write all models and data pipelines myself on pytorch or jax, so usually squeezing out performance is a big part of my job as it can have great impact on performance and number experimentation iterations before the deadline. Difference between bad and good jax code for same model can be literally weeks of training.
GABE!! Don't let these haters bother you man! All your projects are amazing and don't let them take that away from you.
That encyclopedia set weighs more than me and I'm fully grown 0_0
Thank you very much. I’ve enjoyed this video and learned something new, what can be better?
7:43 You only get 16.6 milliseconds per frame though. A single function taking 8 milliseconds will be a noticeable lag unless every other part of the game loop can be finished in under 8 milliseconds
I get this is in the 1 million category recipes so it's not realistic, but it still rubs me the wrong way to just casually disregard a huge source of lag. Especially as 144 hz becomes more and more the standard and a single frame can mean life or death in a game
Why is 1 million recipes unrealistic? For e.g. Minecraft, just one Mod like Computer Craft and you got more than 2^1000_000 crafting recipes. Because Disks keep their 1 MB of stored data, when being recolored in the crafting table. Okay, you can argue, that you would need a different technique of storing these anyway, which Computer Craft of course does, but linear searching would not finish in a lifetime.
Yes but this is no excuse for laziness. Like how hard is it to implement a hash table in most languages? It's a pretty logical thing to convert config data stored in a json or yaml file into a hash table like structure. It's just good engineering practice. Crafting recipe -> config file -> hash table. This is a rather obvious pattern and unless there's other considerations at play not doing so is just sloppy.
this is a casual project without any repercussions. its ok to write sloppy when theres no real reason to write well.
I would argue that this is the reason we need ultra efficient and ultra simple to use libraries/modules/tools so we can use the best algorith as easy as using a bad algorithm and forget about the discusion.
To give an example, with python a hash table embebed in the set() and the list is list(), and in both you can check if an element is inside with 'element in elements' so you can use the correct algorithm by just properly initialize the 'elements' variable. No more thinking.
Its like convolution and fourier transform, the convolution is more easy to implement and the FFT only is a good option when you need to use it for two long matrices, because otherwise you don't ever measure the difference and it can be slower to make it (It tooks me 4 days to understand the fourier transform)
I remember waiting hours upon hours for my Windows XP update to finish just because some Microsoft programmer once thought that O(n^2) sort is fine since number of updates will be always small.
So yeah, unnecessary optimization is unnecessary. But you should always ask yourself really hard how sure you are the dataset won't grow too much before you use inefficient algorithm.
But if I don't use every single thing I learned in CS clown college on this JavaScript image carousel I won't be the star of DockerCon.
Bravo, teaching a valuable lesson on the value of lessening work for the sake of "optimization". It's a game, not a stock trading platform. If someone has a goal of optimizing everything then good on them for their personal preferences, but implying it's the only way show's the lack of flexible thinking. Arguably showing how much they've relied on preformed answers/ established concepts; of which is treated as dogma.
yeah that sort of checking is fine for anything that runs occasionally like that. i think the spot where minecraft could run into problems is when you have a lot more recipes (though not 6.5 gigabytes) but instead of checking occasionally, you have automated crafting running at high speeds with hundreds of instances in parallel. but the simplest fix is to check the recipe once and unless something changes, don’t check again, even with a simple check for a recipe when it changes. it could also be that there’s some inefficiency elsewhere with modded minecraft when doing crafting lookups, and that’s the problem not that it’s not a hash. i’m not sure if i’ve seen mods that replace it with a hash but i think i’ve used one that just added caching, and i think some mods automated crafting adds their own caching, just from how the user interacts with them
Optimization is sometimes trades CPU cycles for memory usage. If you want to populate a hashmap with all the values, you have to preprocess the hashes and store them. 3,5GB of wasted RAM vs. couple of seconds computation. ¯\_(ツ)_/¯
Now measure the time it takes a player to move their currently held item into another crafting field. Even with a large data set it would probably not be very noticeable if you factor that + reaction time to the result of the recipe in.
@@Me__Myself__and__I If you try to optimise everything to avoid that, you'll never ship. And you might spend valuable resources on something that might not even get traction.
@@Me__Myself__and__I I am a professional (web) developer. I know those things too. But as always there are trade-offs between perfect software and (business) goals.
As for personal hobby projects I will rarely spend time optimizing code until I run into performance problems.
At work I get paid to care more about these things, so we of course consider performance as our work impacts at a significantly larger scale.
Judging from your comment, I don’t think we disagree at all 😆
@@Me__Myself__and__I exactly right 🤝
I'm surprised that you have only 34.5K subscribers as this comment is being made ! Also , I have previously seen that knuth quote but it had been edited . The person doing the editing conveniently or not so conveniently left out the "premature" part .
This kind of thinking causes a lot of problems on big software projects. "Just this one thing doesn't have to be efficient" soon adds up into hundreds of things and then one day a small tweak in an algorithm means something the programmer always assumed would run on a small data set, is suddenly run on a big data set causing massive issues out of nowhere. I have seen this multiple times.
In this example, off the top of my head, suppose some time in the future you decide you want to arbitrarily mix and match types of wood like in Minecraft. The number of possible recipes suddenly increases by several orders of magnitude. Now the mouse freezes every time you click in the crafting screen and it's hard to figure out why.
Obviously this is a very simple example, but the general argument holds. If you write a function, you don't have the right to guess how it might be used in the future.
Premature optimisation IS the root of all evil. But that means writing random parts of your code in assembly language for no reason. Leaving complexity landmines littered throughout you code base is insane.
Depending on how many different types of wood, and how the crafting algorithm matches, it may or may not be a difference of an order of magnitude. When I add different wood types, I won't be adding a bunch of crafting recipes for each combination of wood, I'll just check if the type of the item is wood which means the number of checks won't grow at all.
And I don't get where people are getting this idea that if a program stops responding the mouse will stop working. The OS timeslices programs, so even if my program completely froze up, the mouse would still run fine.
And coding for what-ifs is what causes project complexity to grow and for abominations like FizzBuzzEnterpriseEdition to exist. I code for the requirement of today, and if those requirements change the code changes too. If I suddenly exposed this crafting algorithm to a mod, then I would plan for large data sets. However that's not the case, and I have control over the exact size of the data set, so why bother?
I'd disagree with your overall premise and its specific application; I'd even go so far as to say it's dangerously bad advice. First of all, Donald Knuth's quote is from the 1960s, a time when mainframes and punch cards were common. Ignoring the historical context of the quote doesn't change that the main talking point of this video can be summed up as performance doesn't matter.
Throughout the video, you go to show that the 'better' algorithm is measurably faster at every data point while mentioning no downsides, like implementation difficulty, readability, or memory footprint. Assuming all of that is correct, there is no reason not to implement the 'better' algorithm. You are arguing against performance for the sake of it.
Diving into the specificity of this application, it makes even less sense. You are making a game, a performance-heavy application, that doesn't spend 90% of its runtime blocked waiting for data. Even 1μs is an eternity for a performance-critical application, especially considering that crafting would eventually be a back-end feature on a server, one of many services constantly accessed by multiple players, potentially impacting the latency. To use your example, Minecraft has FastWorkbench, an extremely popular mod with over 70m downloads and whose sole purpose is caching recipes.
The idea that you should purposefully write slow code in a performance-heavy application and then profile and refactor it bit by bit, effectively rewriting what you should have written in the first place, is abhorrent. This is precisely why this quote has evolved to "premature micro optimizations are the root of all evil".
This, exactly.
These are just excuses to not build a great software
Were do you go to learn all this information like how to code shaders, the entirety coding methods of the Minecraft methods? is it from articles and documentations? also love your videos
Speaking of optimization. Modded minecraft uses the simplest one for furnaces and crafting: they cache the last used recipe. (mod FastFurnace, FastWorkbench). You can generalize it to LRU cache I guess. And the mod provide numbers.
Lmao, loved this video, you're not wrong. Keep up the good work.
This video completely misses the mark imo. Sure, speed and big O aren't the same, and it's a beginner's trap.
That said, the attitude of "your PC is so incredibly fast" therefore small things don't matter is another beginner's trap.
It's how you end up with large projects, where there are 5000 systems, each only taking a measly 1ms each, and now your program takes an additional 5 seconds to start, which you'll pretty much never be able to get back, because almost nobody has the time and resources to go back and refactor 5000 systems, for miniscule gains.
This is the death by 1000 cuts, and it happens everywhere in large software development projects.
All of these tiny systems could've been written initially to be 100-1000x faster with trivial difficulty, and it'd have resulted in a vastly more pleasant program to use, that's not constantly hitching.
In addition, lagging 15ms in a game is actually insane, even if it's "infrequent".
If 15ms is an acceptable stutter time for a game, then logically manufacturers should stop making displays above 60Hz and competitive players should stop using them.
I learned that lesson well. When I was a young dev I spent a week or so making a performance improvement to a subsystem in the interpreter for an in-house programming language. Testing the old code against my new code there was a night and day difference in performance. I popped in the new code, gave it a try and ... nothing. No measurable improvement. Lesson learned: when the code you're improving is responsible for less than 0.1% of the time taken by the system you aren't going to see a measurable perf improvement, let alone a worthwhile one, even if you could make the new code take zero time. ;) That was a week's time well spent. It saved me countless hours throughout my career.
Shows us he is bad at game design and then tries to talk himself out of it by saying that one frame of lag is negligible
Just a reminder: This isn't an excuse to not optimize your code or not avoid common mistakes while writing your code.
Finally someone calling out the cope of a lot of programmers 🤣🤣🤣
Omg thank you for making this video. I feel like I've had this argument a million times. Just write the code, if it's a problem then refactor it as needed.
The fact that even the "hash" algorithm scales with the size of the data set implies that it might also be around O(N) (maybe because it's dealing with collisions?). So it's not like you're really saving much time with that algorithm. There's also a space complexity trade off that you have to make as well as paying the startup cost of setting up the hash table. Especially in a game like Minecraft, space optimization is more important that saving a few microseconds in the crafting menu.
I agree that optimizing this is one of those easy gains and probably something I'd throw on a TODO at some much later point when I'm bored (if ever) but it's absurd that people were complaining about that in the previous video as if you didn't already know that and made a conscious decision to use the slower algorithm.
Yea the hash version that I implemented for this benchmarking was just a simple early out that would skip the comparisons haha. I updated the benchmarks to use a proper hash set and that performed at a consistent 1 microsecond, regardless of the input size :)
But I appreciate the understanding! It is kind of aggravating when I have a lot of comments that assume I'm just coding without thinking (even if that is true sometimes haha). I try to always code with the priorities of: how often is this run, how critical is this when it's run, and what is the size of the data this needs to operate on. Preferably in that order :)
I agree that your initial crafting algorithm is perfectly fine for your current requirements and the work being done. No need to overcomplicate it and go into something that is not the focus. I sincerely doubt your "critics" were actually suggesting good algorithm design. And what's up with that? BigO is for algorithm analysis, not for performance analysis. Sure, BigO and Performance are correlated, but correlation is not causation.
I guess it is outside the scope of the video, but GHz won't indicate the operations per second that are actually available to any given piece of software. Your code runs way faster because it is compiled C++ in a good machine, but if it were compiled to WASM for example, or it was run in a scripting language, the actual operations per second available would be far less.
One time, I implemented a compression algorithm for web assets, it ran fast in Go, like in microseconds, and I mistakenly believed it would work just fine in a web browser in the order of milliseconds... It took seconds with just around 1MB of data, something that was unacceptable given the requirements for the web app.
On I side note, regarding the video, you probably don't have somebody to check your video scripts and give you feedback, but you kinda came off with an attitude of "the devices of today are really fast, therefore I don't need to think about the algorithms I'm using". The last thing we need is for developers to catch attitudes like that and end up having a bunch of apps wasting system resources (CPU cycles, battery, io time, memory...) oh wait, I just described the current landscape of apps today c: but I digress. I do get that's not the message you are giving, but it doesn't hurt to be careful since well, I a lot of people look up to you as a figure of authority regarding development.
Anyways, the point still stands, BigO doesn't equal actual performance gains. For your series and the current state of the project, your algorithm is more than enough. You are learning and teaching how to do most things from scratch, and I'm sure when the time comes for more complex recipes (because Minecraft has some "wildcard" and interesting recipes that won't work in your current implementation) you will implement a really good crafting system. Take care and good work!
P.D: I need to be able to use fewer words when expressing ideas.
P.D.2: Allow me to take advantage of this opportunity to share this: ubiquity.acm.org/article.cfm?id=1513451 since you quoted Donald Knuth. It is a good read.
I love it... great presentation... you respond to trolls with way more elegance and tolerance than I do...
Great video!
Notice how the people who commented on the last video will not comment on this one, and if they do they'll keep arguing because they can't deal with being wrong.
The performance of an algorithm can also be different across programming languages (and maybe other tools). I implemented a few Game Of Life algorithms in Lua based on a series of articles I found, where each algorithm should perform better than the previous one, but, to my dismay, what I found was mostly the exact opposite.
"if it barely effects performance, its probably fine" - sun tzu
Our teacher just told us about the big oh notation, and he told us excactly this, that the notation does not apply to all cases, like with small samples or when it get's used only a few times
Good video, thanks. I myself feel pain if the non critical piece of code is not optimized as much as I can.
So for me would be helpful, if you'd talk about: what's wrong with hash-tables? It takes seconds to implement, then why make it ugly when you can make it neat?
So, if the computers are so fast, why Minercraft is lagging on my laptop? :(
On the serious note though, I'll just create a profile and then look at the chart to see what took most of the time (for example, clean Wordpress without any plugins will spend 2/3 of the time reading the translation files, if the main language isn't English that is; sucks to be outside of US, UK, 'Stralia and some other countries that's using English language when there are hundreds of the translation files needed to be processed).
I would also look for the unnecessary work that's being done, like for example sending the queries to the mysql for the data that is not dependant on the loop that the program/script is at that point in time. When the first query delivers the same data as 100k query, then what's the point in doing the same thing over and over again, right?
Thank you for letting me worry just a little less about my spaghetti code
This video was a descent into madness and I love every second of it.
Another thing of note is that hashmaps also need hashing, plus a few comparisons because of collisions. Searching in linear space is faster than a hashmap for very small datasets.
Also, people miss too the cache of the processor and how data is accessed internally. If it fits in one cache line, reading left to right is just faster than randomly picking a location.
There are also memory access prediction that prefetch data. For left to right access, the prefetcher is going to put into cache the memory before is needed, where random access via hashes is impossible to predict.
Big O notation is useful but it ignores the reality of how computers work.
This reminds me of my only C I got in graduate school in Analysis of Algorithms because I would answer every question with "buy better hardware".
It wasn't QUITE like that, but close. Turns out my instincts were right in the vast majority of cases. I can't think of an incident in the past ten years of coding where I've had to revise an algorithm for speed outside of test cases -- my major performance issue is reaching outside of code to a REST endpoint or to a database. Compared to those costs, CPU cycles are trivial.