Wie verarbeitet man Std-Container mit Threads?

Question

Ich habe eine Sammlung (derzeit eine std::list<MyClass*>, aber es kann auch eine std::map<int, MyClass*> sein) mit dem Namen my_objects, die Zeiger auf MyClass Instanzen enthält.

Im Moment verarbeiten ich das Array wie folgt:

for(std::list<MyClass*>::iterator iterator = my_objects.begin(), end = my_objects.end(); iterator != end; ++iterator) { 

    (*iterator)->someFunction(); 
    // ... 

} 

someFunction einige der Eigenschaften des aktuellen Elements ändern kann, und kann einige der anderen Elemente Eigenschaften lesen. Aber es gibt keine Eigenschaft, die geändert und von einer anderen Instanz gelesen wird. Das Ergebnis ist unabhängig von der Reihenfolge der Iteration gleich.

Ich mag diese Schleife neu zu schreiben, std::thread vier zu verwenden, und das erste Viertel der Elemente mit dem ersten Thread zu verarbeiten, das zweiten Viertel mit dem Gewinde, etc ...

Ist es möglich, nach innen zu springen der Sammlung, und starten Sie die Iteration dort? Ist es die empfohlene Methode, eine Sammlung so zu verarbeiten? Wenn nicht, wie sollte dies geschehen?

Answer 1

Die empfohlene Methode besteht darin, einen Atomzähler zu verwenden, um eindeutige Objekte für jeden Thread zu verarbeiten. Die Thread-Funktion für jeden Thread sieht ähnlich wie dieser (Pseudocode):

std::atomic<int> atomic_ctr(0); 

void threadfunc() { 
    list_iterator iter = list.begin(); 
    int current_list_pos=0; 
    int next_pos; 
    while((next_pos = atomic_ctr++) < list.size()) { 
    while (current_list_pos < next_pos) { 
     ++iter; 
     ++current_list_pos; 
    } 
    iter->func(); 
    } 
} 

Answer 2

Im einfachsten Fall können Sie ein Worker-Objekt (innerhalb eines Threads) so erstellen, dass Sie es mit einem Verweis auf Ihren Container und zusätzlich den Bereich (Element-Index oder Iteratoren), den es ändern soll, konstruieren .

Wenn es wirklich keine Abhängigkeiten zu den Teilen der Daten gibt, die von Ihren Mitarbeitern geändert werden, sollte arbeiten, auch wenn es ein Hack ist.

Andernfalls müssen Sie eine Art Wrapper-Objekt um Ihren Container erstellen, das einen Sperrmechanismus zum Lesen und Schreiben bestimmter Elemente implementiert (ich würde boost :: upgrade_lock vorschlagen).

Ihre Thread-Worker-Objekte müssten dann mit diesem (gemeinsamen) Objekt für Lese- und Schreibzugriff auf Ihren Container sprechen.

Answer 3

Für den Anfang, moderner C++ Code verwendet Bereich Iteration:

for (const auto &ptr:my_objects) 
{ 
    ptr->someFunction(); 
} 

Reiniger, weniger tippen, vermeidet gemeinsame Iteration Tücke.

Nun, bis zur Partitionierung einer std::list gibt es keine std::list Methode, die einen ersten Iterator irgendwo in der Mitte der Liste zurückgibt. Mit den Random-Access-Iteratoren std::vector ist das trivial, aber das ist nicht, was ein std::list ist. Also, wenn Sie Ihren Container zu einem std::vector ändern möchten, wird dies ein Kinderspiel.

Es ist jedoch nicht wirklich schwer ist, über die gesamte Liste zu durchlaufen, aber nur jedes n te Element verarbeiten:

size_t p=0; 

for (const auto &ptr:my_objects) 
{ 
    if (p == 0) 
     ptr->someFunction(); 
    p = (p+1) % 4; 
} 

So, jetzt dieser Thread ruft someFunction() für jedes vierte Element in der Liste, und ein- viertes aller Elemente in der Liste.

Also, alles, was hier benötigt wird, sind vier Threads, die hier iterieren, mit dem einzigen Unterschied, dass der Anfangswert des ersten Threads von p auf 0 gesetzt wird, wie gezeigt; der Anfangswert des zweiten Threads von wird auf 1 gesetzt; und natürlich der Anfangswert des dritten und vierten Fadens von auf 2 und 3 gesetzt.

Dies teilt die Liste sauber in vier gleiche Teile auf, wobei Listenelemente einem der vier Threads zur Verarbeitung zugewiesen sind.