com.cliffc.aa.util.ConcurrentAutoTable Class Reference

An auto-resizing table of. More...

Inheritance diagram for com.cliffc.aa.util.ConcurrentAutoTable:

Collaboration diagram for com.cliffc.aa.util.ConcurrentAutoTable:

Classes
class	CAT

Public Member Functions
void	add (long x)
	Add the given value to current counter value. More...
void	decrement ()
	add with -1 More...
long	estimate_get ()
	A cheaper get. More...
long	get ()
	Current value of the counter. More...
void	increment ()
	add with +1 More...
int	internal_size ()
	Return the internal counter striping factor. More...
int	intValue ()
	Same as get, included for completeness. More...
long	longValue ()
	Same as get, included for completeness. More...
void	print ()
	A more verbose print than toString, showing internal structure. More...
void	set (long x)
	Atomically set the sum of the striped counters to specified value. More...
String	toString ()
	Return the counter's. More...

Private Member Functions
long	add_if (long x)
boolean	CAS_cat (CAT oldcat, CAT newcat)

Static Private Member Functions
static int	hash ()

Private Attributes
volatile CAT	_cat = new CAT(null,16,0L)

Static Private Attributes
static AtomicReferenceFieldUpdater< ConcurrentAutoTable, CAT >	_catUpdater

Detailed Description

An auto-resizing table of.

longs 

, supporting low-contention CAS operations. Updates are done with CAS's to no particular table element. The intent is to support highly scalable counters, r/w locks, and other structures where the updates are associative, loss-free (no-brainer), and otherwise happen at such a high volume that the cache contention for CAS'ing a single word is unacceptable.

Since

1.5

Author

Cliff Click

Definition at line 19 of file ConcurrentAutoTable.java.

Member Function Documentation

add()

void com.cliffc.aa.util.ConcurrentAutoTable.add

(

long

x

)

Add the given value to current counter value.

Concurrent updates will not be lost, but addAndGet or getAndAdd are not implemented because the total counter value (i.e., get) is not atomically updated. Updates are striped across an array of counters to avoid cache contention and has been tested with performance scaling linearly up to 768 CPUs.

Definition at line 30 of file ConcurrentAutoTable.java.

{ add_if(  x); }

References com.cliffc.aa.util.ConcurrentAutoTable.add_if().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

add_if()

long com.cliffc.aa.util.ConcurrentAutoTable.add_if ( long  x )

private

Definition at line 82 of file ConcurrentAutoTable.java.

