Strategien für die parallele Abarbeitung von Listen (c++ unter Linux)

SeppJ

taff schrieb:

Und da auf der Maschine noch weitere Services laufen, kann ich mir nicht einfach 100% eines Cores schnappen.

Läuft das Ding auf Windows 3.11 oder was? So etwas ist Aufgabe eines Schedulers, der über diesen Diensten läuft, nicht der Dienste selber.

taff

SeppJ schrieb:

taff schrieb:

Und da auf der Maschine noch weitere Services laufen, kann ich mir nicht einfach 100% eines Cores schnappen.

Läuft das Ding auf Windows 3.11 oder was? So etwas ist Aufgabe eines Schedulers, der über diesen Diensten läuft, nicht der Dienste selber.

Der Scheduler kann aber nicht mehr viel verteilen, wenn jeder Thread ohne pause 24h pro Tag 100% CPU-Last erzeugt.

Ich würde mich freuen, wenn du auf die anderen Fragen von mir bzgl. den weiteren angedeuteten Strategien von dir noch antworten könntest.

taff schrieb:

Und da auf der Maschine noch weitere Services laufen, kann ich mir nicht einfach 100% eines Cores schnappen.

taff schrieb:

Der Scheduler kann aber nicht mehr viel verteilen, wenn jeder Thread ohne pause 24h pro Tag 100% CPU-Last erzeugt.

Also entweder arbeitest DU auf einem extrem exotischen System oder Deine Vorstellung wie Threads funktionieren ist falsch. Für die Betriebssysteme mit denen ich arbeite gilt:

a) Natürlich kannst Du versuchen die 100% CPU Last zu schnappen, der Scheduler wird das schon richtig verteilen. Bei 8 Cores kann eh kein Thread mehr als 1/8tel der CPU Leistung belegen.

b) Kein Thread kann mehr systemlast bekommen als der Scheduler ihm zugesteht. Nicht der Task "nimmt" sich CPU, sondern der Scheduler "gibt" sie ihm. Und der der verteilt nach Prioritäten was zur Verfügung steht.

Ich glaube zunehmend das Du versuchst Probleme zu lösen die gar nicht existieren, bzw. die das Betriebssystem für Dich löst und dadurch hier auf Unverständnis stößt. Mir scheint Du versuchst den Task-Scheduler "nachzubauen" weil Dir nicht bewusst ist wie dieser Funktioniert.

Daher machen (für mich) auch solche Aussagen wie: "Alle 100 ne Pause machen." einfach keinen Sinn. Statt dessen würde man einfach den Thread laufen lassen und seine Priorität eben reduzieren....

Der klassische Ansatz ist einfach ganz ganz viele Threads zu erzeugen. Bei 100 Threads fällt es nicht mehr so ins Gewicht, wie der Scheduler sie verteilt.

PS: Über Multithreading mit Auslastung einzelner Cores zu argumentieren macht keinen Sinn.

taff

loks schrieb:

a) Natürlich kannst Du versuchen die 100% CPU Last zu schnappen, der Scheduler wird das schon richtig verteilen. Bei 8 Cores kann eh kein Thread mehr als 1/8tel der CPU Leistung belegen.

Wenn mein Service 5Threads hat und es laufen noch 10 weitere Services mit je 3 Threads, naja dann komm ich nach deiner "Lösung" auf 100% CPU-Last.

Ich finde, meine Fragestellung hat nichts damit zu tun ob ich pausieren will oder nicht. Es gibt einfach Gründe warum ich nicht in einem Rutsch das ganze durchlaufen will und wie hätte einfahc gerne erfahren wie man mittels mehreren Threads eine Abarbeitung realisiert.

rapso

taff schrieb:

rapso schrieb:

...
-- durchsucht die liste mit einem counter der pro element hochgezaehlt wird und bei z.B. counter==1000 -> liste unlock; sleep(100); liste lock und nochmal von vorne ueber die elemente iterieren bis der thread bei einem nicht markierten glied der liste ankommt und da weiter arbeitet.

