In general no, but the provided example depends on parallel memory accesses at the cache level, so cache effects can indeed come into play with instruction-level parallelism. Did you just miss this detail in the article, or are you suggesting it's wrong?
I vouched for your comment since I think it's interesting to see how discussion on a topic evolves over the years, but next time maybe consider leaving out the posts that didn't gain traction.
Reposts after about a year aren't considered a problem on Hacker News[0], but including those comes across as shaming OP for posting an often-posted article and makes finding the actually interesting discussions a bit annoying.
I don’t believe that’s the reason. I think it’s project management priorities.
It’s possible to write efficient code to this day, examples of very complicated software implemented that way are triple-A videogames. However, it’s relatively hard (and therefore expensive) on quite a few levels. Performance targets should be accounted in functional specs, all developers should be aware of these targets, software must be specifically designed for performance, people (or better yet, robots) should continuously profile software, project management should prioritize performance-related issues and bugs.
And another thing. The hardware performance progress between 1975 and 2005 was exponential, driven by rapid advancements in photolithography. In these decades, we observed quite a few times that for many software products it’s often a better strategy to ship sooner relying on hardware progress to “fix” the performance, compared to spending time and money on software optimizations. The hardware performance progress slowed down substantially around 2010. Still, we have a generation of people in all positions over the industry who learned their experience in these decades of exponential explosion of compute power.
There is a lot of good articles on cache effects, this is one of them. On the other hand, I've yet to find a good article on how to effectively find such cache-related issues in your programs, with perf for example. Can you suggest something on this matter?
Once you understand more about CPU caches you can usually just profile and find hot spots, then redo how memory is being accessed.
Making it work well is simple, you just need to access memory linearly/contiguously so the prefetcher can run ahead of your program and read it before you need it. Any time access patterns are skipping around memory it is going to be very slow relative to what the CPU can actually do, but it will mostly matter in the inner loops.
Do you mean "hot" in terms of CPU time? It may sound simple but in mature apps you don't have any obvious hot spots that you can look at. Code is complex enough so just reading it also won't give you clues.
> Making it work well is simple, you just need to access memory linearly/contiguously ...
In real apps you do not usually have some kind of heavy linear array processing, instead they work with thousands of different objects depending on input - a smart prefetching can help but again, it is hard to find cache issues when you don't have obvious hot spots.
Perf can take stack traces on cache misses but the problem is that they are taken "asynchronously" so they do not point on exact instruction which caused cache miss - it's hard to analyze those records afterwards.
Hope I clarified what I meant: you can easily pinpoint slow functions in your program, with all sorts of debug info, but I don't know of a way to do the same efficiently for caching issues.
It may sound simple but in mature apps you don't have any obvious hot spots that you can look at.
This is a defeatist attitude that is basically saying "it's impossible". I'm not sure what your expectations are, but people have been using profilers for a long time, so saying they magically don't work because your program is special is ridiculous.
In real apps you do not usually have some kind of heavy linear array processing, instead they work with thousands of different objects depending on input
This is again not true. If you have thousands of 'different objects' you should think about how you can replace them with a few different arrays of the data you are working on. This is not my idea, this is well worn performance advice.
a smart prefetching can help
It's not smart prefetching, it's just prefetching. If you access memory addresses next to each other sequentially, the prefetcher will grab memory ahead of the CPU and your program won't have to wait for it.
it is hard to find cache issues when you don't have obvious hot spots.
I don't think that's true at all, it just isn't important to deal with cache misses/pointer indirection unless it is repetitive. Memory access patterns are never this confusing to me, but I also plan for it ahead of time now that I have experience dealing with it.
Perf can take stack traces on cache misses but the problem is that they are taken "asynchronously" so they do not point on exact instruction which caused cache miss - it's hard to analyze those records afterwards.
You don't need an exact instruction and it probably wouldn't help you anyway. Memory access isn't a matter of a single instruction, it is about how the memory is layed out in the first place.
you can easily pinpoint slow functions in your program, with all sorts of debug info, but I don't know of a way to do the same efficiently for caching issues.
Once you weed out allocating memory in hot loops and slow IO, your slow functions and cache issues are probably the same thing.
Also you are contradicting yourself here. You said:
It may sound simple but in mature apps you don't have any obvious hot spots
Then:
you can easily pinpoint slow functions in your program
If you have source code on github and you can tell me what lines are slow, I can probably tell you why.
> This is a defeatist attitude that is basically saying "it's impossible"
I did not mean it like that. I am using profilers to find slow code successfully as well. The problem is that such profiler won't find you a spot where one object is slowly loaded from memory because CPU was not smart enough to prefetch it in advance, even if you profile with something as precise as Intel PT.
> saying they magically don't work because your program is special is ridiculous
I did not say that. Once again, I am talking about specific question of finding cache stalls in your program, not generic profiling.
> If you access memory addresses next to each other sequentially
It is of course beneficial to do it that way but it may be not trivial when you have complex relationships between different objects. Besides, the point of profiling is to efficiently find where you may need to do such optimizations, just saying "layout your objects optimally" does not help.
> You don't need an exact instruction and it probably wouldn't help you anyway
Exact instruction will help me to understand what specific object caused memory stall. Maybe this is indeed not that important.
> Also you are contradicting yourself here
I meant that you can easily find slow functions if there are any. If instead you have functiions a, b, c called sequentially and working same amount of time, you don't have obvious place to look at - if function b can be optimized by introducing cache awareness but other ones cannot, profile won't help you.
I think the big picture here is that you are thinking it's difficult to notice cache misses and I think it isn't. Any time you are dereferencing pointers, working with heap allocated objects, vtables etc you can assume they are cache misses.
If they are in a hot loop they could matter. Really any time you aren't running through contiguous memory or dealing with stack variables you should assume there are lots of cache misses. Your entire program is full of cache misses until you specifically structure them out.
Advance profilers will access hardware performance counters that give insights.
For example, if your instructions are (on average), waiting 10ns per load/store, you know that you're operating at the L2 cache level or so.
Although it might be easier to get the count of L1 cache misses, and L2 cache hits instead. :-) Pretty much every event at the lowest level can be counted (although its sampling: only every 1/1000th instruction or so gets profiled when these profilers get turned on).
When you see that some branch is mostly unpredicted, you know to focus on that branch/if statement to figure out how to get the branch predictor to work.
If you see L1 misses or L2 misses, maybe you know to shrink the data. Etc. etc.
perf will give you exactly the number of misses in L1, L2 and L3 if asked (and the total number of accesses). It can also annotate the asm so you can spot the hot loads.
Yes but this level of info is too coarse. It is not sufficient to know your level of L1/L2/L3 misses if your app has megabytes of code and gigabytes in heap. As I said in adjacent response, I tried to record cache misses with `perf` but the info produced by `perf report` is confusing at best - I did not manage to find any good tutorial on debugging cache misses in that way.
You know about the --control=fifo option of perf, right?
You can turn perf on, and off, using that fifo. You can use this to programmatically enable the profiler for individual sections of code, and then disable it for the other sections.
-----------
Are you coarse-profiling your code first? Have you run gprof first and figured out which section of code you're focusing on?
EDIT: Using perf alone (though IMO a bad idea), you can also get instruction counts. You should be focusing on the instructions that are run the most. But because instructions take a variable amount of time, what you really want to be doing is profiling using a timer-based method (ex: gprof) and narrowing your search through that instead. But sometimes, the instruction-based approach is also useful.
Manually enabling/disabling perf is too slow when you want to profile a part that takes <1ms to execute, but it is an option if nothing better exists. It would be great if you could just isolated interesting code in microbenchmark but we all know that this will skew results.
About code execution profiling, I usually use Intel PT so yes, I know where I want to look.
> I did not manage to find any good tutorial on debugging cache misses in that way.
Saddly this is very true. There is a lack of good performance investigation information out there. And pref while very useful is not really a beginner tools.
In your case, you want an "annotated" profile. Where perf will annotate the source code with the even, and basically pin-point which part of your code is producing the offending events (in this case the cache misses).
If you really want to dig deep, i can't recommend intel Vtune. Only works with intel cpu (i think ?), but is the best tool in you want to understand performance at a deeper level.
The problem with cache misses specifically is that perf can't point an event to its exact location so you may get a high rate of cache misses on instruction that does not even work with memory, like jump, so you need to look what gets executed before that instruction and what looks like probable source there. I am interested if there are any more efficient approaches than this.
Perf can. But you need to massage it a bit. Out of the box , perf uses a bunch of generic performance counter which maybe not be the best.
Intel cpu's have a a collection of "precisise" events which record the exact originating/offending instructions. If you use those it should fix your problem
Pmu-tool by default uses precise events when available
You might want to look at https://icl.utk.edu/papi/ . It's a generic library which abstract the details of specific cpu arch and aims to provide a single unify view of performance counters.
I think somewhere in there you can see how perf translate counters to intel (or AMD) specific one.
Hmmm a fellow lover of CPU performance counter :).
Couple of points :
> although its sampling: only every 1/1000th instruction or so gets profiled when these profilers get turned on
Not always, modern CPU ( intel's at least, not sure about arm and AMD), you can control the recorded event and the sampling event (and sampling rate) seperatly. So you can actually both record load/store misses and sample on cache misses to avoid loosing any events.
You still get some sampling artifacts like the fact that the triggering of event is biais in favor or start of Basic block or that some events can be shadowed by others ...
> if your instructions are (on average), waiting 10ns per load/store, you know that you're operating at the L2 cache level or so.
Not always, sometime if you have a chain of depends loads the resolution time of the load has more to do with data dependencies.
Intel's CPU has a collection of "precise" events, around caches events, so it's easy to just deduce precisely where a given loads resolves most of the time by doing the ration of L-cache misses/L cache hit dirrectly)
> When you see that some branch is mostly unpredicted, you know to focus on that branch/if statement to figure out how to get the branch predictor to work.
The hardest part here is to understand if the branch is unpredicted because it's unpredictable or because the branch predictor is not performing as expected : Branch predictors are limited resources, they can't predict all branch all the time.
This is one of maybe 10 articles that made me a decent low-level programmer when I got a job in computer graphics 10 years ago. Shockingly relevant (cache tradeoffs haven't grown significantly since core/lane/memory bandwidth considerations haven't changed in CPUs). I still regularly send this around to people getting started.
IIRC, collisions on the address (key) overwrite the previous cache-line. Effectively, it's a most-recently-used "fully associative" structure. At least I think that's why the language seems to be a bit of a stretch.
I am not seeing it mentioned anywhere, but for people looking for a good starting point on "low-level" CPU performance debugging, intel's CPU top-down u-architecture method (https://www.intel.com/content/www/us/en/docs/vtune-profiler/...) is a good systematic way to understand where you CPU is speeding most of it's cycle.
They also have two tools which basically implement this analysis and spit a bunch of very useful metric that are actionable and very easy to understand
- Intel Vtune is a fantastic tool to start with. It's currently free to use, support most OSes and very friendly to use for beginner.
the methodology itself can be apply to any CPU which have good enough performance counter system.
I know perf supports ARM, but pmu-tools and vtune are x86 only as far as i know.
38 comments
[ 2.7 ms ] story [ 83.5 ms ] threadhttps://news.ycombinator.com/item?id=1094797
https://news.ycombinator.com/item?id=2209979
https://news.ycombinator.com/item?id=3321668
https://news.ycombinator.com/item?id=4382148
https://news.ycombinator.com/item?id=7852298
https://news.ycombinator.com/item?id=8778990
https://news.ycombinator.com/item?id=11189250
https://news.ycombinator.com/item?id=18963841
https://news.ycombinator.com/item?id=19359636
https://news.ycombinator.com/item?id=19469388
https://news.ycombinator.com/item?id=19492424
Reposts after about a year aren't considered a problem on Hacker News[0], but including those comes across as shaming OP for posting an often-posted article and makes finding the actually interesting discussions a bit annoying.
[0] https://news.ycombinator.com/newsfaq.html#reposts
I think it would be better if links were decorated with the number of upvotes and comments, so that one might chose what to read.
It’s possible to write efficient code to this day, examples of very complicated software implemented that way are triple-A videogames. However, it’s relatively hard (and therefore expensive) on quite a few levels. Performance targets should be accounted in functional specs, all developers should be aware of these targets, software must be specifically designed for performance, people (or better yet, robots) should continuously profile software, project management should prioritize performance-related issues and bugs.
And another thing. The hardware performance progress between 1975 and 2005 was exponential, driven by rapid advancements in photolithography. In these decades, we observed quite a few times that for many software products it’s often a better strategy to ship sooner relying on hardware progress to “fix” the performance, compared to spending time and money on software optimizations. The hardware performance progress slowed down substantially around 2010. Still, we have a generation of people in all positions over the industry who learned their experience in these decades of exponential explosion of compute power.
And there is also the cache prefetching that is pretty interesting: https://en.wikipedia.org/wiki/Cache_prefetching
Making it work well is simple, you just need to access memory linearly/contiguously so the prefetcher can run ahead of your program and read it before you need it. Any time access patterns are skipping around memory it is going to be very slow relative to what the CPU can actually do, but it will mostly matter in the inner loops.
Do you mean "hot" in terms of CPU time? It may sound simple but in mature apps you don't have any obvious hot spots that you can look at. Code is complex enough so just reading it also won't give you clues.
> Making it work well is simple, you just need to access memory linearly/contiguously ...
In real apps you do not usually have some kind of heavy linear array processing, instead they work with thousands of different objects depending on input - a smart prefetching can help but again, it is hard to find cache issues when you don't have obvious hot spots.
Perf can take stack traces on cache misses but the problem is that they are taken "asynchronously" so they do not point on exact instruction which caused cache miss - it's hard to analyze those records afterwards.
Hope I clarified what I meant: you can easily pinpoint slow functions in your program, with all sorts of debug info, but I don't know of a way to do the same efficiently for caching issues.
This is a defeatist attitude that is basically saying "it's impossible". I'm not sure what your expectations are, but people have been using profilers for a long time, so saying they magically don't work because your program is special is ridiculous.
In real apps you do not usually have some kind of heavy linear array processing, instead they work with thousands of different objects depending on input
This is again not true. If you have thousands of 'different objects' you should think about how you can replace them with a few different arrays of the data you are working on. This is not my idea, this is well worn performance advice.
a smart prefetching can help
It's not smart prefetching, it's just prefetching. If you access memory addresses next to each other sequentially, the prefetcher will grab memory ahead of the CPU and your program won't have to wait for it.
it is hard to find cache issues when you don't have obvious hot spots.
I don't think that's true at all, it just isn't important to deal with cache misses/pointer indirection unless it is repetitive. Memory access patterns are never this confusing to me, but I also plan for it ahead of time now that I have experience dealing with it.
Perf can take stack traces on cache misses but the problem is that they are taken "asynchronously" so they do not point on exact instruction which caused cache miss - it's hard to analyze those records afterwards.
You don't need an exact instruction and it probably wouldn't help you anyway. Memory access isn't a matter of a single instruction, it is about how the memory is layed out in the first place.
you can easily pinpoint slow functions in your program, with all sorts of debug info, but I don't know of a way to do the same efficiently for caching issues.
Once you weed out allocating memory in hot loops and slow IO, your slow functions and cache issues are probably the same thing.
Also you are contradicting yourself here. You said:
It may sound simple but in mature apps you don't have any obvious hot spots
Then:
you can easily pinpoint slow functions in your program
If you have source code on github and you can tell me what lines are slow, I can probably tell you why.
I did not mean it like that. I am using profilers to find slow code successfully as well. The problem is that such profiler won't find you a spot where one object is slowly loaded from memory because CPU was not smart enough to prefetch it in advance, even if you profile with something as precise as Intel PT.
> saying they magically don't work because your program is special is ridiculous
I did not say that. Once again, I am talking about specific question of finding cache stalls in your program, not generic profiling.
> If you access memory addresses next to each other sequentially
It is of course beneficial to do it that way but it may be not trivial when you have complex relationships between different objects. Besides, the point of profiling is to efficiently find where you may need to do such optimizations, just saying "layout your objects optimally" does not help.
> You don't need an exact instruction and it probably wouldn't help you anyway
Exact instruction will help me to understand what specific object caused memory stall. Maybe this is indeed not that important.
> Also you are contradicting yourself here
I meant that you can easily find slow functions if there are any. If instead you have functiions a, b, c called sequentially and working same amount of time, you don't have obvious place to look at - if function b can be optimized by introducing cache awareness but other ones cannot, profile won't help you.
If they are in a hot loop they could matter. Really any time you aren't running through contiguous memory or dealing with stack variables you should assume there are lots of cache misses. Your entire program is full of cache misses until you specifically structure them out.
For example, if your instructions are (on average), waiting 10ns per load/store, you know that you're operating at the L2 cache level or so.
Although it might be easier to get the count of L1 cache misses, and L2 cache hits instead. :-) Pretty much every event at the lowest level can be counted (although its sampling: only every 1/1000th instruction or so gets profiled when these profilers get turned on).
When you see that some branch is mostly unpredicted, you know to focus on that branch/if statement to figure out how to get the branch predictor to work.
If you see L1 misses or L2 misses, maybe you know to shrink the data. Etc. etc.
You can turn perf on, and off, using that fifo. You can use this to programmatically enable the profiler for individual sections of code, and then disable it for the other sections.
-----------
Are you coarse-profiling your code first? Have you run gprof first and figured out which section of code you're focusing on?
EDIT: Using perf alone (though IMO a bad idea), you can also get instruction counts. You should be focusing on the instructions that are run the most. But because instructions take a variable amount of time, what you really want to be doing is profiling using a timer-based method (ex: gprof) and narrowing your search through that instead. But sometimes, the instruction-based approach is also useful.
About code execution profiling, I usually use Intel PT so yes, I know where I want to look.
Saddly this is very true. There is a lack of good performance investigation information out there. And pref while very useful is not really a beginner tools.
In your case, you want an "annotated" profile. Where perf will annotate the source code with the even, and basically pin-point which part of your code is producing the offending events (in this case the cache misses).
If you really want to dig deep, i can't recommend intel Vtune. Only works with intel cpu (i think ?), but is the best tool in you want to understand performance at a deeper level.
Intel cpu's have a a collection of "precisise" events which record the exact originating/offending instructions. If you use those it should fix your problem Pmu-tool by default uses precise events when available
I think somewhere in there you can see how perf translate counters to intel (or AMD) specific one.
Couple of points :
> although its sampling: only every 1/1000th instruction or so gets profiled when these profilers get turned on
Not always, modern CPU ( intel's at least, not sure about arm and AMD), you can control the recorded event and the sampling event (and sampling rate) seperatly. So you can actually both record load/store misses and sample on cache misses to avoid loosing any events.
You still get some sampling artifacts like the fact that the triggering of event is biais in favor or start of Basic block or that some events can be shadowed by others ...
> if your instructions are (on average), waiting 10ns per load/store, you know that you're operating at the L2 cache level or so.
Not always, sometime if you have a chain of depends loads the resolution time of the load has more to do with data dependencies. Intel's CPU has a collection of "precise" events, around caches events, so it's easy to just deduce precisely where a given loads resolves most of the time by doing the ration of L-cache misses/L cache hit dirrectly)
> When you see that some branch is mostly unpredicted, you know to focus on that branch/if statement to figure out how to get the branch predictor to work.
The hardest part here is to understand if the branch is unpredicted because it's unpredictable or because the branch predictor is not performing as expected : Branch predictors are limited resources, they can't predict all branch all the time.
> Each memory chunk can be stored in any slot in the cache. Effectively, the cache operates like a hash table.
Don't hash tables typically have only a set number of buckets a given key can use, in contrast to a fully associative structure?
They also have two tools which basically implement this analysis and spit a bunch of very useful metric that are actionable and very easy to understand
- Intel Vtune is a fantastic tool to start with. It's currently free to use, support most OSes and very friendly to use for beginner.
- Intel pmu-tools (https://github.com/andikleen/pmu-tools) is basically command line version of Vtune.