I'm writing in C++, but this problem applies to most non-high-level languages, and possibly some high-level ones as well.
I have a graph of heterogeneous nodes. The graph can be instantiated by different subsystems (e.g. it can be read from a file or generated by one out of many algorithms).
I have several algorithms that can work on the graph to compute something. Most algorithms need to store extra information for each node, and some are computationally intensive and I'm trying to optimize them.
Until now I've been using a hash table (a
std::unordered_map<Node*, Data>) to store the extra information of a node, but I just realized that using a hashmap affects performance noticeably: the most intensive algorithm performs 2~5% better if I keep the data in the node type. However placing algorithm-specific data in the node type seems extremely dirty.
What are some good ways to store extra information for each node, in an efficient, yet clean way? Are there any smart ideas/patterns I should consider?