C++ Map Lookup Memoization

Memoization is an old technique. It’s basically caching outputs for giving inputs (usually in a map). But a map lookup itself is not free. How can we memoize map lookups?

I learned from my coworker this nifty trick recently. Let’s say we have a map (e.g. std::unordered_map<K,V>, for which the associations (key -> value mapping) don't change during the lifetime of the program. This is fairly common for things like settings and counters. Now every time you look up a certain key, you have to paid the lookup cost (more instructions, cacheline misses, memory accesses, you name it). How…

Software Engineer at Facebook working on cache infrastructure

Love podcasts or audiobooks? Learn on the go with our new app.