@taff ist etwas davon falsch?

Ja das ist schon sehr nah an dem wie ich es habe.
Es gibt eben dann später Thread A1 und A2
Problem ist der sinnlose Overhead mit dem Durchlauf bis zum nicht markierten Objekt....

denkst du nicht, dass das problem eher ist dass du zwei threads hast, aber nur _ein_ gelocktes datenset hast.
effektiv laeuft doch immer nur ein thread waehrend der andere sleept/wartet, oder?

das ist als ob du zwei ferraris haettest, weil du mit einem 350km/h fahren kannst, mit zweien hast du 2*350km/h. effektiv faehrst du immer nur einen.

oder hab ich das missverstanden?

falls dem so ist, musst du fundamental etwas aendern, und dann wirst du das jetztige problem garnicht mehr haben.

taff

rapso schrieb:

denkst du nicht, dass das problem eher ist dass du zwei threads hast, aber nur _ein_ gelocktes datenset hast.
effektiv laeuft doch immer nur ein thread waehrend der andere sleept/wartet, oder?

Die beiden Threads A1, A2 machen einen ReadLock auf die liste und dann wird das Listenelement an sich noch gelockt --> somit kann sich der andere thread auch durch die liste bewegen.

Ich kann mir auch genau so gut vorstellen, dass ich auch ständig eine queue fülle und diese abarbeite

knivil

100% CPU-Last

Ich sehe da kein Problem an sich. Der Scheduler des Betriebssystems sollte Rechenzeit gerecht verteilen. Ist fuer den Thread keine Arbeit vorhanden, dann gibt es geeignete Synchronisationsmechanismen.

Und da auf der Maschine noch weitere Services laufen, kann ich mir nicht einfach 100% eines Cores schnappen.
Auch andere Threads können auf diese Datenstruktur zugreifen

Fuer den Schutz von Datenstrukturen vor nebenlaeufigem Zugriff existieren geeignete Synchronisationsmechanismen. Schlafen ist in den meisten Faellen ungeeignet.

Ja ein Grund ist, dass ich immer wieder zurückkehre ist, dass der Abbruch des Threads nur in der Thread-Schleife passieren sollte und nicht in anderen Strukturen

Ist normalerweise kein Problem. Beispielsweise kann von ausserhalb ein "stop"-Flag gesetzt werden, dass innerhalb des Threads abgefragt wird.

Das hört sich schon interessanter an

Nun, anscheinend bist du Anfaenger in Bezug auf parallele Programmierung.

Grundsätzlich hätte ich gerne div. Lösungwege gelesn oder ob es hier so eine Art Design-Patterns auch für ständiges paralleles Abarbeiten von Listen gibt

Ja, gibt es. Welche Buecher/Artikel/Tutorials hast du dir schon angesehen?

rapso

taff schrieb:

rapso schrieb:

denkst du nicht, dass das problem eher ist dass du zwei threads hast, aber nur _ein_ gelocktes datenset hast.
effektiv laeuft doch immer nur ein thread waehrend der andere sleept/wartet, oder?

Die beiden Threads A1, A2 machen einen ReadLock auf die liste und dann wird das Listenelement an sich noch gelockt --> somit kann sich der andere thread auch durch die liste bewegen.

also arbeitet entweder
thread A drauf und thread B gammelt
oder
Thread B drauf und thread A gammelt
?

Ich kann mir auch genau so gut vorstellen, dass ich auch ständig eine queue fülle und diese abarbeite

1. du muestest uns/mir mal beschreiben was du eigentlich machst bzw vor hast.
soweit ich sehe hast du:
- ein set von daten
- fuer jeden eintrag soll "GemeindePruefung" aufgerufen werden
- das datenset wir an sich bearbeitet (was genau? sortiert? fuegst du was hinzu? entfernst? modifizierst?)
- ...

2. was macht thread B waehrend thread A die aufrufe macht? wartet der wirklich nur auf thread A dass die daten freigegeben werden? wieviel geschwindigkeitszuwachs hattest du durch das aufteilen in 2 threads erhalten?

