[C++] Ein schlichter paralleler std::vector

[Schrompf]

Moin Loite,

ich habe gerade einen kleinen Auftrag angenommen, bei dem es für ein Wort-Puzzle-Spiel nötig ist, aus einer Liste von 300k Wörtern alle anagram-fähigen Wörter rauszusuchen. Mir ist dazu erstmal nix Schlaueres eingefallen als von jedem Wort alle Permutationen zu bilden und zu testen, ob die in der Wortliste auftauchen.

Wie ihr euch vielleicht vorstellen könnt, dauert das Zeit. Eine knappe halbe Stunde. Empfehlungen algorithmischer Natur nehme ich auch gern entgegen, aber nur zu Lernzwecken - dieser Teil des Auftrags ist damit eigentlich durch und ich möchte vermeiden, da noch viel Optimierungsarbeit reinzustecken. Primär brauche ich eure Fachkenntnis aber zur Bewertung meiner Parallelisierung.

Und die sieht so aus:

Code: Alles auswählen

#pragma omp parallel
for( const std::string& word : allWords )
  GenerateAnagramsAndStoreIfFound( word, allWords, targetStorageVector);

Das klappt prima, da ja alles rein lesende Operationen sind bis auf die Unterbringung gefundener Worte im Ziel-Container. Und dazu habe ich mir einen kleinen parallel beschriebenen Vector gebastelt. Der sieht so aus:

Code: Alles auswählen

template <typename T>
struct ConcurrentVector
{
  std::atomic<size_t> mCount;
  std::vector<T> mBuffer;

public:
  ConcurrentVector( size_t pCapacity) 
    : mCount( 0), mBuffer( pCapacity, T())
  { }

  void push_back( T&& val) 
  {
    size_t slot = mCount.fetch_add( 1);
    if( slot >= mBuffer.capacity() )
      return;

    mBuffer[slot] = std::move( val);
  }
};

Geht prima, soweit ich das Programm beurteilen, was hier grade läuft und tatsächlich alle 8 Cores plattmacht. Aber ich traue dem Braten nicht. Je mehr ich von den atomaren Operationen lese, desto verunsicherter bin ich. Kann ich mich nun darauf verlassen, dass das fetch_add() linear Slots reserviert für alle Aufrufer, egal aus welchen Threads? Der vector muss in dieser Lösung in passender Größe vorallokiert werden, damit die Lösung simpel bleibt.

Geht das so? Oder habe ich da irgendwo einen groben Denkfehler drin?

PS: ich sehe gerade, der Debugger meint, ich hätte viele doppelte Einträge. Irgendwo ist da wohl noch der Wurm drin, aber das dürfte mit dem parallel beschreibbaren Vector nix zu tun haben.

[Schrompf]

Haha. Die automatische Schleifen-Parallelisierung geht anscheinend nicht for std::unordered_set. Der bearbeitet echt in 8 Threads parallel den selben Schleifenwert. Ich mach mir wohl besser noch ne Kopie des Datensatzes in einem std::vector, damit ich eine Integer-Schleife nutzen kann, die der Drops dann hoffentlich parallelisiert bekommt.

[Schrompf]

Tss... hat zwar nix mit dem parallel befüllbaren Vector zu tun, aber ich find's trotzdem mitteilenswert:

Code: Alles auswählen

#pragma omp parallel for
for( const auto& w : werte )

führt bei Visual Studio 2012 zu einem Syntaxfehler, weil er den Doppelpunkt nicht erkennt. Anscheinend wird für OMP-gekennzeichnete Schleifen ein komplett anderer Codezweig benutzt. Ich hatte ahnungslos erstmal nur das "for" vom Ende des pragmas entfernt. So lief es prima:

Code: Alles auswählen

#pragma omp parallel
for( const auto& w : werte )

Nur bearbeitete der nun in 8 Threads jeweils den selben Schleifenwert, eins nach dem anderen. Also habe ich meine Wörterliste zusätzlich in einen std::vector umgefüllt, den ich nun mit Index adressieren kann.

Code: Alles auswählen

std::vector<std::string> wordVector;
wordVector.reserve( words.size());
wordVector.insert( wordVector.begin(), words.cbegin(), words.cend());

size_t wordCount = words.size();
#pragma omp parallel for
for( size_t a = 0; a < wordCount; ++a )

Und jetzt erst springt irgendwas Anderes tief im Compiler an und sagt mir, dass die Schleifenvariable bitte ein vorzeichenbehafteter Int sein soll.

