company_banner

Ужасы Set.removeAll

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

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

      –1

      Так, а что не так с свежей java?
      Если мы пишем на kotlin и запускаем на последнем релизе — мы молодцы и можно не переживать?

        +4
        Всё с ней так. Не так здесь с огромной инерцией пользователей. Все боятся несовместимостей в языке, основной фишкой которого является обратная совместимость. Парадоксально, но факт.
          +2
          Все боятся несовместимостей в языке, основной фишкой которого является обратная совместимость

          У многих другое: работает — не трогай. Немногие хотят получить потенциально неприятные и сложноуловимые проблемы в обмен на сомнительные фичи/фиксы. Поэтому тянут, пока последние не перевесят.
            –1

            Как видим, проблемы нашлись где не ожидали.

              +2
              Я про этап, когда уже все или почти все написано. А если так, то на эту проблему уже должны были найти решение или костыль. Если разработка только началась, то конечно имеет смысл брать более-менее свежую версию.
              +4
              За это как раз стоит благодарить авторов библиотек, которые в погоне за странным пересекают границу, за которой заканчиваются гарантии совместимости языка (reflection, unsafe). И сами при этом не сильно заботятся о совместимости между своими версиями, что вносит здоровый пессимизм в вопрос обновления — вроде бы доверяем языку и не против обновиться, но не доверяем библиотекам и поэтому хороним идею.
              0

              Энтерпрайз он такой, да.

              +1
              Вы уже используете 15-ю Java?
                +1

                Пока последний stable 13 — его и используем.

                +2

                У Kotlin своих коллекций нет, используются стандартные. Но если очень хочется, то можно так


                fun <T> MutableSet<T>.fastRemoveAll(collection: Collection<T>): Boolean {
                    var modified = false
                    for (element in collection) {
                        modified = modified or remove(element)
                    }
                    return modified
                }

                Или в просто Java использовать решение


                    source.removeAll(new HashSet<>(removals));
                +4
                Похоже, в JDK выбран довольно убогий способ справиться с задачей

                Все мы любим покритиковать код, который был написан, когда мы ещё ходили под стол пешком. Но вопрос не в этом. Как правильно-то надо было сделать, расскажи нам :-)

                  +2

                  По-хорошему, надо было не делать проверки size() > c.size(), оставив подобные оптимизации в зоне ответственности вызывающего кода.


                  Всё равно у removeAll нет никакой возможности определить, какая именно асимптотика скрывается за c.contains, а значит и оптимизация не имеет никакого смысла.


                  Теперь так поступить уже нельзя (существующий код может рассчитывать на эту оптимизацию), и придётся городить новые костыли эвристики. Например, можно добавить проверку что переданная коллекция является множеством, поскольку у множеств операция contains должна быть "быстрой". Но тут "в пролёте" окажутся мультимножества...

                    +1

                    А какую ветку из исходного кода оставить, если убрать проверку?

                      +2

                      Разумеется. ту где итерация идёт по внешней коллекции.

                        +1

                        Почему?

                          +2

                          Потому что это для неё известна асимптотика. Для другой ветки асимптотика неизвестна.

                            +1

                            Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти. Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции. Она может отличаться. Например, нам передан TreeSet с компаратором.


                            Далее, кто сказал, что известная асимптотика лучше? Например, моя задача требует передавать параметром Guava Multiset. Я знаю, что contains в нём очень быстрый. Мне может интуитивно кажется, что обойти его тоже быстро, даже если там элементы с огромным количеством повторов. По факту же обход будет включать в себя все повторы, и я также получу провал в производительности на ровном месте.

                              +2
                              Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти.

                              Возможно, метода retainAll вообще не должно было быть.


                              Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции.

                              Зато сейчас у removeAll вообще не определена семантика. Возможно, по-настоящему весёлые баги нас ещё ждут...


                              Далее, кто сказал, что известная асимптотика лучше?

                              Я исхожу из того, что стандартная библиотека должна работать предсказуемо.


                              Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.

                                +1
                                Возможно, метода retainAll вообще не должно было быть.

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


                                Зато сейчас у removeAll вообще не определена семантика

                                Это правда. Я лишь хотел показать, что вопрос "как правильно сделать" гораздо менее тривиальный, чем кажется, и мгновенное "разумеется" вовсе не так разумеется. Любое решение будет набором компромиссов.


                                Я исхожу из того, что стандартная библиотека должна работать предсказуемо.

                                Вариант всегда использовать contains целевой коллекции настолько же предсказуем. Ты вот делаешь неявное предположение, что у переданной коллекции iterator.next() быстрый, а это может быть и не так. К примеру, коллекция может быть фильтруемой на лету вьюшкой над большим сетом. Степень предсказуемости абсолютно одинаковая, она в любом случае зависит от устройства переданной коллекции, и с этим ничего не сделаешь.


                                Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.

                                Во-первых, это не нужно, потому что достаточно сделать mySet.removeAll(multiSet.toElementSet()) (подразумевая твою реализацию). Во-вторых, речь о неожиданных перформансных эффектах. Как ты обучишь каждого пользователя не использовать стандартный метод (или использовать его нестандартно) там, где он работает, выдаёт правильный результат и выполняется быстро на небольших тестовых данных? Либо ждать пока обожжётся (что мы, кстати, имеем в обсуждаемом примере), либо ожидать, что каждый пользователь прочитает и запомнит всю документацию от корки до корки (глупо), либо прокачивать статический анализ (вариант хороший, но ненадёжно).

                                +2

                                Кстати, вот реализация retainAll в .NET — HashSet.cs#L496
                                Отличия от Java:


                                1. Этот метод всегда использует компаратор текущей коллекции, а не переданной
                                2. Этот метод делает проверку на совпадение типа коллекции и компаратора. Если совпали — идёт по оптимальному пути (использует чужой Contains). Если не совпали — использует O(N) дополнительной памяти.

                                Мне кажется, что-то более сложное "наворачивать" нет необходимости.

                                  +1

                                  Мы, кстати, обсуждаем реализацию из AbstractSet, а не возможную специализацию в HashSet. Конечно, когда мы больше знаем хотя бы про свой Set, нам будет проще выделить fast-path.

                                    +2

                                    Ну, AbstractSet в .NET просто нет, и, как мне кажется, как раз по причине подобных приколов с производительностью.

                                +1
                                Почему это неизвестна? Реальный тип можно посмотреть, контейнеров в стандартной библиотеке ограниченное количество, для каждой пары (своя / чужая) можно выбрать нужную реализацию. Хоть if-ами. Выглядеть будет страшно (один раз при разработке и профилировании) работать быстро на миллионах машин.
                                  +2

                                  Увы, но контейнер не обязан находиться в стандартной библиотеке. Пользователь может подключить что-то ещё или даже свою реализацию написать.

                                    0
                                    Вот эту бы проблему я JavaDoc-ом решал — честно проинформировал, о том, что будем проверять в переданной коллекции каждый элемент, случайным образом. Передал туда что-то с безумным временем поиска — сам себе злобный буратино. Был бы архитектором — предложил бы ещё один метод сделать, что-то типа removeAllIndexed, который бы после предварительного анализа* строил индекс над списком элементов для удаления. Хоть это и дополнительная память. Зато минус велосипедостроительство в каждом конкретном куске кода.
                                    * предварительный анализ — а выгодно ли вообще для N строить индекс. И влезет ли он в память, если возьмёмся строить.
                                      +2

                                      В итоге получаем нифига не расширяемую систему типов, где ничего нельзя делать.


                                      Если уж так хочется всё усложнить — лучше завести отдельные маркерные интерфейсы "быстрый Itareble", "Collection с быстрым contains", и смотреть уже на них.

                      +1

                      Я не понял, а в чем ужас-то? Работа метода задокументирована. Метод AbstractSet.removeAll() ведет себя as expected. Никаких гарантий по сложности этого метода ни Set, ни AbstractSet, ни HashSet не дают. Нужно быстрее, пишешь свою реализацию. В чем проблема?

                        +3
                        Работа метода задокументирована.

                        1) Чтобы это играло роль, надо документацию прочитать. Здесь изначально необходимость этого совершенно не видна.


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

                          0

                          Я с вами согласен и со статьей в принципе тоже. Я с оценкой, данной в заголовке, не могу согласиться. Я сам ни разу не использовал этот метод, хотя кое-где необходимость в нем возникала. Меня как раз не устраивала реализация.
                          Это, кстати, не единственный пример. Кажется, метод AbstractMap.merge() тоже сделан неэффективно, и в TreeMap он не переопределен.(Могу быть не прав. Если наврал, поправьте меня, пожалуйста).

                        –1

                        Прекрасная статья, спасибо! Век живи — век учись )

                          0
                          Пруф? Asked 5 years ago Active 10 months ago Viewed 14k times
                          stackoverflow.com/questions/28671903/the-hashsett-removeall-method-is-surprisingly-slow
                          Интересно в C# всё норм или тоже в определенных случаях может работать за O(N²)
                            0

                            Вот ссылка на реализацию: HashSet.cs#L532


                            Нет, в C# соответствующий метод просто в цикле вызывает Remove без всяких хитрых эвристик, а потому работает за O(N) (точнее, O(M), где M — количество удаляемых элементов).

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое