4 ms·

> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I ha

> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I have seen such factors proven as responsible for poor performance This particular assertion does not seem to be well-founded. The importance of spatial and temporal locality to software performance on modern hardware is a singular obsession of data-intensive software architectures. Nor is it difficult to measure, these are some of the highest impact optimizations you can make assuming the code isn't naive. There are perf counters and such but the majority of poor locality is visible via simple code inspection. You don't need perf counters until you are doing serious performance engineering. Locality optimization tends to be architectural in nature. If you do not design your software to have good locality characteristics then it will be complex to fix later. An argument can be made that it isn't worth the cost to fix software designs with poor locality after the fact, but the centrality of locality to software optimization is not controversial.

lmm 3y ago
Anything that can't be objectively measured will inherently be controversial. You claim you can see poor locality via code inspection; will other people who inspect the same code reach the same conclusions? Why should we believe you rather than anyone else?
- jmoss20 3y ago
  Agreed with the general point, but it doesn't apply here. Memory locality can be objectively measured (e.g. with last level cache miss counters), and parent comment is correct besides -- it's usually plain to see in the code. There are mysterious boogiemen in performance optimization, but this isn't really one of them.
  - mejutoco 3y ago
    I am happy (good) science does not take the "is obvious" claim as sufficient, and instead focuses on proving things with objective facts. I am not saying these cannot be plain to see in the code, but the best standard IMO is still to measure before and after the optimization. IMHO, again, you can skip that step, but then other people might rightfully ask you what proof you have that the optimization is faster (I would).
    - meheleventyone 3y ago
      Some of these architectural decisions benefit from being made early. That doesn’t mean you can’t objectively defend them but it does mean the measure, optimize, measure loop you might use on a mature codebase to optimize a hot path can’t be the only standard.
    - jmoss20 3y ago
      It's a matter of economy-- if you spent all day measuring obvious things you'd never get anything done. Clearly which things you choose to measure should be a function of how certain you are about them, and how much you stand to lose if you get them wrong.
anonymoushn 3y ago
Well, it's a lot of work to prove to someone who doesn't do this sort of thing that they have this sort of problem. And it's a lot less work to say that there is this sort of problem. So he sounds right to me.
- meheleventyone 3y ago
  A nice easy one is to benchmark trivial examples for people. For example summing an array of numbers in JS. Have examples of four levels of indirection between objects down to one level, straight numbers in a standard JS array and the same in a TypedArray. This pretty clearly demonstrates the gains that can be had.
sdenton4 3y ago
You need perf measurements to understand the impact. It sounds like you're saying that it's a massive time stick to fix the problems, so it had better be a measurable impact to understand the ROI. I've definitely seen careful memory management make a huge difference in custom RNN code, so don't doubt it can make a difference, but I expect it matters mainly when it's part of a very tight loop.
- jandrewrogers 3y ago
  Unlike some other optimizations, the effects of locality optimization are usually not local. The reduction in cache and bandwidth pressure makes everything run better. These are common optimizations in e.g. databases, even shaving a few bytes off of key data structures can result in system-wide gains of 5-10% performance just from the cache pressure reduction resulting from a seemingly innocuous reduction in data size. You don’t need to measure it to know it will have impact, the relationship between reducing cache pressure and performance is pretty direct and repeatable. Spatial locality is straightforward, temporal locality is a bigger engineering commitment. A canonical example of locality optimization is thread-per-core architectures versus classic multi-threading architectures. By random luck, I was around when thread-per-core architectures were first developed to improve efficiency on many-core processors (on supercomputers). Instant 10x performance improvement on the same hardware. By comparison, aggressive vectorization with AVX-512 might buy you 3x improvement. Locality optimizations are the highest leverage optimization we can do today. It does require disciplined software architecture. There are limits to locality optimization in real systems. If you are doing a good job of it, you frequently run out of memory bandwidth at some point. That’s a pretty good outcome.
