Comment optimiser l'insertion de carte lourde en C++ concernant CPU et de la mémoire

Question

J'itérer une carte où je dois ajouter des éléments sur cette carte en fonction d'une condition qu'un élément ne se trouve pas (il pourrait être toute autre condition).

Mon principal problème est que, avec une grande échelle des mises à jour à ajouter, l'application prend toute la CPU et toute la mémoire.

État Classe:

class State { 

    int id; 

    int timeStamp; 

    int state; 

} 

Méthode État:

void State::updateStateIfTimeStampIsHigher(const State& state) { 
    if (this->id == state.getId() && state.getTimeStamp() > this->getTimeStamp()) { 
     this->timeStamp = state.getTimeStamp(); 
     this->state = state.getState(); 
    } 
} 

code Loop:

std::map<int, State> data; 

const std::map<int, State>& update; 

for (auto const& updatePos : update) { 
    if (updatePos.first != this->toNodeId) { 
     std::map<int, State>::iterator message = data.find(updatePos.first); 
     if (message != data.end() && message->first) { 
      message->second.updateStateIfTimeStampIsHigher(updatePos.second); 
     } else { 
      data.insert(std::make_pair(updatePos.first, updatePos.second)); 
     } 
    } 
} 

Regarder les données KCacheGrind il semble que le data.insert() ligne prend le plus de temps/de mémoire. Je suis nouveau à KCacheGrind, mais cette ligne semble être d'environ 72% du coût.

Avez-vous des suggestions pour améliorer ceci?

Answer 1

je pourrais trouver une réponse satisfaisante grâce à des recherches sur les commentaires à la question. Il a aidé un peu à changer de carte -unordered_map mais je toujours obtenu des résultats peu satisfaisants.

J'ai fini par utiliser le sparsehash de Google qui offre une meilleure utilisation des ressources malgré certains inconvénients liés à l'effacement des entrées (ce que je fais).

La solution de code est la suivante.Tout d'abord j'inclure la bibliothèque requise:

#include <sparsehash/sparse_hash_map> 

Alors, mes nouvelles données définition ressemble à:

struct eqint { 
    bool operator()(int i1, int i2) const { 
     return i1 == i2; 
    } 
}; 

google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint> data; 

Depuis que je dois utiliser « effacer » Je dois le faire après la sparsemap construction:

data.clear_deleted_key(); 
data.set_deleted_key(-1); 

Enfin mon code boucle change très peu:

for (auto const& updatePos : update) { 
    if (updatePos.first != this->toNodeId) { 
     google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint>::iterator msgIt = data.find(updatePos.first); 
     if (msgIt != data.end() && msgIt->first) { 
      msgIt->second.updateStateIfTimeStampIsHigher(updatePos.second); 
     } else { 
      data[updatePos.first] = updatePos.second; 
     } 
    } 
} 

Le temps avant faire les changements pour une application toute exécution avec des paramètres spécifiques a été:

real 0m28,592s 
user 0m27,912s 
sys  0m0,676s 

Et le temps après faire les changements pour toute exécution de l'application sous même paramètres spécifiques est:

real 0m37,464s 
user 0m37,032s 
sys  0m0,428s 

Je l'exécute avec d'autres cas et les résultats sont similaires (d'un point de vue qualitatif). L'utilisation du temps et de l'utilisation du système (CPU et mémoire) diminue et le temps utilisateur augmente. Dans l'ensemble, je suis satisfait du compromis car j'étais plus préoccupé par l'utilisation des ressources que le temps d'exécution (l'application est un simulateur et n'a pas pu terminer et obtenir des résultats sous une charge vraiment lourde et maintenant c'est le cas).

Answer 2

Votre question est tout à fait général, mais je vois les choses tho pour le faire courir plus vite:

1. utilisation insertion insinué/mise en place. Lorsque vous ajoutez un nouvel élément, son itérateur est renvoyé. En supposant que les deux cartes sont ordonnées de la même manière, vous pouvez dire où le dernier a été inséré, donc la recherche devrait être plus rapide (peut-être utiliser un benchmarking ici).
2. Utilisez emplace_hint pour accélérer l'insertion

Exemple de code ici:

std::map<int, long> data; 

const std::map<int, long> update; 
auto recent = data.begin(); 

for (auto const& updatePos : update) { 
    if (updateElemNotFound) { 
     recent = data.emplace_hint(recent, updatePos); 
    } 
} 

Aussi, si vous voulez faire du commerce CPU sur la mémoire, vous pouvez utiliser unordered_map (Is there any advantage of using map over unordered_map in case of trivial keys?), mais premier point ne serait pas question plus .