KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
One of the selling points of immutable data structures is that they are automatically parallelizable. If no mutation is going on, then references to a functional data structure can be passed around between threads without any locking. I got to thinking about how functional data structures would be implemented in c++. Suppose that we have a reference count on each node of our data structure. (Functional data structures share structure between old and updated members of a data structure, so nodes would not belong uniquely to one particular data structure.) The problem is that if reference counts are being updated in different threads, then our data structure is no longer thread safe. And attaching a mutex to every single node is both expensive and defeats the purpose of using immutable data structures for concurrency. Is there a way to make concurrent immutable data structures work in c++ (and other non-garbage collected environments)?
Tags (comma-separated)
Save Edits
Cancel