-
Notifications
You must be signed in to change notification settings - Fork 30
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
No bounded version of ws_deque and mpsc_queue? #52
Comments
Your point is valid and yes, we don't have these kind of data structures right now. We could propose an alternate version of For the |
Blocking is not necessarily bad, it can be a mean of synchronization. |
Note that I am aware of Domainslib.Chan, which have a make_bounded constructor. |
I am not telling that blocking is It is then the responsibility of the user to decide to block or add lock when they see fit. In this case, it would be very easy to do so by properly catching the exception. Also, it gives the user the possibility to act however they want when it happens. |
But I am guessing what you want is a passive wait. I will try to spend some times on it next week and see if I can propose something that will work without costing to much (at least for the |
This "lockfree" word is very misleading. I understand people are using hardware-supported instructions, I guess in the CPU then there is some kind of semaphore. |
Yes, I have one use-case where the only writer wants to passive-wait if the data structure is full. I have another use-case where the only reader wants to passive-wait if the data structure is empty. |
I don't agree that it's misleading. Lockfree programming has been around for a while and practised by folks doing concurrent programming even in other programming languages supporting parallelism. The Wikipedia page summarises the definition well. We've also linked the relevant literature and source papers for the data structures in this library, wherever applicable. That said, we could perhaps make this clear in our documentation.
You're right in that many a times one could have an easy and resonably performant solution with blocking algorithms. As @lyrm mentioned above, it's outside the scope of this library to host blocking structures. A better place for this is perhaps |
I developed a draft implementation of lock-free bounded queue, see #83. It is based on the Michael-Scott queue and keeps track of the length of the queue and a cache of the remaining capacity and avoids additional contention in the happy paths. Unless the capacity is made really small, performance should be good. |
In a long-running program, things should not be able to grow indefinitely.
It would be nice if those data structures have a bounded counterpart.
I.e. you create the data structure with a maximum size parameter N (the data structure can contain
up to N elements maximum).
Once N is reached, all operations which try to grow the data structure should block until some space is available.
UNIX pipes have such a behavior IIRC.
Not only it prevents things from going out of hand, but it also allows some simple/natural synchronization
between parallel workers.
The text was updated successfully, but these errors were encountered: