clear()-Implikation in Java's LinkedList

Question

Ich fürchte, das ist eine wirklich dumme Frage, aber ich sage es trotzdem:

Warum macht sich die clear-Methode in Javas Standard-Implementierung von LinkedList die Mühe, die Liste zu durchlaufen und alle Knoten auszuhängen? Warum nicht einfach den Header abkoppeln und den Rest der Liste verbunden lassen - der GC wird ihn doch sowieso bekommen, oder?

Hier ist die Methode:

/**
 * 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++;
}

Warum zu Fuß gehen? Warum nicht einfach zu header.next = header.previous = header; ?

Das Beste, was ich mir vorstellen kann, ist, dass es dem GC hilft...? Dieser Link http://java.sun.com/docs/books/performance/1st_edition/html/JPAppGC.fm.html#997442 legt das irgendwie nahe.

TIA...

Answer 1

Ihre Methode stellt sicher, dass auch dann, wenn andere Codes noch Verweise auf bestimmte Knoten enthalten, die anderen Knoten GC'ed werden.

Andernfalls würde schon ein einziger externer Verweis auf einen der Knoten verhindern, dass die gesamte Kette erfasst wird.

Außerdem können andere Vorgänge in der Liste gleichzeitig ablaufen (z. B. Ansichten durch subList() o Collections.unmodifiableList() , Iteratoren), und dies stellt sicher, dass diese Dinge die Liste sofort als "leer" wahrnehmen.

Answer 2

IIRC, war dies eine Änderung, die in JDK6 vorgenommen wurde, um die Leistung bestimmter (generativer) GC-Algorithmen zu verbessern. Oft wird die List selbst und ältere Knoten werden einer älteren Generation angehören als einige der anderen Knoten. Die jüngeren Generationen werden häufiger gesammelt, was dazu führt, dass junge Knoten kopiert werden, bevor entdeckt wird, dass alle Knoten Müll sind.

Es handelt sich also um eine kleine Leistungsoptimierung. Die Optimierung der Speicherleistung ist insofern etwas seltsam, als es oft nicht der Code ist, der das Problem verursacht, sondern der die zusätzliche Ausführungszeit benötigt.

Answer 3

Ich habe in meinem Blog zur Spieleentwicklung gerade über genau dieses Thema spekuliert. Danke für die Antwort. Ich würde sagen, dass die Exposition von Knoten eine fragwürdige Design-Erlaubnis war. Es ist auch skizzenhaft, dass alternative Ansichten auf der Liste (Iteratoren und so) würde auf Knoten Unlinking zu fail-fast verlassen. Anstatt sich auf dieses Nebeneffektverhalten zu verlassen, sollten die Unteransichten der Liste die Anzahl der Änderungen überprüfen. Auf jeden Fall verstehe ich, warum sie jetzt daran festhalten.

Answer 4

Der Quellcode von java.util.LinkedList unter http://developer.classpath.org/doc/java/util/LinkedList-source.html schlägt vor, dass Sie das erste und das letzte Element einfach auf Null setzen können.

Wenn Sie dazu neigen, übervorsichtig zu sein, können Sie das Ganze natürlich auch in einer Schleife durchlaufen. Ich persönlich denke, dass dies eine sehr teure Aufgabe sein kann, wenn Ihre Liste mehrere tausend Elemente enthält.