Persistent list

[Marc Schütz via Digitalmars-d]

On Sunday, 15 November 2015 at 20:23:58 UTC, Dicebot wrote:
> On Friday, 13 November 2015 at 23:10:04 UTC, Andrei 
> Alexandrescu wrote:
>> I created a simple persistent list with reference counting and 
>> custom allocation at http://dpaste.dzfl.pl/0981640c2835.
>
>
> There is also another thing I wanted to mention on topic of 
> persistent containers. Right now for me the most intriguing 
> topic is trying to define immutable (and actually thread 
> shared) cache data structure than can be efficiently and safely 
> used without GC. There is whole class of tasks where you can 
> get best performance by building new copy of cache in memory 
> instead of modifying separate elements, trading increased 
> memory concsumption for fast no lock parallel access. However 
> in absence of GC task of deleting memory for older generations 
> of cache becomes rather challenging. I have been thinking about 
> approach with external two-level reference counting + dedicated 
> allocator - quick thread-local RC comes first and once it goes 
> to 0, shared RC in allocator gets decremented (being effetively 
> user thread counter). Do you think it can work?

If the elements are immutable, you can actually write a parallel 
non-stop-the-world GC for your cache. You just need to record the 
"age" of each element, and define a grace period that must have 
passed before they can be freed.

As for your RC idea: You could either start by creating the 
objects as shared and add a `.unshare()` method to them, or start 
with thread-local objects and create the shared RC lazily 
(`.share()`).