Почему не LinkedList.Clear() O (1)

Я предполагал, что LinkedList.Clear() был O (1) в проекте, над которым я работаю, поскольку я использовал LinkedList для слива BlockingQueue у моего потребителя, которому требуется высокая пропускная способность, очистка и повторное использование LinkedList впоследствии.

Оказывается, это предположение было неправильным, поскольку код (OpenJDK) делает это:

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

Это было немного удивительно, есть ли веская причина LinkedList.Clear не может просто "забыть" свой заголовок .next и header.previous?

Ответ 1

Исходный код в версии, которую я смотрю (build 1.7.0-ea-b84) в Eclipse, содержит следующий комментарий:

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

Это делает достаточно понятным, почему они это делают, хотя я согласен с этим немного тревожно, что он превращает операцию O (1) в O (n).

Ответ 2

хотя меня не очень впечатлила причина оптимизации GC - это явно отразилось на вашем случае -

очистка и повторное использование LinkedList

что звучит не так. почему бы просто не создать новый объект LinkedList?

Ответ 3

Так как я не могу прокомментировать ответы (?): указатели между следующим и предыдущим не имеют значения. Поскольку ни одна из внутренних записей не будет доступна из любого корня GC, будет собрана вся структура. Если бы java использовал сборщик refcounting, мы бы столкнулись с проблемой цикла.

Правильные ответы - это то, что отмечает Джон Скит.