[concurrency-interest] Looking for a data struture

Michael Kuhlmann concurrency at kuli.org
Mon Dec 22 12:31:27 EST 2014

Am 22.12.2014 17:10, schrieb Luke Sandberg:
> RE: AtomicReferenceArray.  If i had a strict bound on the number of
> items, i would just allocate it to be that large and use an atomic int
> (getAndIncrement()) to find the next available slot and then remove
> would just be to assign the slot to null.  Iteration would have to read
> a potentially large number of slots, but iterating an array should be
> sufficiently fast that you wouldn't really notice.

What about this solution:

Your data structure has four fields:
a) The (atomic) array
b) The AtomicInteger as the counter for the next free slot
c) A possible replacement array
d) a CountDownLatch for synchronizing the enlargement of the array

Usual adds just increment b) until the length of a) is reached. In that 
case, the array has to be resized. For that, all adding threads that 
reach a)'s limit have to agree which one is resizing the array; it could 
be the one where b).getAndIncrement() is exactly a).length(), or the one 
who's able to compareAndSet a CountDownLatch of size 1 into null-d). The 
other writing threads have to wait on d) until the array is reized.

The resizing algorithm then creates a new, larger array, fills it up the 
the size of the old array with a marker value, and puts it into c). The 
it copies all values from a) to c) by setting all slots of a) to the 
mareker value via getAndSet(), and setting the taken value with a normal 
volatile write into the same position of c). When it's finished, it 
stores the replacement array c) into a), nullifies c) and d), and fires 
d) to wake up other possibly waiting threads that want to add a new value.

When a value if read from a slot, is has to be compared whether it's the 
marker value. In that case, the replacement array will be used from c) 
(if it's null, the resizing process has just finished, so start from 
new), and its value is read. If this is still the marker value, then the 
resizing thread is just copying this exact value, which is just a matter 
of nanoseconds; in that case, just start the get() method again. 
Otherwise, take the value from the replacement array.

Writes have to act in a comparable way; values mustn't just set in the 
array, call compareAndSet() with the expected old value instead to 
catch-up a possible marker state. In that case, write into the 
replacement array c) similar to the get() algorithm.

With this, you'll have a random-access data structure with only very 
little overhead (gets only have to do identity comparisons to the marker 
value, and writes must be compareAndSets). It is lock-free except for 
the resizing algorithm, which can be rather exceptional of you set the 
initial array size large enough.


More information about the Concurrency-interest mailing list