aboutsummaryrefslogtreecommitdiff
path: root/kamon-core/src/main/java/kamon/jsr166/Striped64.java
diff options
context:
space:
mode:
Diffstat (limited to 'kamon-core/src/main/java/kamon/jsr166/Striped64.java')
-rw-r--r--kamon-core/src/main/java/kamon/jsr166/Striped64.java344
1 files changed, 192 insertions, 152 deletions
diff --git a/kamon-core/src/main/java/kamon/jsr166/Striped64.java b/kamon-core/src/main/java/kamon/jsr166/Striped64.java
index 8fbfa4ba..3148bb57 100644
--- a/kamon-core/src/main/java/kamon/jsr166/Striped64.java
+++ b/kamon-core/src/main/java/kamon/jsr166/Striped64.java
@@ -1,14 +1,4 @@
/*
-
-Note: this was copied from Doug Lea's CVS repository
- http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/
-
-Striped64.java version 1.8
-
-*/
-
-
-/*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
@@ -16,13 +6,17 @@ Striped64.java version 1.8
package kamon.jsr166;
-import java.util.Random;
+import java.util.Arrays;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.DoubleBinaryOperator;
+import java.util.function.LongBinaryOperator;
/**
* A package-local class holding common representation and mechanics
* for classes supporting dynamic striping on 64bit values. The class
* extends Number so that concrete subclasses must publicly do so.
*/
+@SuppressWarnings("serial")
abstract class Striped64 extends Number {
/*
* This class maintains a lazily-initialized table of atomically
@@ -32,7 +26,7 @@ abstract class Striped64 extends Number {
* accessed directly by subclasses.
*
* Table entries are of class Cell; a variant of AtomicLong padded
- * to reduce cache contention on most processors. Padding is
+ * (via @Contended) to reduce cache contention. Padding is
* overkill for most Atomics because they are usually irregularly
* scattered in memory and thus don't interfere much with each
* other. But Atomic objects residing in arrays will tend to be
@@ -49,17 +43,20 @@ abstract class Striped64 extends Number {
* number of CPUS. Table slots remain empty (null) until they are
* needed.
*
- * A single spinlock ("busy") is used for initializing and
+ * A single spinlock ("cellsBusy") is used for initializing and
* resizing the table, as well as populating slots with new Cells.
* There is no need for a blocking lock; when the lock is not
* available, threads try other slots (or the base). During these
* retries, there is increased contention and reduced locality,
* which is still better than alternatives.
*
- * Per-thread hash codes are initialized to random values.
- * Contention and/or table collisions are indicated by failed
- * CASes when performing an update operation (see method
- * retryUpdate). Upon a collision, if the table size is less than
+ * The Thread probe fields maintained via ThreadLocalRandom serve
+ * as per-thread hash codes. We let them remain uninitialized as
+ * zero (if they come in this way) until they contend at slot
+ * 0. They are then initialized to values that typically do not
+ * often conflict with others. Contention and/or table collisions
+ * are indicated by failed CASes when performing an update
+ * operation. Upon a collision, if the table size is less than
* the capacity, it is doubled in size unless some other thread
* holds the lock. If a hashed slot is empty, and lock is
* available, a new Cell is created. Otherwise, if the slot
@@ -89,74 +86,42 @@ abstract class Striped64 extends Number {
/**
* Padded variant of AtomicLong supporting only raw accesses plus CAS.
- * The value field is placed between pads, hoping that the JVM doesn't
- * reorder them.
*
* JVM intrinsics note: It would be possible to use a release-only
* form of CAS here, if it were provided.
*/
- static final class Cell {
- volatile long p0, p1, p2, p3, p4, p5, p6;
+ @sun.misc.Contended static final class Cell {
volatile long value;
- volatile long q0, q1, q2, q3, q4, q5, q6;
Cell(long x) { value = x; }
-
final boolean cas(long cmp, long val) {
- return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
+ return U.compareAndSwapLong(this, VALUE, cmp, val);
}
-
- final long getAndSet(long val) {
- long v;
- do {
- v = UNSAFE.getLongVolatile(this, valueOffset);
- } while (!UNSAFE.compareAndSwapLong(this, valueOffset, v, val));
- return v;
+ final void reset() {
+ U.putLongVolatile(this, VALUE, 0L);
+ }
+ final void reset(long identity) {
+ U.putLongVolatile(this, VALUE, identity);
}
// Unsafe mechanics
- private static final sun.misc.Unsafe UNSAFE;
- private static final long valueOffset;
+ private static final sun.misc.Unsafe U;
+ private static final long VALUE;
static {
try {
- UNSAFE = getUnsafe();
- Class<?> ak = Cell.class;
- valueOffset = UNSAFE.objectFieldOffset
- (ak.getDeclaredField("value"));
- } catch (Exception e) {
+ U = getUnsafe();
+ VALUE = U.objectFieldOffset
+ (Cell.class.getDeclaredField("value"));
+ } catch (ReflectiveOperationException e) {
throw new Error(e);
}
}
- }
-
- /**
- * Holder for the thread-local hash code. The code is initially
- * random, but may be set to a different value upon collisions.
- */
- static final class HashCode {
- static final Random rng = new Random();
- int code;
- HashCode() {
- int h = rng.nextInt(); // Avoid zero to allow xorShift rehash
- code = (h == 0) ? 1 : h;
+ final long getAndSet(long val) {
+ return U.getAndSetLong(this, VALUE, val);
}
- }
- /**
- * The corresponding ThreadLocal class
- */
- static final class ThreadHashCode extends ThreadLocal<HashCode> {
- public HashCode initialValue() { return new HashCode(); }
}
- /**
- * Static per-thread hash codes. Shared across all instances to
- * reduce ThreadLocal pollution and because adjustments due to
- * collisions in one table are likely to be appropriate for
- * others.
- */
- static final ThreadHashCode threadHashCode = new ThreadHashCode();
-
/** Number of CPUS, to place bound on table size */
static final int NCPU = Runtime.getRuntime().availableProcessors();
@@ -174,49 +139,57 @@ abstract class Striped64 extends Number {
/**
* Spinlock (locked via CAS) used when resizing and/or creating Cells.
*/
- transient volatile int busy;
+ transient volatile int cellsBusy;
/**
- * Package-private default constructor
+ * Package-private default constructor.
*/
Striped64() {
}
+
/**
* CASes the base field.
*/
- final boolean casBase(long cmp, long val) {
- return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val);
+ final long getAndSetBase(long val) {
+ return U.getAndSetLong(this, BASE, val);
}
+
/**
* CASes the base field.
*/
- final long getAndSetBase(long val) {
- long v;
- do {
- v = UNSAFE.getLongVolatile(this, baseOffset);
- } while (!UNSAFE.compareAndSwapLong(this, baseOffset, v, val));
- return v;
+ final boolean casBase(long cmp, long val) {
+ return U.compareAndSwapLong(this, BASE, cmp, val);
}
/**
- * CASes the busy field from 0 to 1 to acquire lock.
+ * CASes the cellsBusy field from 0 to 1 to acquire lock.
*/
- final boolean casBusy() {
- return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1);
+ final boolean casCellsBusy() {
+ return U.compareAndSwapInt(this, CELLSBUSY, 0, 1);
}
/**
- * Computes the function of current and new value. Subclasses
- * should open-code this update function for most uses, but the
- * virtualized form is needed within retryUpdate.
- *
- * @param currentValue the current value (of either base or a cell)
- * @param newValue the argument from a user update call
- * @return result of the update function
+ * Returns the probe value for the current thread.
+ * Duplicated from ThreadLocalRandom because of packaging restrictions.
+ */
+ static final int getProbe() {
+ return U.getInt(Thread.currentThread(), PROBE);
+ }
+
+ /**
+ * Pseudo-randomly advances and records the given probe value for the
+ * given thread.
+ * Duplicated from ThreadLocalRandom because of packaging restrictions.
*/
- abstract long fn(long currentValue, long newValue);
+ static final int advanceProbe(int probe) {
+ probe ^= probe << 13; // xorshift
+ probe ^= probe >>> 17;
+ probe ^= probe << 5;
+ U.putInt(Thread.currentThread(), PROBE, probe);
+ return probe;
+ }
/**
* Handles cases of updates involving initialization, resizing,
@@ -226,33 +199,37 @@ abstract class Striped64 extends Number {
* reads.
*
* @param x the value
- * @param hc the hash code holder
+ * @param fn the update function, or null for add (this convention
+ * avoids the need for an extra field or function in LongAdder).
* @param wasUncontended false if CAS failed before call
*/
- final void retryUpdate(long x, HashCode hc, boolean wasUncontended) {
- int h = hc.code;
+ 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 (;;) {
+ done: for (;;) {
Cell[] as; Cell a; int n; long v;
if ((as = cells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {
- if (busy == 0) { // Try to attach new Cell
+ if (cellsBusy == 0) { // Try to attach new Cell
Cell r = new Cell(x); // Optimistically create
- if (busy == 0 && casBusy()) {
- boolean created = false;
+ if (cellsBusy == 0 && casCellsBusy()) {
try { // Recheck under lock
Cell[] rs; int m, j;
if ((rs = cells) != null &&
- (m = rs.length) > 0 &&
- rs[j = (m - 1) & h] == null) {
+ (m = rs.length) > 0 &&
+ rs[j = (m - 1) & h] == null) {
rs[j] = r;
- created = true;
+ break done;
}
} finally {
- busy = 0;
+ cellsBusy = 0;
}
- if (created)
- break;
continue; // Slot is now non-empty
}
}
@@ -260,85 +237,147 @@ abstract class Striped64 extends Number {
}
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
- else if (a.cas(v = a.value, fn(v, x)))
+ else if (a.cas(v = a.value,
+ (fn == null) ? v + x : fn.applyAsLong(v, x)))
break;
else if (n >= NCPU || cells != as)
collide = false; // At max size or stale
else if (!collide)
collide = true;
- else if (busy == 0 && casBusy()) {
+ else if (cellsBusy == 0 && casCellsBusy()) {
try {
- if (cells == as) { // Expand table unless stale
- Cell[] rs = new Cell[n << 1];
- for (int i = 0; i < n; ++i)
- rs[i] = as[i];
- cells = rs;
- }
+ if (cells == as) // Expand table unless stale
+ cells = Arrays.copyOf(as, n << 1);
} finally {
- busy = 0;
+ cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
- h ^= h << 13; // Rehash
- h ^= h >>> 17;
- h ^= h << 5;
+ h = advanceProbe(h);
}
- else if (busy == 0 && cells == as && casBusy()) {
- boolean init = false;
+ else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
try { // Initialize table
if (cells == as) {
Cell[] rs = new Cell[2];
rs[h & 1] = new Cell(x);
cells = rs;
- init = true;
+ break done;
}
} finally {
- busy = 0;
+ cellsBusy = 0;
}
- if (init)
- break;
}
- else if (casBase(v = base, fn(v, x)))
- break; // Fall back on using base
+ // Fall back on using base
+ else if (casBase(v = base,
+ (fn == null) ? v + x : fn.applyAsLong(v, x)))
+ break done;
}
- hc.code = h; // Record index for next time
}
+ private static long apply(DoubleBinaryOperator fn, long v, double x) {
+ double d = Double.longBitsToDouble(v);
+ d = (fn == null) ? d + x : fn.applyAsDouble(d, x);
+ return Double.doubleToRawLongBits(d);
+ }
/**
- * Sets base and all cells to the given value.
+ * Same as longAccumulate, but injecting long/double conversions
+ * in too many places to sensibly merge with long version, given
+ * the low-overhead requirements of this class. So must instead be
+ * maintained by copy/paste/adapt.
*/
- final void internalReset(long initialValue) {
- Cell[] as = cells;
- base = initialValue;
- if (as != null) {
- int n = as.length;
- for (int i = 0; i < n; ++i) {
- Cell a = as[i];
- if (a != null)
- a.value = initialValue;
+ final void doubleAccumulate(double x, DoubleBinaryOperator 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
+ done: for (;;) {
+ Cell[] as; Cell a; int n; long v;
+ if ((as = cells) != null && (n = as.length) > 0) {
+ if ((a = as[(n - 1) & h]) == null) {
+ if (cellsBusy == 0) { // Try to attach new Cell
+ Cell r = new Cell(Double.doubleToRawLongBits(x));
+ if (cellsBusy == 0 && casCellsBusy()) {
+ try { // Recheck under lock
+ Cell[] rs; int m, j;
+ if ((rs = cells) != null &&
+ (m = rs.length) > 0 &&
+ rs[j = (m - 1) & h] == null) {
+ rs[j] = r;
+ break done;
+ }
+ } finally {
+ cellsBusy = 0;
+ }
+ continue; // Slot is now non-empty
+ }
+ }
+ collide = false;
+ }
+ else if (!wasUncontended) // CAS already known to fail
+ wasUncontended = true; // Continue after rehash
+ else if (a.cas(v = a.value, apply(fn, v, x)))
+ break;
+ else if (n >= NCPU || cells != as)
+ collide = false; // At max size or stale
+ else if (!collide)
+ collide = true;
+ else if (cellsBusy == 0 && casCellsBusy()) {
+ try {
+ if (cells == as) // Expand table unless stale
+ cells = Arrays.copyOf(as, n << 1);
+ } finally {
+ cellsBusy = 0;
+ }
+ collide = false;
+ continue; // Retry with expanded table
+ }
+ h = advanceProbe(h);
+ }
+ else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
+ try { // Initialize table
+ if (cells == as) {
+ Cell[] rs = new Cell[2];
+ rs[h & 1] = new Cell(Double.doubleToRawLongBits(x));
+ cells = rs;
+ break done;
+ }
+ } finally {
+ cellsBusy = 0;
+ }
}
+ // Fall back on using base
+ else if (casBase(v = base, apply(fn, v, x)))
+ break done;
}
}
// Unsafe mechanics
- private static final sun.misc.Unsafe UNSAFE;
- private static final long baseOffset;
- private static final long busyOffset;
+ private static final sun.misc.Unsafe U;
+ private static final long BASE;
+ private static final long CELLSBUSY;
+ private static final long PROBE;
static {
try {
- UNSAFE = getUnsafe();
- Class<?> sk = Striped64.class;
- baseOffset = UNSAFE.objectFieldOffset
- (sk.getDeclaredField("base"));
- busyOffset = UNSAFE.objectFieldOffset
- (sk.getDeclaredField("busy"));
- } catch (Exception e) {
+ U = getUnsafe();
+ BASE = U.objectFieldOffset
+ (Striped64.class.getDeclaredField("base"));
+ CELLSBUSY = U.objectFieldOffset
+ (Striped64.class.getDeclaredField("cellsBusy"));
+
+ PROBE = U.objectFieldOffset
+ (Thread.class.getDeclaredField("threadLocalRandomProbe"));
+ } catch (ReflectiveOperationException e) {
throw new Error(e);
}
}
+
/**
* Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package.
* Replace with a simple call to Unsafe.getUnsafe when integrating
@@ -352,20 +391,21 @@ abstract class Striped64 extends Number {
} catch (SecurityException tryReflectionInstead) {}
try {
return java.security.AccessController.doPrivileged
- (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
- public sun.misc.Unsafe run() throws Exception {
- Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
- for (java.lang.reflect.Field f : k.getDeclaredFields()) {
- f.setAccessible(true);
- Object x = f.get(null);
- if (k.isInstance(x))
- return k.cast(x);
- }
- throw new NoSuchFieldError("the Unsafe");
- }});
+ (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
+ public sun.misc.Unsafe run() throws Exception {
+ Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
+ for (java.lang.reflect.Field f : k.getDeclaredFields()) {
+ f.setAccessible(true);
+ Object x = f.get(null);
+ if (k.isInstance(x))
+ return k.cast(x);
+ }
+ throw new NoSuchFieldError("the Unsafe");
+ }});
} catch (java.security.PrivilegedActionException e) {
throw new RuntimeException("Could not initialize intrinsics",
- e.getCause());
+ e.getCause());
}
}
-}
+
+} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-27 14:56:22 +0000