Il peut être intéressant de ne stocker qu'un seul std::string pour toutes vos données combinées, et utilisez std::string_view dans la carte. Cela élimine les conflits de mutex car il n'y a qu'une seule allocation de mémoire nécessaire. string_view a un destructeur trivial donc vous n'avez pas besoin d'un thread pour cela.
J'ai déjà utilisé cette technique avec succès pour accélérer un programme de 2 500 %, mais c'était aussi parce que cette technique réduisait l'utilisation totale de la mémoire.
Vous pouvez essayer d'utiliser un std::vector pour stocker la mémoire. std::vector les éléments sont stockés de manière contiguë, ce qui réduira les erreurs de cache (voir Qu'est-ce qu'un code "cache-friendly" ?)
Vous aurez donc un map<???,size_t> au lieu de map<???,std::string> vous aurez une autre indirection pour obtenir votre chaîne (ce qui signifie un coût de temps d'exécution supplémentaire) mais cela vous permettra d'itérer sur toutes les chaînes avec beaucoup moins de cache-miss.
Ce serait formidable si vous recréiez le problème que vous rencontrez avec un MVCE et que vous le montriez :vous savez, plusieurs fois, le problème auquel vous pensez est votre problème... n'est pas le problème.
Comment puis-je trouver avec certitude que les 2 problèmes de mémoire ci-dessus en sont la cause (quels outils/métriques ?)
Compte tenu des informations ici, je suggérerais d'utiliser un profileur - gprof (compiler avec -g -pg) étant celui de base. Si vous disposez du compilateur Intel, vous pouvez utiliser vtune.
Il existe une version gratuite de vtune mais je n'ai personnellement utilisé que la version commerciale.
En plus de cela, vous pouvez insérer des minutages dans votre code :à partir de la description textuelle, il n'est pas clair si le temps nécessaire pour remplir la carte est comparable au temps nécessaire pour l'effacer, ou s'il augmente de manière cohérente lorsqu'il est exécuté simultanément. Je commencerais par si. Notez que la version actuelle de malloc() est également grandement optimisée pour la concurrence (est-ce Linux ? - ajoutez une balise à la question s'il vous plaît).
Bien sûr, lorsque vous effacez la carte, il y a des millions de free() est appelé par std::~string() - mais vous devez être sûr que c'est le problème ou non :vous pouvez utiliser une meilleure approche (beaucoup mentionnée dans les réponses/commentaires) ou un répartiteur personnalisé soutenu par un énorme bloc de mémoire que vous créez/détruisez comme une seule unité.
Si vous fournissez un MVCE comme point de départ, moi ou d'autres personnes pourrons fournir une réponse cohérente (ce n'est pas encore une réponse - mais trop long pour être un commentaire)
Juste pour clarifier, le programme n'alloue délibérément jamais de choses et n'en libère pas d'autres en même temps, et il n'a que 2 threads, un dédié uniquement à la suppression.
Gardez à l'esprit que chaque chaîne de la carte nécessite un (ou plusieurs) new et un delete (basé sur malloc() et free() respectivement), étant les chaînes soit dans les clés, soit dans les valeurs.
Qu'avez-vous dans les "valeurs" de la carte ?
Puisque vous avez un map<string,<set<int>> vous avez de nombreuses allocations :chaque fois que vous effectuez un map[string].insert(val) d'une nouvelle clé, votre code appelle implicitement malloc() pour la chaîne et l'ensemble. Même si la clé est déjà dans la carte, un nouvel int dans l'ensemble nécessite l'allocation d'un nouveau nœud dans l'ensemble.
Vous avez donc vraiment beaucoup d'allocations lors de la construction de la structure :votre mémoire est très fragmentée d'un côté, et votre code semble vraiment "malloc intensif", ce qui pourrait en principe conduire à affamer les appels mémoire.
Allocations/désallocations de mémoire multithread
Une particularité des sous-systèmes de mémoire modernes, c'est qu'ils sont optimisés pour les systèmes multicœurs :lorsqu'un thread alloue de la mémoire sur un cœur, il n'y a pas de verrou global, mais un verrou thread-local ou core-local pour un thread-local pool .
Cela signifie que lorsqu'un thread a besoin de libérer la mémoire allouée par un autre, un verrou non local (plus lent) est impliqué.
Cela signifie que la meilleure approche est que chaque thread alloue/libère sa propre mémoire. A déclaré qu'en principe, vous pouvez optimiser beaucoup votre code avec des structures de données qui nécessitent moins d'interactions malloc/free, votre code sera plus local, par rapport aux allocations mémoire, si vous laissez chaque thread :
- obtenir un bloc de données
- construire le
map<string,<set<int>> - libérez-le
Et vous avez deux threads qui effectuent cette tâche à plusieurs reprises.
REMARQUE :vous avez besoin d'assez de RAM pour gérer les évaluateurs simultanés, mais maintenant vous en utilisez déjà 2 chargés simultanément avec un schéma de double tampon (un remplissage, un nettoyage). Êtes-vous sûr que votre système n'échange pas à cause de l'épuisement de la RAM ?
De plus, cette approche est évolutive :vous pouvez utiliser autant de threads que vous le souhaitez. Dans votre approche, vous étiez limité à 2 threads - l'un construisant la structure, l'autre la détruisant.
Optimisation
Sans MVCE, il est difficile de donner des instructions. Juste des idées dont vous savez seulement si elles peuvent être appliquées à l'heure actuelle :
- remplacer l'ensemble par un vecteur trié, réservé au moment de la création
- remplacez les clés de carte par un vecteur plat de chaînes triées et espacées de manière égale
- stocker les clés de chaîne séquentiellement dans un vecteur plat, ajouter des hachages pour garder une trace des clés de la carte. Ajoutez une table de hachage pour suivre l'ordre des chaînes dans le vecteur.