Remix.run Logo
zvrba 7 months ago

I implemented an academic paper (join tree) in C# here https://github.com/zvrba/Pfm

It provides the opposite: a mutable CoW data structure that is extremely cheap to "fork" so that all subsequent updates occur only on the new "fork" and are invisible to the old "fork".

zelphirkalt 7 months ago | parent [-]

Isn't that the point of well designed persistent data structures?

zvrba 7 months ago | parent [-]

Depends on how you define "persistent data structure". In most definitions that I've encountered, a new version is made after each update. This code makes a new version only when you explicitly request it with Fork(). This allows you to

- Use the data structure as a "standard" tree, sharing one instance across threads and use locking for thread-safety

- Use it as a fully-persistent structure by calling "Fork" before every modification

- Or anything in between

I needed the 3rd case: a cache manager gives out a forked view of the actual cache contents to its clients. Thus the cache is always in control of the "master" copy, and if a client modifies its own fork, the cache and other clients are not affected.