search

ocaml-multicore / saturn

Lock-free data structures for multicore OCaml
ISC License
202 stars 30 forks source link

Lock-based Skiplist implementation #87

Open koonwen opened 1 year ago

koonwen commented 1 year ago

Hi there! I notice that saturn is now accepting locked-based concurrent data structures. I happen to have a Lazy Skiplist implemented according to The Art of Multiprocessor Programming section 14.3 from a previous project. It's been moderately bench marked showing good scaling properties as number of domains increase. Thread safety also seems to be preserved from my testing.

Am wondering if there's any interest in adding it to this library before I start trying to port it here. Have a first look here

lyrm commented 1 year ago

Hi! I will have a proper look next week ! Thanks for sharing your work.

After a very (very) quick look, and as we are trying to avoid adding dependencies, I am wondering : would your implementation work well without batteries (with the adequate changes, obviously) ?

koonwen commented 1 year ago

So I've used batteries just for the Re-entrant Mutex because it's not available in the Stdlib. I had a look into how it's implemented there and seems like it could be moved into saturn without introducing additional dependencies. Let me play around with it over the weekend and update again if it works.

lyrm commented 1 year ago

I should add that we already have a lockfree skiplist implementation (PR #65) waiting for (me to do) improvements (like adding polymorphism) and (then) a proper review.

I am however very interested in seeing how the (final version of those) skiplist algorithms compared in different cases of uses !

koonwen commented 1 year ago

Owing to the sharp observation by @polytypic that the current implementation of the Re-entrant Mutex is incompatible with effect-based schedulers and no straightforward solution exists yet. Should we close this or is it still worth building even with constraints on when it can be used?

polytypic commented 1 year ago

Should we close this or is it still worth building even with constraints on when it can be used?

Let's not be hasty. The issues with Stdlib locks and blocking primitives in general has been known for a long time already and it is something we do plan to work on. So, unless you have some sort of deadline then I wouldn't recommend to close the PR. We should be able to review the code otherwise even without the scheduler friendly primitives and can then update it to use those when such primitives exist.