Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group and released to the public domain, as explained at
  package com.codahale.metrics;
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.
 abstract class Striped64 extends Number {
      * This class maintains a lazily-initialized table of atomically
      * updated variables, plus an extra "base" field. The table size
      * is a power of two. Indexing uses masked per-thread hash codes.
      * Nearly all declarations in this class are package-private,
      * accessed directly by subclasses.
      * Table entries are of class Cell; a variant of AtomicLong padded
      * to reduce cache contention on most processors. 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
      * placed adjacent to each other, and so will most often share
      * cache lines (with a huge negative performance impact) without
      * this precaution.
      * In part because Cells are relatively large, we avoid creating
      * them until they are needed.  When there is no contention, all
      * updates are made to the base field.  Upon first contention (a
      * failed CAS on base update), the table is initialized to size 2.
      * The table size is doubled upon further contention until
      * reaching the nearest power of two greater than or equal to the
      * number of CPUS. Table slots remain empty (null) until they are
      * needed.
      * A single spinlock ("busy") 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 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
      * exists, a CAS is tried.  Retries proceed by "double hashing",
      * using a secondary hash (Marsaglia XorShift) to try to find a
      * free slot.
      * The table size is capped because, when there are more threads
      * than CPUs, supposing that each thread were bound to a CPU,
      * there would exist a perfect hash function mapping threads to
      * slots that eliminates collisions. When we reach capacity, we
      * search for this mapping by randomly varying the hash codes of
      * colliding threads.  Because search is random, and collisions
      * only become known via CAS failures, convergence can be slow,
      * and because threads are typically not bound to CPUS forever,
      * may not occur at all. However, despite these limitations,
      * observed contention rates are typically low in these cases.
      * It is possible for a Cell to become unused when threads that
      * once hashed to it terminate, as well as in the case where
      * doubling the table causes no thread to hash to it under
      * expanded mask.  We do not try to detect or remove such cells,
      * under the assumption that for long-running instances, observed
      * contention levels will recur, so the cells will eventually be
      * needed again; and for short-lived ones, it does not matter.

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 p0p1p2p3p4p5p6;
         volatile long value;
         volatile long q0q1q2q3q4q5q6;
         Cell(long x) {
              = x;
        final boolean cas(long cmplong val) {
            return .compareAndSwapLong(thiscmpval);
        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long valueOffset;
        static {
            try {
                 = getUnsafe();
                Class<?> ak = Cell.class;
                 = .objectFieldOffset
            } catch (Exception 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 = .nextInt(); // Avoid zero to allow xorShift rehash
             = (h == 0) ? 1 : h;

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();

Table of cells. When non-null, size is a power of 2.
    transient volatile Cell[] cells;

Base value, used mainly when there is no contention, but also as a fallback during table initialization races. Updated via CAS.
    transient volatile long base;

Spinlock (locked via CAS) used when resizing and/or creating Cells.
    transient volatile int busy;

Package-private default constructor
    Striped64() {

CASes the base field.
    final boolean casBase(long cmplong val) {
        return .compareAndSwapLong(thiscmpval);

CASes the busy field from 0 to 1 to acquire lock.
    final boolean casBusy() {
        return .compareAndSwapInt(this, 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.

currentValue the current value (of either base or a cell)
newValue the argument from a user update call
result of the update function
    abstract long fn(long currentValuelong newValue);

Handles cases of updates involving initialization, resizing, creating new Cells, and/or contention. See above for explanation. This method suffers the usual non-modularity problems of optimistic retry code, relying on rechecked sets of reads.

x the value
hc the hash code holder
wasUncontended false if CAS failed before call
    final void retryUpdate(long xHashCode hcboolean wasUncontended) {
        int h = hc.code;
        boolean collide = false;                // True if last slot nonempty
        for (; ; ) {
            Cell[] as;
            Cell a;
            int n;
            long v;
            if ((as = ) != null && (n = as.length) > 0) {
                if ((a = as[(n - 1) & h]) == null) {
                    if ( == 0) {            // Try to attach new Cell
                        Cell r = new Cell(x);   // Optimistically create
                        if ( == 0 && casBusy()) {
                            boolean created = false;
                            try {               // Recheck under lock
                                Cell[] rs;
                                int mj;
                                if ((rs = ) != null &&
                                        (m = rs.length) > 0 &&
                                        rs[j = (m - 1) & h] == null) {
                                    rs[j] = r;
                                    created = true;
                            } finally {
                                 = 0;
                            if (created)
                            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.valuefn(vx)))
                else if (n >=  ||  != as)
                    collide = false;            // At max size or stale
                else if (!collide)
                    collide = true;
                else if ( == 0 && casBusy()) {
                    try {
                        if ( == as) {      // Expand table unless stale
                            Cell[] rs = new Cell[n << 1];
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[i];
                             = rs;
                    } finally {
                         = 0;
                    collide = false;
                    continue;                   // Retry with expanded table
                h ^= h << 13;                   // Rehash
                h ^= h >>> 17;
                h ^= h << 5;
            } else if ( == 0 &&  == as && casBusy()) {
                boolean init = false;
                try {                           // Initialize table
                    if ( == as) {
                        Cell[] rs = new Cell[2];
                        rs[h & 1] = new Cell(x);
                         = rs;
                        init = true;
                } finally {
                     = 0;
                if (init)
            } else if (casBase(v = fn(vx)))
                break;                          // Fall back on using base
        hc.code = h;                            // Record index for next time

Sets base and all cells to the given value.
    final void internalReset(long initialValue) {
        Cell[] as = ;
         = 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;
    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long baseOffset;
    private static final long busyOffset;
    static {
        try {
             = getUnsafe();
            Class<?> sk = Striped64.class;
             = .objectFieldOffset
             = .objectFieldOffset
        } catch (Exception 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 into a jdk.

a sun.misc.Unsafe
    private static sun.misc.Unsafe getUnsafe() {
        try {
            return sun.misc.Unsafe.getUnsafe();
        } catch (SecurityException ignored) {
        try {
                    (new<sun.misc.Unsafe>() {
                        public sun.misc.Unsafe run() throws Exception {
                            Class<sun.misc.Unsafek = sun.misc.Unsafe.class;
                            for (java.lang.reflect.Field f : k.getDeclaredFields()) {
                                Object x = f.get(null);
                                if (k.isInstance(x))
                                    return k.cast(x);
                            throw new NoSuchFieldError("the Unsafe");
        } catch ( e) {
            throw new RuntimeException("Could not initialize intrinsics",
New to GrepCode? Check out our FAQ X