How I Optimized My JavaScript Project (Complete Walkthrough) | Faster Spatial Hash Grids
HTML-код
- Опубликовано: 6 дек 2020
- Follow me on:
Twitter: / iced_coffee_dev
Github: github.com/simondevyoutube/
In this project, we're doing some JavaScript optimization. This is a follow-up to our last project that covered spatial hash grids, or spatial hashing as it's sometimes referred to. Anyway, we're continuing and building on that JavaScript spatial hash grid implementation, but we'll be examining it in detail with Chrome's DevTools profiler, looking for hotspots and optimization opportunities. I'll take you step by step through the process, benchmarking the code, examining the profile, and ultimately making the existing implementation dramatically faster.
Whether you're a game developer interested in this specific spatial hash grid data structure, or a JavaScript developer looking to work on your optimization skills, this has a lot to offer.
Understanding datastructures, having a complete and thorough basis with them is a key skill for any game developer. It's a complex field with tradeoffs between memory, time complexity, and even development and maintenance cost all come into play. Understanding how to look at code, profile, optimize, and in short speed it up are import skills for a developer.
In the video, we cover:
* Looking at the overall optimization strategy, how to approach a chunk of code for improvement.
* Profiling & Optimization in Chrome, using the built-in DevTools to capture profiling data and examine it.
* Walking through the sources tab to look at line-by-line hotspots in JavaScript code.
* Weighing datastructure options, discussing the tradeoffs between Set containers, Map containers, arrays, and linked lists.
* Actually making the JavaScript code optimized. 
Наука
If you enjoyed this, help support me: www.patreon.com/simondevyt
Who knew devtools had that line-by-line performance thing! Awesome!
I didn't know ;(
@@duncan5521 Neither did I!
Everyone who cared enough
Thank you for the tip SimonDev! This is exactly what I was looking for
I don't know why but even after i run a performance round I am not able to see the ms on the source panel... :(
Dude, that trick with exchanging the item to be removed with the last one is genius!
The pregnant women analogy! 😂
Why didn't I dive into this channel sooner? Amazing content; sprinkles of dry, quirky humor; great high-level overviews in the most accessible programming language, but applicable to any language. You rock, man.
Happy you're enjoying it :D
Thanks for taking the time to make corrections to the code, the biggest problems I see with tutorials is they just say it's "good enough" and don't explain the pitfalls.
Wow, how did I not think about swapping the target item with the last item when removing it from the array. Now I feel stupid.
you just need enough moments that make you feel stupid, until you find out that you are stupid for sure, only then u can become a great programmer :)
every few years i discover this trick again... each time my mind=blown
@@ananthrao7802 yea i think a lot of us, who program regularly, do :D
@@heinzorse6007 and hoping that when are stupid there are enough moments to get you to feel even feel more stupid, until the point you find out that you are again, and you become a great programmer =)
It's worth mentioning that the queryId technique you are using for cell deduplication is not thread or async safe. Two queries cannot be run against the same hash grid at the same time, because they could stomp on each other's queryIds. This is not a problem in Javascript, as long as the functions are synchronous, or in any other game where you are not using threads. But it is an important limitation to point out, especially because doing multiple such queries on the same frame would normally be trivial to parallelize across threads.
Very true. This is just an example of the concept, so I think it's fine to be pared down to basics. In actual game code (C++), I'd minimally add asserts to check calling thread. Would really depend on expected use.
It's not an issue since Javascript is single threaded anyways and doing these kind of tasks in a worker would be significantly slower due to communication overhead.
Loving these optimization videos man. Keep up the good work :)
Thx! I should have another optimization related one up on monday.
I love how each of your videos gives progressive understanding, and it's clear, concise, and only as long as it needs to be. No fluff. Thank you! Please continue to make videos!
This is awesome! Thanks for the great step by step guide of how you actually do your optimizations.
This video is a banger, watching it made me realize the importance of knowing data structures. Super well explained and engaging too, thanks for making it ❤
You're amazing, even tho i don't understand any part of code your explanation is amazing and clean and gives many ideas how to write faster running code. Thank You ❤️!
Happy to hear that!
Thanks for this. Its hard to find videos on actual indepth JS optimization. I rewatched several times
This is exactly what I needed to push myself to learn more about DS/algorithms, thank you!
It's been a while since I last found such an interesting channel. Thanks for sharing your knowledge!
This is some next level JS, wow! I bet none of the devs in my company know how to optimise JS like you. Thanks for the video!
I love this, I would just like to add that having tests in performance optimization is important to know you're not breaking anything.
Definitely
Really glad I found this video and your channel. I'm doing some live streamed JS optimization these days, and I'm scouring RUclips for info to help me establish if I'm on the right track. This video is very accessible and bolsters my confidence in my game plan. Subscribed!
I immediately regreted that I didn't turn the bell on this channel a while ago. Don't be like me.
The video was super cool and I gained a bunch of ideas just from watching it. Thank you!
“Nine pregnant women can’t produce a baby in one month”
_you’re not trying hard enough_
I would but the wife disapproves
To be fair the average birthrate is high enough it's just the inconsistent birthtimes that ruin the experience for the player.
Nine pregnant women can produce nine babies in 9/10 month, which is pretty close to that!
Loving your work keep on going
ty!
I even learnt how to call that hamburger button you clicked on ! 10/10 thanks !
Apparently it's called a kebab menu! Someone told me the name in the comments here somewhere heh.
@@simondev758 Yes, hamburger is the wider one with three lines, kebap is the skinny one. You can't make this up.
Hamburger menus are square buttons with three lines, and they open a side menu with a list of items for navigation.
Hamburger menu is an official Google Android name for the 3-line menu. Some dude made up kebab later, apparently, for what Google Android calls the More Vertical menu or Overflow menu.
Loved it man, the way u explained evything, afyer watching first 5mins i subscribed ur channel
I enjoy these videos a lot, it gives me a different perspective on javascript.
Awesome stuff shared, thanks alot, being self taught developer it was very good information
Thanks
Thanks alot! You made me realize how important is DSA is :)
Glad it was useful!
@@simondev758 waiting for more! Thanks a lot!
Watching a random two year old video and I see you already knew of the array deletion trick. If only other people knew this trick.
I love spatial hash grids!
Ok, this helped a LOT. I totally forgot about the quick removal of array elements that are not order relevant by doing the swap + pop().
I will have to go through my code again and see how many more optimisations I can still do. I had been using the profiler already to figure out where in my code I was being a doofus. However, I didn't know that the sources tab also shows the time spent on that line! This'll help even more I hope.
I'm curious to see how you'd deal with (hyper)optimisations when it concerns the GC. As it is one of the things I was interested in fixing in my own little javascript project(s).
11:36 swap, pop was new for me :)!
12:11 that's like exactly what i do in my delete methods for lists :D i also keep track of deleted cell id's to re-use them when needed :)
13:08 actually that's the way strictly typed languages demand you to code- by predefining your arrays or lists with fixed length and types. I find this method better cause of the "sense of control" over what you are doing ^_^
I just discovered this video and it was great! I love how unintuitive it feels when optimization actually sometimes means you need more code :D and i loved how for an optimization you needed to involve lower level programming approach (pre-define & linked lists) to achieve greater speeds, it shows well how you need to strive away from javascripts dynamic and loosely typing to gain performance.
Also, about javascript, i have experienced that array's specially "push" operation is pretty slow. Instead i used key-value pair object, i am not sure why but {a: 'b'}, accessing and iterating this datatype is ~10x faster than ['b'].
re: 12:11 - lists - interesting, what do you get from reusing the cell ids?
re: 13:08 - arrays - Are you talking about languages like C++ where you have to specify a size to allocate an array? That's totally true, although I tend to think of JavaScript's array as more like a std::vector.
That's really interesting that the push operation is so slow, do you have a micro benchmark or timings? I'm really curious about this. So if you have
const test1 = ['b'];
const test2 = {a: 'b'};
Iterating test2 is 10x faster than test1? And just normal pushes to test1 are slower than adding to the dict?
@@simondev758 sometimes I might want to undo the delete, then I can just stich back the pointers of deleted cell :)
Yes I did my own local benchmarking and the project that taught me about the difference is still alive to this date, I don't to share the url publicly in this comment section but i will explain the operation it's performing (where i replaced array with object and got a significant performance boost):
* Goal is to find "noise/seed" (float number) which is used in a hashing function.
* This hashing function must go trough all numbers from 0 to 16,777,216 without a collision and must also be capable of hashing any string input.
* now while probing a random noise float, i store 0th hash to an "array" iterate to 1 hash it, and check if this array had already this output (a collision), repeat till 16M
* finding hashes in array and pushing them to array of a length of 1 million was slow, very slow- but when i changed them to {[hash]: 1, ...} then checking if the key existed was lightning fast. Same with adding a new key.
This project is fun but it is private due to lack of security implementation. I made it for myself and close friends :D if you're interested in taking a peak i can definitely send you the link just tell me where :)
I realise this is an old video, but I had a look and didn't see anyone comment on this yet. In the "slow" version of your spatial hash grid, you initialise _cells as a Map, but then you are using it like an object - if(k in this._cells), this._cells[k] = ..., etc.
The Map API should be like if(this._cells.has(k)), this._cells.set(k, ...), and so on. This won't make an asymptotic difference because JS objects are essentially themselves just hashmaps, but there is some performance difference between a regular object and a map since the former is more optimised for fixed accesses like obj.static_key rather than dynamic ones like obj[dynamic_key]. V8 does try to tell when you're using an object like a dictionary and switches its internal representation, but when you know you want dynamic accesses, using the Map API should be better.
Thanks, I'll keep that in mind if I do any kind of followup!
Good stuff 🙂
ty
I had no idea you can view the profiler in a sources tab, that is much more readable then the default view. Would be awesome to do this with vue or react . Great way to learn to code.
wow time per line, so cool
hey so I see some possible solutions to a problem I've been trying to solve. I would love a video on grids and gridlike structures and specifics of how to set it up, use it, find neighbors, I've read papers, watched videos and more but it just hasn't clicked yet. I feel like you would explain it nicely
This was a follow-up to the first video, which detailed the spatial hash grids. Is that what you're looking for?
Just got this video in recommended. And I see a for of loop in your code. Not sure if this is still a thing, but in js, at least a few years ago, for of loops and [...spread] operations were in orders of magnitude slower than regular for loop with increment. And using let item = arr[i] instead of for (let item of arr) usually increases performance by a lot. That's caused by all the Iterator/Generator logic behind the scenes of 'for of'
I profiled them at some point and confirmed the same, they're way slower. Pretty sure the "fast" version of this code doesn't use the "for of" form.
I was about to comment the same, I don't that smart to know what he's doing but after watching ThePrimeagen I knew that was a gotcha
thx this is awsome
I like the way you say javascript
Bravo!!!
Nice! The queryid method is clever, but you can't easily use it in a multi threaded environment.
i like this
3:18 that type of menu icon is called the "Kebab" (Not that it's important at all for this video)
Thanks heaps for making these videos!
Hah thanks, wonder why it's called that.
@@simondev758 because if you draw a line down the middle it looks meat on a stick apparently haha
@@simondev758 the one where the dots are lines is called a burger menu
3 vertical dots is called a kebab. 3 vertical lines is a hamburger menu.
A small improvement to your iteration work is avoiding using the for…of enhanced for loop.
It’s syntactically pleasant but it has performance costs for larger datasets. Going with a .forEach would be a good middle ground for speed vs syntactic sugar.
Either way, super great video. Really enjoyed the structure of the video.
I'm still getting use to JavaScript's little gotchas on performance, I feel like I should gather them all together for a video one day.
How .forEach could be any faster than for...of? .forEach does a function call for each item, which is the worst you can do. If you want speed, do a classical loop (for (var i = 0; i < array.length; i++).
@@Stnaire This is correct. Even for...of is faster than forEach.
800x but when I play it on 2x speed it is 1600x
I love your videos! Advanced bundlers do all these optimizations for JS devs, sad how abstracted we are from these critical things sometimes.
Those bundlers refactor your code to use different data structures?
@@simondev758 haha definitely not. xD sidenote JS translates some piece of hot zone(frequently called) code into web assembly.
@@pinch-of-salt Ok that sounds much more reasonable!
@@simondev758 There's a JIT in most JS engines now so any hot spot is compiled natively :)
Have you tried cleaning up the grid and re-inserting the objects instead of updating them? Cause for me it brings better performance in cases when all objects are in motion. I store the indices of "dirty" cells in an array(actually, a JS fixed type, fixed size array) and use a timestamp to prevent duplicates same way it's used to prevent duplicates in query results.
Or should updating objects be faster and I'm doing something wrong?
I haven't tried no, but if I revisit this I'll definitely experiment with more approaches!
F12 also brings up dev tools 😋
I think there is a little bug in the "_GetCellIndex" method. Substracting "1" from the dimensions gives wrong results. It´s not obvious on huge maps like 2000*2000, but i tried a 5*5 map, so i found this. 10pixel each * 5 cells -> let´s take pixel 11, shoule be index 1 -> floor (0.22 * ( 5 - 1 )) = 0.88 = 0
You're right, it's kind of wasting a cell, good catch. Doing i = min(dims - 1, floor(x * dims)) works I think, haven't checked thoroughly. I'll update the code when I have a minute.
Sir have you came across any enginnering problem which required you to read Research papers? Want to learn more from you ☺️
I hit the like button, but honestly, I'm in the shallow end of the pool, so most of this doesn't make much sense to me. I have to actually work my way up to optimizing my code; I am happy just to figure the simplest thing out
That's good feedback. I try to experiment and change the videos a bit, to see what works and what doesn't. Optimizing is fun for me, since I did a lot of it in my career, but it's a very advanced topic. Hopefully you checked out the first video on implementing the spatial hash grid.
Dayum
also when working with JS you got to be aware of hidden classes and how polymorphism effects it in v8
whats a hidden class?
It's amazing how you work with the profiler. You probably created that thing while working at google didn't you? :D
Nah, closest is having worked a bit with the team that did.
@@simondev758 :D close enough.
I would also like to work at Google one day. Not sure if my CS bachelor in Germany will bring me there though >_>
What was the reason for changing _cells from a Map to a 2d array? Was it just for nicer initialization of the empty cells?
It's been forever since I did this, pretty sure it was to move this from an amortized O(1) lookup in a map, to a constant time array lookup.
Great video, thank you. One thing that doesn't click for me... why is the array faster than the set? As you show, inserting and deleting in a set is advertised as O(1). Aren't you effectively reimplementing a set with the swap + pop trick, couldn't the set implementation do the same under the hood?
A set is most likely implemented with something like a hash table, etc. since the elements are required to be unique. Let's run with hash table, deletion is O(1) amortized, O(n) worst case, since in a basic implemention you need to hash the object, lookup the bucket, and either probe subsequent addresses (probing) or search the bucket (chaining).
An array delete, with a known index and swap is a couple memory accesses + whatever overhead is imposed.
Hi, i got a question: Why do you use IIFEs to export objects in your modules? Wouldnt it be good enough to just define the functions/classes in the module and export them afterwards?
I learned to do it that way initially, I don't work professionally in JS, so I've just used that in my own personal projects. After posting some of these, more knowledgeable people have pointed out it's unnecessary, so I'll switch it up in the future :)
@@simondev758 Not sure if more knowledgeable, it's just prior to ES6. But looking forward to seeing those new videos with the subject from this video!
very interesting video, but if font size be bigger, it would be even better. now it is not very convenient to view on mobile devices
It's only a hamburger icon if it's made of horizontal lines.
I think someone here pointed out it's actually called a kebab menu, if I'm remembering right.
Can I ask something? I'm a beginner at JavaScript but I know some stuff. I am curious why do you prefix some of your variables with an underscore?
The only time I've ever used it was for a temporary value inside a setter in a class.
I spent most of my career in C++, last year or so doing some python, and I had never touched JS until starting these videos. Didn't look up proper naming conventions, just starting using a weird hybrid of conventions from other languages.
@@simondev758 Thanks Simon, appreciate you responding to me. I thought there was a specific purpose and I fell like a was missing something :)
1:00
The only thing my stupid ass can think:
"Why is this in the destructor?"
4:12 I dont see the "ms" next to the lines of code. :(
Does anyone experience the same problem and know how to fix it?
yep, i am really NOT prepared for refactorice mi code into a highger lvl...well into a higher lvl maybe yes, but performance lvl not so sure
Was thinking about making a game in js, since I am already familiar with node and electron. I'm just worried about keeping everything functional at 60fps, thats only 16.67ms per loop. Maybe its not viable in js. It makes me sad cause I am super fluent in it.
Ran the github code and... maybe my Ryzen 5950x isn't up to snuff, but was only pulling 47ms on the non-naive find nearby. I'll have to dig through the perf to figure it out
bah, chrome removed the line-level of detail.
... MicrosoftEdge doesn't and that's when I noticed the github page only runs Slow, not Fast :D
I learned how much more I need to learn. :(
There's really never a point where you don't feel that way. Well, unless you have a crazy big ego.
Learning is part of the fun!
so queryId is effectively a "seen" flag that gets reset every query.
I can understand 9 words in that book
Oh, so THAT is what AB testing means.
F12 to open the developer tools.
ah yeah i always forget the other ways to open it
It's Ctrl+Shift+I :v
Ctrl+Shift+C is "Inspect Element" :v
Does anyone know of a profiler for C code that does something similar? The Chrome profiler is pretty amazing.
I used to love vtune when I worked in game development, my goto for pc cpu profiling.
@@simondev758 thanks!
Great videos. Although I'm a little confused with "this._cells = [...Array(x)].map(_ => [...Array(y)].map(_ => (null)));". What is the C# equivalent to this if you don't mind me asking.
it creates an empty array of arrays, with all 'null' values inside, so that the current index is always 'something' that exists (i think).
[[null, null, ...], [null, null, ...], ...]
That's right, it's just a kinda gross but concise way of instantiating a multi-dimensional array.
In C#, for an empty 2d array, you just do: _cells = new Cell[x, y];
Do you have any tips for doing a similar sort of thing in the nodejs realm?
This is just JS, so should run without much trouble in node?
@@simondev758 you're right. There's pretty much no significant difference between browser APIs and Node's ones. It could be even faster to use node, because you can customize the environment and take full advantage of node's internals to communicate with OS in a more efficient way.
What is the math.sat() function? I can´t find anything on the Internet.
docs.microsoft.com/en-us/windows/win32/direct3dhlsl/dx-graphics-hlsl-saturate
Specifically, "sat" was, I think, an specific instruction from the assembly version of shaders from the original xbox and for whatever reason it's stuck in my head so I keep using it. It's just clamping to [0, 1]
at 12:51 why did you do [...Array()]? why not just set it equal to Array()?
I have no idea, don't count on me to write perfect JS heh.
@@simondev758 Great video! Using the spread operator is necessary because Array(len) by itself produces a sparse array (a length without slots). If you open up a REPL you can see it:
> new Array(5)
[ ]
> [...new Array(5)]
[ undefined, undefined, undefined, undefined, undefined ]
new Array(5).map(_ => null), wouldn't even iterate, and the array will remain completely empty, but with a length specified (aka sparse).
what do you think about React three fiber?
Haven't tried it yet, although I had someone recently recommending I do.
@@simondev758 when you make a web page with 3d animation, do you just use three.js and pure css and html?
Yes. Keep in mind any web page I make, is mostly scaffolding to display any project/game I made, so yeah just pure css/html.
@@simondev758 Seconded !
I would also love to see/hear your thoughts/tutorial on react-three-fiber !!
@@Kastanienbraunhaus Hah ok lemme bump up the priority on it, see when I can slot it in.
To create Android game apps with JS... what do you recommend?
Heard good things about Electron, but can't vouch for it personally since I've never used it. Might be less painful to just use Unity though, since you can compile out to whatever target you want.
@@simondev758 Understood and thank you
Sources tab no longer shows the run times. Really sucks. Why did they change it? "Disable Javascript samples" is not checked. I can see run times for functions but not on a line-by-line level shown here. 4:21
Code execution is usually ms territory. Isn't stuff like 'Draw calls' the bottleneck?
What makes you say that?
The problem is is when you have a specific frame budget that is only like 30 or even 16 milliseconds, 4 milliseconds is a lot of time to lose. Also its not necissarily that fast to run your code depending on what your doing.
Is the misspelling of subscribe an inside joke? have noticed it in a couple of your videos already.
Oh man where am I writing it, I don't even remember writing it into any videos, although I barely remember what's in this video.
@@simondev758 :D, for example 0:53. Awesome videos though
How to find out if you're a programmer: 2:22
You sound kinda like bob off bobs burgers
Very interesting optimization. BTW, that icon is called kebab (menu).
Neat, never heard that name, thanks!
im pretty sure it is called Burger just like he said in the video
its too bad things cant be both readable and performant :'(
That's what comments and design documents are for! :)
I thought the answer is almost never a linked list.
temporal coherence.... okay im going back to school.
That queryIds optimization is equally genius and ugly.
Can’t find the “Subcribe” button so I guess I’ll just have to press “Subscribe” instead. 😉
I got most of the letters, and in the right order. Pretty proud of myself, earned a beer.
When you should narrate Christmas carrols but instead do programming :
double linked list, cache
ruclips.net/video/oewDaISQpw0/видео.html , ruclips.net/video/oewDaISQpw0/видео.html Is there a reason why you do NOT use triple checks? Also for performance reasons?
No compelling reason, beyond I just didn't think to. I'm trying to use it more, as it's the recommended pattern, but old habits :p
@@simondev758 Thanks for your quick feedback. highly appreciated! :-)
subcribe
The text is too small to be able to follow on a smartphone, but it can be enlarged (lots of empty space). Thanks
me
Linked lists make people feel clever but they're terrible for performance :v
Ъ
This light mode developer console is a crime
optimization, no, not in the sprint. do you know agile ? :)
You can make nine women pregnant in one month. That's fast enough
I don't even remember what I was talking about in that video that I had to use that analogy.