Memory, Cache Locality, and why Arrays are Fast (Data Structures and Optimization)
ฝัง
- เผยแพร่เมื่อ 25 มิ.ย. 2024
- Why is the first loop 10x faster than the second, despite doing the exact same work?
Follow me on:
Twitter: / iced_coffee_dev
Github: github.com/simondevyoutube/
In this video we talk a bit about memory, the cpu caches (specifically the L1/L2/L3 cache), hardware prefetching, and how all this comes together for arrays. We'll be covering each of these topics in enough detail for you to get a solid understanding, working through real world examples to help illustrate the point. We'll talk about the most fundamental data structure, arrays, how they work, what situations they're great in, and when they suck. We'll also touch on some algorithmic complexity. Finally, we'll be talking about why understanding this is important and how this leads in to more advanced topics and data structures.
What's covered:
* How memory allocation works, memory addresses
* Contiguous memory
* CPU Caches, L1/L2/L3 cache
* Hardware prefetching
* Array operations, what's fast and what isn't
* Closing thoughts, why this is important to understand, how this relates to more advanced data structures - วิทยาศาสตร์และเทคโนโลยี
If you enjoyed this, help support me: www.patreon.com/simondevyt
As for the question at the beginning, as a first hint, look at how the indices for the arrays are generated in both loops. Write out a few, and think about the pattern in memory. Actual answer below.
Both loops touch all memory exactly once.
First loop generates indices sequentially (ie. 0, 1, 2, 3, 4, ...), meaning memory accesses will also be sequential.
Second loop uses a large stride (0, 4000, 8000, 12000, ...), so cache misses will be common.
@@heinzerbrew It's the indexing, just unroll the loop a few times to confirm. Sequential, predictable memory access vs jumping around, main topic of video. Php? Don't know much about it, other than it's an interpreted language. Guessing the overhead of that drowns out other things.
@@heinzerbrew Again, you can't use php to test this. And this has nothing to do with memory allocations. Additionally, please don't use the pinned comment for this.
would a modern c/c++ compiler be smart enough to detect and optimize it?
This is a pretty contrived example. I tried to think of the absolute, most basic thing that would illustrate the point without needing to build a lot of extra boilerplate code around it. But in this example, using "gcc -O3" doesn't optimize it, but gcc -Ofast does, because it disables strict standards compliance. So it does sorta catch it, but is held back because you have to explicitly tell the compiler that you don't care much about the order. Remember that floating point operations are NOT associative, so it tends to be the compiler reordering them without explicit permission from the programmer is a no-no. V8 doesn't seem to catch it, but can't say for sure why.
So the difference in timings between the loops should still largely come down the difference in memory access patterns.
We could make the setup a little more complex with some structs with useless info to pad them out, or an array vs linked list, or something to that effect. Maybe it would have been a better choice? Would be more legit, but harder to parse for beginners. I dunno, I'm learning how to present this as I go heh.
@@hww3136 what if you intend to iterate that way? You'll get a bug
“why the code on the top runs faster? watch the video and find out” ...and no mention of the code again. Otherwise nice video.
Hah yeah, I feel kinda stupid for not looping around, live and learn. I'll continue the series and make sure I actually answer it next time!
@@simondev758 Nah you managed to explain without relying on code. If anything cut the intro.
One is accessing the array in row major order, and the other is accessing it in column major order. The top one is faster because the memory is being accessed in a contiguous way, which means you'll get a lot of cache hits (very fast, going to main memory much less). The bottom is is NOT accessing memory in a contagious way, meaning every access is a cache MISS. en.wikipedia.org/wiki/Row-_and_column-major_order
@@bonehelm maybe I am blind but the only thing he switched was the + and *
@@tagg1080 That's exactly the only change. He's using a formula to treat a 1D array as if it were a 2D array. But the order of + and * determines whether it's accessed row by row, or column by column.
Best Director Award goes to Simon, i have never seen such a beautiful explanation without answering question, amazing!!!!
hah
"let's head to apple store. I don't actually own one, because they are super expensive and I'm super cheap, but I like to look at them" 😂🤣😆
Man this was soooo relatable on so many levels 😂
You didn't explain why the original code posted was 10x slower. The reason being that the method in which the array was effectively traversed was not sequential or easily predictable, causing a lot of cache misses.
This cleared up so many things that my professor failed to teach me (or even understand it himself)
We truly need more videos explaining how the cpu works when we code
Thank you so much!
Nice, lemme know if there's other subjects I should cover too.
This channel is pure gold man. Although I already know most of these concepts, you explain them pretty clearly and in a very understandable way ! Well done friend, subbed!
I feel like this is going to be an awesome series, especially for people like me who learnt programming by themselves and never really had a formal education teaching them about what parts of your code does under the hood.
I did study computer science, but none of this was covered. This is mostly from years of experience learning at companies and applying these optimizations.
Me too!
@@simondev758 i share this experience. in computer science, we also never covered that. only when i had to do projects and facing performance optimization problems, i was motivated to tackle the fundamentals of data structures and how to squeeze more and more efficiancy out of my code.
@@Ainigma wait really? I’m at the first semester of computer engeneering and i’ve alterady learned about this, Idk if the way they teach is different here in Brazil or not
Different universities teach different curricula. I went to a university that's considered pretty good (ie. often included in top lists), the focus was much more on theory and mathematics. I mentored a few Stanford grads while I was at Google, came off with the same impression. Super strong bases in theory/math.
Also, computer engineering != computer science. I can totally believe that an engineering oriented curricula would learn way more about the underlying hardware.
Wow this video is almost 10 minutes but it felt like 1 minute! I really enjoyed it (Y) will definitely rewatch this later today!
Awesome!
The video became x10 faster for you
I was jumping around randomly and it felt like 10 minutes
This has got to be the best educational video on youtube, fuckimg amazing
Awesome, glad you enjoyed it!
4:20 you ain't cheap bruh, your content is way better than expensive internet courses.
ty! If you have suggestions for future vids, let me know.
@@simondev758I'd love this series just keep doing it
hahaha weed number
@@simondev758 I hope you will grow so much that you will be able to afford one of those macs without feeling its price, i watch your videos for quite some time now and you deserve it.
I dutifully paused the video at the beginning and took _way_ too long to spot the differences between the code samples. (I've never been much of a programmer.) After getting it I still learned a lot more from your discussion on the caches and all that. Thanks.
Posting this for anyone else out there like me.
As someone who knows JUST enough code to be dangerous, I feel dense for not getting it sooner.
My brain absolutely looked at the two for loops, saw them moving through the same numbers, and even though I recognized there was a difference in the last line, my thought process collapsed to "alright so you move through all the same array positions eventually," and I spent ten minutes trying to figure out, on my own, why changing the order of operations would make it faster while ignoring, y'know, the actual result of iteratively running the loops.
The first comment I saw mentioned row vs column major ordering, and even then, I thought "that's silly, it's a 1D array!" and failed to make the connection.
Took me seeing someone list the resulting indices in order to finally click. Despite so much of video focusing on contiguousness.
So for anyone else that did the same, we're a special kind of stupid, but at least not a unique kind.
It's hard, which is why optimization is often a specialty.
An amazing series start, Simon! Thank you for this dive into memory allocation/access details, very helpful! Surely looking forward to a (contiguous?) continuation and your other quick projects & cool tips! Very kind of you to put in so much work and share it. Again, thanks!
np, glad you enjoyed it!
you are made for creating videos like these, I could watch this for hours, thanks so much for the content
Hey, thanks for giving me a good explanation on what cache hits/misses were. I've seen it being tossed around but never knew what it meant until now.
AMAZING!!!
Waiting to watch the rest of this series
thx!
Good Stuff, my man! The explanation is very clear and the dry humor is appreciated. I went into this video not knowing what a contiguous array was and now I have an idea of what it is.
Question; I understand that the L1, L2, and L3 caches reside on the CPU itself. Is there a typically a controller on the CPU like a northbridge? Or is it the CPU itself that access the caches hence the low latency; no middle man.
That's awesome! That's right, caches typically reside on the CPU. They're also built with a different kind of memory (SRAM), faster. Northbridge is the interface between CPU & main memory and resides on motherboard. That's my understanding anyway.
This is explained so clearly, I'm now going to binge watch your videos 😃 Thanks to YT for recommending me your channel. Subscribed! 🌟
I don't remember I watched this video before until I saw the L1/2/3 Cache example. The drawing is making the video so interesting. Now I come back for the new videos after finishing my algorithm final exam!
Absolutely loved it. Just the right way to explain a concept top to bottom. Keep it up
I love how he goes into depth of things, please continue your great efforts sir 🔥
Arrays are also slow when you have multiple threads, each bound to its own CPU, trying to access a global array. Suppose you have an array of size 4 int32_t, and 4 threads labeled 0 to i. The i th thread accesses the i th index in the array and modifies it repeatedly. This will cause major slowdowns as each modification will mark the cache of the other 3 threads/CPUs as modified, and each thread will have to do extra work to update their cache, even though the value that the thread cares about isn't being modified. This essentially makes the parallel code sequential. A linked list would be much better to use here since the memory locations will not be adjacent to each other, or each thread can modify a local variable and only write to the array at the end.
I have code that uses multiple threads to generate large arrays using perlin noise, and get near perfect scaling with threads. If you were doing something that multiple threads had tons of modifications, the L3 cache would still be valid, as that is shared between cores, so it wouldn't be that big of an issue. The bigger issue would be multiple threads constantly updating the same data causing race conditions, or bizarre behavior due to how memory reads and writes work.
Holy f. This is so good, youtube finally recommend me something that worth my time. Please, release more episode!!!
Second video in the series is the linked list one.
Loved this video! Will enjoy watching the whole series definitely.
This was amazing. THANK YOU. More like this for Javascript. Keep it coming and don't stop!
I wasn’t ready for it to be over!
I have a final tomorrow over this stuff and this video just happened to pop into my recommended. Probably cause I was googling virtual memory, caching, etc. Super informational video, and I was able to study and be entertained at the same time. I’m a fan 👍🏼
Good luck on your final!
This is a very great high-level view of arrays and CPU caching! I wish I had this video as an introduction when I was taking my Computer Systems class in college!
Great explanation. Clear and concise. Thanks!
But why is the code example from the very start of the video faster than the other example? I feel like that wasn't covered or I missed the point.
Youness covered it well, but I left it open as sort of an "exercise for the viewer". Kinda wanted the video to be in depth enough that you could answer it yourself.
@@simondev758 Leaving as an exercise to the viewer is fine, but as a suggestion for the format it would be good to circle back to the question at the end of the video and call it out. The way it's structured now it seems like the question is just forgotten about.
Great feedback Mike, 100% agree! Tried it out but next time I'll make sure to close the circle.
One is accessing the array in row major order, and the other is accessing it in column major order. The top one is faster because the memory is being accessed in a contiguous way, which means you'll get a lot of cache hits (very fast, going to main memory much less). The bottom is is NOT accessing memory in a contagious way, meaning every access is a cache MISS. en.wikipedia.org/wiki/Row-_and_column-major_order
@@bonehelm I still don't get it, both FOR starts looping on x and then y. So both should have the same speed. The only difference here is that on the first one you do the multiplication before the addition... And on the second one the other way around... And it doesn't seems to be a continuous problem here....
Even if I know this topic, your video was so interesting that time has passed unnoticed and I watched whole video. Wow
Awesome! Looking forward to this series :)
It's really not easy teaching about memory and data structures without the audience falling asleep, but you've done a great job!
Unfortunately JS arrays are messy and not exactly contiguous... :(
Hah yeah, I actually had a small section on JS arrays in there just to clarify about them, but cut it due to time (and laziness).
You're totally right, they're non-contiguous "array-like" objects. The TypedArray is closer to what you'd get in C++ or something.
Man. Your channel (even i don't use js so much) is freaking awesome!! I would buy your course or book without hesitation! Thank you!
No courses at the moment, I just put it all online for free :)
Thank you so much for creating this series, this is what ( even now ) I think more programmers ( and sometimes myself ) should pay attention to.
A simple and interesting explation of arrays, I came here to watch this video just to make sure I knew exactly how everything works. Having hardware classes with programming coursesreally, does help out a lot to understand computers, both on hardware and software level.
Problably the best vide have ever watched about how arrays works
Got it as a recommendation, instantly subscribed.
Superb series! thank you for the content!
your videos deserve a way bigger audience
Very helpful video, you explained everything clearly.. Reminded me of my university teacher back in the day. Thank you for the upload!
Awesome, if you have suggestions on topics to cover too, let me know
If you'd have been my tuition teacher I'd have been a topper in my class
Your way of explaining is so cool man👌
I'm inspired
Sir, your channel is a gem! thx for these videos
Already knew these concepts but still an amazing video, definitely helpful to cs students!
Great series!
Thanks for sharing this amazing tutorial!
Your videos are amazing! Thank you for this content
8:24 the animation made me smile
Loving this series man. Please keep going. Would love to see more of real world optimization like you did previously. But yeah fundamentals need to be cleared up first.
Btw I remember there was one cpu level hack which exploited this eager loading behavior in cpu. Some private part of memory was located by measuring the access speed, if the access was faster that meant the memory location just after current location was already cached by the cpu even though later on it was restricted to actually use due to other privacy constraints.
More real world optimization? Sure, I can probably swing that.
Sounds a lot like Meltdown: en.wikipedia.org/wiki/Meltdown_(security_vulnerability)
@@simondev758 ah yeah, its Meltdown.
Thanks man. Love your videos.
This video was amazing, you have my subscription
Arrays are fast, except when they aren’t ;)
Great video!
Well said!
Your content PLUS the video production = 🙌 SUBSCRIBED
Nice video, thanks for that!
love your explanation and examples..
Great job, I like your style. Easy like and sub 💯
Learned a lot. Thank you
6:02 snipe'ns a good job mate
Okey, you got me :) awesome videos!
For all those of you who are wondering why he accessed 1d array like if it is 2d, here is the real world example. Assume that in C++ you write a class that represents a matrix. You can go with 1d array or something like vector< vector< int > >, which you can think of as being 2d array. So why the hack then to use 1d array. There are many pros of using this approach. One of them is much faster work of constructor and destructor. Assume that you need to allocate memory for NxM matrix m. With 1d array it is one call of malloc (which asks the system at allocate a chunk of memory for you). With 2d array you should call malloc N times, once for each row. The same logic applies when you want to free memory. So now once we chose to represent our matrix as 1d array, assume that the user of our class wants to sum all of its elements. The user has no idea how did we choose to represent the matrix under the hood, he only knows that he can access an element of the matrix by using operator() as m(x, y). Your operator() in turn will have to calculate the position of an element by evaluating y * M + x and in the essence this will be exectly the same code as he showed in the video.
Awesome explanation, exactly what I had in mind when making the example.
Here king, you dropped this. . .
Omg is very useful, thanks a lot !
Nice video ! Thanks
Great video!
I want more!! Can't wait
thx!
i found this channel and its briliant
Hi Man. Very nice explanation. I was curious how you made the animations in your video.
I love this. Thank you for sharing.
thx
this was very helpful. thank you
np!
Well explained 👏👌👍
This video kicks ass.
Great video. I’m your fan for now
This is super nice!
more js content sir love it❤️ thank you
Your videos are awesome
excellent explanation! new sub!
thanks simon
You are my guru man
This blew my mind
Wow, man. I mean literally you just made it simple; not like other people who go through so much technical stuff and use buzz words.
I mentored a junior guy recently who did that, spoke entirely in jargon and buzzwords. I always wondered if he specifically practiced doing that.
Took me a good minute to find the difference between the 2 codes.
Awesome Stuff!
ty!
Awesome content ❤❤
My only formal training in programming is an elective course in C in college. I've loved it so much I end up writing device drivers for baremetal code running on top of ARM Cortex M processors as a hobby. There is no substitute for learning the fundamentals. It pains me to see some universities starting Computer Science students with a course in Java...
My first exposure to programming was Java in my intro to computer science class heh :P
Some people are just naturally good at logic and programming. We can count ourselves in that group
Great video 🔥👍
thanks!
There are pros and cons to this worth noting. It can be a valid form of redundancy to have an array as a 'look-up' to speed up data coming from a query in a relational database (rather than hitting the query over and over). That helps performance sometimes. However, the cache vulnerabilities can be exploited. An array does not have the same benefits of a linked-list in terms of being able to specify pointers for pass by address versus pass by reference. Also though, in some languages a linked list can be a problem as it needs objects, and that means garbage collection (Java) can happen at anytime, thereby making performance hard to predict and sometimes rather stuttering.
How does the processor look up data in the L-caches? I thought it was looking not for specific data, but for whatever data is in a specific data address. Do the L-caches keep the data alongside the address of that data in memory, where it came from?
Great video. You may have forgotten to revisit and explain in detail the code at the start though...
Yes... yes I did heh. Answer is pinned.
I just subbed. I will be checking out your videos.
I liked this channel so far. Keep making please...,🤩
Amazing channel
Thanks!
Had a chair on advanced computer architecture, this covered some weeks on a 10 min video. Wish I had this kind of resources back then. Also had to make a simulator with several caching sizes and strategies, good times 😂
Ooh that simulator sounds kinda fun to play with.
More of this please
Working on the next one right now actually.
Thank you)))
This was really clear and easy to understand, thanks
Thanks! I couldn't understand cache misses or contiguous arrays before your video. It felt like 3Blue1Brown of Computer Science
I just applied this on my internship and I solved a serious bottleneck!!! Thanks Simon
That's really cool! What kind of problem were you solving?
I optimized some existent numerical C++ code (for signal processing) from 420ms per iteration to 45ms, but the goal was 30ms per iteration. There is a giant nested for loop that was taking 44ms to run. So I applied the change specified in the video to reduce cache misses. Now it's taking 22ms. Maybe I could further optimize it by writing a special data structure (probably just a linked list), but that's good enough for the manager by now and he has other priorities for me.
Great explanation, thanks for your effort
I hope to see future videos on how javascript garbage collection work behind the scenes
Ooh that'd be an interesting subject.
I think it uses the reachability idea. If there is no way a part of memory can be reached it will be garbage collected.
They didn't use reference count approach because that doesn't handle 2 pieces referencing each other but are completely isolated and not reachable.
Perfect!
Never even saw the difference in those highlighted for loops in the beginning, until I saw the answer :(
Great video! But I still do not understand the Intro example, is the array in the bottom a dynamic array or just the top one a hash table?
array
May you tell me which recorder and editing software you use, Because mine are completely bonkers.