Es kann sich lohnen, nur einen einzigen std::string zu speichern für alle Ihre Daten zusammen und verwenden Sie std::string_view in der Karte. Dies eliminiert Mutex-Konflikte, da nur eine Speicherzuordnung benötigt wird. string_view hat einen trivialen Destruktor, also brauchen Sie dafür keinen Thread.
Ich habe diese Technik schon früher erfolgreich eingesetzt, um ein Programm um 2500 % zu beschleunigen, aber das lag auch daran, dass diese Technik die Gesamtspeichernutzung reduziert hat.
Sie können es mit std::vector versuchen zum Speichern der Erinnerung. std::vector Elemente werden zusammenhängend gespeichert, wodurch Cache-Fehler reduziert werden (siehe Was ist ein "Cache-freundlicher" Code?)
Sie haben also einen map<???,size_t> statt map<???,std::string> Sie haben einen weiteren Umweg, um Ihren String zu erhalten (was zusätzliche Laufzeitkosten bedeutet), aber Sie können alle Strings mit viel weniger Cache-Miss durchlaufen.
Es wäre großartig, wenn Sie das Problem, auf das Sie mit einem MVCE stoßen, nachstellen und es zeigen:Wissen Sie, oft ist das Problem, an das Sie denken, Ihr Problem ... ist nicht das Problem.
Wie kann ich sicher feststellen, dass die oben genannten 2 Speicherprobleme die Ursache sind (irgendwelche Tools/Metriken?)
Angesichts der Informationen hier würde ich vorschlagen, einen Profiler zu verwenden - gprof (kompilieren mit -g -pg) ist der grundlegende. Wenn Sie den Intel-Compiler zur Verfügung haben, können Sie vtune verwenden.
Es gibt eine kostenlose Version von vtune, aber ich persönlich habe nur die kommerzielle Version verwendet.
Außerdem können Sie Timings in Ihren Code einfügen:Aus der Textbeschreibung geht nicht hervor, ob die Zeit zum Füllen der Karte mit der Zeit zum Löschen vergleichbar ist, oder ob sie bei gleichzeitiger Ausführung konstant wächst. Ich würde mit wenn beginnen. Beachten Sie, dass die aktuelle Version von malloc() auch stark für Parallelität optimiert ist (ist dies Linux? - Fügen Sie der Frage bitte ein Tag hinzu).
Sicher, wenn Sie die Karte löschen, gibt es Millionen von free() wird von std::~string() aufgerufen - aber Sie müssen sicher sein, dass dies das Problem ist oder nicht:Sie können einen besseren Ansatz (viele in den Antworten/Kommentaren erwähnt) oder einen benutzerdefinierten Allokator verwenden, der von einem riesigen Speicherblock unterstützt wird, den Sie als einzelne Einheit erstellen/zerstören.
Wenn Sie ein MVCE als Ausgangspunkt angeben, können ich oder andere eine konsistente Antwort geben (dies ist noch keine Antwort - aber zu lang, um ein Kommentar zu sein)
Nur zur Verdeutlichung:Das Programm weist absichtlich niemals Daten zu und gibt gleichzeitig andere frei, und es hat nur 2 Threads, von denen einer nur zum Löschen bestimmt ist.
Denken Sie daran, dass jeder String in der Map einen (oder mehrere) new benötigt und ein delete (basierend auf malloc() und free() bzw.), wobei die Zeichenfolgen entweder in den Schlüsseln oder in den Werten enthalten sind.
Was haben Sie in den "Werten" der Karte?
Da Sie einen map<string,<set<int>> haben Sie haben viele Zuweisungen:Jedes Mal, wenn Sie einen map[string].insert(val) ausführen eines neuen Schlüssels ruft Ihr Code implizit malloc() auf sowohl für die Saite als auch für das Set. Selbst wenn sich der Schlüssel bereits in der Map befindet, erfordert ein neues int im Set, dass ein neuer Knoten im Set zugewiesen wird.
Sie haben also wirklich viele Allokationen beim Aufbau der Struktur:Ihr Speicher ist auf der einen Seite sehr fragmentiert, und Ihr Code scheint wirklich "malloc-intensiv" zu sein, was im Prinzip dazu führen könnte, dass die Speicheraufrufe verhungern.
Multithreaded-Speicherzuweisungen/-aufhebungen
Eine Besonderheit moderner Speichersubsysteme ist, dass sie für Mehrkernsysteme optimiert sind:Wenn ein Thread Speicher auf einem Kern zuweist, gibt es keine globale Sperre, sondern eine Thread-lokale oder Kern-lokale Sperre für einen Thread-lokalen Pool .
Das bedeutet, dass, wenn ein Thread den von einem anderen zugewiesenen Speicher freigeben muss, eine nicht-lokale (langsamere) Sperre beteiligt ist.
Das bedeutet, dass der beste Ansatz darin besteht, dass jeder Thread seinen eigenen Speicher zuweist/freigibt. Sagte, dass man im Prinzip viel optimieren kann Ihr Code mit Datenstrukturen, die weniger malloc/free-Interaktionen erfordern, wird Ihr Code in Bezug auf Speicherzuweisungen lokaler sein, wenn Sie jeden Thread:
lassen- einen Datenblock erhalten
- baue den
map<string,<set<int>> - Befreie es
Und Sie haben zwei Threads, die diese Aufgabe wiederholt ausführen.
HINWEIS:Sie benötigen ausreichend RAM, um gleichzeitige Evaluatoren zu handhaben, aber jetzt verwenden Sie bereits 2 davon, die gleichzeitig mit einem doppelten Pufferungsschema geladen werden (ein Füllen, ein Reinigen). Sind Sie sicher, dass Ihr System aufgrund von RAM-Erschöpfung nicht wechselt?
Darüber hinaus ist dieser Ansatz skalierbar:Sie können so viele Threads verwenden, wie Sie möchten. In Ihrem Ansatz waren Sie auf 2 Threads beschränkt - einer baut die Struktur auf, einer zerstört sie.
Optimierung
Ohne MVCE ist es schwierig, Anweisungen zu geben. Nur Ideen, von denen Sie nur wissen, ob sie jetzt angewendet werden können:
- Set durch sortierten Vektor ersetzen, der zum Zeitpunkt der Erstellung reserviert ist
- Ersetzen Sie die Zuordnungsschlüssel durch einen flachen Vektor aus gleichmäßig verteilten, sortierten Zeichenfolgen
- Speichern Sie die Zeichenfolgenschlüssel sequentiell in einem flachen Vektor, fügen Sie Hashes hinzu, um die Schlüssel der Karte zu verfolgen. Fügen Sie eine Hash-Map hinzu, um die Reihenfolge der Zeichenfolgen im Vektor zu verfolgen.