Short cache related question

Started by
1 comment, last by dodheim 18 years, 5 months ago
Hi! Recently I've seen in someone else's code excess usage of traversing arrays backwards (so from the last element to the first). I know that it's good practice to traverse arrays forwards and linearly as it lets the CPU preload memory blocks that are ahead of us into the cache. So I'm curious if the cache system can work backwards too (btw I hardly think so) or the above approach is bound to produce a lot of cache misses.. thx
Advertisement
The number of cache misses will be the same backwards and forwards. Each time you address outside a cache line, the cache will fill an entire line from DRAM. Whether you fill waiting on the last or the first byte doesn't matter if you have a smart cache/memory controller that fills the desired bytes first (I know PPC used to do this; haven't actually checked for modern CPUs).

So, array traversal forwards or backwards are pretty much the same from a caching point of view -- and significantly better than linked lists, where you're guaranteed a cache miss for EACH element you visit!
enum Bool { True, False, FileNotFound };
Hmm that sounds reasonable, thanks for your reply ;)

This topic is closed to new replies.

Advertisement