3 ms·

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