3 ms·
Concurrent tries with non-blocking snapshots [0] Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently.
by manuelabeledo 4y ago
Concurrent tries with non-blocking snapshots [0]
Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently. Fast accesses are a pain if you decide to use traditional read-write locks.
Ctries are entirely lock-free, thus there is no waiting for your read operations when an update is happening, i.e. you run lookups on snapshots while updates happen.
They are also a lot of fun to implement, especially if you aren't familiar with lock-free algorithms! I did learn a lot doing it myself [1]
[0] http://aleksandar-prokopec.com/resources/docs/ctries-snapshot.pdf http://aleksandar-prokopec.com/resources/docs/ctries-snapsho...
[1] https://github.com/mabeledo/ctrie-java https://github.com/mabeledo/ctrie-java
- nly 4y agoSounds like if you want a version of this that doesn't leak memory you need a garbage collected language?
- manuelabeledo 4y agoYeah, either that or you implement your own. Doing so with reference counts might not be too hard, though.
- nly 4y agoThe reference count on each element would presumably require atomic operations that could race with those used to update the actual data structure, and therefore you'd lose all your concurrency guarantees?
- manuelabeledo 4y agoGenerally speaking, this shouldn't be an issue if you perform batch collections. Either way, any new mechanism to release memory would need to take into account both the generation and the reference count, and the atomic release should be performed in the same GCAS fashion.