/*
More tests of various singleton implementations
last update: Mon Mar 26 20:19:39 2001 Doug Lea (dl at gee)
*/
class TSS extends Thread {
static abstract class Singleton {
// a field and method to prevent some compiler optimizations
int aField = System.identityHashCode(this);
int aMethod(int i) { return (i % 17) != 0 ? aField: i; }
}
static class EagerSingleton extends Singleton {
static final EagerSingleton theInstance = new EagerSingleton();
static EagerSingleton getInstance() {
return theInstance;
}
}
static class SynchedSingleton extends Singleton {
static SynchedSingleton theInstance;
static synchronized SynchedSingleton getInstance() {
if (theInstance == null)
theInstance = new SynchedSingleton();
return theInstance;
}
}
static class ThreadLocalSingleton extends Singleton {
static final ThreadLocal perThreadInstance = new ThreadLocal();
static final Object lock = new Object();
static ThreadLocalSingleton theInstance;
static ThreadLocalSingleton getInstance() {
ThreadLocalSingleton instance = (ThreadLocalSingleton)(perThreadInstance.get());
if (instance == null) {
synchronized(lock) {
instance = theInstance;
if (instance == null)
instance = theInstance = new ThreadLocalSingleton();
}
// copy global to per-thread
perThreadInstance.set(instance);
}
return instance;
}
}
static class SimulatedThreadLocalSingleton extends Singleton {
static SimulatedThreadLocalSingleton theInstance;
static final Object lock = new Object();
static final Object key = new Object();
static Singleton getInstance() {
TSS t = (TSS)(Thread.currentThread());
Singleton instance = (Singleton)(t.threadLocalHashtable.get(key));
if (instance == null) {
synchronized(lock) {
instance = theInstance;
if (instance == null)
instance = theInstance = new SimulatedThreadLocalSingleton();
}
// copy global to per-thread
t.threadLocalHashtable.put(key, instance);
}
return instance;
}
}
static class VolatileSingleton extends Singleton {
static final Object lock = new Object();
static volatile VolatileSingleton theInstance;
static VolatileSingleton getInstance() {
VolatileSingleton instance = theInstance;
if (instance == null) {
synchronized(lock) {
instance = theInstance;
if (instance == null)
instance = theInstance = new VolatileSingleton();
}
}
return instance;
}
}
static class DirectThreadFieldSingleton extends Singleton {
static DirectThreadFieldSingleton theInstance;
static final Object lock = new Object();
static Singleton getInstance(TSS t) {
Singleton instance = t.singleton;
if (instance == null) {
synchronized(lock) {
instance = theInstance;
if (instance == null)
instance = theInstance = new DirectThreadFieldSingleton();
}
// copy global to per-thread
t.singleton = instance;
}
return instance;
}
}
static class ThreadFieldSingleton extends Singleton {
static final Object lock = new Object();
static ThreadFieldSingleton theInstance;
static Singleton getInstance() {
TSS t = (TSS)(Thread.currentThread());
Singleton instance = t.singleton;
if (instance == null) {
synchronized(lock) {
instance = theInstance;
if (instance == null)
instance = theInstance = new ThreadFieldSingleton();
}
// copy global to per-thread
t.singleton = instance;
}
return instance;
}
}
static final int ITERS = 1000000;
static final int NTHREADS = 8;
static int total; // accumulate calls to aMethod, to prevent overoptimizing
final IDHashMap threadLocalHashtable = new IDHashMap(8);
Singleton singleton;
int mode;
TSS(int md) { mode = md; }
public void run() {
int sum = 0; // to prevent optimizations
if (mode == 0) {
for (int i = 0; i < ITERS; ++i) {
sum += EagerSingleton.getInstance().aMethod(i);
}
}
else if (mode == 1) {
for (int i = 0; i < ITERS; ++i) {
sum += ThreadLocalSingleton.getInstance().aMethod(i);
}
}
else if (mode == 2) {
for (int i = 0; i < ITERS; ++i) {
sum += SimulatedThreadLocalSingleton.getInstance().aMethod(i);
}
}
else if (mode == 3) {
for (int i = 0; i < ITERS; ++i) {
sum += VolatileSingleton.getInstance().aMethod(i);
}
}
else if (mode == 4) {
for (int i = 0; i < ITERS; ++i) {
sum += SynchedSingleton.getInstance().aMethod(i);
}
}
else if (mode == 5) {
for (int i = 0; i < ITERS; ++i) {
sum += DirectThreadFieldSingleton.getInstance(this).aMethod(i);
}
}
else if (mode == 6) {
for (int i = 0; i < ITERS; ++i) {
sum += ThreadFieldSingleton.getInstance().aMethod(i);
}
}
total += sum;
}
public static void main(String[] args) {
Thread[] threads = new Thread[NTHREADS];
for (int reps = 0; reps < 3; ++reps) {
for (int i = 0; i < NTHREADS; ++i)
threads[i] = null;
System.gc();
for (int mode = 0; mode < 7; ++mode) {
if (mode == 0)
System.out.print("Eager: ");
else if (mode == 1)
System.out.print("ThreadLocal: ");
else if (mode == 2)
System.out.print("SimThreadLocal: ");
else if (mode == 3)
System.out.print("Volatile (DCL): ");
else if (mode == 4)
System.out.print("Synch: ");
else if (mode == 5)
System.out.print("Direct Field: ");
else if (mode == 6)
System.out.print("Thread Field: ");
long startTime = System.currentTimeMillis();
for (int i = 0; i < NTHREADS; ++i)
threads[i] = new TSS(mode);
for (int i = 0; i < NTHREADS; ++i)
threads[i].start();
try {
for (int i = 0; i < NTHREADS; ++i)
threads[i].join();
}
catch (InterruptedException ie) {
System.out.println("Interrupted");
return;
}
long elapsed = System.currentTimeMillis() - startTime;
System.out.println(elapsed + "ms");
if (total == 0) // ensure total is live to avoid optimizing away
System.out.println("useless number = " + total);
}
}
}
}
/*
Renamed and hacked version of 1.4 IdentityHashMap so can test on pre-1.4
*/
class IDHashMap {
/**
* The initial capacity used by the no-args constructor.
* MUST be a power of two. The value 32 corresponds to the
* (specified) expected maximum size of 21, given a load factor
* of 2/3.
*/
private static final int DEFAULT_CAPACITY = 32;
/**
* The minimum capacity, used if a lower value is implicitly specified
* by either of the constructors with arguments. The value 4 corresponds
* to an expected maximum size of 2, given a load factor of 2/3.
* MUST be a power of two.
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<29.
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
* Special value used to mark slots as deleted.
*/
private static final Object DELETED = new Object();
/**
* Special value used to mark slots as empty.
*/
private static final Object EMPTY = new Object();
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
private transient Object[] table;
/**
* The number of key-value mappings contained in this identity hash map.
*
* @serial
*/
private int size;
/**
* The next size value at which to resize (capacity * load factor).
*/
private transient int threshold;
/**
* Constructs a new, empty identity hash map with a default expected
* maximum size (21).
*/
public IDHashMap() {
init(DEFAULT_CAPACITY);
}
/**
* Constructs a new, empty map with the specified expected maximum size.
* Putting more than the expected number of key-value mappings into
* the map may cause the internal data structure to grow, which may be
* somewhat time-consuming.
*
* @param expectedMaxSize the expected maximum size of the map.
* @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
*/
public IDHashMap(int expectedMaxSize) {
if (expectedMaxSize < 0)
throw new IllegalArgumentException("expectedMaxSize is negative");
init(capacity(expectedMaxSize));
}
/**
* Returns the appropriate capacity for the specified expected maximum
* size. Returns the smallest power of two between MINIMUM_CAPACITY
* and MAXIMUM_CAPACITY, inclusive, that is greater than
* (3 * expectedMaxSize)/2, if such a number exists. Otherwise
* returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
* is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
*/
private int capacity(int expectedMaxSize) {
// Compute min capacity for expectedMaxSize given a load factor of 2/3
int minCapacity = (3 * expectedMaxSize)/2;
// Compute the appropriate capacity
int result;
if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
result = MAXIMUM_CAPACITY;
} else {
result = MINIMUM_CAPACITY;
while (result < minCapacity)
result <<= 1;
}
return result;
}
/**
* Initialize object to be an empty map with the specified initial
* capacity, which is assumed to be a power of two between
* MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
*/
private void init(int initCapacity) {
// assert (initCapacity & -initCapacity) == initCapacity; // power of 2
// assert initCapacity >= MINIMUM_CAPACITY;
// assert initCapacity <= MAXIMUM_CAPACITY;
threshold = (initCapacity * 2)/3;
table = new Object[2 * initCapacity];
for (int i = 0; i < table.length; i += 2)
table[i] = EMPTY;
}
/**
* Returns the number of key-value mappings in this identity hash map.
*
* @return the number of key-value mappings in this map.
*/
public int size() {
return size;
}
/**
* Returns <tt>true</tt> if this identity hash map contains no key-value
* mappings.
*
* @return <tt>true</tt> if this identity hash map contains no key-value
* mappings.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Return index for Object x given table size len, where len is a power of
* two.
*/
private static int hash(Object x, int len) {
int h = System.identityHashCode(x);
return h & (len-2);
}
/**
* Returns the value to which the specified key is mapped in this identity
* hash map, or <tt>null</tt> if the map contains no mapping for
* this key. A return value of <tt>null</tt> does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it is also
* possible that the map explicitly maps the key to <tt>null</tt>. The
* <tt>containsKey</tt> method may be used to distinguish these two
* cases.
*
* @param key the key whose associated value is to be returned.
* @return the value to which this map maps the specified key, or
* <tt>null</tt> if the map contains no mapping for this key.
* @see #put(Object, Object)
*/
public Object get(Object key) {
int i = hash(key, table.length);
while (true) {
Object item = table[i];
if (item == key)
return table[i+1];
if (item == EMPTY)
return null;
if ((i+=2) >= table.length)
i = 0;
}
}
/**
* Associates the specified value with the specified key in this identity
* hash map. If the map previously contained a mapping for this key, the
* old value is replaced.
*
* @param key the key with which the specified value is to be associated.
* @param value the value to be associated with the specified key.
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>. (A
* <tt>null</tt> return can also indicate that the map previously
* associated <tt>null</tt> with the specified key.)
* @see Object#equals(Object)
* @see #get(Object)
* @see #containsKey(Object)
*/
public Object put(Object key, Object value) {
/*
* insertionIndex is the index of the first DELETED
* entry passed over while checking if x is already
* present. If such a slot exists, we should use it
* rather than trailing null slot
*/
int insertionIndex = -1;
int i = hash(key, table.length);
while (true) {
Object item = table[i];
if (item == EMPTY) {
if (insertionIndex < 0)
insertionIndex = i;
table[insertionIndex] = key;
table[insertionIndex+1] = value;
if (++size >= threshold) resize();
return null;
} else if (item == key) {
Object oldValue = table[++i];
table[i] = value;
return oldValue;
} else if (item == DELETED && insertionIndex < 0) {
insertionIndex = i;
}
if ((i+=2) >= table.length)
i = 0;
}
}
/**
* Double the size of the table
*/
private void resize() {
int oldTableSize = table.length;
if (oldTableSize == 2*MAXIMUM_CAPACITY) { // can't expand any further
if (threshold == MAXIMUM_CAPACITY-1)
throw new IllegalStateException("Capacity exhausted.");
threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
return;
}
int newSize = 2 * oldTableSize;
threshold = (oldTableSize * 2)/3;
Object[] oldTable = table;
table = new Object[newSize];
for (int i = 0; i < table.length; i +=2)
table[i] = EMPTY;
for (int j = 0; j < oldTable.length; j+=2) {
Object key = oldTable[j];
if (key != EMPTY && key != DELETED) {
Object value = oldTable[j+1];
int i = hash(key, table.length);
while (table[i] != EMPTY) {
if ((i+=2) == table.length)
i = 0;
}
table[i] = key;
table[i+1] = value;
}
}
}
/**
* Removes the mapping for this key from this map if present.
*
* @param key key whose mapping is to be removed from the map.
* @return previous value associated with specified key, or <tt>null</tt>
* if there was no entry for key. (A <tt>null</tt> return can
* also indicate that the map previously associated <tt>null</tt>
* with the specified key.)
*/
public Object remove(Object key) {
int i = hash(key, table.length);
while (true) {
Object item = table[i];
if (item == EMPTY)
return null;
else if (item == key) {
Object oldValue = table[i+1];
markAsDeleted(i);
return oldValue;
}
if ((i+=2) >= table.length)
i = 0;
}
}
/**
* Mark table[index] as either DELETED or, if possible, EMPTY.
*/
private void markAsDeleted(int index) {
/*
* Because table[index] could have been between two real items
* without an intervening EMPTY, it must normally be marked as
* DELETED so that linear probing continues to work. But if it is
* part of a sequence of DELETEDs ending in a EMPTY, table[index] and
* other members of the sequence can be set to EMPTY, which will
* shorten subsequent searches, especially after bursts of
* removals. It also guarantees that an empty table has no DELETED
* markers. In practice, this keeps the number of DELETED markers
* low enough to not hurt search times much in the presence of
* deletions.
*
* Note that the alternative of re-inserting old elements rather
* than using a DELETED marker cannot be used here because this
* could re-arrange items in the midst of an iteration.
*/
--size;
table[index+1] = null; // null out value;
int j = index;
while (true) { // Traverse starting at next slot after index
if ((j+=2) == table.length)
j = 0;
Object item = table[j];
if (item == EMPTY) // Found a sequence ending in EMPTY
break;
else if (item != DELETED) { // no such luck
table[index] = DELETED;
return;
}
}
while (true) { // Run backwards until not DELETED
if ((j-=2) < 0)
j = table.length - 2;
if (j == index || table[j] == DELETED)
table[j] = EMPTY;
else
return;
}
}
/**
* Removes all mappings from this map.
*/
public void clear() {
for (int i = 0; i < table.length; i+=2)
table[i] = EMPTY;
for (int i = 1; i < table.length; i+=2)
table[i] = null;
size = 0;
}
}
