Мы привыкли, что стандартные коллекции в JDK сделаны достаточно хорошо и ведут себя интуитивно-понятно. Но так ли это на самом деле? Вчера Роман Елизаров elizarov опубликовал в твиттере новость о новом интересном косяке, найденном на SO.
Держитесь покрепче: Set.removeAll(list) в определенных случаях может работать за O(N²). Как же так?
Jon Skeet недавно опубликовал пост «There's a hole in my abstraction, dear Liza, dear Liza», в котором он рассматривает следующий интересный случай.
Допустим, у нас есть HashSet, из которого мы собираемся что-то удалить. Допустим, мы удаляем из одной коллекции A элементы другой коллекции B. Часто так бывает, что многие элементы из B просто не существуют в A. Разберем специальный случай, когда A и B вообще не пересекаются — то есть, делать ничего не нужно.
Напишем простую программку, в которой размеры наших коллекций задаются из командной строки. Чтобы эти множества точно не пересекались, одну из них заполним только положительными, а другую — только отрицательными числами. Потом удалим из первой коллекции все элементы второй и измерим прошедшее время с помощью System.currentTimeMillis(). Это не самый лучший в мире способ посчитать промежуток времени, но он дает возможность скопипастить код прямо из Хабра в Идею и избавляет нас от необходимости настраивать новый проект Maven для JMH.
import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
Очень простой код, который можно написать, не приходя в сознание. Давайте теперь прогоним его с разными параметрами. Вначале попробуем набор из 100 элементов, из которых нужно выбросить 100:
$ java Test 100 100
Time taken: 1ms
Пока что все достаточно быстро, но что будет, если увеличить числа?
java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
Как вам такое: теперь мы ждем три минуты. Интуитивно кажется, что время обработки меньшей коллекции (300 000 элементов во втором случае) должно быть меньше, чем при обработке большей коллекции (миллион элементов в первом случае). Тут же все наоборот. К такому нас жизнь не готовила, верно?
Теперь секрет фокуса.
На самом деле, он описан в открытом виде в соответствующем JavaDoc:
Код реализации устанавливает, что меньше: set или коллекция. Это делается с помощью метода
sizeна каждом из них. Если в set элементов меньше, то производится итерация по set-у, и на каждой итерации проверяется, находится ли текущий элемент в коллекции. Если да, то элемент удаляется из set-а с помощью методаremoveитератора. Если же окажется, что коллекция меньше по количеству элементов, тогда нужно будет обойти уже коллекцию, удаляя из set-а все такие элементы с помощью методаremoveиз set-а.
На практике это значит, что при вызове source.removeAll(removals):
- Если коллекция
removalsменьше, чемsource, то вызывается методremoveвHashSet, и это довольно быстро; - Если коллекция
removalsбольше или равна по размеру, чемsource, то вызывается методremovals.contains, который очень медленно работает дляArrayList.
В JDK 8 за это отвечает примерно такой кусок кода:
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
Похоже, в JDK выбран довольно убогий способ справиться с задачей, но поскольку он уже описан в JavaDoc, то пути назад нет.
Или есть?
Роман Елизаров опубликовал этот пост в Twitter с сообщением, что сам обнаружил проблему, когда отлаживал кусок кода, который по удивительной причине работал слишком медленно. Он запустил его во встроенном в IntelliJ IDEA профилировщике и мгновенно увидел на флеймграфе, что все время тратится внутри метода AbstractSet.removeAll на вызов list.contains (ссылка на точное место в коде).
Мгновенно в этот твит набежали люди, и Жека Козлов нашел соответствующий баг, выставленный на JDK 15 с исполнителем — Стюартом Марксом.
А следом за этим в тред ворвался и сам Стюарт Маркс и подтвердил, что действительно занимается этой проблемой:
Так что свет в конце тоннеля есть. Если вы обновляетесь до свежих версий Java, конечно.
Выводы
Выводы из этой истории такие: есть проблема, о которой стоит знать. Проблему уже чинят, но починят только для счастливых пользователей свежей Java, и особо надеяться на это не стоит.
В целом, когда вы пытаетесь в коллекциях в Java хранить много данных, у вас могут случаться разные неинтуитивные проблемы, к которым надо быть готовым.
Итак, детки, сегодня мы выучили что-то новое!
В качестве продолжения банкета, рекомендую посмотреть какие-нибудь доклады Романа Елизарова, который помог вытащить на свет божий этот баг. К самому багу эти доклады никакого отношения, конечно, не имеют, но там есть куча разной другой жести:
- «Корутины в Kotlin» (JPoint 2018)
- «Kotlin: Асинхронное программирование с корутинами (часть 1)» (JUG 2017)
- «Kotlin: Асинхронное программирование с корутинами (часть 2)» (JUG 2017)
- «Многопоточное программирование — теория и практика» (JPoint 2016)
- «Жди своего счастья без блокировки!» (JPoint 2016)
- «Почему GC съедает все моё CPU?» (Joker 2014)
- «Теоретический минимум для понимания Java Memory Model» (JPoint 2014)
- «Факты и заблуждения о Java-сериализации» (Joker 2013)
- «Миллионы котировок в секунду на чистой Java» (JUG 2013)
Можно не только смотреть записи со старого JPoint, но и вживую прийти на новый, который пройдет 15-16 мая в Москве. Программа все еще формируется, и то, что сейчас уже есть, можно посмотреть по ссылке.
Автор: olegchir
