Pointer Mutex Threads

[acdc]

Hallo,


ich habe jetzt schon ein größeres Programm, das mitunter 2 Stringlisten vergleicht, die jeweils in einer QStringList gespeichert sind.

inStringList = ISL
Liste in der gesucht wird
forStringList = FSL
Listenelemente, nach denen in der inStringList gesucht werden soll

Da das ganze mit mehreren Threads laufen soll, damit auch 2 oder mehr CPUs genutzt werden können, teile ich die FSL in mehrere teillisten auf und übergebe jedem Thread einen Teil.
Nun bekommt auch jeder Thread die ganze ISL - Liste (welche sehr lange und daher groß sein kann). Die ÜBergabe funktioniert hier mit einem Pointer und somit nutzen mehrere Threads den Speicherplatz, auf welchen dieser Pointer der ISL zeigt.

Wenn nun gleiche Elemente gefunden werden, müssten die betroffenen Elemente in der ISL nicht mehr beachtet werden und könnten aus der ISL gelöscht werden. So kann es vorkommen, dass mehrere Threads zugleich auf diesen Speicher (der immer über Pointer angesprochen wird) lesend und schreiben zugreifen und somit sicher Probleme entstehen.

Ich habe gelesen, dass man mit einem QMutex eine Variable schützen kann. Ich habe mir das entwa so überlegt:

Code: Alles auswählen

class thread1 : public QThread
{
  QMutex mutexThread1;
  QStringList *ISL;
  ...
}

//Thread 
 void thread1::run()
 {
     mutexThread1.lock();
     ISL->() .. operationen lesen/schreiben
     mutexThread1.unlock();
 }

QStringList *inList=new QStringList;


//  listenerstellung
  QSTringList forlist;
  for(..)
    inList->append(sx);
// threads
  thread1 *t1=new thread1(forlist,inList); //übergabe jeweils einmal per Value und einmal mit Pointer
  thread1 *t2=new thread1(forlist,inList);
  thread1 *t3=new thread1(forlist,inList);
  
//threads starten
  t1->start(); 
  t2->start();
  t3->start();
  
  
*/

Wäre das grundsätzlich richtig, oder gehe ich da etwas ganz falsch an?

In der Doku steht, dass es folgende Möglichkeiten gibt:
QMutex
QMutexLocker
QReadLocker
QReadWriteLock
QWriteLocker

Ist eine dieser Klassen besonders geeignet für meine Aufgabe?
Wie schütze ich jetzt den Speicher, auf den der Pointer zeigt, richtig?
Wie kann ich testen, ob es keine Konflickte zwischen den Threads gibt?

Danke für eure Antworten, ich hoff ich habe nichts wichtiges vergessen.
Benutze Qt 4.7 auf Windows 7

acdc

[solarix]

Wie die Aufgabe zu bewältigen ist, ist für Aussenstehende schwierig zu beurteilen (wie gross ist z.B. "sehr gross"? Ist das Entfernen aus der ISL notwendig oder nur eine Optimierung (auf welche evt. verzichtet werden könnte)).

Aber zwei Denkanstösse kann ich schonmal schreiben:

1. Du musst die Daten schützen, nicht die Threads . Wenn du pro Thread ein Mutex erzeugst, bringt das ja nichts. Du brauchst 1 Mutex für 1 Stringlist. Was Thread-Entwickler in solchen Fällen tun ist, einen eigenen, thread-sicheren, Datenpool zu entwickeln (in deinem Fall: eine neue Klasse, welche die StringList durch den Mutex schützt).

2. Wenn du den Zugriff auf die Liste mit einem Mutex serialisierst, bringen die Threads nichts mehr, weil immer nur einer darauf arbeiten kann, während die anderen warten... mit anderen Worten: die Aufgabe wird von X-Threads genau gleich schnell bearbeitet wie von einem einzigen..

[acdc]

Danke für die rasche Antwort.

Derzeit sind die beiden Listen so 50000 Einträge groß. Wenn die beiden Listeninhalte ungleich sind, dann ergibt sich die Problematik nicht, da man ohnehin jedes mit jedem vergleichen muss.
Nur wenn die Beiden gleichen Inhalts sind, könnte man in einer Liste die bereits gefundenen Einträge löschen und nicht nochmals durchlaufen.

mhm, also benötige ich einen Mutex für eine Stringlist - ok jetzt ergibt das Sinn. Das hob ich noch nirgendends gelesen.