3. wie lange dauern die 100aufrufe von thread A? 1ms? 1s? 10s? 10min? von sowas haengt auch ab wie fein granular man die threads synchronisieren wuerde.

taff

knivil schrieb:

Fuer den Schutz von Datenstrukturen vor nebenlaeufigem Zugriff existieren geeignete Synchronisationsmechanismen. Schlafen ist in den meisten Faellen ungeeignet.

du meinst einen lock? Ja das wird sowieso gemacht

knivil schrieb:

Ja ein Grund ist, dass ich immer wieder zurückkehre ist, dass der Abbruch des Threads nur in der Thread-Schleife passieren sollte und nicht in anderen Strukturen

Ist normalerweise kein Problem. Beispielsweise kann von ausserhalb ein "stop"-Flag gesetzt werden, dass innerhalb des Threads abgefragt wird.

Deswegen u.a. auch die unterbrechung der Abbarbeitung, weil dieses "stop" habe ich ungern in der Datenstruktur drinnen.

knivil schrieb:

Das hört sich schon interessanter an

Nun, anscheinend bist du Anfaenger in Bezug auf parallele Programmierung.

Ich habe nie was anderes behauptet, oder?

knivil schrieb:

Grundsätzlich hätte ich gerne div. Lösungwege gelesn oder ob es hier so eine Art Design-Patterns auch für ständiges paralleles Abarbeiten von Listen gibt

Ja, gibt es. Welche Buecher/Artikel/Tutorials hast du dir schon angesehen?

ich kenne eigentlich nur die 0815-Patterns (factory, singleton, adapter, usw.), aber ev. könntest du mir Tipps in diesem Bereich für paralles Abarbeiten geben?

rapso schrieb:

taff schrieb:

rapso schrieb:

denkst du nicht, dass das problem eher ist dass du zwei threads hast, aber nur _ein_ gelocktes datenset hast.
effektiv laeuft doch immer nur ein thread waehrend der andere sleept/wartet, oder?

Die beiden Threads A1, A2 machen einen ReadLock auf die liste und dann wird das Listenelement an sich noch gelockt --> somit kann sich der andere thread auch durch die liste bewegen.

also arbeitet entweder
thread A drauf und thread B gammelt
oder
Thread B drauf und thread A gammelt
?

Nein, warum sollte ein Thread gammeln? Mittels dem Readlock können beide Threads auf die Vectoren zugreifen und der Zugriff auf das Daten-Objekt (=Gemeinde) wird mittels TryWriteLock gemacht und somit blockiert mich auch nicht der andere Thread beim Durchlauf.

rapso schrieb:

Ich kann mir auch genau so gut vorstellen, dass ich auch ständig eine queue fülle und diese abarbeite

1. du muestest uns/mir mal beschreiben was du eigentlich machst bzw vor hast.
soweit ich sehe hast du:
- ein set von daten
- fuer jeden eintrag soll "GemeindePruefung" aufgerufen werden
- das datenset wir an sich bearbeitet (was genau? sortiert? fuegst du was hinzu? entfernst? modifizierst?)
- ...

2. was macht thread B waehrend thread A die aufrufe macht? wartet der wirklich nur auf thread A dass die daten freigegeben werden? wieviel geschwindigkeitszuwachs hattest du durch das aufteilen in 2 threads erhalten?

3. wie lange dauern die 100aufrufe von thread A? 1ms? 1s? 10s? 10min? von sowas haengt auch ab wie fein granular man die threads synchronisieren wuerde.

ad1)
- Für jede Gemeinde wird eine Prüfung gemacht (nur für diesen benötige ich Thread A1 & A2)
- Die Gemeinde kann einem anderen Bundesland zugewiesen gelöscht oder neu angelegt werden.
- Die Gemeinde daten werden auch aktualisiert

ad2) Wie vorhin beschrieben wartet Thread A nicht auf B. Die Überprüfung aller Daten ist nun ca. um 35% schneller (statt 10sec nun 6-7sec)

