5 ms·

Here's a question: How often does this matter? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory acces

Here's a question: How often does this matter? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating them for that reason only (assuming that there is any non-perf reason to stick with them) is a premature optimization. But if you ARE optimizing, yeah, you need to think about how often worst-case occurs. Because big O only tells you about worst-case. NOT the average.

cdavid 10y ago
Memory contiguity may be the most fundamental thing to keep in mind when doing numerical computing, for example.
- qwertyuiop924 10y ago
  Okay, so now I know.
SamReidHughes 10y ago
Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.
- qwertyuiop924 10y ago
  Oh. Sorry.
timmytokyo 10y ago
In game dev, it often matters a lot. The difference between code that takes cache performance into account and code that does not is often measured in frames per second.
corysama 10y ago
A cache miss isn't noticeable by a human. Code that cache misses a lot runs 10-100x slower than code that takes into consideration that it's running on a physical machine and not an abstraction. That is very noticeable by humans. Even when your data structures and algos are designed with a nice O(logN), it's very noticeable when one program bogs down with 1/6 the data compared to another. I work in games, so the story I tell new kids is: The PlayStation2 ran at 300Mhz and a cache miss would cost you 50 cycles. The PlayStation3 ran at 3200Mhz and a cache miss would cost you 500 cycles. So, if you are cache missing a lot, your PS3 game will run as if it were on a PS2. In other words, not paying attention to cache make your computer run like it's 10 years older than it is. You paid for a modern machine, but you are getting the results of a Craigslist junker. This is true outside of games. It's the reason 4x2Ghz cellphones struggle to run seemingly simple apps. It's a big part of the reason people struggle to orchestrate armies of servers (distributed computing is easier when it's 90% less distributed). Is it really harder to work with the cache system instead of ignoring it? Yeah, it requires a tiny bit of study an a little bit of planning. In contrast, the theme I see a lot online is to completely dismiss physical reality in favor or theory. And, the theme I see almost universally in the students (and many senior engineers) I interview is complete ignorance of the very existence of cache and it's effects on the code they write. It's very concerning...
- qwertyuiop924 10y ago
  No, I don't deny it's important to know that cache misses exist, and what they can do: to the contrary, it's vital. However, in 90% of applications, it's not going to matter, because those applications are spending hundreds of cycles waiting anyways: Disk or network IO, user input, all that stuff is way slower than a cache miss. If you're writing a video game, or a database, or other software with very high soft-realtime speed requirements, or heavy data access, by all means, optimize to avoid cache miss. But if you're writing a company-internal Rails app, nobody's going to notice, even if you're getting cache miss after cache miss. Which you probably won't. Actually, if your language isn't compiled, a cache miss is the least of your worries, perf-wise. And now I've got to see if I can optimize my code to avoid cache misses. But the code's in Scheme, so unless the initial access cost is amortized, I'm already doomed...
malisper 10y ago
This advice applies a ton to databases. At my job, our application is heavily disk i/o bound, with a database query typically taking several seconds. I benchmarked how different sorting the rows in our db by time would be compared to our current layout (partially sorted by user, partially sorted by time, which was completely accidental). Sorting by time benchmarked ~10x faster, which is absolutely huge.
- qwertyuiop924 10y ago
  Yeah, heavy data access is where this matters.
pmelendez 10y ago
In games, critical systems and high traffic backend systems it means a lot.
- qwertyuiop924 10y ago
  That I could guess. My point is that most code isn't in high traffic backend systems and games.
  - TillE 10y ago
    There are a million things that a person writing a boring CRUD web app doesn't need to know. But if you want to be a good programmer, you should probably understand how a computer works.
    - qwertyuiop924 10y ago
      I didn't say you shouldn't. I just asked how often that kind of performance optimization mattered. The world is not comprised only of CRUD and situations where that kind of perf matters. But I do agree that even if you don't have to worry about cache latency for every single thing you write, it is something you should know about.
omgtehlion 10y ago
> How much do those few useconds really matter There is at least one area where even a split micro will cost you millions. P.S.: and even in consumer apps there microseconds here and there add up and then user will have overall sluggish experience.

cdavid 10y ago

Memory contiguity may be the most fundamental thing to keep in mind when doing numerical computing, for example.

qwertyuiop924 10y ago
Okay, so now I know.

SamReidHughes 10y ago

Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.

qwertyuiop924 10y ago
Oh. Sorry.

timmytokyo 10y ago

In game dev, it often matters a lot. The difference between code that takes cache performance into account and code that does not is often measured in frames per second.

corysama 10y ago

A cache miss isn't noticeable by a human. Code that cache misses a lot runs 10-100x slower than code that takes into consideration that it's running on a physical machine and not an abstraction. That is very noticeable by humans. Even when your data structures and algos are designed with a nice O(logN), it's very noticeable when one program bogs down with 1/6 the data compared to another. I work in games, so the story I tell new kids is: The PlayStation2 ran at 300Mhz and a cache miss would cost you 50 cycles. The PlayStation3 ran at 3200Mhz and a cache miss would cost you 500 cycles. So, if you are cache missing a lot, your PS3 game will run as if it were on a PS2. In other words, not paying attention to cache make your computer run like it's 10 years older than it is. You paid for a modern machine, but you are getting the results of a Craigslist junker. This is true outside of games. It's the reason 4x2Ghz cellphones struggle to run seemingly simple apps. It's a big part of the reason people struggle to orchestrate armies of servers (distributed computing is easier when it's 90% less distributed). Is it really harder to work with the cache system instead of ignoring it? Yeah, it requires a tiny bit of study an a little bit of planning. In contrast, the theme I see a lot online is to completely dismiss physical reality in favor or theory. And, the theme I see almost universally in the students (and many senior engineers) I interview is complete ignorance of the very existence of cache and it's effects on the code they write. It's very concerning...

qwertyuiop924 10y ago
No, I don't deny it's important to know that cache misses exist, and what they can do: to the contrary, it's vital. However, in 90% of applications, it's not going to matter, because those applications are spending hundreds of cycles waiting anyways: Disk or network IO, user input, all that stuff is way slower than a cache miss. If you're writing a video game, or a database, or other software with very high soft-realtime speed requirements, or heavy data access, by all means, optimize to avoid cache miss. But if you're writing a company-internal Rails app, nobody's going to notice, even if you're getting cache miss after cache miss. Which you probably won't. Actually, if your language isn't compiled, a cache miss is the least of your worries, perf-wise. And now I've got to see if I can optimize my code to avoid cache misses. But the code's in Scheme, so unless the initial access cost is amortized, I'm already doomed...

malisper 10y ago

This advice applies a ton to databases. At my job, our application is heavily disk i/o bound, with a database query typically taking several seconds. I benchmarked how different sorting the rows in our db by time would be compared to our current layout (partially sorted by user, partially sorted by time, which was completely accidental). Sorting by time benchmarked ~10x faster, which is absolutely huge.

qwertyuiop924 10y ago
Yeah, heavy data access is where this matters.

pmelendez 10y ago

In games, critical systems and high traffic backend systems it means a lot.

qwertyuiop924 10y ago
That I could guess. My point is that most code isn't in high traffic backend systems and games.
- TillE 10y ago
  There are a million things that a person writing a boring CRUD web app doesn't need to know. But if you want to be a good programmer, you should probably understand how a computer works.
  - qwertyuiop924 10y ago
    I didn't say you shouldn't. I just asked how often that kind of performance optimization mattered. The world is not comprised only of CRUD and situations where that kind of perf matters. But I do agree that even if you don't have to worry about cache latency for every single thing you write, it is something you should know about.

omgtehlion 10y ago

> How much do those few useconds really matter There is at least one area where even a split micro will cost you millions. P.S.: and even in consumer apps there microseconds here and there add up and then user will have overall sluggish experience.