[concurrency-interest] Looking for a data struture
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