ad 3) Das kann man so nicht sagen, weil 100 Überprüfungen können 50msec sein, aber auch einmal 100msec.

Wie gesagt geht es mir nicht darum, dass ich es nicht nicht funktioniert, sondern wie ich das ganze optimal löse ohne unnötigen overhead (überspringen der schon überprüften Gemeinden, etc.)

rapso

taff schrieb:

rapso schrieb:

taff schrieb:

rapso schrieb:

denkst du nicht, dass das problem eher ist dass du zwei threads hast, aber nur _ein_ gelocktes datenset hast.
effektiv laeuft doch immer nur ein thread waehrend der andere sleept/wartet, oder?

Die beiden Threads A1, A2 machen einen ReadLock auf die liste und dann wird das Listenelement an sich noch gelockt --> somit kann sich der andere thread auch durch die liste bewegen.

also arbeitet entweder
thread A drauf und thread B gammelt
oder
Thread B drauf und thread A gammelt
?

Nein, warum sollte ein Thread gammeln?

das war meine initialle kristalkugelleserei die du mit "ja" beantworte hattest

Mittels dem Readlock können beide Threads auf die Vectoren zugreifen und der Zugriff auf das Daten-Objekt (=Gemeinde) wird mittels TryWriteLock gemacht und somit blockiert mich auch nicht der andere Thread beim Durchlauf.

das problem ist aber, dass der trywritelock nur erfolgreich ist, wenn du die Thread A0, A1... regelmaessig (also nach 100iterationen) unlocken laesst und die dann ne zeitlang 'gammeln' ?

rapso schrieb:

Ich kann mir auch genau so gut vorstellen, dass ich auch ständig eine queue fülle und diese abarbeite

1. du muestest uns/mir mal beschreiben was du eigentlich machst bzw vor hast.
soweit ich sehe hast du:
- ein set von daten
- fuer jeden eintrag soll "GemeindePruefung" aufgerufen werden
- das datenset wir an sich bearbeitet (was genau? sortiert? fuegst du was hinzu? entfernst? modifizierst?)
- ...

2. was macht thread B waehrend thread A die aufrufe macht? wartet der wirklich nur auf thread A dass die daten freigegeben werden? wieviel geschwindigkeitszuwachs hattest du durch das aufteilen in 2 threads erhalten?

3. wie lange dauern die 100aufrufe von thread A? 1ms? 1s? 10s? 10min? von sowas haengt auch ab wie fein granular man die threads synchronisieren wuerde.

ad1)
- Für jede Gemeinde wird eine Prüfung gemacht (nur für diesen benötige ich Thread A1 & A2)
- Die Gemeinde kann einem anderen Bundesland zugewiesen gelöscht oder neu angelegt werden.
- Die Gemeinde daten werden auch aktualisiert

ad2) Wie vorhin beschrieben wartet Thread A nicht auf B.

wenn Thread A staendig auf den daten arbeiten mittels readlock, wie koennte thread B jemals drankommen mit dem trywritelock? doch nur indem thread A ab und zu pausiert um zu warten dass thread B eine chance bekommt, oder?

Die Überprüfung aller Daten ist nun ca. um 35% schneller (statt 10sec nun 6-7sec)

ad 3) Das kann man so nicht sagen, weil 100 Überprüfungen können 50msec sein, aber auch einmal 100msec.

Wie gesagt geht es mir nicht darum, dass ich es nicht nicht funktioniert, sondern wie ich das ganze optimal löse ohne unnötigen overhead (überspringen der schon überprüften Gemeinden, etc.)

