tag:blogger.com,1999:blog-5171098727364395242.post5832916162573769001..comments2023-05-14T13:23:31.669+01:00Comments on Psychosomatic, Lobotomy, Saw: Notes On Concurrent Ring Buffer Queue MechanicsNitsanhttp://www.blogger.com/profile/10496299147100350513noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-5171098727364395242.post-6992616125283130662014-07-21T13:22:58.391+01:002014-07-21T13:22:58.391+01:00The single/multi refers to the threads, not the ca...The single/multi refers to the threads, not the call sites(i.e. methods/classes calling a method). A single producer thread may still offer into a queue from any number of classes/methods and still satisfy the single producer criteria. The restriction is in place to allow certain assumptions to be made about concurrent access to the queue internal data structure.<br />Using a linked list will typically mean an unbounded queue, but there are counter examples. Akka for instance has a bounded linked MPSC queue implementation. An unbounded SPSC/MPSC queue is included in JCTools.<br />A linked list based queue may be lock free or blocking, there is no need for it to be one or the other. ConcurrentLinkedQueue is a lock free linked list based queue for example. The JCTools linked queues are also lock free.<br />One can use a series of linked bounded queues to construct an unbounded queue thus mixing the 2 approaches.<br />Creating a bounded queue does not contradict processing all the requests, I'm not sure I understand that last question...<br />Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-78061450461483166422014-07-21T11:32:47.337+01:002014-07-21T11:32:47.337+01:00i am quite confuse in Single producer and multi-pr...i am quite confuse in Single producer and multi-producer.<br />is single producer is one type of business logic such as one class which is having its method. and it is used by one thread only?<br />is multi-producer is one type of business logic such as one class which is having its method. used by multiple threads or its two-three type type of business logic with different different class which will be used by many threads but 1 thread will execute only one class?<br /><br />also what is the main difference b/w using linkedlist and using this ringbufferQueue. the difference which i knows are bounded/unbounded and blocking the request.<br />bt why we will created a bounded queue when we know we have to process all requests.Anonymoushttps://www.blogger.com/profile/12134735999623610582noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-85732353578673354372014-05-26T13:31:47.022+01:002014-05-26T13:31:47.022+01:00Currently JAQ has MPMC and MPSC covered, but both ...Currently JAQ has MPMC and MPSC covered, but both implementations are bound, so this is probably not helpful. There is an unbounded SPSC and I plan to implement linked list and linked buffer versions for SPSC and other variants. If this is an area you would like to collaborate in I'd be happy to assist.<br />If I understand correctly, the system you describe is for generic 'Actors' passing messages to each other. If the actors can be assumed non-blocking I believe the best result would be achieved by balancing the tasks/actors on top of a fixed size thread pool and routing messages via SPSC queues. This is not a trivial exercise and I have no proof to back my opinion here, so that is all it is for now.Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-56943257827021308342014-05-15T21:14:26.192+01:002014-05-15T21:14:26.192+01:00Hello. I'm currently working on performance im...Hello. I'm currently working on performance improvements for the RxJava library and we have two places where a faster MPSC/MPMC behavior would come in handly.<br /><br />One place is where event delivery to an observer needs to be serialized, i.e., when multiple threads produce events, they have to be delivered one after the other. Currenlty, we use synchronized block with queue/drain logic, i.e., when one thread wins the right of emission, it would emit the values of the others too. The current implementation when run on a single thread is 10x slower than a directly emitting the same event.<br /><br />The second place where some better queueing could come in handy are some worker threads, each having separate queues (due to the requirement that tasks from the same source should be executed on the same thread, so no thread hopping). The implementation is backed by ScheduledThreadPoolExecutor and throughput barely reaches 10Mops/s on an older i7 920. An extra nice-to-have feature would be that workers could take/steal work from each other if such work hasn't been pinned to a particular thread yet.<br /><br />In addition, both places would need grow as necessary because a producer might be on the same thread as the consumer.<br /><br />Do you have any tips?David Karnokhttps://www.blogger.com/profile/07920580392321059533noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-29847238951775036742014-05-15T06:43:35.112+01:002014-05-15T06:43:35.112+01:00Thanks! As always very interesting.
True, I was a...Thanks! As always very interesting.<br /><br />True, I was always confident that Ring Buffer for only SPSC and not thought to check it ;-)<br />But SPSC can avoid CAS and use only lazyset.CGenhttps://www.blogger.com/profile/02121454668347497828noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-62765707069851445732014-04-23T21:38:54.197+01:002014-04-23T21:38:54.197+01:00Oh, sorry, got confused there, thought it was mult...Oh, sorry, got confused there, thought it was multiple consumer! :-)Duartehttps://www.blogger.com/profile/10984656401243076538noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-91436695241704612182014-04-23T21:36:44.883+01:002014-04-23T21:36:44.883+01:00That makes sense. Thanks for the explanation!That makes sense. Thanks for the explanation!Duartehttps://www.blogger.com/profile/10984656401243076538noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-34057287703393951382014-04-23T20:25:17.817+01:002014-04-23T20:25:17.817+01:00MPSC -> Single consumer, only one thread.
The c...MPSC -> Single consumer, only one thread.<br />The consumer is making the slots visible after they are null, which implies producer cannot overwrite an unconsumed slot. As the head value is indicative (it is indeed where the consumer is) and since the consumer cannot move past a null slot the producer store must be visible for the head to progress past the slot. So producers cannot wrap past each other as the producer write must be seen by the consumer to allow the next producer to wrap back to the same element.<br />Not sure it's a clear enough explanation... keep pushing if it still doesn't make sense.<br />Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-91575295125590576992014-04-23T20:14:52.550+01:002014-04-23T20:14:52.550+01:00:-) you are not missing anything, but the side eff...:-) you are not missing anything, but the side effect is reduced capacity, not a correctness issue. it's a tradeoff between space and speed. We will be giving up on up to LOOK_AHEAD - 1 capacity for the speedup.<br />This has a further side effect which can be positive when the lost capacity is more than a cache line. As the producer avoids writing all the way up to the consumer they will not be contending on the cache line when the queue is near full.<br />Thank you for reading the code so closely, I appreciate the feedback.Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-87333241531888053022014-04-23T20:01:40.096+01:002014-04-23T20:01:40.096+01:00In MpscBoundedQueue::poll it seems more than one t...In MpscBoundedQueue::poll it seems more than one thread can return the same element. Also, if sufficient time passes before a thread executes soHead(currentHead + 1) to allow the queue to wrap around, we can lose an element.Duartehttps://www.blogger.com/profile/10984656401243076538noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-68992877640079953042014-04-23T19:51:03.753+01:002014-04-23T19:51:03.753+01:00Imagine you have a 6 element array with a look ahe...Imagine you have a 6 element array with a look ahead of 4. You start at index zero and look ahead to index 4. This holds true. The produces puts items until it reaches index 4 and the consumer consumes index 0, writing null. At index 4, the producer looks ahead at index 2, which is non-null, and returns false, despite index 0 being free. What am I missing?Duartehttps://www.blogger.com/profile/10984656401243076538noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-39490368888962126142014-04-23T18:14:57.548+01:002014-04-23T18:14:57.548+01:00In the SPSC case the null elements are continuous,...In the SPSC case the null elements are continuous, so:<br />buffer[i] is null && buffer[i + K] is null => buffer[j] is null for all i<=j<=i+K<br />Because the nulling of elements (in poll()) is ordered and done by a single thread.<br />How do you expect this to fail?Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-25059745389435882962014-04-23T17:35:18.678+01:002014-04-23T17:35:18.678+01:00Regarding tailIsClearUntil, is it not possible tha...Regarding tailIsClearUntil, is it not possible that we're skipping over empty positions, in particular when we're wrapping around?Duartehttps://www.blogger.com/profile/10984656401243076538noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-31994474122301115412014-04-22T22:34:41.890+01:002014-04-22T22:34:41.890+01:00s/also//
My takeaway from this is to not attempt ...s/also//<br /><br />My takeaway from this is to not attempt concurrent programming before morning coffee.Elihttp://siliconsprawl.comnoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-56012517793726051912014-04-22T22:30:27.670+01:002014-04-22T22:30:27.670+01:00Ah-ha! Must've had my eyes crossed; I complet...Ah-ha! Must've had my eyes crossed; I completely missed that the element was also volatile. Thanks :)Elihttp://siliconsprawl.comnoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-51880204102400058612014-04-22T17:57:26.897+01:002014-04-22T17:57:26.897+01:00The 2nd SPSC version employs a volatile array elem...The 2nd SPSC version employs a volatile array element read (lvElement) and an ordered array element store (soElement).<br />These are not easily available in java and require you either:<br />1. Use an AtomicReferenceArray (http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicReferenceArray.html)<br />2. Use Unsafe to achieve the same effect. Which is exactly what AtomicReferenceArray if you look at the code.<br />The full code of a queue using this approach can be found here: https://github.com/nitsanw/JAQ-InABox/blob/master/jaq-inabox/src/main/java/io/jaq/spsc/FFBufferWithOfferBatch.java<br />Thanks for reading :-), do ask if anything else is unclear.Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-9343382060099037882014-04-22T16:57:39.174+01:002014-04-22T16:57:39.174+01:00I think I'm misunderstanding something fundame...I think I'm misunderstanding something fundamental about the SpscBoundedQueue (4th snippet). How are there visibility guarantees when the reader and writer never access the same volatile vars?Elihttp://siliconsprawl.comnoreply@blogger.com