LongAdder Striped64 wasUncontended Implementierungsdetail

Question

Das ist eine Frage nicht, wie LongAdder funktioniert, es handelt sich um ein faszinierendes Implementierungsdetail, das ich nicht herausfinden kann.

Hier ist der Code von Striped64 ist (ich habe einige Teile ausgeschnitten und die entsprechenden Teile für die Frage links):

final void longAccumulate(long x, LongBinaryOperator fn, 
          boolean wasUncontended) { 
    int h; 
    if ((h = getProbe()) == 0) { 
     ThreadLocalRandom.current(); // force initialization 
     h = getProbe(); 
     wasUncontended = true; 
    } 
    boolean collide = false; // True if last slot nonempty 
    for (;;) { 
     Cell[] as; Cell a; int n; long v; 
     if ((as = cells) != null && (n = as.length) > 0) { 
      if ((a = as[(n - 1) & h]) == null) { 
       //logic to insert the Cell in the array 
      } 
      // CAS already known to fail 
      else if (!wasUncontended) { 
       wasUncontended = true;  // Continue after rehash 
      } 
      else if (a.cas(v = a.value, ((fn == null) ? v + x : fn.applyAsLong(v, x)))){ 
       break; 
      } 

Viele Dinge von Code sind mir klar, mit Ausnahme der:

 // CAS already known to fail 
     else if (!wasUncontended) { 
      wasUncontended = true;  // Continue after rehash 
     } 

Woher kommt diese Sicherheit, dass der folgende CAS fehlschlägt? Das ist wirklich verwirrend für mich zumindest, weil diese Prüfung nur für einen einzigen Fall sinnvoll ist: wenn ein Thread die longAccumulate Methode zum n-ten Mal (n> 1) eingibt und der Busy-Spin im ersten Zyklus ist .

Es ist wie dieser Code sagt: Wenn Sie (einige Thread) schon einmal hier gewesen sind und Sie haben einen Streit auf einem bestimmten Zelle-Slot, versuchen Sie nicht, Ihren Wert zu dem bereits vorhandenen CAS, sondern stattdessen die Sonde.

Ich hoffe wirklich, dass ich einen Sinn für jemanden machen werde.

Answer 1

Es ist nicht, dass es scheitern wird, es ist mehr, dass es gescheitert ist. Der Aufruf dieser Methode erfolgt über die Methode LongAdderadd.

public void add(long x) { 
    Cell[] as; long b, v; int m; Cell a; 
    if ((as = cells) != null || !casBase(b = base, b + x)) { 
     boolean uncontended = true; 
     if (as == null || (m = as.length - 1) < 0 || 
      (a = as[getProbe() & m]) == null || 
      !(uncontended = a.cas(v = a.value, v + x))) 
      longAccumulate(x, null, uncontended); 
    } 
} 

1. Der erste Satz von conditionals auf Existenz der langen Zellen zusammen. Wenn die erforderliche Zelle nicht existiert, wird sie versuchen, sich nicht zu akkumulieren (da es keinen Versuch gab, sie hinzuzufügen), indem sie die erforderliche Zelle atomar hinzufügt und dann hinzufügt. Wenn die Zelle vorhanden ist, versuchen Sie, (v + x) hinzuzufügen. Wenn das Add scheiterte dann war da noch eine gewisse Form der Behauptung, in diesem Fall versuchen, das Ansammeln optimistischer/atomar zu tun (spin bis zum erfolgreichen)

Warum hat es

wasUncontended = true;  // Continue after rehash 

Meine beste Vermutung ist, Bei starker Konkurrenz wird es versuchen, dem laufenden Thread Zeit zum Aufholen zu geben und eine Wiederholung der vorhandenen Zellen erzwingen.