Нужна эффективная Карта или Набор, который НЕ производит никакого мусора при добавлении и удалении

Поэтому, поскольку Javolution не работает ( см. Здесь), мне очень нужна эффективная реализация Java Map, которая не создает мусора при простом использовании. java.util.Map будет производить мусор при добавлении и удалении ключей. Я проверил Trove и Guava, но, похоже, у них нет реализаций Set. Где я могу найти простую и эффективную альтернативу java.util.Map?

Редактировать для EJP:

Объект записи выделяется при добавлении записи и освобождается в GC при ее удалении.:(

   void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
Источник

4 ответа

Решение

Один из вариантов - попытаться исправить реализацию HashMap для использования пула записей. Я сделал это.:) Есть и другие оптимизации скорости, которые вы можете сделать там. Я согласен с вами: эта проблема с Javolution FastMap ошеломляет.:(

Источник

В буквальном смысле я не знаю ни о какой существующей реализации Map или Set, которая никогда не создает мусора при добавлении и удалении ключа.

Фактически, единственный способ, которым это было бы технически возможно (в Java, используя Map а также Set APIs, как определено), если вы должны были установить строгую верхнюю границу для количества записей. Практические реализации Map и Set нуждаются в дополнительном состоянии, пропорциональном количеству элементов, которые они содержат. Это состояние должно храниться где-то, и когда текущее выделение будет превышено, это хранилище необходимо расширить. В Java это означает, что должны быть выделены новые узлы.

(Хорошо, вы могли бы спроектировать класс структуры данных, который бы навсегда удерживал старые бесполезные узлы и, следовательно, никогда не создавал никакого собираемого мусора... но он все еще генерирует мусор.)

Так что вы можете сделать с этим на практике... чтобы уменьшить количество мусора. Давайте принимать HashMap В качестве примера:

  • Мусор создается при удалении записи. Это неизбежно, если вы не замените цепочки хеширования реализацией, которая никогда не освобождает узлы, представляющие записи цепочки. (И это плохая идея... если только вы не можете гарантировать, что размер пула свободных узлов всегда будет маленьким. См. Ниже, почему это плохая идея.)

  • Мусор создается при изменении размера основного хеш-массива. Этого можно избежать несколькими способами:

    • В конструкторе HashMap вы можете задать аргумент 'Capacity', чтобы установить размер исходного массива хешей, достаточно большой, чтобы вам никогда не приходилось изменять его размер. (Но это потенциально тратит впустую пространство... особенно если вы не можете точно предсказать, насколько велика HashMap будет расти.)

    • Вы можете указать смешное значение аргумента 'load factor', чтобы HashMap никогда не изменял свой размер. (Но в результате получается HashMap, чьи цепочки хешей не ограничены, и вы в конечном итоге получаете O(N) поведение для поиска, вставки, удаления и т. д.

На самом деле, создание мусора не обязательно ухудшает производительность. Действительно, зависание на узлах, чтобы сборщик мусора не собирал их, на самом деле может ухудшить производительность.

Стоимость прогона GC (в предположении современного копировального сборщика) в основном состоит из трех областей:

  • Поиск узлов, которые не являются мусором.
  • Копирование этих узлов без мусора в "космос".
  • Обновление ссылок в других узлах без мусора для указания на объекты в "пространстве".

(Если вы используете коллектор с малой паузой, существуют и другие затраты... обычно пропорциональные количеству не-мусора.)

Единственная часть работы GC, которая фактически зависит от количества мусора, - это обнуление памяти, которую мусорные объекты когда-то занимали, чтобы подготовить ее к повторному использованию. И это можно сделать с помощью одного bzero призывать весь "из космоса"... или использовать трюки виртуальной памяти.

Предположим, что ваше приложение / структура данных зависает на узлах, чтобы избежать создания мусора. Теперь, когда GC запускается, он должен выполнить дополнительную работу, чтобы обойти все эти дополнительные узлы и скопировать их в "пространство", даже если они не содержат никакой полезной информации. Кроме того, эти узлы используют память, а это означает, что, если остальная часть приложения генерирует мусор, будет меньше места для его хранения, и GC необходимо будет запускать чаще.

И если вы использовали слабые / мягкие ссылки, чтобы позволить GC отбирать узлы из вашей структуры данных, то это еще больше работы для GC ... и пространство для представления этих ссылок.

Примечание: я не утверждаю, что пул объектов всегда ухудшает производительность, просто это часто происходит, особенно если пул становится неожиданно большим.

И, конечно же, именно поэтому HashMap и аналогичные классы структуры данных общего назначения не выполняют никаких пулов объектов. Если бы они это сделали, они бы значительно хуже работали в ситуациях, когда программист этого не ожидал... и они были бы по-настоящему сломлены, ИМО.

Наконец, существует простой способ настройки HashMap, так что добавление, за которым сразу следует удаление того же ключа, не создает мусора (гарантировано). Оберните его в класс Map, который кэширует последнюю добавленную запись и выполняет только put на реале HashMap когда будет добавлена ​​следующая запись. Конечно, это НЕ универсальное решение, но оно касается варианта использования вашего предыдущего вопроса.

Источник

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

Источник

http://sourceforge.net/projects/high-scale-lib/ имеет реализации Set и Map, которые не создают мусора при добавлении или удалении ключей. Реализация использует один массив с чередующимися ключами и значениями, поэтому put(k,v) не создает объект Entry.

Теперь есть несколько предостережений:

  • Rehash создает мусор b/c, он заменяет базовый массив
  • Я думаю, что эта карта будет перефразироваться с учетом достаточного количества чередующихся операций вставки и удаления, даже если общий размер стабилен. (Чтобы собрать ценности надгробной плиты)
  • Эта карта создаст объект Entry, если вы запросите набор записей (по одному во время итерации)

Класс называется NonBlockingHashMap.

Источник
Другие вопросы по тегам