Dann ist das Ganze eigentlich unsinnig und kann mit einem Thread genau so gut bearbeitet werden.

Wenn ich die Stringliste nur lese, muss ich dann auch einen Mutex benutzen?

acdc

[padreigh]

Keine Antort auf deine Frage, bitte hier nicht weiterlesen wenn nicht daran interessiert.

warum umgehst du das Problem nicht einfach, indem du die inListe splittest?
Dann kannst du jedem Thread alle Suchbegriffe mitgeben (const Stringlist &) und eine Teil-inListe die er nach belieben verändern darf.

Ich nehme mal an das deine Datenmengen so groß sind das ein einfaches

Code: Alles auswählen

foreach(const QString & searchIt, forStringList)
   inStringList.removeAll(searchIt);

nicht ausreicht?

Ansonsten ist es glaube ich sinnvoller den QWriteLocker oder QMutexLocker zu nutzen, die brauchst du nur einmal setzen und sie lösen sich auf wenn sie den Scope verlassen --> weniger Fehler

Je nachdem könnte es sich auch lohnen auf den Listen ein

Code: Alles auswählen

removeDuplicates ()

zu nutzen, kommt auf die Art der Daten an, wenn dadurch massiv reduziert wird ...

[acdc]

Keine Antort auf deine Frage, bitte hier nicht weiterlesen wenn nicht daran interessiert.

warum umgehst du das Problem nicht einfach, indem du die inListe splittest?
Dann kannst du jedem Thread alle Suchbegriffe mitgeben (const Stringlist &) und eine Teil-inListe die er nach belieben verändern darf.

Ich nehme mal an das deine Datenmengen so groß sind das ein einfaches

Code: Alles auswählen

foreach(const QString & searchIt, forStringList)
   inStringList.removeAll(searchIt);

nicht ausreicht?

Ansonsten ist es glaube ich sinnvoller den QWriteLocker oder QMutexLocker zu nutzen, die brauchst du nur einmal setzen und sie lösen sich auf wenn sie den Scope verlassen --> weniger Fehler

Naja, die Inliste splitten ist so eine sache, da meine beiden Listen gleich sind und ich nicht jedes mit jedem vergleichen möchte. Wenn ich nun Gleiche finde, so möchte ich diese Information an alle anderen Threads weiterleiten und ihnen sagen, dass sie zum Beispiel das 300. Element nicht mehr untersuchen brauchen! Damit werden die zu Verlgeichenden Elemente immer weniger. Das wollte ich durch das Löschen dieser Elemente in der gemeinsamen Stringliste ermöglichen.

Wäre auch über signals möglich?!

acdc

[solarix]

Wäre auch über signals möglich?!

Selbstverständlich..

Aber mal unter uns: lohnt sich das überhaupt? Wieviele Elemente meinst du, werden da pro Auftrag entfernt? Wenn das von 50000 ein paar hundert sind, würde ich da keinen grossen Wirbel drum machen..

[acdc]

Wäre auch über signals möglich?!

Selbstverständlich..

Aber mal unter uns: lohnt sich das überhaupt? Wieviele Elemente meinst du, werden da pro Auftrag entfernt? Wenn das von 50000 ein paar hundert sind, würde ich da keinen grossen Wirbel drum machen..

Wenn man das reine Vergleichen von Strings beachtet, ist das sicher nicht ausschlaggebend. Verwende ich jetzt aber andere Daten, dann kann das vergleichen länger dauern und somit wäre eine Parallelisierung sinnvoll und das Abnehmen der Datenmenge wäre gut.
Sind die beiden listen gleich und ich vergleiche das Erst mit dem Ersten, so sind die Beiden gleich und ich brauch beim nächsten Durchgang das Erste nicht mehr ansehen usw.

Somit sind beim letzten Vergleich alle vorigen Element bereits gelöscht und muss nicht nochmal die gesamte liste durchackern.

Eigentlich ist es mir jetzt nur um die Mutexgrundlagen gegangen. Aber wenn auf Grund eines Mutex erst wieder eine serielle Verarbeitung das Resultat ist, dann muss ich mir das irgendwie anders überlegen.

acdc

[solarix]

Ist der Aufwand des Vergleichens wirklich ausschlaggebend? Prozentual ist der Unterschied zwischen einer Liste von integern und einer Liste mit grossen structs genau gleich (Beispiel: mit integern 1.1s, mit structs 1.1min).. das ist dem Anwender doch egal.

