Ужасы Set.removeAll

Мы привыкли, что стандартные коллекции в 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 мая в Москве. Программа все еще формируется, и то, что сейчас уже есть, можно посмотреть по ссылке.