| 26 |
|
* update a common sum that is used for purposes such as collecting |
| 27 |
|
* statistics. In this case, performance may be significantly faster |
| 28 |
|
* than using a shared {@link AtomicLong}, at the expense of using |
| 29 |
< |
* much more space. On the other hand, if it is known that only one |
| 30 |
< |
* thread can ever update the sum, performance may be significantly |
| 31 |
< |
* slower than just updating a local variable. |
| 29 |
> |
* more space. On the other hand, if it is known that only one thread |
| 30 |
> |
* can ever update the sum, performance may be significantly slower |
| 31 |
> |
* than just updating a local variable. |
| 32 |
|
* |
| 33 |
|
* <p>A StripedAdder may optionally be constructed with a given |
| 34 |
|
* expected contention level; i.e., the number of threads that are |
| 69 |
|
* find a free slot. |
| 70 |
|
* |
| 71 |
|
* By default, the table is lazily initialized. Upon first use, |
| 72 |
< |
* the table is set to size 2 (the minimum non-empty size), but |
| 73 |
< |
* containing only a single Adder. The maximum table size is |
| 74 |
< |
* bounded by nearest power of two >= the number of CPUS. The |
| 75 |
< |
* table size is capped because, when there are more threads than |
| 76 |
< |
* CPUs, supposing that each thread were bound to a CPU, there |
| 77 |
< |
* would exist a perfect hash function mapping threads to slots |
| 78 |
< |
* that eliminates collisions. When we reach capacity, we search |
| 79 |
< |
* for this mapping by randomly varying the hash codes of |
| 80 |
< |
* colliding threads. Because search is random, and failures only |
| 81 |
< |
* become known via CAS failures, convergence will be slow, and |
| 82 |
< |
* because threads are typically not bound to CPUS forever, may |
| 83 |
< |
* not occur at all. However, despite these limitations, observed |
| 84 |
< |
* contention is typically low in these cases. |
| 72 |
> |
* the table is set to size 1, and contains a single Adder. The |
| 73 |
> |
* maximum table size is bounded by nearest power of two >= the |
| 74 |
> |
* number of CPUS. The table size is capped because, when there |
| 75 |
> |
* are more threads than CPUs, supposing that each thread were |
| 76 |
> |
* bound to a CPU, there would exist a perfect hash function |
| 77 |
> |
* mapping threads to slots that eliminates collisions. When we |
| 78 |
> |
* reach capacity, we search for this mapping by randomly varying |
| 79 |
> |
* the hash codes of colliding threads. Because search is random, |
| 80 |
> |
* and failures only become known via CAS failures, convergence |
| 81 |
> |
* will be slow, and because threads are typically not bound to |
| 82 |
> |
* CPUS forever, may not occur at all. However, despite these |
| 83 |
> |
* limitations, observed contention is typically low in these |
| 84 |
> |
* cases. |
| 85 |
|
* |
| 86 |
|
* A single spinlock is used for resizing the table as well as |
| 87 |
|
* populating slots with new Adders. After initialization, there |
| 136 |
|
static final ThreadHashCode threadHashCode = new ThreadHashCode(); |
| 137 |
|
|
| 138 |
|
/** |
| 139 |
< |
* Table of adders. When non-null, size is a power of 2, at least 2. |
| 139 |
> |
* Table of adders. When non-null, size is a power of 2. |
| 140 |
|
*/ |
| 141 |
|
private transient volatile Adder[] adders; |
| 142 |
|
|
| 160 |
|
*/ |
| 161 |
|
public StripedAdder(int expectedContention) { |
| 162 |
|
int cap = (expectedContention < NCPU) ? expectedContention : NCPU; |
| 163 |
< |
int size = 2; |
| 163 |
> |
int size = 1; |
| 164 |
|
while (size < cap) |
| 165 |
|
size <<= 1; |
| 166 |
|
Adder[] as = new Adder[size]; |
| 178 |
|
Adder[] as; Adder a; int n; // locals to hold volatile reads |
| 179 |
|
HashCode hc = threadHashCode.get(); |
| 180 |
|
int h = hc.code; |
| 181 |
< |
boolean collide; |
| 181 |
> |
boolean contended; |
| 182 |
|
if ((as = adders) != null && (n = as.length) > 0 && |
| 183 |
|
(a = as[(n - 1) & h]) != null) { |
| 184 |
|
long v = a.value; |
| 185 |
|
if (UNSAFE.compareAndSwapLong(a, valueOffset, v, v + x)) |
| 186 |
|
return; |
| 187 |
< |
collide = true; |
| 187 |
> |
contended = true; |
| 188 |
|
} |
| 189 |
|
else |
| 190 |
< |
collide = false; |
| 191 |
< |
retryAdd(x, hc, collide); |
| 190 |
> |
contended = false; |
| 191 |
> |
retryAdd(x, hc, contended); |
| 192 |
|
} |
| 193 |
|
|
| 194 |
|
/** |
| 197 |
|
* explanation. This method suffers the usual non-modularity |
| 198 |
|
* problems of optimistic retry code, relying on rechecked sets of |
| 199 |
|
* reads. |
| 200 |
+ |
* |
| 201 |
+ |
* @param x the value to add |
| 202 |
+ |
* @param hc the hash code holder |
| 203 |
+ |
* @param precontended true if CAS failed before call |
| 204 |
|
*/ |
| 205 |
< |
private void retryAdd(long x, HashCode hc, boolean collide) { |
| 205 |
> |
private void retryAdd(long x, HashCode hc, boolean precontended) { |
| 206 |
|
int h = hc.code; |
| 207 |
+ |
boolean collide = false; // true if last slot nonempty |
| 208 |
|
for (;;) { |
| 209 |
|
Adder[] as; Adder a; int n; |
| 210 |
|
if ((as = adders) != null && (n = as.length) > 0) { |
| 211 |
< |
if ((a = as[(n - 1) & h]) != null) { |
| 212 |
< |
boolean shared = true; // Slot exists |
| 213 |
< |
if (collide && n < NCPU && busy == 0 && |
| 214 |
< |
UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 215 |
< |
try { |
| 216 |
< |
if (adders == as) { // Expand table |
| 217 |
< |
Adder[] rs = new Adder[n << 1]; |
| 218 |
< |
for (int i = 0; i < n; ++i) |
| 219 |
< |
rs[i] = as[i]; |
| 220 |
< |
adders = rs; |
| 221 |
< |
shared = false; |
| 211 |
> |
if ((a = as[(n - 1) & h]) == null) { |
| 212 |
> |
if (busy == 0) { // Try to attach new Adder |
| 213 |
> |
Adder r = new Adder(x); // Optimistically create |
| 214 |
> |
if (busy == 0 && |
| 215 |
> |
UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 216 |
> |
boolean created = false; |
| 217 |
> |
try { // Recheck under lock |
| 218 |
> |
Adder[] rs; int m, j; |
| 219 |
> |
if ((rs = adders) != null && |
| 220 |
> |
(m = rs.length) > 0 && |
| 221 |
> |
rs[j = (m - 1) & h] == null) { |
| 222 |
> |
rs[j] = r; |
| 223 |
> |
created = true; |
| 224 |
> |
} |
| 225 |
> |
} finally { |
| 226 |
> |
busy = 0; |
| 227 |
|
} |
| 228 |
< |
} finally { |
| 229 |
< |
busy = 0; |
| 230 |
< |
} |
| 221 |
< |
if (shared || (h & n) != 0) { |
| 222 |
< |
collide = false; |
| 223 |
< |
continue; // Array or index changed |
| 228 |
> |
if (created) |
| 229 |
> |
break; |
| 230 |
> |
continue; // Slot is now non-empty |
| 231 |
|
} |
| 232 |
|
} |
| 233 |
+ |
collide = false; |
| 234 |
+ |
} |
| 235 |
+ |
else if (precontended) // CAS already known to fail |
| 236 |
+ |
precontended = false; // Continue after rehash |
| 237 |
+ |
else { |
| 238 |
|
long v = a.value; |
| 239 |
|
if (UNSAFE.compareAndSwapLong(a, valueOffset, v, v + x)) |
| 240 |
|
break; |
| 241 |
< |
collide = shared; |
| 242 |
< |
} |
| 243 |
< |
else { // Try to attach new Adder |
| 244 |
< |
if (busy == 0 && |
| 245 |
< |
UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 246 |
< |
boolean created = false; |
| 247 |
< |
try { // Recheck under lock |
| 248 |
< |
Adder[] rs; int m, j; |
| 249 |
< |
if ((rs = adders) != null && (m = rs.length) > 0 && |
| 250 |
< |
rs[j = (m - 1) & h] == null) { |
| 251 |
< |
rs[j] = new Adder(x); |
| 252 |
< |
created = true; |
| 241 |
> |
if (!collide) |
| 242 |
> |
collide = true; |
| 243 |
> |
else if (n >= NCPU || adders != as) |
| 244 |
> |
collide = false; // Can't expand |
| 245 |
> |
else if (busy == 0 && |
| 246 |
> |
UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 247 |
> |
collide = false; |
| 248 |
> |
try { |
| 249 |
> |
if (adders == as) { // Expand table |
| 250 |
> |
Adder[] rs = new Adder[n << 1]; |
| 251 |
> |
for (int i = 0; i < n; ++i) |
| 252 |
> |
rs[i] = as[i]; |
| 253 |
> |
adders = rs; |
| 254 |
|
} |
| 255 |
|
} finally { |
| 256 |
|
busy = 0; |
| 257 |
|
} |
| 258 |
< |
if (created) |
| 246 |
< |
break; |
| 247 |
< |
continue; // Slot is now non-empty |
| 258 |
> |
continue; |
| 259 |
|
} |
| 249 |
– |
collide = false; |
| 260 |
|
} |
| 261 |
|
h ^= h << 13; // Rehash |
| 262 |
|
h ^= h >>> 17; |
| 263 |
|
h ^= h << 5; |
| 264 |
|
} |
| 265 |
< |
else if (busy == 0) { // Default-initialize |
| 266 |
< |
Adder r = new Adder(x); |
| 267 |
< |
Adder[] rs = new Adder[2]; |
| 268 |
< |
rs[h & 1] = r; |
| 269 |
< |
if (adders == as && busy == 0 && |
| 270 |
< |
UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 271 |
< |
boolean init = false; |
| 272 |
< |
try { |
| 273 |
< |
if (adders == as) { |
| 274 |
< |
adders = rs; |
| 275 |
< |
init = true; |
| 265 |
> |
else if (adders == as) { // Try to default-initialize |
| 266 |
> |
Adder[] rs = new Adder[1]; |
| 267 |
> |
rs[0] = new Adder(x); |
| 268 |
> |
boolean init = false; |
| 269 |
> |
while (adders == as) { |
| 270 |
> |
if (UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1)) { |
| 271 |
> |
try { |
| 272 |
> |
if (adders == as) { |
| 273 |
> |
adders = rs; |
| 274 |
> |
init = true; |
| 275 |
> |
} |
| 276 |
> |
} finally { |
| 277 |
> |
busy = 0; |
| 278 |
|
} |
| 279 |
< |
} finally { |
| 268 |
< |
busy = 0; |
| 279 |
> |
break; |
| 280 |
|
} |
| 281 |
< |
if (init) |
| 281 |
> |
if (adders != as) |
| 282 |
|
break; |
| 283 |
+ |
Thread.yield(); // Back off |
| 284 |
|
} |
| 285 |
+ |
if (init) |
| 286 |
+ |
break; |
| 287 |
|
} |
| 274 |
– |
else if (adders == as) // Lost initialization race |
| 275 |
– |
Thread.yield(); |
| 288 |
|
} |
| 289 |
|
hc.code = h; // Record index for next time |
| 290 |
|
} |
