java.util.LinkedList clear() improvement

[Christopher Hegarty - Sun Microsystems Ireland]

Hi Martin,

I put the diffs in the public comments of 4863813, but if you can't wait 
for bug.sun.com to catch up the diffs are attached.

-Chris.

On 27/08/2009 18:24, Martin Buchholz wrote:
> Very interesting - thanks for the pointer to the bug id.
> Chris, could you update the bug report to contain a (public) diff
> of the actual changes that were made?
> The bug report does not mention clear().
> 
> Curiously, the jsr166 team has been working on fixing the same
> kinds of issues in java.util.concurrent queue implementations recently.
> At least one clear() implementation was intentionally
> changed from O(1) to O(N) for correctness.
> 
> For LinkedList.clear(), I think we might be able to get an optimal
> hybrid solution,
> that would unlink just the 2 immediate neighbors of the header node (if any),
> remaining O(1), but also being generational-GC-friendly (e.g. if an
> existing Node
> was tenured - avoid links from a dead tenured Node to a live Node).
> 
> Martin
> 
> On Thu, Aug 27, 2009 at 09:01, Christopher Hegarty -Sun Microsystems
> Ireland<Christopher.Hegarty at sun.com> wrote:
>> I think this change was made to address:
>>
>> 4863813: Stressing single LinkedList from multiple threads causes heapspace
>> to completely
>>
>>  http://bugs.sun.com/view_bug.do?bug_id=4863813
>>
>> -Chris.
>>
>> Guy Korland wrote:
>>> How does it help the GC?
>>> As I understand the M&S algorithm, there's no real advantages in doing so.
>>>
>>> In fact in many places to "null" references is considered to be an
>>> anti pattern in java.
>>>
>>> Guy
>>>
>>> On Thu, Aug 27, 2009 at 4:37 PM, Tom Hawtin<Thomas.Hawtin at sun.com> wrote:
>>>> Guy Korland wrote:
>>>>
>>>>> It seems like linkedList.clear() can be easily fixed to O(1) instead of
>>>>> O(n).
>>>> The code is like that on purpose(!). It was done to help GC, in mustang
>>>> IIRC. There really isn't a problem with clear() being O(n) - it's going
>>>> to
>>>> take at least O(n) to populate it, and in reality *many* times more
>>>> cycles.
>>>>
>>>> Tom
>>>>
>>>
>>>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: LinkedList4863813.diffs
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090828/1d3ccd39/LinkedList4863813.diffs>