Was ich dir mitteilen möchte ist folgendes: bei Optimierungen erreicht man meist die ersten 90% mit 50% Projektaufwand.. für die restlichen 10% Gewinn investierst du dann nochmals 50% Projektaufwand (Zeit).
Also: wenn du mit Threads auf einfache Weise den Vorgang von 30s auf 10s kriegst: mach es. Wenn du dann noch eine (aufwendige, mit Mutexes, Signals usw.) Variante siehst, um von 10s noch auf 9 zu kommen: lass es

[acdc]

Ist der Aufwand des Vergleichens wirklich ausschlaggebend? Prozentual ist der Unterschied zwischen einer Liste von integern und einer Liste mit grossen structs genau gleich (Beispiel: mit integern 1.1s, mit structs 1.1min).. das ist dem Anwender doch egal.

Was ich dir mitteilen möchte ist folgendes: bei Optimierungen erreicht man meist die ersten 90% mit 50% Projektaufwand.. für die restlichen 10% Gewinn investierst du dann nochmals 50% Projektaufwand (Zeit).
Also: wenn du mit Threads auf einfache Weise den Vorgang von 30s auf 10s kriegst: mach es. Wenn du dann noch eine (aufwendige, mit Mutexes, Signals usw.) Variante siehst, um von 10s noch auf 9 zu kommen: lass es

Ok, eine fertige Lösung habe ich bereits, werde diese einfach ohne Mutex optimieren - da finde ich sicher noch andere Möglichkeiten.

Falls aber jemand noch einen Herausragenden Vorschlag hat, dann bitte hier posten!
Danke

acdc

[acdc]

1. Du musst die Daten schützen, nicht die Threads . Wenn du pro Thread ein Mutex erzeugst, bringt das ja nichts. Du brauchst 1 Mutex für 1 Stringlist. Was Thread-Entwickler in solchen Fällen tun ist, einen eigenen, thread-sicheren, Datenpool zu entwickeln (in deinem Fall: eine neue Klasse, welche die StringList durch den Mutex schützt).

Hierzu noch eine Frage:

Wie sieht hier eine einfache Klasse aus, die eine QStringList schüzt?
Muss ich das im Konstruktor machen oder nur bei einem "append"?

acdc

[solarix]

Bei jedem Zugriff auf die Liste

Code: Alles auswählen

MtStringList::MtStringList
{
   // kein Zugriff auf die Liste... es gibt nichts zu tun
}

void MtStringList::append(const QString &s)
{
  lock();
  mList << s;
  unlock();
}

.. usw.

Aber: Lesen kann ja parallel erfolgen.. daher gibt es noch die Verfeinerung durch die "Locker"-Klassen: Hier wird das parallele Lesen zugelassen, aber das Lesen gesperrt wenn gerade auf die Liste geschrieben wird..

Anwendung siehe:
http://doc.qt.nokia.com/4.7/qreadlocker.html#details

hth..

[padreigh]

war mal neugierig:
a) Bibel ( http://www.kahal.de/bibel_elb_bibel.zip ) zeilenweise laden aus Datei + Zeile am " " splitten und alles in ne QStringList FLOTT
c) Duplicate entfernen AUCHFLOTT
d) alles shuffeln ... IMMER NOCH FLOTT
e) duplikate mit foreach entfernen gäääääääähn
f) duplikate mit for entfernen genauso gäääääähn2 - wobei ich gedacht hätte das das flotter geht da dort die zu durchsuchende Liste kleiner werden sollte

Die Bibel ist natürlich ein hoch redundanter Datensatz ... ich bekam 801000 Strings nach splitten, ohne Duplikate bleiben nur ~58000 über.

Load file start
Load file end 0.39 s (Release 0.377 s)

shallow 'copy' list start
shallow 'copy' list end 0 s // ist ja shared, daher flott

remove duplicates start
size: 801001
duplicates: 743065
new size: 57936
remove duplicates end 0.275 s (Release 0.275 s)

shuffling search list start
shuffling search list end 0.396 s (Release 0.293 s)

removing all (unique) occurences in 'search' from 'inList' start using foreach
removing all (unique) occurences in 'search' from 'inList' end 588.466 s (Release: 423.883 s)

removing all (unique) occurences in 'search' from 'inList' start using for()
removing all (unique) occurences in 'search' from 'inList' end 583.329 s (Release: 411.893 s)

Da das mit dem duplikate entfernen so rasant ging ist der Stringvergleich und removeAll() wohl nicht das gelbe vom Ei ... vielleicht ein suboptimaler Container dafür? Dann in die Doku geguckt: http://doc.qt.nokia.com/4.6/containers. ... er-classes

