ArrayList.subList

[Doug Lea]

On 07/28/11 18:53, Mike Duigou wrote:
> I had a similar issue with Set recently. The problem is that structural
> changes in sub-sub-lists aren't correctly reflected in the sub-list parents
> if the sub-sub-lists are disconnected from the parent. The chain back to to
> the parent through all intermediate sub-lists is used to update list bounds.
> Seems weird to me but that's nonetheless how the original implementors made
> it work.

Thanks.  I hadn't noticed that the parenthesized "i.e., this list"
in the List specs 
(http://download.oracle.com/javase/7/docs/api/java/util/List.html#subList%28int,%20int%29 
-- pasted below)
overly constrains the interpretation of "backing list",
which would otherwise naturally refer to the ArrayList. This
would be challenging to fix in ArrayList while retaining
compatibility, even though it is sensibly ignored in
other List implementations.


The semantics of the list returned by this method become undefined if the
backing list (i.e., this list) is structurally modified in any way other than
via the returned list. (Structural modifications are those that change the size
of this list, or otherwise perturb it in such a fashion that iterations in
progress may yield incorrect results.)


> On Jul 28 2011, at 13:40 , Doug Lea wrote:
>
>>
>> While puzzling over why one of the demo videos on ForkJoin out there
>> required surprisingly high sequential thresholds, I noticed that
>> ArrayList.subList creates lists with per-access overhead proportional to
>> the sublist depth. Which is not at all conducive to recursive use. Does
>> anyone know any reason why this was done? (No one who I thought would know
>> the answer does.) It is easy to keep the overhead flat (we do so in
>> CopyOnWriteArrayList and the new jsr166e.extra ReadMostlyVector.) If no one
>> knows a reason not to, I'll put together a patch. (I have a vague deja vu
>> feeling that I might have done this once before years ago...)
>>
>> -Doug
>>
>>
>>
>>
>>
>
>