[concurrency-interest] ReadMostlyVector ListIterator bug

Stanimir Simeonoff stanimir at riflexo.com
Mon Aug 13 10:00:13 EDT 2012


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>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120813/60a47d5f/attachment.html>


More information about the Concurrency-interest mailing list