Memory, Cache Locality, and why Arrays are Fast (Data Structures and Optimization)

Why is the first loop 10x faster than the second, despite doing the exact same work?

Follow me on:

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

[simondev]

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.

[WojtekKozowski]

“why the code on the top runs faster? watch the video and find out” ...and no mention of the code again. Otherwise nice video.

[User-tyml]

Best Director Award goes to Simon, i have never seen such a beautiful explanation without answering question, amazing!!!!

[Chadderbox]

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.

[Rssks]

Wow this video is almost 10 minutes but it felt like 1 minute! I really enjoyed it (Y) will definitely rewatch this later today!

[sukkrad]

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!

[AllAboutCode]

4:20 you ain't cheap bruh, your content is way better than expensive internet courses.

[MrLazini]

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!

[osambrojevanisam]

This has got to be the best educational video on youtube, fuckimg amazing

[vitalino]

"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 😂

[xeridea]

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.

[cuteswan]

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.

[eddiemuller]

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.

[brucea]

I'm glad I'm not the only one who noticed he didn't answer the original question. I already knew most of what he discussed (how memory and the caches work) but he didn't explain how that applied to the question he posed. The reasonable answer (as I suspected before I watched the video) is that one piece of code accesses the data by rows and the other by columns. The cache would load the data by rows which would make the code that accesses the data by rows faster since there would be a lot of cache misses for the code that accessed the data by columns.

[pist]

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... :(

[Dionny]

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.

[EpsilonKnight]

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.

[nathanp]

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 👍🏼

[thegibusguy]

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.

[mahmoudhammmad]

AMAZING!!!
Waiting to watch the rest of this series