re: Taking Hash Tables Off The Shelf VIEW POST


One thing that would eventually be neat to learn more about is cache misses with various data structures. I know that's a whole other ball of wax, but it ends up being somewhat important when choosing data structures to run on particular hardware (at least from my limited understanding).


Hi Joel,

Thanks for the recommendation; I can add it to my list! Could you give me a little more context so I know what to research? Or do you just mean caching as a concept?



I don't have a huge understanding of the topic, but from what I understand certain data structures tend to play well with level 1 caches. Essentially, you want your most frequently used data to be cached, and certain processors try to be smart and pre-fetch things that they think will be used. If the data structures make it difficult to pre-fetch, it results in a cache miss that results in a performance hit. The idea is to structure your data (and use algorithms) as to minimize cache misses. A bit of it is dependent on things like cache sizes and data structure sizes, but some of it is dependent on the algorithm itself.

Again I don't know a ton about this, which is why I want to learn more about it! :P

From my (further) limited understanding on the topic, cache misses occur when the processors cannot predict what you will access next. For example, if I'm writing a game engine and I use a map of entity IDs to entities, then iterate through the keys and access the values, the processor cannot prefetch the next entity because it's not necessarily contiguous in memory. However, if I used an array of entities and mapped their position to their ID separately (or better yet just kept their ID on them and used the array on its own), then I could iterate through the entity array and the processor can predict what entity comes next and load it into the cache.

This is the kind of stuff that I'd like to learn more about, but it seems like the kind of thing that is rarely stated anywhere, and seems so platform specific. I bet a person could learn a lot more about it by writing a few benchmarks for the specific target platform, but it's rare that we get to hear much about results from little experiments like that.

code of conduct - report abuse