Поиск неограниченной параллельной реализации java.util.Set на основе очередей. - PullRequest
Новая
       18

Поиск неограниченной параллельной реализации java.util.Set на основе очередей.

4 голосов
/ 17 августа 2011

Я ищу реализацию java.util.Set со следующими функциями:

  1. Не должно быть одновременной синхронизации; Поэтому очевидно, что я не хочу использовать Collections.synchronizedSet ().
  2. Следует сохранить порядок ввода. Поэтому ConcurrentSkipListSet не является предпочтительным, поскольку он использует compareTo () как equals () и требует предоставления реализации Comparable или Comparator. Существует также ConcurrentLinkedHashMap , который, несмотря на LinkedHashMap, не сохраняет порядок вставки.
  3. Должен быть неограниченным.
  4. Рекомендуется быть связанным списком FIFO, так как мои операции выполняются только с первым элементом очереди.

Насколько я мог найти, единственный правильный импл это CopyOnWriteArraySet , но в документации говорится, что:

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

В моем случае у меня есть много вставок в конец очереди (установлено) и много Любых удалений (и прочитанных) из заголовка очереди. Итак, какие рекомендации?

1 Ответ

6 голосов
/ 17 августа 2011

Следующее решение имеет условие гонки на удаление. Он также ведет себя несколько иначе, чем стандартные реализации JDK Set.

Однако он использует стандартные объекты JDK и является простой реализацией. Только вы можете решить, является ли это условие гонки приемлемым, или вы готовы потратить время на поиск / внедрение решения без гонок. 

public class FifoSet<T>
{
    private ConcurrentHashMap<T,T> _map;
    private ConcurrentLinkedQueue<T> _queue;

    public void add(T obj)
    {
       if (_map.put(obj,obj) != null)
          return;
       _queue.add(obj);
    }

    public T removeFirst()
    {
       T obj = _queue.remove();
       _map.remove(obj);
       return obj;
    }
}

Еще одно объяснение: ConcurrentHashMap существует исключительно как охранник на ConcurrentLinkedList; его put() метод по сути является сравнением и обменом. Таким образом, вы гарантируете, что у вас ничего нет на карте перед добавлением в очередь, и вы не удаляете с карты, пока не удалите из очереди.

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

Это относительно незначительное состояние расы. Тот, который гораздо менее важен, чем разрыв во времени между удалением элемента из очереди и выполнением каких-либо действий с этим элементом.

...