Necesidad de acelerar el código C++ que impliquen Impulso multi-índice de búsquedas y a unordered_multimap

Question

Estoy buscando estrategias para acelerar un agente basado en modelo que se basa en objetos de la clase Host, los punteros a los cuales se almacenan en un Impulso multi-índice de contenedor.He usado Tiburón para determinar que la gran mayoría del tiempo es consumido por una función calcSI():

La función calcSI() tiene que calcular para cada instancia de la clase Host ciertas probabilidades que dependen de los atributos de otras instancias de la clase Host.(Hay aproximadamente 10,000-50,000 casos de Host, y estos cálculos se ejecutan para cada host aproximadamente 25,600 veces).

Si estoy interpretando el perfil correctamente, la mayoría del tiempo que pasó en calcSI() va a Host::isInfectedZ(int), que simplemente cuenta las instancias de algo en un Impulso unordered_multimap de tipo 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;

Todos los miembros de Host contienen InfectionMap carriage, y Host::isInfectedZ(int) simplemente cuenta el número de Infections asociado con un determinado int clave:

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

1. Estoy teniendo problemas para encontrar la información sobre cómo costosos de la count la función es para el Impulso de la desordenada multimaps.Debo aumentar la sobrecarga mediante la adición de Host separado en dos dimensiones de la matriz para el seguimiento del número de instancias de cada clave (es decir, el número de Infections asociado con cada int)?

2. Me pregunto si una mayor revisión estructural de refuerzo multi-índice, como la eliminación de uno o dos menos necesaria compuesto de los índices más importantes, sería más útil.El fondo de mantenimiento de la multi-índice no aparece en el analizador, que (tal vez estúpidamente) hace que me preocupe podría ser grande.Tengo 8 índices en el multi-índice, la mayoría de los cuales son ordered_non_unique.

3. Hay otras cosas que deben ocuparse de que no aparezcan en el analizador, o me estoy perdiendo un importante resultado de la profiler?

Paralelización y múltiples hilos de calcSI() desgraciadamente no son opciones.

Actualización: Puede ser útil saber que InfectionMap carriage rara vez tiene más de 10 pares y por lo general tiene <5.

---

Actualización 2: He probado la estrategia propuesta en el punto #1, dando a cada Host una matriz int carriageSummary[ INIT_NUM_STYPES ], que es indexado por los posibles valores de z (para la mayoría de las simulaciones, hay <10 valores posibles).El valor de cada entrada de las pistas de los cambios realizados a carriage.El Host::isInfectedZ( int z ) la función lee ahora:

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

Y el tiempo dedicado a esta función aparece que han bajado sustancialmente--yo no puedo hacer una comparación exacta ahora mismo: Obviamente, el uso de una matriz es una especie de voluminosos, pero está bien para pequeños rangos de z.Sería otro recipiente (es decir, no un unordered_map) ser más eficientes para rangos mayores?

Me gustaría alguna retroalimentación sobre el cambio de multi-índice demasiado.

Answer 1

Como sugirió en el n. ° 1, intente mantener una matriz de conteo de carro junto al host :: carro undered_multimap y manténgalos a ambos "sincronizados". Su anfitrión :: IsInfectedZ luego usaría la matriz (con suerte) de conteo de carro más rápida:

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

Si el rango de enteros que se puede transmitir en ISInfected es grande, use una matriz asociativa para su recuento de carruajes.

Puede usar std :: map o boost :: desordenado para la matriz asociativa. Para las búsquedas, el primero tiene complejidad temporal logarítmica y la segunda tiene una complejidad temporal constante. Pero dado que esta matriz asociativa sería típicamente muy pequeña, el mapa std :: podría ser en realidad más rápido. std :: map también puede ocupar menos espacio en lo alto. Prueba ambos y ejecuta tu perfilador para ver. Mi apuesta está en std :: map. :-)

EDITAR:

Al ver su respuesta a mi comentario, sugeriría usar una matriz de tamaño fijo regular para el recuento de carruajes. Olvídate de las cosas de la matriz asociativa.

Edit2:

Es posible que quieras desechar

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

Y enrolle su propia clase de mapa de infección escrita a mano, ya que está tratando con índices tan pequeños.

Respuesta a la actualización #2:

Me alegro de ver que has hecho una mejora. Dudo que encuentre un contenedor que sea "menos voluminoso" que una matriz fija de, digamos, 16 enteros. Los contenedores STL y Boost asignan memoria en trozos y terminarán tan grandes como su matriz de tamaño fijo, incluso si tienen pocos elementos.

Es posible que esté interesado en Boost :: Array, que envuelve una interfaz similar a STL alrededor de una matriz fija de estilo C. Esto hará que sea más fácil "intercambiar" su matriz de tamaño fijo para un mapa STD :: Vector o STD ::.