Untitled attachment

Notices where this attachment appears

1. 𝘾𝙔𝘽𝙀𝙍𝙁𝙍𝙄𝙀𝙉𝘿 (ninjawedding@sdfn-01.ninjawedding.org)'s status on Monday, 17-Jul-2017 15:28:45 UTC 𝘾𝙔𝘽𝙀𝙍𝙁𝙍𝙄𝙀𝙉𝘿
   "Array Layouts for Comparison-Based Searching": https://arxiv.org/pdf/1509.05053.pdf
   
   One thing that I've had to repeatedly struggle with in gamedev is the importance of keeping the CPU fed with data. This usually means predictable memory access patterns and contiguous data structure layouts.
   
   Unfortunately some very useful data structures -- maps, for instance -- are usually implemented in a way that are non-contiguous and don't have predictable access patterns. What do? Well, the easiest (and often quite sufficient) way is to maintain a array of (key, value) tuples, sorted on key, and binary-search it. There are other methods, though, and this paper is a neat survey of those methods.
   
   Bonus: Section 2, "Processor Architecture Considerations", seems to me to be a pretty good overview of just how badly memory latency will slow your code down and the methods employed by CPUs to overcome that latency.