Need to speed up C++ code involving Boost multi-index and lookups to unordered_multimap

Question

I'm looking for strategies to speed up an agent-based model that's based on objects of class Host, pointers to which are stored in a Boost multi-index container. I've used Shark to determine that the vast majority of the time is consumed by a function calcSI():

Function calcSI() has to compute for every instance of class Host certain probabilities that depend on attributes of other instances of class Host. (There are approximately 10,000-50,000 instances of Host, and these calculations are run for each host approximately 25,600 times.)

If I'm interpreting the profile correctly, the majority of the time spent in calcSI() goes to Host::isInfectedZ(int), which simply counts instances of something in a Boost unordered_multimap of type InfectionMap:

struct Infection {
public:
  explicit Infection( double it, double rt ) : infT( it ), recT( rt ) {}
  double infT;
  double recT;
};
typedef boost::unordered_multimap< int, Infection > InfectionMap;

All members of Host contain InfectionMap carriage, and Host::isInfectedZ(int) simply counts the number of Infections associated with a particular int key:

int Host::isInfectedZ( int z ) const {
  return carriage.count( z );
}

1. I'm having trouble finding information on how costly the count function is for Boost's unordered multimaps. Should I increase the overhead by adding to Host a separate two-dimensional array to track the number of instances of each key (i.e., the number of Infections associated with each int)?

2. I'm wondering if a larger structural overhaul of the Boost multi-index, like eliminating one or two less-needed composite key indices, would be more helpful. The background maintenance of the multi-index doesn't appear in the profiler, which (maybe stupidly) makes me worry it might be large. I have 8 indices in the multi-index, most of which are ordered_non_unique.

3. Are there other things I should be concerned with that might not appear in the profiler, or am I missing a major result from the profiler?

Parallelization and multithreading of calcSI() are unfortunately not options.

Update: It might be helpful to know that InfectionMap carriage rarely has more than 10 pairs and usually has <5.

---

Update 2: I tried the strategy proposed in #1 above, giving each Host an array int carriageSummary[ INIT_NUM_STYPES ], which is indexed by the possible values of z (for most simulations, there are <10 possible values). The value of each entry tracks changes made to carriage. The Host::isInfectedZ( int z ) function now reads:

int Host::isInfectedZ( int z ) const {
  //return carriage.count( z );
  return carriageSummary[ z ];
}

And the time dedicated to this function appears to have dropped substantially--I can't do an exact comparison right now: Obviously, using an array is kind of bulky but okay for small ranges of z. Would some other container (i.e., not an unordered_map) be more efficient for larger ranges?

Would love any feedback on changing multi-index too.

Answer 1

Like you suggested in #1, try maintaining a carriage count array next to the Host::carriage unordered_multimap and keep them both "synchronised". Your Host::isInfectedZ would then use the (hopefully) faster carriage count array:

int Host::isInfectedZ( int z ) const {
  return carriageCount[ z ];
}

If the range of integers that can be passed into isInfected is large, then use an associative array for your carriage count.

You can use std::map or boost::unordered for the associative array. For lookups, the former has logarithmic temporal complexity and the latter has constant temporal complexity. But since this associative array would be typically very small, std::map might actually be faster. std::map may also take up less space overhead. Try both and run your profiler to see. My bet is on std::map. :-)

EDIT:

Upon seeing your answer to my comment, I would suggest using a regular fixed-size array for the carriage count. Forget about the associative array stuff.

EDIT2:

You might want to scrap

typedef boost::unordered_multimap< int, Infection > InfectionMap;

and roll-up your own hand-written InfectionMap class, since you're dealing with such small indices.

RESPONSE TO UPDATE #2:

Glad to see you've made an improvement. I doubt you'll find an container that is "less bulky" than a fixed array of, say, 16 integers. STL and boost containers allocate memory in chunks and will end up as large as your fixed-size array, even if they have few elements.

You might be interested in boost::array, which wraps an STL-like interface around a C-style fixed array. This will make it easier to "swap-out" your fixed-size array for a std::vector or std::map.