27.02.2020 17:40
olegchir 32 14000 Источник
Мы привыкли, что стандартные коллекции в JDK сделаны достаточно хорошо и ведут себя интуитивно-понятно. Но так ли это на самом деле? Вчера Роман Елизаров elizarov опубликовал в твиттере новость о новом интересном косяке.

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



Роман обнаружил проблему, когда отлаживал кусок кода, который по удивительной причине работал слишком медленно. Он запустил его во встроенном в IntelliJ IDEA профилировщике и мгновенно увидел на флеймграфе, что все время тратится внутри метода AbstractSet.removeAll на вызов list.contains (ссылка на точное место в коде).

Чтобы разобраться, что происходит, рассмотрим немного другой пример. Ранее 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, то пути назад нет.

Или есть?

На твит Романа Елизарова мгновенно набежали люди, и Жека Козлов нашел соответствующий баг, выставленный на JDK 15 с исполнителем — Стюартом Марксом.

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


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

Выводы


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

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


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

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


Можно не только смотреть записи со старого JPoint, но и вживую прийти на новый, который пройдет в 2020 году в Москве. Программа все еще формируется, и то, что сейчас уже есть, можно посмотреть по ссылке.

Комментарии (32)