Necessità di accelerare codice C ++ che coinvolge Boost multi-indice e le ricerche a unordered_multimap

Question

sto cercando strategie per accelerare un modello basato su agenti che si basa su oggetti di classe Host, puntatori a cui sono memorizzati in un contenitore Boost multi-indice. Ho usato Shark per determinare che la stragrande maggioranza del tempo viene consumato da una funzione calcSI():

calcSI() funzione deve calcolare per ogni istanza della classe Host certe probabilità che dipendono da attributi di altri istanze della classe Host. (Ci sono circa 10.000-50.000 casi di Host, e questi calcoli vengono eseguiti per ogni host circa 25.600 volte.)

Se sto interpretando correttamente il profilo, la maggior parte del tempo trascorso in calcSI() va a Host::isInfectedZ(int), che conta semplicemente le istanze di qualcosa in un unordered_multimap Boost di 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;

Tutti i membri del Host contengono InfectionMap carriage, e Host::isInfectedZ(int) conta semplicemente il numero di Infections associato con una particolare chiave int:

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

1. Sto avendo Ricerca di informazioni guai quanto costoso la funzione count è per multimaps non ordinate di Boost. Devo aumentare l'overhead aggiungendo ad Host una matrice bidimensionale separato per tenere traccia del numero di istanze di ciascun tasto (cioè il numero di Infections associato ad ogni int)?

2. sto chiedendo se una grande revisione strutturale del Boost multiindice, come eliminare uno o due indici di riferimento composito meno necessarie, sarebbe più utile. Lo sfondo di manutenzione del multi-indice non compare nel profiler, che (forse stupidamente) mi fa preoccupare che potrebbe essere di grandi dimensioni. Ho 8 indici nel multiindice, la maggior parte dei quali sono ordered_non_unique.

3. Ci sono altre cose che dovrebbero essere interessati con che potrebbero non apparire nel profiler, o mi sto perdendo un importante risultato dal profiler?

Parallelizzazione e multithreading di calcSI() sono, purtroppo, non opzioni.

Aggiornamento:. potrebbe essere utile sapere che InfectionMap carriage ha raramente più di 10 coppie e di solito ha <5

---

Aggiornamento 2: Ho provato la strategia proposta sopra 1 #, dando ogni Host un int carriageSummary[ INIT_NUM_STYPES ] matrice, che viene indicizzato dai possibili valori di z (per la maggior parte delle simulazioni, ci sono <10 valori possibili ). Il valore di ogni traccia di entrata modifiche apportate al carriage. La funzione Host::isInfectedZ( int z ) ora recita:

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

E il tempo dedicato a questa funzione appare di aver sceso notevolmente - non posso fare un confronto esatto in questo momento: Ovviamente, utilizzando una matrice è di tipo ingombrante ma va bene per piccoli intervalli di z. Sarebbe un altro contenitore (cioè non un unordered_map) essere più efficiente per intervalli più grandi?

amerebbero tutte le risposte a cambiare multi-indice di troppo.

Answer 1

come da te suggerito a # 1, prova a mantenere un allineamento conteggio carrozza accanto alla Host :: unordered_multimap trasporto e tutti e due "sincronizzati" mantenere. Your Host :: isInfectedZ sarebbe quindi utilizzare la matrice (si spera) più veloce trasporto count:

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

Se l'intervallo di numeri interi che può essere passato in isInfected è grande, quindi utilizzare un array associativo per il valore del trasporto.

È possibile utilizzare std :: map o boost :: non ordinata per l'array associativo. Per le ricerche, la prima ha logaritmica complessità temporale e quest'ultima è costante complessità temporale. Ma poiché questo array associativo sarebbe in genere molto piccola, std :: mappa potrebbe in realtà essere più veloce. std :: map può anche occupare meno spazio sopra la testa. Prova entrambi e eseguire il profiler per vedere. La mia scommessa è sulla std :: map. : -)

EDIT:

Dopo aver visto la tua risposta al mio commento, vi suggerirei di usare un normale matrice a dimensione fissa per il conteggio del carrello. Dimenticate la roba array associativo.

EDIT2:

Si potrebbe desiderare di rottami

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

e roll-up la propria classe InfectionMap scritta a mano, dal momento che hai a che fare con questi piccoli indici.

RISPOSTA A UPDATE # 2:

Mi fa piacere vedere che hai fatto un miglioramento. Dubito troverete un contenitore che è "meno ingombrante" di una serie fissa di, diciamo, 16 interi. STL e Boost contenitori allocare memoria in blocchi e finiranno pari alla dimensione della matrice a dimensione fissa, anche se hanno pochi elementi.

Si potrebbe essere interessato boost :: array, che avvolge uno STL-come l'interfaccia intorno ad una serie fisso C-style. In questo modo sarà più facile "di swap-out" la matrice di dimensioni fisse per uno std :: vector o std :: map.