Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2011 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.util.concurrent;
 
 
 import java.util.List;
A striped Lock/Semaphore/ReadWriteLock. This offers the underlying lock striping similar to that of ConcurrentHashMap in a reusable form, and extends it for semaphores and read-write locks. Conceptually, lock striping is the technique of dividing a lock into many stripes, increasing the granularity of a single lock and allowing independent operations to lock different stripes and proceed concurrently, instead of creating contention for a single lock.

The guarantee provided by this class is that equal keys lead to the same lock (or semaphore), i.e. if (key1.equals(key2)) then striped.get(key1) == striped.get(key2) (assuming java.lang.Object.hashCode() is correctly implemented for the keys). Note that if key1 is not equal to key2, it is not guaranteed that striped.get(key1) != striped.get(key2); the elements might nevertheless be mapped to the same lock. The lower the number of stripes, the higher the probability of this happening.

There are three flavors of this class: Striped<Lock>, Striped<Semaphore>, and Striped<ReadWriteLock>. For each type, two implementations are offered: strong and weak Striped<Lock>, strong and lazyWeakSemaphore(int,int) Striped<Semaphore>, and readWriteLock(int) and weak Striped<ReadWriteLock>. Strong means that all stripes (locks/semaphores) are initialized eagerly, and are not reclaimed unless Striped itself is reclaimable. Weak means that locks/semaphores are created lazily, and they are allowed to be reclaimed if nobody is holding on to them. This is useful, for example, if one wants to create a Striped<Lock> of many locks, but worries that in most cases only a small portion of these would be in use.

Prior to this class, one might be tempted to use Map<K, Lock>, where K represents the task. This maximizes concurrency by having each unique key mapped to a unique lock, but also maximizes memory footprint. On the other extreme, one could use a single lock for all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of choosing either of these extremes, Striped allows the user to trade between required concurrency and memory footprint. For example, if a set of tasks are CPU-bound, one could easily create a very compact Striped<Lock> of availableProcessors() * 4 stripes, instead of possibly thousands of locks which could be created in a Map<K, Lock> structure.

