tag:blogger.com,1999:blog-5171098727364395242.post2293289160542525675..comments2023-05-14T13:23:31.669+01:00Comments on Psychosomatic, Lobotomy, Saw: Porting Pitfalls: Turning D.Vyukov MPSC Wait-free queue into a j.u.QueueNitsanhttp://www.blogger.com/profile/10496299147100350513noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-5171098727364395242.post-58664139040114751882017-01-06T16:06:50.702+00:002017-01-06T16:06:50.702+00:00A bit of a side note, back in 1987, Mellor Crummey...A bit of a side note, back in 1987, Mellor Crummey (the MC in MCS lock) already had a queue using getAndSet() (it was called fetch-and-store back then) with the same enqueueing mechanism as Dmitry's. The dequeuing is more complex because MC was aiming for full linearizability, while Dmitry's is MPSC and has "serializability" for the enqueues, i.e. Dmitry's queue may return an empty when it isn't.<br />Here is the link to the paper in case you're interested:<br />https://www.cs.rice.edu/~johnmc/papers/cqueues-mellor-crummey-TR229-1987.pdf<br />pages 4 and 5 have the relevant code.<br /><br />Cool post!Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-21875584264755917382015-04-27T09:11:39.737+01:002015-04-27T09:11:39.737+01:00Hi, Nitsan!
I counted iterations of this spin loo...Hi, Nitsan!<br /><br />I counted iterations of this spin loop and found that for some workload it shows 100K or even 1M iterations. <br /><br />Here is how I try to mitigate that CPU wasting by limiting number of spin iterations and then resheduling current thread and consumer:<br />https://github.com/plokhotnyuk/actors/blob/c5bac2e1bf70bab518102c13269838ea9b9e90e6/src/test/scala/com/github/gist/viktorklang/Actor.scala#L52<br />Andriy Plokhotnyukhttps://www.blogger.com/profile/17683648196667373541noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-23412439448850137472015-04-23T10:02:40.883+01:002015-04-23T10:02:40.883+01:00This is an interesting study in interpretations :)...This is an interesting study in interpretations :)<br />The offer implementations are all similar (except the bounded version which blocks like BlockingQueue.put). The poll versions have slight variations but are also blocking (except for Mailbox one which may eventually return null).<br />The Mailbox solution to O(n) size is nice.<br />I contributed some minor fixes in this area: https://github.com/akka/akka/pull/15596<br />Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-72878067965576591572015-04-23T09:10:25.647+01:002015-04-23T09:10:25.647+01:00Great work, Nitsan!
I played with D.Vyukov MPSC a...Great work, Nitsan!<br /><br />I played with D.Vyukov MPSC about 3 years ago by porting it in Scala: https://github.com/plokhotnyuk/actors/commit/f852ba9882ce8200b60ef37316e06a54e98d239e<br /><br />Than it was grown to bounded and unbounded MPMC versions of Akka mailbox:<br />https://github.com/plokhotnyuk/actors/blob/6eb4d8c98a1226777293169f8148716ad3d515bc/src/test/scala/akka/dispatch/Mailboxes.scala<br /><br />And MPSC versions with functional batch handler for Scalaz and The Minimalist actors accordingly:<br />https://github.com/scalaz/scalaz/blob/dce8a804cfb79e5904cace2e6655dbc933c1d756/concurrent/src/main/scala/scalaz/concurrent/Actor.scala<br />https://github.com/plokhotnyuk/actors/blob/6eb4d8c98a1226777293169f8148716ad3d515bc/src/test/scala/com/github/gist/viktorklang/Actor.scalaAndriy Plokhotnyukhttps://github.com/plokhotnyuknoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-59195334244634244132015-04-22T20:48:38.717+01:002015-04-22T20:48:38.717+01:00I haven't, you can extract the queue from Abst...I haven't, you can extract the queue from AbstractQueuedSynchronizer and see where you get.<br />Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-78805590643808689852015-04-22T18:27:33.931+01:002015-04-22T18:27:33.931+01:00Thank for the post, has anybody run benchmarks com...Thank for the post, has anybody run benchmarks comparing CLH and this implementation?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-73606393497403336832015-04-22T16:47:55.174+01:002015-04-22T16:47:55.174+01:00Regarding size: I have seen Doug Lea saying this s...Regarding size: I have seen Doug Lea saying this somewhere, that value of size in concurrent queue is pretty meaningless so you might just as well return 0 if it is empty and 42 otherwise. Might have been a joke but I can't say its not tempting :)Anonymoushttps://www.blogger.com/profile/11028610626385804121noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-29913793150077237572015-04-22T16:46:49.002+01:002015-04-22T16:46:49.002+01:00Hi Nitsan, thanks -- I enjoyed the posting.
As ...Hi Nitsan, thanks -- I enjoyed the posting. <br /><br />As an aside, it's interesting to note the duality between queues and mutual exclusion locks. It's usually trivial to convert a lock-free MPSC queue -- multiple-producer-single-consumer -- into a lock. Threads in lock() arrive and enqueue an "acquire" request upon which they wait. Only the owner can dequeue at unlock()-time, thus the "SC" constraint. Conversely, you can take a queue-based lock such as CLH and deconstruct it to yield an MPSC queue such as Vyukov's MPSC queue. <br />Dave Dicehttps://blogs.oracle.com/dave/noreply@blogger.com