[concurrency-interest] ReadMostlyVector ListIterator bug

Martin Buchholz martinrb at google.com
Mon Aug 13 15:11:07 EDT 2012


It's difficult.

SequenceLock is more problematic to use correctly and usefully than was
expected.
http://safari.ece.cmu.edu/MSPC2012/papers/p12-boehm.pdf

The List interface is quite concurrency-hostile.

Compare the efforts taken in latest ArrayBlockingQueue to get iterators
right, which required heroic action, despite the apparent simplicity of
getting it right when locks are held on access.  ABQ tries to keep track of
whether an iterator is currently active, and in principle ReadMostlyVector
could do something similar.

Martin

On Mon, Aug 13, 2012 at 7:00 AM, Stanimir Simeonoff <stanimir at riflexo.com>wrote:

>
>
> On Mon, Aug 13, 2012 at 4:24 PM, Doug Lea <dl at cs.oswego.edu> wrote:
>
>> On 08/13/12 08:07, Stanimir Simeonoff wrote:
>>
>>  Actually, I wanted to see how to implement an iterator over a sequence
>>> lock data
>>> structure. If elements are removed from the middle and then added at the
>>> end
>>> (concurrently) it looks some elements may be skipped. So unless copying
>>> the
>>> entire structure under exclusive lock or a retry loop it won't be a
>>> replacement
>>> for COWArrayList.
>>>
>>> Is my reasoning correct?
>>>
>>
>> Yes. You can imagine the results more simply by just contemplating
>> using index-by-index access instead of iterators: Changes spanning
>> more than one position may lead to either skips or revisits.
>>
>> (More generally: Arrays are great for isolated parallelism;
>> but lousy for shared concurrency. Mixtures are challenging.)
>>
>>
> Exactly what I thought.
> Now I wonder if a mixture between COW and MostlyRead would make sense:
> Adding at the tail of an array backed list is amortized O(1), so it's ok.
> However, inserting/deletion in the middle is O(n) - creating a new Object[]
> is also O(n) [+allocation cost and GC of course]. Hence if modifying the
> List in the middle  - a COW operation replacing the entire Object[] but
> when adding/removing at the tail, it's a cheap one under lock.  Setting an
> arbitrary element is also O(1).
>
> The iterators never skip or revisit elements and they operate on the
> Object[] when they have been created. I think this offers somehow better
> consistency w/o any significant penalties, e.g iterating linked lists.
>
> Thanks again
> Stanimir
>
> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/**listinfo/concurrency-interest<http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>>
>
>
> _______________________________________________
> 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/20120813/858c400b/attachment.html>


More information about the Concurrency-interest mailing list