und das hier probiert:

Code: Alles auswählen

    QSet<QString> IN = inList.toSet();
    QSet<QString> SE = search.toSet();
    QSet<QString> result = IN.subtract(SE);

mit folgendem Resultat:

putting all into sets
done putting all into sets 0.437 s

IN set size: 57936
SE set size: 57936
start substracting sets: IN-SE
done substracting sets 0.103 s

Die sets sind bei mir identisch ... das könnte die performance erklären - probioers halt mal mit deinen Daten.

... was in 0.11s läuft - natürlich reduziert das toSet() die 801000 tokens auf knapp 58k tokens, aber du kannst das ja trotzdem mal mit deinen Daten versuchen ... sollte um Längen schneller sein als das was du versucht hast - weiss aber nicht obs auch mit deinen "anderen" Datentypen klappen wird.

[padreigh]

und nochmal ich. sieht so aus als wäre die Wahl des Containers wichtig nun topp das mit einer QThread Lösung (für Strings) kleiner Nachteil: da geht die Reihenfolge der Strings flöten, wenn das wichtig ist:

- inListe --> QMultiMap<QString,int> wobei int die position ist
- statt

Code: Alles auswählen

result = IN.subjstract(SE); // --> IN.intersect(SE)

nur das was in beiden ist bleibt über.
- alles was in result ist in QMultiMap löschen.
die QMultiMap wieder zusammendröseln ... (jeder vorhandene key hat einne/mehrere ints .. als position wo das hingehört ... am besten ne neue QMap<int, QString> (jedes Wort an genau einer position) machen und die aus der anderen füllen, dann das ganze toList() und es sollte passen.

Code: Alles auswählen

#include <QtCore>
#include <QtDebug>

inline QString simApe(const int length)
{
    static const QString tasten = "1234567890qwertzuiopü+asdfghjklöä#yxcvbnm,.-"
                           "!§$%&/()=QWERTZUIOPÜ*ASDFGHJKLÖÄ'>YXCVBNM;:_"
                           "'¹²³¼½¬{[]}¸@ł¤¶ŧ←↓→øþ¨~æſðđŋħł˝^`|»«¢„“”µ·…\"\\";
    static const int lenT = tasten.size();

    QString result;
    for (int i=0; i<length; ++i)
    {
        result.append( tasten [rand()%lenT] );
    }

    return result;
}

inline QStringList apeShit(const QString s)
{
    QTime time;
    qDebug() << "Start of creating: " + s;
    time.restart();
    // create some words
    QStringList list;
    {
        // simulate apes .. generate 500k words
        for(int i=0;i < 500000; ++i) {
            list << simApe(rand()%15+3); // words of 3 - 17 chars
        }
    }
    qDebug() << "End of creating: " + s + " it took:" << time.elapsed()/1000.0 << " s\n";

    return list;
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    qsrand(QTime(0,0,0,0).msecsTo(QTime::currentTime()));
    simApe(0); // create statics inside once
    QTime time;

    const QStringList constInListe = apeShit("inList");
    const QStringList constLookListe = apeShit("lookList");

    qDebug() << "Start of putting all into sets";
    time.restart();
    QSet<QString> IN = constInListe.toSet();
    QSet<QString> SE = constLookListe.toSet();
    qDebug() << "End of putting all into sets: it took:" << time.elapsed()/1000.0 << " s\n";

    qDebug() << "IN set size: " << IN.size();
    qDebug() << "SE set size: " << SE.size();

    qDebug() << "Start of substracting sets: IN-SE";
    time.restart();
    QSet<QString> result = IN.subtract(SE);
    qDebug() << "End of substracting sets: it took:" << time.elapsed()/1000.0 << " s\n";

    qDebug() << "Unique words: " << result.size();

    a.quit();
}

"Start of creating: inList"
"End of creating: inList it took:" 0.326 s

"Start of creating: lookList"
"End of creating: lookList it took:" 0.327 s

Start of putting all into sets
End of putting all into sets: it took: 0.345 s

IN set size: 498002
SE set size: 497934
Start of substracting sets: IN-SE
End of substracting sets: it took: 0.531 s

Unique words: 495342

Leider ist das was die Affen auf der "Schreibmaschiene" produzieren keine Bibel geworden ( http://de.wikipedia.org/wiki/Infinite-Monkey-Theorem ) aber ich habe ja zuwenig und zu kurz tippen lassen