6 ms·

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-

by vient 3y ago

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?

CyberDildonics 3y ago
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.
- vient 3y ago
  > just profile and find hot spots 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.
  - CyberDildonics 3y ago
    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.
    - vient 3y ago
      > 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.
      - CyberDildonics 3y ago
        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.
dragontamer 3y ago
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.
- gpderetta 3y ago
  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.
- vient 3y ago
  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.
  - dragontamer 3y ago
    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.

by vient 3y ago

CyberDildonics 3y ago

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.

vient 3y ago
> just profile and find hot spots 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.
- CyberDildonics 3y ago
  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.
  - vient 3y ago
    > 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.
    - CyberDildonics 3y ago
      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.

dragontamer 3y ago

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.

gpderetta 3y ago
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.
vient 3y ago
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.
- dragontamer 3y ago
  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.