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<[email protected]> 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<[email protected]> 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
------- LinkedList.java -------
*** /tmp/geta29341 Fri Aug 28 05:04:16 2009
--- /tmp/getb29341 Fri Aug 28 05:04:16 2009
***************
*** 131,139 ****
* @throws NoSuchElementException if this list is empty.
*/
public E removeFirst() {
! E first = header.next.element;
! remove(header.next);
! return first;
}
/**
--- 131,137 ----
* @throws NoSuchElementException if this list is empty.
*/
public E removeFirst() {
! return remove(header.next);
}
/**
***************
*** 143,151 ****
* @throws NoSuchElementException if this list is empty.
*/
public E removeLast() {
! E last = header.previous.element;
! remove(header.previous);
! return last;
}
/**
--- 141,147 ----
* @throws NoSuchElementException if this list is empty.
*/
public E removeLast() {
! return remove(header.previous);
}
/**
***************
*** 289,297 ****
* Removes all of the elements from this list.
*/
public void clear() {
! modCount++;
header.next = header.previous = header;
! size = 0;
}
--- 285,300 ----
* Removes all of the elements from this list.
*/
public void clear() {
! Entry<E> e = header.next;
! while (e != header) {
! Entry<E> next = e.next;
! e.next = e.previous = null;
! e.element = null;
! e = next;
! }
header.next = header.previous = header;
! size = 0;
! modCount++;
}
***************
*** 354,362 ****
* range (<tt>index < 0 || index >= size()</tt>).
*/
public E remove(int index) {
! Entry<E> e = entry(index);
! remove(e);
! return e.element;
}
/**
--- 357,363 ----
* range (<tt>index < 0 || index >= size()</tt>).
*/
public E remove(int index) {
! return remove(entry(index));
}
/**
***************
*** 582,587 ****
--- 583,589 ----
public void remove() {
checkForComodification();
+ Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) {
***************
*** 588,594 ****
throw new IllegalStateException();
}
if (next==lastReturned)
! next = lastReturned.next;
else
nextIndex--;
lastReturned = header;
--- 590,596 ----
throw new IllegalStateException();
}
if (next==lastReturned)
! next = lastNext;
else
nextIndex--;
lastReturned = header;
***************
*** 637,650 ****
return newEntry;
}
! private void remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
e.previous.next = e.next;
e.next.previous = e.previous;
size--;
modCount++;
}
/**
--- 639,656 ----
return newEntry;
}
! private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
+ E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
+ e.next = e.previous = null;
+ e.element = null;
size--;
modCount++;
+ return result;
}
/**