1>Anagram.cpp(119): error C3016: "a": Die Indexvariable in der For-Anweisung von OpenMP muss einen ganzzahligen Typ mit Vorzeichen aufweisen.

Ich frage mich, was der bis dahin eigentlich kompiliert hat. Umbau auf int und nun rollt der Rubel, hochparallel und tatsächlich mit verschiedenen Schleifenteilen.

[Sternmull]

Ich bin grad in Eile und hab mir nicht alles durchgelesen... aber ich glaube das Problem ist dein Algorithmus: Wenn du die Buchstaben jeden Wortes sortierst und als Schlüssel verwendest, dann sind alle Worte mit gleichem Schlüssel Anagramme voneinander. Für 300k Wörter sollte da der Rechenaufwand unproblematisch sein.

[Schrompf]

UI, nicht die Antwort, die ich erhofft hatte, aber auf ganz andere Art erhellend. Buchstaben jedes Wortes sortieren und vergleichen... ich komme mir gerade ziemlich doof vor. Aber zumindest habe ich was über Parallelisierung gelernt.

[TGGC]

Hatte mich auch schon gewundert, das du sowas kompliziertes machst. ;-)

[Bergmon]

Hast du es schon ein Mal mit http://msdn.microsoft.com/en-us/library ... rallel_for versucht? Vielleicht geht es dann mit den Containern.

Tipps für einen besseren Algorithmus wolltest du ja nicht, aber da schon jemand vor mir angefangen hat :mrgreen: ich auch:
EIn Anagram zwischen zwei Wörtern liegt genau dann vor, wenn beide Wörter die gleiche Anzahl an verschiedenen Buchstaben haben.

Das heißt, du kannst dir eine Abbildung aufbauen, die von deinem Alphabet, als mehrdimensionales Integer-Gitter aufgefasst, auf eine Menge von Wörtern abbildet. Dann zählst du einfach nur die Anzahl der Buchstaben des jeweiligen Wortes und fügst es unter dem Schlüssel (der einen Vektor in deinem Integer-Gitter darstellt) hinzu. Für längere Wörter (längere als die Anzahl der Symbole in deinem Alphabet) ist das vermutlich schneller, als die Wörter zu sortieren.

Viele Grüße
Bergmon

[Alexander Kornrumpf]

EIn Anagram zwischen zwei Wörtern liegt genau dann vor, wenn beide Wörter die gleiche Anzahl an verschiedenen Buchstaben haben.

Wie bitte? Alphabet {a, b, c, d}. Die Wörter ab und cd haben beide zwei verschiedene Buchstaben, sind aber keine Anagramme.

[Schrompf]

Ich denke, ich weiß, was er meint. Und inzwischen habe ich den Algorithmus auch nach Sternmulls Empfehlung auf SortierteBuchstaben-Keys umgebaut. Könnte jetzt bitte jemand was zu den Parallel-Teil sagen?

[dot]

Ich seh erstmal kein Problem mit deinem Container. Ich denk in dem Fall sollte es sogar ein fetch_add_explicit mit relaxed memory order tun...

[Krishty]

Warum nicht jeden Thread in seinen eigenen Container schreiben lassen, und in einem finalen Schritt alle Container zu einem verschmelzen? Üblicherweise bricht die Speicherbandbreite ein, wenn mehrere CPU-Kerne dieselbe Cache-Zeile im Wettlauf beackern, wie es bei einem nebenläufigen std::vector trotz lock-free halt immernoch der Fall ist (vier Kerne pollen und beschreiben im Wettlauf die Größenangabe).

Der Windows-Heap ist ebenfalls lock-free implementiert, dort wäre also auch keine versteckte Synchronisation. In einem Mehrprozessorsystem kannst du außerdem nur dann Gebrauch vom Vielfachen Cache machen, wenn die Kerne auch jeweils auf möglichst unterschiedlichen Daten operieren, und nicht alles in ein gemeinsames Array schmeißen, das dann als vielfache Kopie bei jedem Kern im Cache liegt. Denk dann aber an dein Hyper-Threading, wo plötzlich zwei Kerne um denselben Cache konkurrieren.

[Schrompf]

Gute Einwände. Allerdings kann ich dann kein simples OMP mehr benutzen. Aber mal leicht themenfremd eingeworfen: Eine ordentliche Jobqueue für alle möglichen Zwecke wäre aber eine gute Sache. Kriegen wir mal sowas zustande?