[concurrency-interest] ReadMostlyVector ListIterator bug
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
>> (concurrently) it looks some elements may be skipped. So unless copying
>> entire structure under exclusive lock or a retry loop it won't be a
>> 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.
Concurrency-interest at cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest