search

wvwwvwwv / scalable-concurrent-containers

High performance containers and utilities for concurrent and asynchronous programming
Apache License 2.0
306 stars 15 forks source link

Concurrent Deferred Reference Counting may be useful #85

Closed chnlkw closed 8 months ago

chnlkw commented 1 year ago

I found some paper which optimizes concurrent binary search tree (Natarajan-Mittal tree) by using Concurrent Memory Reclamation and Automatic Reference Counting. Wish it be useful to this library

https://github.com/cmuparlay/concurrent_deferred_rc

Daniel Anderson, Guy E. Blelloch, Yuanhao Wei: Turning manual concurrent memory reclamation into automatic reference counting.

https://www.youtube.com/watch?v=40nJlQCgf8I&list=PLyrlk8Xaylp4aGsN5wVcECG736A2JeMon&index=64

wvwwvwwv commented 1 year ago

Thanks a lot for the information! I'll definitely look into this and see if there is anything helpful for this library.

wvwwvwwv commented 1 year ago

Briefly looked into the interfaces and the video, and it seems to me that scc::ebr provides most functionality that concurrent_deferred_rc offers, e.g., scc::ebr::Arc is an EBR-backed ARC, zero -> one reference counting is correctly prevented (though, very differently), and scc::ebr::Ptr can be also marked (tagged). I guess there are two functional features that will come in handy in various parts of the library.

Hyaline

I am already aware of it, but was quite reluctant to implement this because of two reasons. 1. The use of CAS, 2. The use of a global list. I didn't measure the performance of any Hyaline implementations, but I surmise that the overhead of entering a protected region won't be as low as EBR due to the reasons. Note that, the overhead of a scc::ebr::Barrier (and Guard in crossbeam_epoch as well) is only about a couple of nanoseconds on my M1 laptop, and I strongly doubt that the CAS and scanning of the global list can be performed within ~ten nanoseconds on the same machine.

However, I still highly value their idea of deterministic garbage collection, and there must be use cases especially under circumstances where many threads are seldom used. So, I'll implement it in the foreseeable future, but as a separate module, not as a replacement of EBR (maybe generalize both as in [concurrent_deferred_rc](https://github.com/cmuparlay/concurrent_deferred_rc)? not sure).

Weak pointer

Yes, it's missing in this library, just because I didn't have enough time.

wvwwvwwv commented 8 months ago

Sorry, I think I won't be able to spend my time on this.

Some notes.

Hyaline

https://crates.io/crates/seize/0.2.5 can be considered, but I doubt that it's fast enough.

Weak pointer

ebr::Ptr can act as a weak pointer, though it's !Send and !Sync.