Lock frei verkettete Liste funktioniert schlechter als das gesperrte Gegenstück

Ich versuche, die Leistung der gesperrten und sperren frei verknüpften Liste Datenstruktur zu vergleichen. Ich habe this Algorithmus für Lock frei verkettete Liste implementiert. Beide Programme sind in C implementiert.Lock frei verkettete Liste funktioniert schlechter als das gesperrte Gegenstück

Ich teste für 4 Threads. Jeder Thread hat 1000 Einfügeoperationen.

Ich verwende Intel PCM-Tool, um die Leistung zu messen.

Hier sind meine Ergebnisse: frei Lock:

Median of L3 Misses=1012699 
Median of L2 Misses=1479741 
Median of L3 Hits=484128 
Median of L2 Hits=1797537 
Median of Time=1.80696 
Median of Cycles=5296042019 
Median of IPC=1.536135 
Median of Bytes Read=444423232 
Median of Bytes Written=25414144

Gesperrt:

Median of L3 Misses=711796.5 
Median of L2 Misses=1517899 
Median of L3 Hits=819408.5 
Median of L2 Hits=2282527 
Median of Time=0.244517 
Median of Cycles=894265192 
Median of IPC=0.8495695 
Median of Bytes Read=174872576 
Median of Bytes Written=24722912

Die gesperrte Version auf jeder Zählung außer IPC besser abschneidet. Soll das geschehen? Oder das Schloss Freie Datenstruktur sollte besser funktionieren?

Wenn ja, welchen Nutzen hat die Verwendung von lockfreien Datenstrukturen? Jede Hilfe wird geschätzt.

Quelle

2016-07-12 Sumant

Gehen Sie zu dieser Seite: https: //stackoverflow.com/questions/33083270 Auf dieser Seite finden Sie einen Youtube-Video-Link zu einem Vortrag bei CppCon über blocklose Implementierungen und Kompromisse. Das Video wurde in zwei Teile geteilt und der Link ist für Teil 2. Also, finden Sie Teil 1.Das Video insgesamt ist ungefähr 2 Stunden, aber der Sprecher ist ziemlich unterhaltsam und kennt seine Sachen wirklich –

Diese [Antwort] (http://stackoverflow.com/a/4044614/5781248) könnte das Leistungsproblem erklären (Konkurrenz) . Lock-freie Datenstrukturen helfen wahrscheinlich teure Kontextwechsel zu vermeiden. –

Sie sehen nicht das eigentliche Problem. Die Cache-Trefferrate ist absolut schrecklich, ein Standardproblem bei herkömmlichen verknüpften Listen auf einem modernen Prozessor. Ein sehr wichtiges Detail, das diese alten Zeitungen ignorieren. Benutze sie nicht. –

Die gesperrte Version funktioniert besser bei jeder Zählung außer IPC. Soll das geschehen? Oder das Schloss Freie Datenstruktur sollte besser funktionieren?

Im Allgemeinen hängt die Leistung besser von den Details der Arbeitslast und den Implementierungsdetails ab. Das Papier, das Sie sagt Referenz

Lock-freie Datenstrukturen auch das Potenzial haben eine bessere Leistung zu haben

(Hervorhebung hinzugefügt), aber es verspricht nicht eine bessere Leistung in jedem Fall. Obwohl mehrere Threads in der Lage sein können, die blockierungsfreie Datenstruktur zur gleichen Zeit zu modifizieren, beinhaltet jede Änderung mehr Operationen, selbst wenn keine Konflikte auftreten. Wenn Konflikte sind, verschlechtert sich die Leistung.

Ich beobachte auch, dass Ihr Lock-Free-Code einen höheren Anteil an Cache-Misses hat als Ihr gesperrter Code. Das kann ich zwar nicht souverän erklären, aber ich kann mir zumindest zwei plausible Gründe vorstellen, warum dies eine zu erwartende Konsequenz der lockfreien Umsetzung wäre. Natürlich beeinträchtigt eine weniger effektive Cache-Nutzung die Leistung erheblich.

Wenn ja, was ist der Vorteil der Verwendung von lockfreien Datenstrukturen?

Das Papier sagt, dass der Hauptvorteil ist:

Wenn eine Implementierung Lock-frei ist, Verzögerungen oder Ausfälle einzelner Prozesse nicht blockieren den Fortschritt der anderen Prozesse im System.

Quelle

2016-07-12 20:56:44

Danke für die Antwort. Irgendwelche Hilfe, wie man den Cache vermisst? – Sumant

@Sumant, Cache-Trefferrate ist hauptsächlich eine Funktion von Datenzugriffsmustern, die selbst eine Funktion von Arbeitslast und Implementierungsdetails sind, genau wie die Gesamtleistung. Wenn möglich, würden Sie es vorziehen, linear durch den Speicher zu scannen und ein Springen zu vermeiden. Eine Möglichkeit, die Sie erleichtern können, besteht darin, Listenknoten in mittelgroßen Gruppen statt einzeln zuzuweisen. Das Auslegen von Strukturelementen zum Minimieren der Auffüllung kann ebenfalls hilfreich sein. –

Insgesamt ist es jedoch sehr unwahrscheinlich, dass Sie den beobachteten Leistungsunterschied zwischen den beiden Ansätzen mit solchen Tricks ausgleichen. Wenn die Leistung die bestimmende Priorität ist, testen Sie jeden Ansatz mit einer Arbeitsauslastung, die die erwartete simuliert, und wählen Sie die Lösung mit der besseren Leistung aus. –

Lock frei verkettete Liste funktioniert schlechter als das gesperrte Gegenstück

Antwort

Verwandte Themen