mein vorschlag:
ein einziges simples lock fuer das array
jeglicher thread der traversiert muss das lock halten
die "A"s markieren dabei das element das sie bearbeiten mit einem 'lock' was nicht atomic sein muss da sie ja schon das globale lock halten. und in dem moment lassen sie das lock auch schon los und merken sich nur den index an dem sie sind.
wenn "A"s fertig sind (was deiner angabe ca einmal pro ms passiert), nehmen sie sich das lock wieder, 'unlocken' ihr element, traversieren eins weiter und locken das element und lassen das globale lock wieder los.
"B" kann sich das lock nun viel oefter schnappen, denn thread "A" haelt es nur microsekunden waehrend der traversierung, also ca 0.1% der zeit und thread "B" kann elemente vertauschen, sofern sie nicht selbst gelockt sind. Da thread "A" nur einen index hat, darf der vector der elemente (das muessen natuerlich pointer vector sein) frei vertauschen usw.

ich nehme jetzt mal an die reihenfolge der elemente ist nicht wichtig und thread A iteriert eh im loop ueber alles, sodass es nicht tragisch ist, dass es eine kleine chance gibt ein element mal in einem loop durchgang nicht zu erwischen.

auf diese weise hast du kaum synchronizations overhead zwischen den threads, du koenntest von thread "A" einige erstellen die vor sich hin arbeiten und haettest eine relativ lineare performance skalierung. (bis du keine cores mehr frei hast)

taff

@rapso
Danke für deine Erklärung und Bespiele.
Irgendwie kommt mir vor, dass wir das gleiche meine, aber unterschiedliches schreiben

Ich poste nochmal meine Datenstruktur und erweitere um die Locks

class Gemeinde
{
public:
    RwLock gemeindelock;
    Gemeinde();
    GemeindePruefung();
};

class Bundesland
{
public:
    std::vector<boost::shared_ptr<Gemeinde> > gemeinden;
    Bundesland();
};

class Staat
{
public:
    RwLock vectorenlock;
    std::vector<boost::shared_ptr<Bundesland> > bundeslaender;
    Staat();
};

Die Threads A1 und A2 machen einen vectorenlock.ReadLock() --> somit können A1/A2 ohne Einschränkung durch die Vectoren wandern.

GemeindePruefung() ruft gemeindelock.TryWriteLock() auf
--> ist der lock erfolgreich, dann wird die eigentlich GemeindePruefung gemacht
--> der lock ist nicht erfolgreich es wird keine GemeindePruefung gemacht und zu der nächsten Gemeinde somit weiter gegangen.
--> für A1/A2 muss kein "gammelen" notwendig sein, damit jeder Thread erfolgreich arbeiten kann.
--> nach zb. 100 erfolgreichen, also wo TryWriteLock möglich war und wo die Gemeinde auch noch nicht abgearbeitet wurde, wird eben der Vorgang abgebrochen
und nun wird "gegammelt", damit Thread B Bundesland/Gemeinde verschieben/löschen/einfügen/aktualisieren kann.

Ich glaube bis zu dieser Stelle habe ich nichts falsch gemacht und die beiden Threads A1/A2 schließen sich auch nicht gegenseitig aus (jedenfalls funktioniert die Abarbeitung ja jetzt schneller)

Wenn ich das Richtig verstehe, würdest du rapso den vectorenlock sofort wieder unlockenn, wenn ich mir den Gemeinde-SmartPtr geholt habe. Und ich muss mit einem Index arbeiten, statt mit Iteratoren
--> dadurch würden die Threads B/C/etc. schneller zum Zug kommen

Und ja es ist egal, wenn ich mal eine Gemeinde nicht sofort abarbeite/überprüfe, aber ich muss ständig die beiden Indizes überprüfen ob sie eh kleiner sind als die Größe der Vectoren --> ist dieser Aufwand eher egal? Oder eben der Lock-Aufwand, dass nun

Die beiden Threads A1/A2 dürfen ruhig die anderen Threads ausbremsen bzw. ordnen sich die anderen Threads B/C/etc ja sowieso durch ein WriteLock auf Vectorenebene zur Abarbeitung ein.

