4 ms·

Often you can get pretty good results from just knowing that cache misses are expensive and working from that point: Store together what is accessed together, u

Often you can get pretty good results from just knowing that cache misses are expensive and working from that point: Store together what is accessed together, use linear arrays to help prefetcher, prefetch manually if really needed (it usually isn't and the prefetch instruction isn't free), if your data is accessed effectively randomly try packing used parts into smaller amount of cache lines, etc... The latency numbers are still useful for making back of the envelope calculations about how much it is possible to gain and whether it's worth the trouble.

andi999 6y ago
Can you explain the radomly accessing data cache mitigation strategy more?
- oriolid 6y ago
  Well, it doesn't work if the access is so random that everything is guaranteed cache miss. On the other hand, if there's a subset that's accessed more often than rest, it reduces cache pollution from accessing outside the core subset.
  - mjevans 6y ago
    If it's this random it might be worth stepping back and trying to figure out how to get the portion of the results that are desired using a more effective mechanism. Sometimes the source data structure is just a bad fit for the expressed data. I've seen this often in combinatorial expansions of data stored in hierarchal structure to a 2d table. Sometimes all, or a majority, of the data is going to be touched anyway so it's more costly to avoid a full read and instead more optimal to make the results of that read parallel; either by sorting to a more suitable structure or by working on streams / permutations / parallel processes from a dispatch design.
- dragontamer 6y ago
  A linked list is a random-memory traversal every time you do "node = node->next". You can grossly mitigate the random-memory read/write by using unrolled linked lists (https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list). Or, instead of using binary-heaps, use d-heaps: https://en.wikipedia.org/wiki/D-ary_heap https://en.wikipedia.org/wiki/D-ary_heap

andi999 6y ago

Can you explain the radomly accessing data cache mitigation strategy more?

oriolid 6y ago
Well, it doesn't work if the access is so random that everything is guaranteed cache miss. On the other hand, if there's a subset that's accessed more often than rest, it reduces cache pollution from accessing outside the core subset.
- mjevans 6y ago
  If it's this random it might be worth stepping back and trying to figure out how to get the portion of the results that are desired using a more effective mechanism. Sometimes the source data structure is just a bad fit for the expressed data. I've seen this often in combinatorial expansions of data stored in hierarchal structure to a 2d table. Sometimes all, or a majority, of the data is going to be touched anyway so it's more costly to avoid a full read and instead more optimal to make the results of that read parallel; either by sorting to a more suitable structure or by working on streams / permutations / parallel processes from a dispatch design.
dragontamer 6y ago
A linked list is a random-memory traversal every time you do "node = node->next". You can grossly mitigate the random-memory read/write by using unrolled linked lists (https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list). Or, instead of using binary-heaps, use d-heaps: https://en.wikipedia.org/wiki/D-ary_heap https://en.wikipedia.org/wiki/D-ary_heap