Lock-based Skiplist implementation

[koonwen]

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]

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]

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]

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]

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]

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.

[lyrm]

Thanks for the issue and the work. I have closed the PR as we are not moving in this direction and thus I am also closing this issue.