ABER
- Da ich mehrfach verschachtelte Vectoren habe, ist es dann schon noch so geschickt, wenn ich mir dann hier die div. Indizes merke? Weil ev. finde ich meine letzte Gemeinde gar nicht mehr in dem Bundesland?
- Soll ich mir den "Luxus" leisten und zusätzlich noch einen globalen GemeindeVector führen? zb. std::vector<boost::shared_ptr<Gemeinde> > allegemeinden; und so eine Abarbeitung vereinfachen?
- Oder Wäre es sogar sinnvoller, wenn man alle Gemeinden zusätzlich noch in eine AbarbeitungsQueue gibt und auf diesem Weg sich A1/A2 immer eine Gemeinde rausholen und abarbeiten bis die Queue leer ist --> anschließend wird sie wieder gefüllt für die nächste Abarbeitung. Vorteil davon wäre, dass die anderen Threads von A1 und A2 nicht blockiert werden (außer beim Füllen der AbarbeitungsQueue)

rapso

taff schrieb:

Die Threads A1 und A2 machen einen vectorenlock.ReadLock() --> somit können A1/A2 ohne Einschränkung durch die Vectoren wandern.

GemeindePruefung() ruft gemeindelock.TryWriteLock() auf
--> ist der lock erfolgreich, dann wird die eigentlich GemeindePruefung gemacht
--> der lock ist nicht erfolgreich es wird keine GemeindePruefung gemacht und zu der nächsten Gemeinde somit weiter gegangen.
--> für A1/A2 muss kein "gammelen" notwendig sein, damit jeder Thread erfolgreich arbeiten kann.
--> nach zb. 100 erfolgreichen, also wo TryWriteLock möglich war und wo die Gemeinde auch noch nicht abgearbeitet wurde, wird eben der Vorgang abgebrochen
und nun wird "gegammelt", damit Thread B Bundesland/Gemeinde verschieben/löschen/einfügen/aktualisieren kann.

genau das meine ich mit 'gammeln'
wenn Threads A1/A2 einen lock auf die gemeinde haben, dann koennen sie den lock auf den vector loesen und muessen garnicht nach n-iterationen gammeln.

Ich glaube bis zu dieser Stelle habe ich nichts falsch gemacht und die beiden Threads A1/A2 schließen sich auch nicht gegenseitig aus (jedenfalls funktioniert die Abarbeitung ja jetzt schneller)

Threads A und Thread B schliessen sich aus, wobei 99.9% der zeit niemand auf dem vector arbeitet.

Wenn ich das Richtig verstehe, würdest du rapso den vectorenlock sofort wieder unlockenn, wenn ich mir den Gemeinde-SmartPtr geholt habe. Und ich muss mit einem Index arbeiten, statt mit Iteratoren
--> dadurch würden die Threads B/C/etc. schneller zum Zug kommen

genau meine intention. dann wuerdest du mehr parralelitaet haben (also schneller sein) und zugleich das ursprungsproblem vom 'von anfang an iterieren' garnicht haben, da die Thread A nichtmal wissen, ob/dass Thread B etwas machte.

Und ja es ist egal, wenn ich mal eine Gemeinde nicht sofort abarbeite/überprüfe, aber ich muss ständig die beiden Indizes überprüfen ob sie eh kleiner sind als die Größe der Vectoren --> ist dieser Aufwand eher egal? Oder eben der Lock-Aufwand, dass nun

ich weiss nicht genau was du damit meinst. welche zwei indices? wozu ueberpruefen? was genau ist "staendig", ist es das was "gemeindepruefung" macht? oder meinst du beim iterieren waehrend du den lock haelst?

Die beiden Threads A1/A2 dürfen ruhig die anderen Threads ausbremsen bzw. ordnen sich die anderen Threads B/C/etc ja sowieso durch ein WriteLock auf Vectorenebene zur Abarbeitung ein.

ABER
- Da ich mehrfach verschachtelte Vectoren habe, ist es dann schon noch so geschickt, wenn ich mir dann hier die div. Indizes merke? Weil ev. finde ich meine letzte Gemeinde gar nicht mehr in dem Bundesland?

