It is a cache (memoization), so design it like a cache.
One approach is to store a map inside the valuator.
I think this is the correct approach, or at least, the first choice. Any other approach would have required modification or extra allocation with the
Object. "Map" refers to the general concept that, given a "key" extracted from an "Object", one can retrieved some stored "value" from some data structure.
When using this approach, make sure there is a robust "garbage collection" to remove the cached data from each
Processor for objects that no longer exist. Otherwise, the cache will be filled up with useless data. This is a form of memory/resource leak.
In some situations, a slightly hybrid approach may be needed. Consider the case where not every object have associated cached data. You would like to avoid a hash map lookup if it is not going to be there. In this case, you can use a single bit (flag) in your object to indicate the existence of cached data residing in each
Processor. This is a lower and more predictable increase in the memory size of
Object. It is convenient to reserve, say, a hard-coded limit of 64 bits (8 bytes) in the
Object for this purpose. See
std::bitset (en.cppreference.com) for example.
Every time, an object is passed to foo, a look up is required that harms performance.
Fix the performance issues; don't reject this approach.
You should begin with (
std::unordered_map en.cppreference.com). If you were using
std::map before, you can switch over to
std::unordered_map and don't have to worry about the performance issue.
std::unordered_map is not fast enough, you will want to know deeply about the underlying implementation you are using. Check whether a lookup is
O(log N). Check the hash function. Check for collision rates. Check how it handles collision. Check the criteria it uses for growing.
You will need to learn to read the compiled disassembly code, and to use CPU profiling (more correctly CPU sampling) tools to investigate whether the hash map qualifies as a hotspot and deserves the performance optimizations you're willing to invest.
If you are concerned about the CPU cache locality issues, keep this in mind:
- If your
Object objects are laid out sequentially in memory and are accessed sequentially, and your
Processor also visits objects in the same sequential order, you can design your cache to lay out its cached data in the same sequential order as your objects. This is where customization of the hash map is beneficial.
- If any of the above is not true, i.e. not everything is sequentially ordered, cache efficiency will be degraded to "what is popular" (objects visited more frequently than others) and "what is recent". This is the basic level of performance you can expect; you do not have to do any code optimization to get to this level of performance. Just optimize the inside of each object.