Ужасы Set.removeAll

Мы привыкли, что стандартные коллекции в JDK сделаны достаточно хорошо и ведут себя интуитивно-понятно. Но так ли это на самом деле? Вчера Роман Елизаров elizarov ^[1] опубликовал в твиттере ^[2] новость о новом интересном косяке, найденном ^[3] на SO.

Держитесь покрепче: Set.removeAll(list) в определенных случаях может работать за O(N²). Как же так?

Jon Skeet недавно опубликовал пост «There's a hole in my abstraction, dear Liza, dear Liza» ^[3], в котором он рассматривает следующий интересный случай.

Допустим, у нас есть 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 ^[4]:

Код реализации устанавливает, что меньше: 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 (ссылка на точное место в коде ^[5]).

Мгновенно в этот твит набежали люди, и Жека Козлов ^[6] нашел соответствующий баг ^[7], выставленный на JDK 15 с исполнителем — Стюартом Марксом.

А следом за этим в тред ворвался и сам Стюарт Маркс и подтвердил, что действительно занимается этой проблемой:

Так что свет в конце тоннеля есть. Если вы обновляетесь до свежих версий Java, конечно.

Выводы

Выводы из этой истории такие: есть проблема, о которой стоит знать. Проблему уже чинят, но починят только для счастливых пользователей свежей Java, и особо надеяться на это не стоит.

В целом, когда вы пытаетесь в коллекциях в Java хранить много данных, у вас могут случаться разные неинтуитивные проблемы, к которым надо быть готовым.

Итак, детки, сегодня мы выучили что-то новое!

В качестве продолжения банкета, рекомендую посмотреть какие-нибудь доклады Романа Елизарова, который помог вытащить на свет божий этот баг. К самому багу эти доклады никакого отношения, конечно, не имеют, но там есть куча разной другой жести:

• «Корутины в Kotlin» ^[9] (JPoint 2018)
• «Kotlin: Асинхронное программирование с корутинами (часть 1)» ^[10] (JUG 2017)
• «Kotlin: Асинхронное программирование с корутинами (часть 2)» ^[11] (JUG 2017)
• «Многопоточное программирование — теория и практика» ^[12] (JPoint 2016)
• «Жди своего счастья без блокировки!» ^[13] (JPoint 2016)
• «Почему GC съедает все моё CPU?» ^[14] (Joker 2014)
• «Теоретический минимум для понимания Java Memory Model» (JPoint 2014) ^[15]
• «Факты и заблуждения о Java-сериализации» ^[16] (Joker 2013)
• «Миллионы котировок в секунду на чистой Java» ^[17] (JUG 2013)

Можно не только смотреть записи со старого JPoint, но и вживую прийти на новый, который пройдет 15-16 мая в Москве. Программа все еще формируется, и то, что сейчас уже есть, можно посмотреть по ссылке ^[18].

Автор: olegchir

Источник ^[19]