On 3/2/15 3:30 PM, [email protected] wrote: > Author: psteitz > Date: Mon Mar 2 22:30:03 2015 > New Revision: 1663451 > > URL: http://svn.apache.org/r1663451 > Log: > Eliminated thread yield when factory method latency is 0. > > Added: > > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java > (with props) > Modified: > > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/GenericObjectPool.java > > commons/proper/pool/trunk/src/test/java/org/apache/commons/pool2/WaiterFactory.java
Sorry for the screw-up here, guys. I meant to commit only the test change. Others have been reverted. Phil > > Modified: > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/GenericObjectPool.java > URL: > http://svn.apache.org/viewvc/commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/GenericObjectPool.java?rev=1663451&r1=1663450&r2=1663451&view=diff > ============================================================================== > --- > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/GenericObjectPool.java > (original) > +++ > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/GenericObjectPool.java > Mon Mar 2 22:30:03 2015 > @@ -1120,7 +1120,8 @@ public class GenericObjectPool<T> extend > * wrappers used internally by the pool. > */ > private final Map<T, PooledObject<T>> allObjects = > - new ConcurrentHashMap<T, PooledObject<T>>(); > + new StaticBucketMap<T, PooledObject<T>>(); > + //new ConcurrentHashMap<T, PooledObject<T>>(); > /* > * The combined count of the currently created objects and those in the > * process of being created. Under load, it may exceed {@link > #_maxActive} > > Added: > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java > URL: > http://svn.apache.org/viewvc/commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java?rev=1663451&view=auto > ============================================================================== > --- > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java > (added) > +++ > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java > Mon Mar 2 22:30:03 2015 > @@ -0,0 +1,718 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You 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 org.apache.commons.pool2.impl; > + > +import java.util.AbstractCollection; > +import java.util.AbstractSet; > +import java.util.ArrayList; > +import java.util.Collection; > +import java.util.Iterator; > +import java.util.Map; > +import java.util.NoSuchElementException; > +import java.util.Set; > + > +/** > + * A StaticBucketMap is an efficient, thread-safe implementation of > + * <code>java.util.Map</code> that performs well in in a highly > + * thread-contentious environment. The map supports very efficient > + * {@link #get(Object) get}, {@link #put(Object,Object) put}, > + * {@link #remove(Object) remove} and {@link #containsKey(Object) > containsKey} > + * operations, assuming (approximate) uniform hashing and > + * that the number of entries does not exceed the number of buckets. If the > + * number of entries exceeds the number of buckets or if the hash codes of > the > + * objects are not uniformly distributed, these operations have a worst case > + * scenario that is proportional to the number of elements in the map > + * (<i>O(n)</i>).<p> > + * > + * Each bucket in the hash table has its own monitor, so two threads can > + * safely operate on the map at the same time, often without incurring any > + * monitor contention. This means that you don't have to wrap instances > + * of this class with {@link java.util.Collections#synchronizedMap(Map)}; > + * instances are already thread-safe. Unfortunately, however, this means > + * that this map implementation behaves in ways you may find disconcerting. > + * Bulk operations, such as {@link #putAll(Map) putAll} or the > + * {@link Collection#retainAll(Collection) retainAll} operation in collection > + * views, are <i>not</i> atomic. If two threads are simultaneously > + * executing > + * > + * <pre> > + * staticBucketMapInstance.putAll(map); > + * </pre> > + * > + * and > + * > + * <pre> > + * staticBucketMapInstance.entrySet().removeAll(map.entrySet()); > + * </pre> > + * > + * then the results are generally random. Those two statement could cancel > + * each other out, leaving <code>staticBucketMapInstance</code> essentially > + * unchanged, or they could leave some random subset of <code>map</code> in > + * <code>staticBucketMapInstance</code>.<p> > + * > + * Also, much like an encyclopedia, the results of {@link #size()} and > + * {@link #isEmpty()} are out-of-date as soon as they are produced.<p> > + * > + * The iterators returned by the collection views of this class are > <i>not</i> > + * fail-fast. They will <i>never</i> raise a > + * {@link java.util.ConcurrentModificationException}. Keys and values > + * added to the map after the iterator is created do not necessarily appear > + * during iteration. Similarly, the iterator does not necessarily fail to > + * return keys and values that were removed after the iterator was > created.<p> > + * > + * Finally, unlike {@link java.util.HashMap}-style implementations, this > + * class <i>never</i> rehashes the map. The number of buckets is fixed > + * at construction time and never altered. Performance may degrade if > + * you do not allocate enough buckets upfront.<p> > + * > + * The {@link #atomic(Runnable)} method is provided to allow atomic > iterations > + * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic} > + * will basically result in a map that's slower than an ordinary synchronized > + * {@link java.util.HashMap}. > + * > + * Use this class if you do not require reliable bulk operations and > + * iterations, or if you can make your own guarantees about how bulk > + * operations will affect the map.<p> > + * > + * The source for this class was forked from Commons Collections > + * trunk r1661551.<p> > + * > + * @version $Id: StaticBucketMap.java 1477799 2013-04-30 19:56:11Z tn $ > + */ > +class StaticBucketMap<K, V> implements Map<K, V> { > + > + /** The default number of buckets to use */ > + private static final int DEFAULT_BUCKETS = 255; > + /** The array of buckets, where the actual data is held */ > + private final Node<K, V>[] buckets; > + /** The matching array of locks */ > + private final Lock[] locks; > + > + /** > + * Initializes the map with the default number of buckets (255). > + */ > + public StaticBucketMap() { > + this(DEFAULT_BUCKETS); > + } > + > + /** > + * Initializes the map with a specified number of buckets. The number > + * of buckets is never below 17, and is always an odd number > (StaticBucketMap > + * ensures this). The number of buckets is inversely proportional to the > + * chances for thread contention. The fewer buckets, the more chances > for > + * thread contention. The more buckets the fewer chances for thread > + * contention. > + * > + * @param numBuckets the number of buckets for this map > + */ > + @SuppressWarnings("unchecked") > + public StaticBucketMap(final int numBuckets) { > + int size = Math.max(17, numBuckets); > + > + // Ensure that bucketSize is never a power of 2 (to ensure maximal > distribution) > + if (size % 2 == 0) { > + size--; > + } > + > + buckets = new Node[size]; > + locks = new Lock[size]; > + > + for (int i = 0; i < size; i++) { > + locks[i] = new Lock(); > + } > + } > + > + //----------------------------------------------------------------------- > + /** > + * Determine the exact hash entry for the key. The hash algorithm > + * is rather simplistic, but it does the job: > + * > + * <pre> > + * He = |Hk mod n| > + * </pre> > + * > + * <p> > + * He is the entry's hashCode, Hk is the key's system identity > hashCode, and n is > + * the number of buckets. > + * </p> > + */ > + private int getHash(final Object key) { > + if (key == null) { > + return 0; > + } > + int hash = System.identityHashCode(key); > + hash += ~(hash << 15); > + hash ^= (hash >>> 10); > + hash += (hash << 3); > + hash ^= (hash >>> 6); > + hash += ~(hash << 11); > + hash ^= (hash >>> 16); > + hash %= buckets.length; > + return (hash < 0) ? hash * -1 : hash; > + } > + > + /** > + * Gets the current size of the map. > + * The value is computed fresh each time the method is called. > + * > + * @return the current size > + */ > + public int size() { > + int cnt = 0; > + > + for (int i = 0; i < buckets.length; i++) { > + synchronized(locks[i]) { > + cnt += locks[i].size; > + } > + } > + return cnt; > + } > + > + /** > + * Checks if the size is currently zero. > + * > + * @return true if empty > + */ > + public boolean isEmpty() { > + return (size() == 0); > + } > + > + /** > + * Gets the value associated with the key. > + * > + * @param key the key to retrieve > + * @return the associated value > + */ > + public V get(final Object key) { > + final int hash = getHash(key); > + > + synchronized (locks[hash]) { > + Node<K, V> n = buckets[hash]; > + > + while (n != null) { > + if (n.key == key) { > + return n.value; > + } > + > + n = n.next; > + } > + } > + return null; > + } > + > + /** > + * Checks if the map contains the specified key. > + * > + * @param key the key to check > + * @return true if found > + */ > + public boolean containsKey(final Object key) { > + final int hash = getHash(key); > + > + synchronized (locks[hash]) { > + Node<K, V> n = buckets[hash]; > + > + while (n != null) { > + if (n.key == key || (n.key != null && n.key.equals(key))) { > + return true; > + } > + > + n = n.next; > + } > + } > + return false; > + } > + > + /** > + * Checks if the map contains the specified value. > + * > + * @param value the value to check > + * @return true if found > + */ > + public boolean containsValue(final Object value) { > + for (int i = 0; i < buckets.length; i++) { > + synchronized (locks[i]) { > + Node<K, V> n = buckets[i]; > + > + while (n != null) { > + if (n.value == value || (n.value != null && > n.value.equals(value))) { > + return true; > + } > + > + n = n.next; > + } > + } > + } > + return false; > + } > + > + //----------------------------------------------------------------------- > + /** > + * Puts a new key value mapping into the map. > + * > + * @param key the key to use > + * @param value the value to use > + * @return the previous mapping for the key > + */ > + public V put(final K key, final V value) { > + final int hash = getHash(key); > + > + synchronized (locks[hash]) { > + Node<K, V> n = buckets[hash]; > + > + if (n == null) { > + n = new Node<K, V>(); > + n.key = key; > + n.value = value; > + buckets[hash] = n; > + locks[hash].size++; > + return null; > + } > + > + // Set n to the last node in the linked list. Check each key > along the way > + // If the key is found, then change the value of that node and > return > + // the old value. > + for (Node<K, V> next = n; next != null; next = next.next) { > + n = next; > + > + if (n.key == key || (n.key != null && n.key.equals(key))) { > + final V returnVal = n.value; > + n.value = value; > + return returnVal; > + } > + } > + > + // The key was not found in the current list of nodes, add it to > the end > + // in a new node. > + final Node<K, V> newNode = new Node<K, V>(); > + newNode.key = key; > + newNode.value = value; > + n.next = newNode; > + locks[hash].size++; > + } > + return null; > + } > + > + /** > + * Removes the specified key from the map. > + * > + * @param key the key to remove > + * @return the previous value at this key > + */ > + public V remove(final Object key) { > + final int hash = getHash(key); > + > + synchronized (locks[hash]) { > + Node<K, V> n = buckets[hash]; > + Node<K, V> prev = null; > + > + while (n != null) { > + if (n.key == key || (n.key != null && n.key.equals(key))) { > + // Remove this node from the linked list of nodes. > + if (null == prev) { > + // This node was the head, set the next node to be > the new head. > + buckets[hash] = n.next; > + } else { > + // Set the next node of the previous node to be the > node after this one. > + prev.next = n.next; > + } > + locks[hash].size--; > + return n.value; > + } > + > + prev = n; > + n = n.next; > + } > + } > + return null; > + } > + > + //----------------------------------------------------------------------- > + /** > + * Gets the key set. > + * > + * @return the key set > + */ > + public Set<K> keySet() { > + return new KeySet(); > + } > + > + /** > + * Gets the values. > + * > + * @return the values > + */ > + public Collection<V> values() { > + return new Values(); > + } > + > + /** > + * Gets the entry set. > + * > + * @return the entry set > + */ > + public Set<Map.Entry<K, V>> entrySet() { > + return new EntrySet(); > + } > + > + //----------------------------------------------------------------------- > + /** > + * Puts all the entries from the specified map into this map. > + * This operation is <b>not atomic</b> and may have undesired effects. > + * > + * @param map the map of entries to add > + */ > + public void putAll(final Map<? extends K, ? extends V> map) { > + for (final Map.Entry<? extends K, ? extends V> entry : > map.entrySet()) { > + put(entry.getKey(), entry.getValue()); > + } > + } > + > + /** > + * Clears the map of all entries. > + */ > + public void clear() { > + for (int i = 0; i < buckets.length; i++) { > + final Lock lock = locks[i]; > + synchronized (lock) { > + buckets[i] = null; > + lock.size = 0; > + } > + } > + } > + > + /** > + * Compares this map to another, as per the Map specification. > + * > + * @param obj the object to compare to > + * @return true if equal > + */ > + @Override > + public boolean equals(final Object obj) { > + if (obj == this) { > + return true; > + } > + if (obj instanceof Map<?, ?> == false) { > + return false; > + } > + final Map<?, ?> other = (Map<?, ?>) obj; > + return entrySet().equals(other.entrySet()); > + } > + > + /** > + * Gets the hash code, as per the Map specification. > + * > + * @return the hash code > + */ > + @Override > + public int hashCode() { > + int hashCode = 0; > + > + for (int i = 0; i < buckets.length; i++) { > + synchronized (locks[i]) { > + Node<K, V> n = buckets[i]; > + > + while (n != null) { > + hashCode += n.hashCode(); > + n = n.next; > + } > + } > + } > + return hashCode; > + } > + > + //----------------------------------------------------------------------- > + /** > + * The Map.Entry for the StaticBucketMap. > + */ > + private static final class Node<K, V> implements Map.Entry<K, V> { > + protected K key; > + protected V value; > + protected Node<K, V> next; > + > + public K getKey() { > + return key; > + } > + > + public V getValue() { > + return value; > + } > + > + @Override > + public int hashCode() { > + return ((key == null ? 0 : key.hashCode()) ^ > + (value == null ? 0 : value.hashCode())); > + } > + > + @Override > + public boolean equals(final Object obj) { > + if (obj == this) { > + return true; > + } > + if (obj instanceof Map.Entry<?, ?> == false) { > + return false; > + } > + > + final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj; > + return ( > + (key == null ? e2.getKey() == null : > key.equals(e2.getKey())) && > + (value == null ? e2.getValue() == null : > value.equals(e2.getValue()))); > + } > + > + public V setValue(final V obj) { > + final V retVal = value; > + value = obj; > + return retVal; > + } > + } > + > + /** > + * The lock object, which also includes a count of the nodes in this > lock. > + */ > + private final static class Lock { > + public int size; > + } > + > + //----------------------------------------------------------------------- > + private class BaseIterator { > + private final ArrayList<Map.Entry<K, V>> current = new > ArrayList<Map.Entry<K,V>>(); > + private int bucket; > + private Map.Entry<K, V> last; > + > + public boolean hasNext() { > + if (current.size() > 0) { > + return true; > + } > + while (bucket < buckets.length) { > + synchronized (locks[bucket]) { > + Node<K, V> n = buckets[bucket]; > + while (n != null) { > + current.add(n); > + n = n.next; > + } > + bucket++; > + if (current.size() > 0) { > + return true; > + } > + } > + } > + return false; > + } > + > + protected Map.Entry<K, V> nextEntry() { > + if (!hasNext()) { > + throw new NoSuchElementException(); > + } > + last = current.remove(current.size() - 1); > + return last; > + } > + > + public void remove() { > + if (last == null) { > + throw new IllegalStateException(); > + } > + StaticBucketMap.this.remove(last.getKey()); > + last = null; > + } > + } > + > + private class EntryIterator extends BaseIterator implements > Iterator<Map.Entry<K, V>> { > + > + public Map.Entry<K, V> next() { > + return nextEntry(); > + } > + > + } > + > + private class ValueIterator extends BaseIterator implements Iterator<V> { > + > + public V next() { > + return nextEntry().getValue(); > + } > + > + } > + > + private class KeyIterator extends BaseIterator implements Iterator<K> { > + > + public K next() { > + return nextEntry().getKey(); > + } > + > + } > + > + private class EntrySet extends AbstractSet<Map.Entry<K, V>> { > + > + @Override > + public int size() { > + return StaticBucketMap.this.size(); > + } > + > + @Override > + public void clear() { > + StaticBucketMap.this.clear(); > + } > + > + @Override > + public Iterator<Map.Entry<K, V>> iterator() { > + return new EntryIterator(); > + } > + > + @Override > + public boolean contains(final Object obj) { > + final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; > + final int hash = getHash(entry.getKey()); > + synchronized (locks[hash]) { > + for (Node<K, V> n = buckets[hash]; n != null; n = n.next) { > + if (n.equals(entry)) { > + return true; > + } > + } > + } > + return false; > + } > + > + @Override > + public boolean remove(final Object obj) { > + if (obj instanceof Map.Entry<?, ?> == false) { > + return false; > + } > + final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; > + final int hash = getHash(entry.getKey()); > + synchronized (locks[hash]) { > + for (Node<K, V> n = buckets[hash]; n != null; n = n.next) { > + if (n.equals(entry)) { > + StaticBucketMap.this.remove(n.getKey()); > + return true; > + } > + } > + } > + return false; > + } > + > + } > + > + private class KeySet extends AbstractSet<K> { > + > + @Override > + public int size() { > + return StaticBucketMap.this.size(); > + } > + > + @Override > + public void clear() { > + StaticBucketMap.this.clear(); > + } > + > + @Override > + public Iterator<K> iterator() { > + return new KeyIterator(); > + } > + > + @Override > + public boolean contains(final Object obj) { > + return StaticBucketMap.this.containsKey(obj); > + } > + > + @Override > + public boolean remove(final Object obj) { > + final int hash = getHash(obj); > + synchronized (locks[hash]) { > + for (Node<K, V> n = buckets[hash]; n != null; n = n.next) { > + final Object k = n.getKey(); > + if ((k == obj) || ((k != null) && k.equals(obj))) { > + StaticBucketMap.this.remove(k); > + return true; > + } > + } > + } > + return false; > + } > + > + } > + > + > + private class Values extends AbstractCollection<V> { > + > + @Override > + public int size() { > + return StaticBucketMap.this.size(); > + } > + > + @Override > + public void clear() { > + StaticBucketMap.this.clear(); > + } > + > + @Override > + public Iterator<V> iterator() { > + return new ValueIterator(); > + } > + > + } > + > + /** > + * Prevents any operations from occurring on this map while the > + * given {@link Runnable} executes. This method can be used, for > + * instance, to execute a bulk operation atomically: > + * > + * <pre> > + * staticBucketMapInstance.atomic(new Runnable() { > + * public void run() { > + * staticBucketMapInstance.putAll(map); > + * } > + * }); > + * </pre> > + * > + * It can also be used if you need a reliable iterator: > + * > + * <pre> > + * staticBucketMapInstance.atomic(new Runnable() { > + * public void run() { > + * Iterator iterator = staticBucketMapInstance.iterator(); > + * while (iterator.hasNext()) { > + * foo(iterator.next(); > + * } > + * } > + * }); > + * </pre> > + * > + * <b>Implementation note:</b> This method requires a lot of time > + * and a ton of stack space. Essentially a recursive algorithm is used > + * to enter each bucket's monitor. If you have twenty thousand buckets > + * in your map, then the recursive method will be invoked twenty > thousand > + * times. You have been warned. > + * > + * @param r the code to execute atomically > + */ > + public void atomic(final Runnable r) { > + if (r == null) { > + throw new NullPointerException(); > + } > + atomic(r, 0); > + } > + > + private void atomic(final Runnable r, final int bucket) { > + if (bucket >= buckets.length) { > + r.run(); > + return; > + } > + synchronized (locks[bucket]) { > + atomic(r, bucket + 1); > + } > + } > + > +} > > Propchange: > commons/proper/pool/trunk/src/main/java/org/apache/commons/pool2/impl/StaticBucketMap.java > ------------------------------------------------------------------------------ > svn:eol-style = native > > Modified: > commons/proper/pool/trunk/src/test/java/org/apache/commons/pool2/WaiterFactory.java > URL: > http://svn.apache.org/viewvc/commons/proper/pool/trunk/src/test/java/org/apache/commons/pool2/WaiterFactory.java?rev=1663451&r1=1663450&r2=1663451&view=diff > ============================================================================== > --- > commons/proper/pool/trunk/src/test/java/org/apache/commons/pool2/WaiterFactory.java > (original) > +++ > commons/proper/pool/trunk/src/test/java/org/apache/commons/pool2/WaiterFactory.java > Mon Mar 2 22:30:03 2015 > @@ -144,6 +144,9 @@ KeyedPooledObjectFactory<K,Waiter> { > } > > protected void doWait(long latency) { > + if (latency == 0) { > + return; > + } > try { > Thread.sleep(latency); > } catch (InterruptedException ex) { > > >
