Есть некий проект, в котором узким местом является работа в set'ом (я сам офигел- но это факт, подтверждённый инструментацией).
Когда-то давно в качестве реализации был выбран THashSet из trove4j.
Сейчас- похоже, что проблемным стало вот что- иногда некоторые set'ы резко вырастают - до 6М элементов, потом размер проседает до 300К. А вставка в сет идёт достаточно хитрым путём - gnu.trove.impl.hash.TObjectHash#insertKeyRehash

Смотрю на trove4j - он не обновляется с 2012го года. А JDK за это время как раз хорошо оптимизировали.
Как кто считает- стоит ли попробовать перести на стандартный HashSet? Там, конечно, внутри тот ещё оверинжиниринг (Map'ы)...
Или может гугл что хорошее написал?

--<br /> Алексей.<br />

Leonid KudryavtsevА написать синтетический тест для случая "set'ы резко вырастают - до 6М элементов, потом размер проседает до 300К" ? Все же IMHO, паттерн использования весьма специфический.

Посмотрел на исходники, они зачем то ищут именно до free slots, параллельно просматривая removed. Если понимать, что делаешь, вполне можно создать свой класс и переопределить protected int insertKey(T key). Но тут я не советчик, знания об алгоритмах у меня не достаточно хорошее, что бы понять, почему у них именно такая реализация. IMHO

Ага. Более того- это set WeakReference. Т.е. мысль- либо уйти на WeakHashMap, либо , действительно, переписать insertKey, который будет считать "опустевшие" ссылки пустыми. Думаю пока, пробую.

Leonid KudryavtsevТам в исходном коде, проверка для выхода из цикла НЕ на любой свободный элемент в set'е ("free slots", "removed"), а именно на "free slots".

Т.ч. если сет сначала разросся, а потом сжался и 99.99% элементов стало "removed", то наверное может быть замедление. Но почему так сделано - не понятно. Наверное были свои причины. Разбираться желания нет. Пусть автор топика разбирается )))

Разобрался.
Там несложно.
Когда мы вставляем элемент V1, потом V2 с хэшсетов, приводящим первоначально в тот же элемент (совпал hash % _set.length) - то элемент будет вставлен по индексу +probe.
Если мы после этого удалим V1, а потом вставим ещё раз V2, то мы сразу наткнёмся на REMOVED элемент.
Если мы вставим его сразу- то V2 будет в set'е дважды.
Поэтому надо запомнить позицию, но добрести до FREE элемента (либо до equals).

Фигня в том, что при частой удалении/вставке мы бродим по set'у в поисках свободного угла ОЧЕНЬ долго.
Авторы кода, который я оптимизирую, решили съэкономить память (не использовав WeakHashMap) и, как результат, теперь это создаёт проблемы производительности.

Правда истинная причина совершенно в другом месте, но тот код я пока не в состоянии исправить- приходится костылять