hinkley 3y ago
The first memorable locality problem I ever solved, I had clocked a function at 10% overall cpu time. The more I looked at it, the more I realized we were calling it way too often. It wasn’t allocating a lot of memory, it was just crunching a bit of data. A bit of jiggling of the call structure above it and it goes from 2 invocations per call to one. So almost exactly half as many calls overall. I ran my end to end benchmark again, expecting 4-6% improvement in run time. I got 20%. Twice what I would have expected to get by commenting the function out entirely. Few years later, similar situation. Operation taking about 5 times as long as we were allowed. Function A gets a list from the database. Function B gets the same list. I don’t recall what percent of the overall time this was, but it was a tall tent pole and obvious waste. Something like 30%. As a first course for a longer optimization engagement, I changed the method signatures to take the list and return a result, looked up the list once in the common parent function. Best case I figured a 20% reduction, which is still slow enough I can use the stopwatch function on my phone to estimate the improvement at the UI. I didn’t get 20%, I got 90%. So I went from 5x over the target to half, in one change. Unfortunately even this result didn’t convince some people they were barking up the wrong tree with respect to performance problems. Right about the time of the first experience I had been learning an ugly truth: profilers lie. They aren’t the floodlight people think they are. They’re a book of matches in the dark. They reveal part of the picture, and cast as many shadows as they do light. You have to fill in a lot of gaps yourself, and that takes mechanical sympathy and more than a little stubbornness. Hardware counters narrow that gap a lot, but they still aren’t perfect, and a lot of languages seem not to use them.
- nerpderp82 3y ago
  Performance (Really) Matters by Emery Berger talks a lot about layout. https://www.youtube.com/watch?v=7g1Acy5eGbE https://www.youtube.com/watch?v=7g1Acy5eGbE And the topic of Coordinated Omission, "How NOT to Measure Latency" by Gil Tene https://www.youtube.com/watch?v=lJ8ydIuPFeU https://www.youtube.com/watch?v=lJ8ydIuPFeU Injection slowness into an application to measure the relative impact of that portion of the application has really worked well for me.
  - hinkley 3y ago
saagarjha 3y ago
Most code is naive. FWIW, in my experience most people who just look around for poor code locality focus on things that don't actually matter, while the most expensive misses (when you actually profile and decide you care about them) end up in surprising places, or they were just missed in someone's quest to reorder all the structs they see in the codebase.
- meheleventyone 3y ago
  It’s memory not code locality (do you mean in the instruction cache or something else?) that matters. The problem for a naive solution with poor memory locality is that the memory locality issue is more akin to a rewrite to a faster language. The performance gap left on the table can be significant but the need for it not show up in profiles because everything is slow.
  - saagarjha 3y ago
    That is very often the case, yes.

lmm 3y ago

Anything that can't be objectively measured will inherently be controversial. You claim you can see poor locality via code inspection; will other people who inspect the same code reach the same conclusions? Why should we believe you rather than anyone else?

jmoss20 3y ago
Agreed with the general point, but it doesn't apply here. Memory locality can be objectively measured (e.g. with last level cache miss counters), and parent comment is correct besides -- it's usually plain to see in the code. There are mysterious boogiemen in performance optimization, but this isn't really one of them.
- mejutoco 3y ago
  I am happy (good) science does not take the "is obvious" claim as sufficient, and instead focuses on proving things with objective facts. I am not saying these cannot be plain to see in the code, but the best standard IMO is still to measure before and after the optimization. IMHO, again, you can skip that step, but then other people might rightfully ask you what proof you have that the optimization is faster (I would).
  - meheleventyone 3y ago
    Some of these architectural decisions benefit from being made early. That doesn’t mean you can’t objectively defend them but it does mean the measure, optimize, measure loop you might use on a mature codebase to optimize a hot path can’t be the only standard.
  - jmoss20 3y ago
    It's a matter of economy-- if you spent all day measuring obvious things you'd never get anything done. Clearly which things you choose to measure should be a function of how certain you are about them, and how much you stand to lose if you get them wrong.

anonymoushn 3y ago

Well, it's a lot of work to prove to someone who doesn't do this sort of thing that they have this sort of problem. And it's a lot less work to say that there is this sort of problem. So he sounds right to me.

meheleventyone 3y ago
A nice easy one is to benchmark trivial examples for people. For example summing an array of numbers in JS. Have examples of four levels of indirection between objects down to one level, straight numbers in a standard JS array and the same in a TypedArray. This pretty clearly demonstrates the gains that can be had.

