Jump to content
  • Advertisement
Sign in to follow this  
dodheim

Short cache related question

This topic is 4867 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!