davon wuste ich bisher nichts. eventuell kannst du die verschachtelten vectoren auch nur per pointer referenzieren, dann waere es egal wie tief du in der rekursion bist, du muestest dir nur einen pointer zum aktuellen vector objekt ablegen und den index darin (vielleicht einen custom iterator dafuer schreiben sodass du per typedef zwischen der jetzigen und der neuen loesung wechseln kannst?)

- Soll ich mir den "Luxus" leisten und zusätzlich noch einen globalen GemeindeVector führen? zb. std::vector<boost::shared_ptr<Gemeinde> > allegemeinden; und so eine Abarbeitung vereinfachen?
- Oder Wäre es sogar sinnvoller, wenn man alle Gemeinden zusätzlich noch in eine AbarbeitungsQueue gibt und auf diesem Weg sich A1/A2 immer eine Gemeinde rausholen und abarbeiten bis die Queue leer ist --> anschließend wird sie wieder gefüllt für die nächste Abarbeitung. Vorteil davon wäre, dass die anderen Threads von A1 und A2 nicht blockiert werden (außer beim Füllen der AbarbeitungsQueue)

falls das nicht zuviel overhead ist fuer Thread B (der vermutlich die queue fuellen muss) koenntest du das machen. an sich sind solche producer-consumer architekturen zu bevorzugen, da es ohne locks auf den eigentlichen daten einfach ueber die container die 'ownership' regeln (du bist also nicht intrusive nur um die hardware besser zu belasten).
du kannst das befuellen optimieren indem du entweder
a) double buffered queues machst, also immer wenn eine leer ist, wird ein pointer vertauscht und die As haben eine neue volle queue und muessen nicht 'gammeln' und zugleich hat Thread B eine neue leere queue die 'irgendwann in naechster zeit' befuellt werden koennte.
b) du machst einen cirkularen buffer (round robin queuing). so kann Thread B immer weiter daten nachschieben und threads A koennen die queue immer weiter leeren.

in einem optimalen system gebe es an sich nur 'worker', falls die queue voll laeuft, wuerden ALLE threads die A aufgabe uebernehmen und falls die queue leer ist, alle als B die queue befuellen. oder um es noch flexibler zu halten, die queue haette die "tasks" der einzelnen woerker enthalten. ein 'fueller B' wuerde z.b. die halbe queue mit A-tasks befuellen und am ende ein B-Task einfuegen, anschliessen weiter den rest befuellen und wieder ein B-Task einfuegen. immer wenn die halbe queue leer waere, wuerde ein thread einen B-Task aufgreifen und die queue befuellen. auf diese weise koenntest du vielleicht 100 threads haben und 99mal schneller sein als mit einem thread.

Buffer[8]={A,A,A,B,A,A,A,B};
.
.
size_t TaskIndexGet=0;
size_t TaskIndexPut=8;
do
{
  if(TaskIndexGet>=TaskIndexPut)
    continue;
  T=Buffer[TaskIndexGet++%8];
  switch(T)
  {
    case A:doA();break;
    case B:FillBuffer();TaskIndexPut+=4;break;
  }  
}while(true);

das ist noch nicht safe, soll nur die grobe idee von wiedergeben falls du dein system weiter ausbauen wollen wuerdest

taff

rapso schrieb:

genau das meine ich mit 'gammeln'
wenn Threads A1/A2 einen lock auf die gemeinde haben, dann koennen sie den lock auf den vector loesen und muessen garnicht nach n-iterationen gammeln.

Threads A und Thread B schliessen sich aus, wobei 99.9% der zeit niemand auf dem vector arbeitet.

genau meine intention. dann wuerdest du mehr parralelitaet haben (also schneller sein) und zugleich das ursprungsproblem vom 'von anfang an iterieren' garnicht haben, da die Thread A nichtmal wissen, ob/dass Thread B etwas machte.

Die Tätigkeit von den anderen Threads B/C/etc. ist nicht sehr hoch, also wäre es nicht so wichtig, aber wenn man das alles theoretisch angeht und die Möglichkeiten für "starke" andere Threads erlauben möchte, dann ist die Lösung sicher besser

