[concurrency-interest] Looking for a data struture

Benedict Elliott Smith sub at laerad.com
Wed Dec 31 07:51:54 EST 2014


I have a simple wait-free collection supporting insertion, removal and
arbitrary-order traversal here
<https://github.com/belliottsmith/bes-utils/blob/master/src/bes/concurrent/collections/SimpleCollection.java>,
and a lock-free insert, wait-free remove, in-order traversible collection
here
<https://github.com/belliottsmith/bes-utils/blob/master/src/bes/concurrent/collections/SimpleWaitFreeCollection.java>
(on
which the former is built), and have attempted to blog about the latter here
<http://belliottsmith.com/eventual-consistency-concurrent-data-structures/>.

These are doubly-linked lists, much like CLDeque, but the implementation is
a little different, resulting in  wait-free worst-case constant time (and
CAS-free) deletion, but with the possibility of some garbage accumulation
under high contention. Since contention necessarily drops as the list
grows, the amount of garbage should be pretty limited, and is limited to
the nodes themselves, not the data. The lack of CAS operation means
uncontended (i.e. non-adjacent) deletes should be appreciably cheaper,
though I haven't benchmarked it extensively since I mostly use it because
it is easy to reason about.

On 31 December 2014 at 01:44, Martin Buchholz <martinrb at google.com> wrote:

>
>
> On Tue, Dec 30, 2014 at 4:22 PM, Luke Sandberg <lukeisandberg at gmail.com>
> wrote:
>
>> A doubly linked list that exposes the nodes would have that behavior.
>>
> And ConcurrentLinkedDeque is essentially a lock-free doubly linked list
> that supports all operations except interior insertion, which we don't know
> how to (and don't need to) implement.
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141231/874cccd1/attachment-0001.html>


More information about the Concurrency-interest mailing list