java.util.LinkedList clear() improvement

[Martin Buchholz]

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
>>>
>>
>>
>>
>