How to store state data when the data is related to another entity?

Question

In order to increase the parallel-ability of my objects, I try to make them read-only and include only data that naturally belong to the entity. I have

class Object { ... };
class Processor { 
  void foo(const Object& o) { ... }
}

The benefit of this model is I need only one Processor instance for any number of Object instances. However, sometimes Processor may need to store state information per object. One approach is to store a map inside the Processor. Every time, an object is passed to foo, a look up is required that harms performance.

Another approach is to store the information with the object. But I don't want to pollute the object with data that don't naturally belong there. Additionally, different Processor's store different state. The Object can't anticipate all the user types.

Is there any design idiom or trick for this situation?

Edit: The Processor in this particular scenario wishes to associate partial computation result with each Object to improve speed.

Answer 1

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.

Answer 2

It looks like you are trying to build your code according to some of principles of the functional programming paradigm:

• objects / data are immutable: as you note this makes it easy for the objects / data to be processed in parallel.
• no side effects: operations performed on an object/data should not affect that object/data's state (or have any interaction with calling functions or the outside world.

The solution in the world of functional programming can be pretty simple:
make a new object based on the original one with the state for that Processor.

The reference to the original object / data in the queue (or other mechanism) for that Processor should be replaced with a reference to the new object/data.
The original object / data still exists for other Processors (it is not deleted or overwritten).

This leads to some overhead in memory (multiple versions of the same object with different states will exist), but should not harm performance.