Author(s):
Dimitris Andreou
Since:
13.0
 
 public abstract class Striped<L> {
   private Striped() {}

  
Returns the stripe that corresponds to the passed key. It is always guaranteed that if key1.equals(key2), then get(key1) == get(key2).

Parameters:
key an arbitrary, non-null key
Returns:
the stripe that the passed key corresponds to
 
   public abstract L get(Object key);

  
Returns the stripe at the specified index. Valid indexes are 0, inclusively, to size(), exclusively.

Parameters:
index the index of the stripe to return; must be in [0...size())
Returns:
the stripe at the specified index
  public abstract L getAt(int index);

  
Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
  abstract int indexFor(Object key);

  
Returns the total number of stripes in this instance.
  public abstract int size();

  
Returns the stripes that correspond to the passed objects, in ascending (as per getAt(int)) order. Thus, threads that use the stripes in the order returned by this method are guaranteed to not deadlock each other.

It should be noted that using a Striped<L> with relatively few stripes, and bulkGet(keys) with a relative large number of keys can cause an excessive number of shared stripes (much like the birthday paradox, where much fewer than anticipated birthdays are needed for a pair of them to match). Please consider carefully the implications of the number of stripes, the intended concurrency level, and the typical number of keys used in a bulkGet(keys) operation. See Balls in Bins model for mathematical formulas that can be used to estimate the probability of collisions.

Parameters:
keys arbitrary non-null keys
Returns:
the stripes corresponding to the objects (one per each object, derived by delegating to get(java.lang.Object); may contain duplicates), in an increasing index order.
  public Iterable<L> bulkGet(Iterable<?> keys) {
    // Initially using the array to store the keys, then reusing it to store the respective L's
    final Object[] array = Iterables.toArray(keysObject.class);
    int[] stripes = new int[array.length];
    for (int i = 0; i < array.lengthi++) {
      stripes[i] = indexFor(array[i]);
    }
    Arrays.sort(stripes);
    for (int i = 0; i < array.lengthi++) {
      array[i] = getAt(stripes[i]);
    }
    /*
     * Note that the returned Iterable holds references to the returned stripes, to avoid
     * error-prone code like:
     *
     * Striped<Lock> stripedLock = Striped.lazyWeakXXX(...)'
     * Iterable<Lock> locks = stripedLock.bulkGet(keys);
     * for (Lock lock : locks) {
     *   lock.lock();
     * }
     * operation();
     * for (Lock lock : locks) {
     *   lock.unlock();
     * }
     *
     * If we only held the int[] stripes, translating it on the fly to L's, the original locks
     * might be garbage collected after locking them, ending up in a huge mess.
     */
    @SuppressWarnings("unchecked"// we carefully replaced all keys with their respective L's
    List<L> asList = (List<L>) Arrays.asList(array);
    return Collections.unmodifiableList(asList);
  }
  // Static factories

  
Creates a Striped<Lock> with eagerly initialized, strongly referenced locks, with the specified fairness. Every lock is reentrant.

Parameters:
stripes the minimum number of stripes (locks) required
Returns:
a new Striped<Lock>
  public static Striped<Locklock(int stripes) {
    return new CompactStriped<Lock>(stripesnew Supplier<Lock>() {
      public Lock get() {
        return new PaddedLock();
      }
    });
  }

  
Creates a Striped<Lock> with lazily initialized, weakly referenced locks, with the specified fairness. Every lock is reentrant.

Parameters:
stripes the minimum number of stripes (locks) required
Returns:
a new Striped<Lock>
  public static Striped<LocklazyWeakLock(int stripes) {
    return new LazyStriped<Lock>(stripesnew Supplier<Lock>() {
      public Lock get() {
        return new ReentrantLock(false);
      }
    });
  }

  
Creates a Striped<Semaphore> with eagerly initialized, strongly referenced semaphores, with the specified number of permits and fairness.

Parameters:
stripes the minimum number of stripes (semaphores) required
permits the number of permits in each semaphore
Returns:
a new Striped<Semaphore>
  public static Striped<Semaphoresemaphore(int stripesfinal int permits) {
    return new CompactStriped<Semaphore>(stripesnew Supplier<Semaphore>() {
      public Semaphore get() {
        return new PaddedSemaphore(permits);
      }
    });
  }

  
Creates a Striped<Semaphore> with lazily initialized, weakly referenced semaphores, with the specified number of permits and fairness.

Parameters:
stripes the minimum number of stripes (semaphores) required
permits the number of permits in each semaphore
Returns:
a new Striped<Semaphore>
  public static Striped<SemaphorelazyWeakSemaphore(int stripesfinal int permits) {
    return new LazyStriped<Semaphore>(stripesnew Supplier<Semaphore>() {
      public Semaphore get() {
        return new Semaphore(permitsfalse);
      }
    });
  }

  
Creates a Striped<ReadWriteLock> with eagerly initialized, strongly referenced read-write locks, with the specified fairness. Every lock is reentrant.

Parameters:
stripes the minimum number of stripes (locks) required
Returns:
a new Striped<ReadWriteLock>
  public static Striped<ReadWriteLockreadWriteLock(int stripes) {
    return new CompactStriped<ReadWriteLock>(stripes);
  }

  
Creates a Striped<ReadWriteLock> with lazily initialized, weakly referenced read-write locks, with the specified fairness. Every lock is reentrant.

Parameters:
stripes the minimum number of stripes (locks) required
Returns:
a new Striped<ReadWriteLock>
  public static Striped<ReadWriteLocklazyWeakReadWriteLock(int stripes) {
    return new LazyStriped<ReadWriteLock>(stripes);
  }
  // ReentrantReadWriteLock is large enough to make padding probably unnecessary
  private static final Supplier<ReadWriteLockREAD_WRITE_LOCK_SUPPLIER =
      new Supplier<ReadWriteLock>() {
    public ReadWriteLock get() {
      return new ReentrantReadWriteLock();
    }
  };
  private abstract static class PowerOfTwoStriped<L> extends Striped<L> {
    
Capacity (power of two) minus one, for fast mod evaluation
    final int mask;
    PowerOfTwoStriped(int stripes) {
      Preconditions.checkArgument(stripes > 0, "Stripes must be positive");
      this. = stripes > . ?  : ceilToPowerOfTwo(stripes) - 1;
    }
    @Override final int indexFor(Object key) {
      int hash = smear(key.hashCode());
      return hash & ;
    }
    @Override public final L get(Object key) {
      return getAt(indexFor(key));
    }
  }

  
Implementation of Striped where 2^k stripes are represented as an array of the same length, eagerly initialized.
  private static class CompactStriped<L> extends PowerOfTwoStriped<L> {
    
Size is a power of two.
    private final Object[] array;
    private CompactStriped(int stripesSupplier<L> supplier) {
      super(stripes);
      Preconditions.checkArgument(stripes <= ."Stripes must be <= 2^30)");
      this. = new Object[ + 1];
      for (int i = 0; i < .i++) {
        [i] = supplier.get();
      }
    }
    @SuppressWarnings("unchecked"// we only put L's in the array
    @Override public L getAt(int index) {
      return (L) [index];
    }
    @Override public int size() {
      return .;
    }
  }

  
Implementation of Striped where up to 2^k stripes can be represented, using a Cache where the key domain is [0..2^k). To map a user key into a stripe, we take a k-bit slice of the user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced.
  private static class LazyStriped<L> extends PowerOfTwoStriped<L> {
    final ConcurrentMap<Integer, L> cache;
    final int size;
    LazyStriped(int stripesSupplier<L> supplier) {
      super(stripes);
      this. = ( == ) ? . :  + 1;
      this. = new MapMaker().weakValues().makeComputingMap(Functions.forSupplier(supplier));
    }
    @Override public L getAt(int index) {
      Preconditions.checkElementIndex(indexsize());
      return .get(index);
    }
    @Override public int size() {
      return ;
    }
  }

  
A bit mask were all bits are set.
  private static final int ALL_SET = ~0;
  private static int ceilToPowerOfTwo(int x) {
    return 1 << IntMath.log2(x.);
  }
  /*
   * This method was 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/licenses/publicdomain
   *
   * As of 2010/06/11, this method is identical to the (package private) hash
   * method in OpenJDK 7's java.util.HashMap class.
   */
  // Copied from java/com/google/common/collect/Hashing.java
  private static int smear(int hashCode) {
    hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
    return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
  }
  private static class PaddedLock extends ReentrantLock {
    /*
     * Padding from 40 into 64 bytes, same size as cache line. Might be beneficial to add
     * a fourth long here, to minimize chance of interference between consecutive locks,
     * but I couldn't observe any benefit from that.
     */
    @SuppressWarnings("unused")
    long q1q2q3;
    PaddedLock() {
      super(false);
    }
  }
  private static class PaddedSemaphore extends Semaphore {
    // See PaddedReentrantLock comment
    @SuppressWarnings("unused")
    long q1q2q3;
    PaddedSemaphore(int permits) {
      super(permitsfalse);
    }
  }
New to GrepCode? Check out our FAQ X