{ return _cat.add_if(x,hash(),this); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, com.cliffc.aa.util.ConcurrentAutoTable.CAT.add_if(), and com.cliffc.aa.util.ConcurrentAutoTable.hash().

Referenced by com.cliffc.aa.util.ConcurrentAutoTable.add(), com.cliffc.aa.util.ConcurrentAutoTable.decrement(), and com.cliffc.aa.util.ConcurrentAutoTable.increment().

Here is the call graph for this function:

Here is the caller graph for this function:

CAS_cat()

boolean com.cliffc.aa.util.ConcurrentAutoTable.CAS_cat ( CAT  oldcat, CAT  newcat  )

private

Definition at line 88 of file ConcurrentAutoTable.java.

{ return _catUpdater.compareAndSet(this,oldcat,newcat); }

References com.cliffc.aa.util.ConcurrentAutoTable._catUpdater.

Referenced by com.cliffc.aa.util.ConcurrentAutoTable.CAT.add_if(), and com.cliffc.aa.util.ConcurrentAutoTable.set().

Here is the caller graph for this function:

decrement()

void com.cliffc.aa.util.ConcurrentAutoTable.decrement

(

)

add with -1

Definition at line 32 of file ConcurrentAutoTable.java.

{ add_if(-1L); }

References com.cliffc.aa.util.ConcurrentAutoTable.add_if().

Here is the call graph for this function:

estimate_get()

long com.cliffc.aa.util.ConcurrentAutoTable.estimate_get

(

)

A cheaper get.

Updated only once/millisecond, but as fast as a simple load instruction when not updating.

Definition at line 60 of file ConcurrentAutoTable.java.

{ return _cat.estimate_sum(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.estimate_sum().

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.tableFull(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.tableFull().

Here is the call graph for this function:

Here is the caller graph for this function:

get()

long com.cliffc.aa.util.ConcurrentAutoTable.get

(

)

Current value of the counter.

Since other threads are updating furiously the value is only approximate, but it includes all counts made by the current thread. Requires a pass over the internally striped counters.

Definition at line 50 of file ConcurrentAutoTable.java.

{ return      _cat.sum(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.sum().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.reprobes(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.reprobes(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.size(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.size(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.slots(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.slots().

Here is the call graph for this function:

Here is the caller graph for this function:

hash()

static int com.cliffc.aa.util.ConcurrentAutoTable.hash ( )

staticprivate

Definition at line 91 of file ConcurrentAutoTable.java.

                            {
    //int h = (int)Thread.currentThread().getId();
    int h = System.identityHashCode(Thread.currentThread());
    return h<<3;                // Pad out cache lines.  The goal is to avoid cache-line contention
  }

Referenced by com.cliffc.aa.util.ConcurrentAutoTable.add_if(), and com.cliffc.aa.util.ConcurrentAutoTable.CAT.add_if().

Here is the caller graph for this function:

increment()

void com.cliffc.aa.util.ConcurrentAutoTable.increment

(

)

add with +1

Definition at line 34 of file ConcurrentAutoTable.java.

{ add_if( 1L); }

References com.cliffc.aa.util.ConcurrentAutoTable.add_if().

Here is the call graph for this function:

internal_size()

int com.cliffc.aa.util.ConcurrentAutoTable.internal_size

(

)

Return the internal counter striping factor.

Useful for diagnosing performance problems.

Definition at line 77 of file ConcurrentAutoTable.java.

{ return _cat._t.length; }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT._t.

intValue()

int com.cliffc.aa.util.ConcurrentAutoTable.intValue

(

)

Same as get, included for completeness.

Definition at line 52 of file ConcurrentAutoTable.java.

{ return (int)_cat.sum(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.sum().

Here is the call graph for this function:

longValue()

long com.cliffc.aa.util.ConcurrentAutoTable.longValue

(

)

Same as get, included for completeness.

Definition at line 54 of file ConcurrentAutoTable.java.

{ return      _cat.sum(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.sum().

Here is the call graph for this function:

print()

void com.cliffc.aa.util.ConcurrentAutoTable.print

(

)

A more verbose print than toString, showing internal structure.

Useful for debugging.

Definition at line 71 of file ConcurrentAutoTable.java.

{ _cat.print(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.print().

Here is the call graph for this function:

set()

void com.cliffc.aa.util.ConcurrentAutoTable.set

(

long

x

)

Atomically set the sum of the striped counters to specified value.

Rather more expensive than a simple store, in order to remain atomic.

Definition at line 39 of file ConcurrentAutoTable.java.

                            { 
    CAT newcat = new CAT(null,4,x);
    // Spin until CAS works
    while( !CAS_cat(_cat,newcat) ) {/*empty*/}
  }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAS_cat().

Here is the call graph for this function:

toString()

String com.cliffc.aa.util.ConcurrentAutoTable.toString

(

)

Return the counter's.

long 

value converted to a string.

Definition at line 65 of file ConcurrentAutoTable.java.

{ return _cat.toString(); }

References com.cliffc.aa.util.ConcurrentAutoTable._cat, and com.cliffc.aa.util.ConcurrentAutoTable.CAT.toString().

Here is the call graph for this function:

Member Data Documentation

_cat

volatile CAT com.cliffc.aa.util.ConcurrentAutoTable._cat = new CAT(null,16,0L)

private

Definition at line 85 of file ConcurrentAutoTable.java.

Referenced by com.cliffc.aa.util.ConcurrentAutoTable.add_if(), com.cliffc.aa.util.ConcurrentAutoTable.CAT.add_if(), com.cliffc.aa.util.ConcurrentAutoTable.estimate_get(), com.cliffc.aa.util.ConcurrentAutoTable.get(), com.cliffc.aa.util.ConcurrentAutoTable.internal_size(), com.cliffc.aa.util.ConcurrentAutoTable.intValue(), com.cliffc.aa.util.ConcurrentAutoTable.longValue(), com.cliffc.aa.util.ConcurrentAutoTable.print(), com.cliffc.aa.util.ConcurrentAutoTable.set(), and com.cliffc.aa.util.ConcurrentAutoTable.toString().

_catUpdater

AtomicReferenceFieldUpdater<ConcurrentAutoTable,CAT> com.cliffc.aa.util.ConcurrentAutoTable._catUpdater

staticprivate

Initial value:

=
    AtomicReferenceFieldUpdater.newUpdater(ConcurrentAutoTable.class,CAT.class, "_cat")

Definition at line 86 of file ConcurrentAutoTable.java.

Referenced by com.cliffc.aa.util.ConcurrentAutoTable.CAS_cat().

---

The documentation for this class was generated from the following file:

• ConcurrentAutoTable.java