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.
If 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(1)
or 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.