Блог

Я ищу структуру данных коллекции, которая является:

1. потокобезопасный
2. замок свободен
3. нераспределение (амортизированный или предварительно распределенный — это нормально)
4. ненавязчивый
5. не используя экзотические внутренние компоненты

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

• Список .NET не является потокобезопасным.
• Если я добавлю к нему мьютекс, то он не будет заблокирован.
• ConcurrentStack .NET является потокобезопасным, без блокировок, использует простой CompareExchange , но выделяет новый Node для каждого элемента.
• Если я перемещаю next указатель с Node самого элемента на сам элемент, то это становится навязчивым.
• Структуры данных без блокировок на основе массивов, как правило, требуют встроенных элементов из нескольких слов.

Я чувствую, что упускаю что-то очень очевидное. Это должно быть решаемой проблемой.

• ConcurrentQueue .NET удовлетворяет всем пяти требованиям. Он выделяет, когда в резервном хранилище заканчивается место, аналогично List<T> , но пока есть дополнительная емкость, выделения не происходят. К сожалению, единственный способ зарезервировать дополнительную емкость заранее — это инициализировать ее с помощью коллекции того же размера, а затем удалить из очереди все элементы.
• то же самое верно и для .Совпадающий пакет NET’s ConcurrentBag