java - sheet - ¿Por qué no es LinkedList.Clear() O(1)

insertion sort complexity

Question

Estaba asumiendo que LinkedList.Clear () era O (1) en un proyecto en el que estoy trabajando, ya que utilicé una LinkedList para vaciar una BlockingQueue en mi consumidor que necesita un alto rendimiento, eliminar y reutilizar la LinkedList posteriormente.

Resulta que la suposición era incorrecta, ya que el código (OpenJDK) hace esto:

 Entry<E> e = header.next;
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}

Esto fue un poco sorprendente, ¿hay alguna buena razón para que LinkedList.Clear no pueda simplemente "olvidar" su header.next y header.previous miembro?

Answer 1

El código fuente en la versión que estoy viendo (compilación 1.7.0-ea-b84) en Eclipse tiene este comentario sobre ellos:

// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator

Eso deja bastante claro por qué lo están haciendo, aunque estoy de acuerdo en que es un poco alarmante que convierta una operación O (1) en O (n).

Answer 2

Si bien no estoy muy impresionado con la razón de la optimización de GC, en su caso es claramente contraproducente.

Limpiando y reutilizando el LinkedList

Eso no suena bien. ¿Por qué no crear un nuevo objeto LinkedList?

Answer 3

Ya que parece que no puedo comentar las respuestas (?): Los indicadores entre el siguiente y el anterior no importan. Dado que no se podrá acceder a ninguna de las entradas internas desde ninguna raíz GC, se recopilará toda la estructura. Si Java hubiera utilizado un recolector de recuento de recuentos, estaríamos atascados con el problema del ciclo.

Las respuestas correctas es lo que señala John Skeet.