SpinLock Skalierbarkeit und Einschränkungen

Question

Ich habe ein einfaches Programm geschrieben, um den Durchsatz des CLH-Lock zu testen. Ich habe den Code wie in "Die Kunst der Multicore-Programmierung" beschrieben. Als nächstes habe ich einen Zähler auf eine sich ändernde Anzahl von Threads für 10 Sekunden laufen lassen und den Zähler/10.0 als Durchsatz definiert.

Meine Frage ist, ob die Ergebnisse, die ich bekommen habe, im logischen Bereich liegen und was der Grund dafür sein könnte, dass sie so sind wie sie sind. Ich frage, weil der Durchsatzabfall für das CLH-Lock extrem schnell ist. Dies sind die Ergebnisse für die cLH-Sperre, wobei links die Anzahl der Threads und rechts der Durchsatz angibt (die Größe des Zählers wurde mit jedem Thread erhöht, einmal in dem durch die CLH-Sperre geschützten kritischen Abschnitt, geteilt durch 10).

CLH 1 2.89563825E7 2 1.33501436E7 4 5675832.3 8 15868.9 16 11114.4 32 68.4

Wie Sie sehen die Drop-Off-verrückt ist und lässt mich denken, dass ich etwas anderes durcheinander haben.

Dies ist mein Code für die CLH Sperre (so wie es in dem oben erwähnten Buch ist):

static class CLHLock implements Lock { 
    AtomicReference<QNode> tail; 
    ThreadLocal<QNode> myNode, myPred; 

    public CLHLock() { 
     tail = new AtomicReference<QNode>(new QNode()); 

     this.myNode = new ThreadLocal<QNode>() { 
      protected QNode initialValue() { 
       return new QNode(); 
      } 
     }; 

     this.myPred = new ThreadLocal<QNode>() { 
      protected QNode initialValue() { 
       return null; 
      } 
     }; 
    } 

    public void lock() { 
     QNode qnode = this.myNode.get(); 
     qnode.locked.set(true);   

     QNode pred = this.tail.getAndSet(qnode); 
     myPred.set(pred);   
     while (pred.locked.get()) {}  
    } 

    public void unlock() { 
     QNode qnode = this.myNode.get(); 
     qnode.locked.set(false);  
     this.myNode.set(this.myPred.get()); 
    } 

    static class QNode { 
     public AtomicBoolean locked = new AtomicBoolean(false); 
    } 
} 

Der Lauf des Hauptthread 10 Sekunden lang warten, besteht, während die andere zu sperren versuchen, erhöht und entsperren, bis ein flüchtiger Boolescher Wert besagt, dass die Zeit abgelaufen ist.

Answer 1

über Ihre CLH Sperre Implementierung

Die Umsetzung sieht ziemlich Standard, mit Ausnahme des geschäftigen Spin. Sie sind wahrscheinlich besser dran oder parken (obwohl das etwas mehr Code erfordert).

über Ihre Benchmarking-Ergebnisse

urteilen über die Korrektheit von Code aus seinen Performance-Tests ist eine Aufgabe, die zumindest so viel Wissen wie die Beurteilung über die Korrektheit von Code von seiner Richtigkeit Tests erfordert.

Sie beobachten wahrscheinlich eine Vielzahl von Nebenwirkungen, die nicht direkt mit Ihrem Code zusammenhängen. Um diese Effekte zu minimieren, verwenden Sie ein Benchmarking-Tool wie JMH, sonst messen Sie etwas, das nicht unbedingt Ihr Code ist.

Hier ist eine spekulative Erklärung über Ihre Ergebnisse, die falsch sein können, aber es ist völlig plausibel:

• Mit 1 Faden, den Code extrem schnell ausgeführt wird, weil es auf der Sperre praktisch keine Konkurrenz ist und es gibt keinen Cache Prügel. Sie profitieren wahrscheinlich von einer erfolgreichen Verzweigungsvorhersage und von einer frühzeitigen Einführung von JIT ohne spätere De-Optimierung.
• Mit 2 und 4 Threads, erhalten Sie etwas Durchsatzrückgang. Es ist nicht so schlimm, weil Sie immer noch Hardware-Threads haben, aber jetzt erleben Sie Cache-Thrashing (vielleicht sogar falsches Sharing), etwas Kohärenz-Traffic und vielleicht eine Verzweigungsfehlvorhersage (aufgrund der gemeinsamen Infrastruktur Ihres Benchmarks). Obwohl Sie den Durchsatz bei der parallelen Ausführung nicht erhöhen, sind Sie immer noch in Ordnung.
• Mit 8 und 16 Threads sind Sie jetzt über die Grenzen der verfügbaren Hardware-Threads auf Ihrem Computer hinaus. Sie haben Probleme mit dem Betriebssystem-Scheduling, viel bedeutenderem Cache-Thrashing sowie erheblichen Konflikten in Ihrem Code.
• Mit 32 Threads gehen Sie über die Grenze einiger der schnellen Hardware-Caching-Mechanismen (L1-Cache, TLB) und Downgrade auf den nächstschnelleren Mechanismus. Es ist nicht notwendig, die Cache-Größenbeschränkung zu überschreiten, um dies zu erfahren. Sie können auch die Assoziativitätsgrenze überschreiten.