rapso schrieb:

ich weiss nicht genau was du damit meinst. welche zwei indices? wozu ueberpruefen? was genau ist "staendig", ist es das was "gemeindepruefung" macht? oder meinst du beim iterieren waehrend du den lock haelst?

Wenn man von einer Gemeinde zur anderen springt muss ich den Bundesland-idx überprüfen ( Bundesland-idx < bundeslander.size()) und auch den Gemeinde-idx < gemeinden.size() und dies muss ich quasi ständig überprüfen (inkl. lock)

rapso schrieb:

davon wuste ich bisher nichts. eventuell kannst du die verschachtelten vectoren auch nur per pointer referenzieren, dann waere es egal wie tief du in der rekursion bist, du muestest dir nur einen pointer zum aktuellen vector objekt ablegen und den index darin (vielleicht einen custom iterator dafuer schreiben sodass du per typedef zwischen der jetzigen und der neuen loesung wechseln kannst?)

also den smart-ptr auf das bundesland merken und dann den idx auf die Gemeinde. Nur wie komm ich dann auf das nächste Bundesland, wenn der smart-ptr abgearbeitet wurde, weil eigentlich weiß ich ja gar nicht wo genau mein Bundesland ist.
Oder ich verstehe deinen Lösungsvorschlag nicht

rapso schrieb:

falls das nicht zuviel overhead ist fuer Thread B (der vermutlich die queue fuellen muss) koenntest du das machen. an sich sind solche producer-consumer architekturen zu bevorzugen, da es ohne locks auf den eigentlichen daten einfach ueber die container die 'ownership' regeln (du bist also nicht intrusive nur um die hardware besser zu belasten).

Moment. Warum komme ich dann ohne locks auf die daten aus? ich würde ja trotzdem mit allen Threads dank smart-ptr auf die gleichen Daten zugreifen, aber eben nicht über die gleiche Listen-Struktur.

rapso schrieb:

du kannst das befuellen optimieren indem du entweder
a) double buffered queues machst, also immer wenn eine leer ist, wird ein pointer vertauscht und die As haben eine neue volle queue und muessen nicht 'gammeln' und zugleich hat Thread B eine neue leere queue die 'irgendwann in naechster zeit' befuellt werden koennte.
b) du machst einen cirkularen buffer (round robin queuing). so kann Thread B immer weiter daten nachschieben und threads A koennen die queue immer weiter leeren.

hmm und welche der beiden Lösungen ist besser geeignet, wenn man die Queue nie überfüllen möchte? Also wenn Thread A1/A2 nicht so schnell abarbeiten können wie Thread B nachschiebt (was ja bei Lösung B passieren könne) ?

rapso schrieb:

in einem optimalen system gebe es an sich nur 'worker', falls die queue voll laeuft, wuerden ALLE threads die A aufgabe uebernehmen und falls die queue leer ist, alle als B die queue befuellen. oder um es noch flexibler zu halten, die queue haette die "tasks" der einzelnen woerker enthalten. ein 'fueller B' wuerde z.b. die halbe queue mit A-tasks befuellen und am ende ein B-Task einfuegen, anschliessen weiter den rest befuellen und wieder ein B-Task einfuegen. immer wenn die halbe queue leer waere, wuerde ein thread einen B-Task aufgreifen und die queue befuellen. auf diese weise koenntest du vielleicht 100 threads haben und 99mal schneller sein als mit einem thread.
Buffer[8]={A,A,A,B,A,A,A,B};
.
.
size_t TaskIndexGet=0;
size_t TaskIndexPut=8;
do
{
  if(TaskIndexGet>=TaskIndexPut)
    continue;
  T=Buffer[TaskIndexGet++%8];
  switch(T)
  {
    case A:doA();break;
    case B:FillBuffer();TaskIndexPut+=4;break;
  }  
}while(true);
das ist noch nicht safe, soll nur die grobe idee von wiedergeben falls du dein system weiter ausbauen wollen wuerdest

danke der Vorschlag hilft mir sehr weiter