sdenton4 3y ago

You need perf measurements to understand the impact. It sounds like you're saying that it's a massive time stick to fix the problems, so it had better be a measurable impact to understand the ROI. I've definitely seen careful memory management make a huge difference in custom RNN code, so don't doubt it can make a difference, but I expect it matters mainly when it's part of a very tight loop.

jandrewrogers 3y ago
Unlike some other optimizations, the effects of locality optimization are usually not local. The reduction in cache and bandwidth pressure makes everything run better. These are common optimizations in e.g. databases, even shaving a few bytes off of key data structures can result in system-wide gains of 5-10% performance just from the cache pressure reduction resulting from a seemingly innocuous reduction in data size. You don’t need to measure it to know it will have impact, the relationship between reducing cache pressure and performance is pretty direct and repeatable. Spatial locality is straightforward, temporal locality is a bigger engineering commitment. A canonical example of locality optimization is thread-per-core architectures versus classic multi-threading architectures. By random luck, I was around when thread-per-core architectures were first developed to improve efficiency on many-core processors (on supercomputers). Instant 10x performance improvement on the same hardware. By comparison, aggressive vectorization with AVX-512 might buy you 3x improvement. Locality optimizations are the highest leverage optimization we can do today. It does require disciplined software architecture. There are limits to locality optimization in real systems. If you are doing a good job of it, you frequently run out of memory bandwidth at some point. That’s a pretty good outcome.

hinkley 3y ago

The first memorable locality problem I ever solved, I had clocked a function at 10% overall cpu time. The more I looked at it, the more I realized we were calling it way too often. It wasn’t allocating a lot of memory, it was just crunching a bit of data. A bit of jiggling of the call structure above it and it goes from 2 invocations per call to one. So almost exactly half as many calls overall. I ran my end to end benchmark again, expecting 4-6% improvement in run time. I got 20%. Twice what I would have expected to get by commenting the function out entirely. Few years later, similar situation. Operation taking about 5 times as long as we were allowed. Function A gets a list from the database. Function B gets the same list. I don’t recall what percent of the overall time this was, but it was a tall tent pole and obvious waste. Something like 30%. As a first course for a longer optimization engagement, I changed the method signatures to take the list and return a result, looked up the list once in the common parent function. Best case I figured a 20% reduction, which is still slow enough I can use the stopwatch function on my phone to estimate the improvement at the UI. I didn’t get 20%, I got 90%. So I went from 5x over the target to half, in one change. Unfortunately even this result didn’t convince some people they were barking up the wrong tree with respect to performance problems. Right about the time of the first experience I had been learning an ugly truth: profilers lie. They aren’t the floodlight people think they are. They’re a book of matches in the dark. They reveal part of the picture, and cast as many shadows as they do light. You have to fill in a lot of gaps yourself, and that takes mechanical sympathy and more than a little stubbornness. Hardware counters narrow that gap a lot, but they still aren’t perfect, and a lot of languages seem not to use them.

nerpderp82 3y ago
Performance (Really) Matters by Emery Berger talks a lot about layout. https://www.youtube.com/watch?v=7g1Acy5eGbE https://www.youtube.com/watch?v=7g1Acy5eGbE And the topic of Coordinated Omission, "How NOT to Measure Latency" by Gil Tene https://www.youtube.com/watch?v=lJ8ydIuPFeU https://www.youtube.com/watch?v=lJ8ydIuPFeU Injection slowness into an application to measure the relative impact of that portion of the application has really worked well for me.
- hinkley 3y ago

saagarjha 3y ago

Most code is naive. FWIW, in my experience most people who just look around for poor code locality focus on things that don't actually matter, while the most expensive misses (when you actually profile and decide you care about them) end up in surprising places, or they were just missed in someone's quest to reorder all the structs they see in the codebase.

meheleventyone 3y ago
It’s memory not code locality (do you mean in the instruction cache or something else?) that matters. The problem for a naive solution with poor memory locality is that the memory locality issue is more akin to a rewrite to a faster language. The performance gap left on the table can be significant but the need for it not show up in profiles because everything is slow.
- saagarjha 3y ago
  That is very often the case, yes.