Могут ли функциональные / неизменные структуры данных быть полезными для параллелизма в контексте без сбора мусора?

Question

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

Я задумался о том, как будут реализованы функциональные структуры данных в c ++. Предположим, что у нас есть счетчик ссылок на каждый узел нашей структуры данных. (Функциональные структуры данных разделяют структуру между старыми и обновленными членами структуры данных, поэтому узлы не будут однозначно принадлежать одной конкретной структуре данных.)

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

Есть ли способ заставить параллельные неизменные структуры данных работать в c ++ (и других средах без сбора мусора)?

Answer 1

Существуют алгоритмы подсчета ссылок без блокировки, см., Например, Подсчет ссылок без блокировки , Указатели атомного подсчета ссылок .

Также обратите внимание, что C ++0x (который, вероятно, скоро станет C ++ 11) содержит атомарные целочисленные типы, особенно для таких целей, как эта.

Answer 2

Что ж, языки с сборкой мусора также имеют проблемы с многопоточными средами (а изменяемые структуры нелегки).

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