tag:blogger.com,1999:blog-5171098727364395242.post6794533256222754695..comments2023-05-14T13:23:31.669+01:00Comments on Psychosomatic, Lobotomy, Saw: GC 'Nepotism' And Linked QueuesNitsanhttp://www.blogger.com/profile/10496299147100350513noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-5171098727364395242.post-50534918893385366442016-06-08T22:27:18.174+01:002016-06-08T22:27:18.174+01:00Hi Nitsan,
Is the head/tail in the sample linked...Hi Nitsan, <br /><br />Is the head/tail in the sample linked queue reversed on purpose? Anonymoushttps://www.blogger.com/profile/00589602522977588703noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-47557391200388070342016-05-02T10:54:18.241+01:002016-05-02T10:54:18.241+01:00I know your post has more than 1 month, but I'...I know your post has more than 1 month, but I've just read it today and it reminds me a talk about twitter: https://www.youtube.com/watch?v=M9o1LVfGp2A and why they have a dedicated JVM team.Anonymoushttps://www.blogger.com/profile/16131229716912332110noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-56357304748321156012016-04-03T06:55:45.588+01:002016-04-03T06:55:45.588+01:00Sure! Its not important since this class is schedu...Sure! Its not important since this class is scheduled for removal, but you're welcome to take a gander.<br />https://github.com/ben-manes/caffeine/blob/master/caffeine/src/main/java/com/github/benmanes/caffeine/SingleConsumerQueue.javaBen Maneshttps://www.blogger.com/profile/00834822013559658168noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-46417956374206816242016-04-03T06:51:38.375+01:002016-04-03T06:51:38.375+01:00Challenge accepted!!! If you drop a link to the re...Challenge accepted!!! If you drop a link to the relevant code I'll have a go, or if you want to continue discussion over skype/mail I'm happy to try help :-) <br />Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-88400222926724518662016-04-02T19:34:26.890+01:002016-04-02T19:34:26.890+01:00That's true, its more that the low write rate ...That's true, its more that the low write rate tends to not exacerbate the problem. Unfortunately it is a fundamental flaw in the approach if the producers expect to linearizability. In that case I don't think there is a convenient way break the linkages when using a combining arena. For the optimistic version (where producers hand off and don't wait), which is what the cache uses, this isn't a problem and thanks to your article that's now fixed.Ben Maneshttps://www.blogger.com/profile/00834822013559658168noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-10782738543859968412016-04-02T10:29:06.974+01:002016-04-02T10:29:06.974+01:00"...because the queues are drained immediatel..."...because the queues are drained immediately..." - If your implementation has an effectively contiguous linked list from node to node that is never broken as nodes are removed you may want to reconsider the likelihood of an issue here.<br /><br />Unless you can exclude GC from happening while nodes are in flight (which as a library writer you are not in a position to do IMO), all it will take is one node getting promoted. The probability of a live node during a young GC cycle will grow as the application up time grows. In a server application (that is not restarted daily...) this will become a reasonable likelihood.<br /><br />To guess at an acceptable solution, you might find it possible to break the chain when the consumer observes the queue to be empty, or at some other convenient time. Breaking the chain minimizes the worst case damage to the maximum number of linked nodes. I would guess that this (low probability of quite limited GC overhead ever so often) is acceptable to most applications. Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-68790064196630463342016-04-02T00:51:23.908+01:002016-04-02T00:51:23.908+01:00Somewhere I picked up referring to this problem as...Somewhere I picked up referring to this problem as being GC hygienic. I think it was a phrase Hans Boehm used that I took note of due to those reoccurring issues, but I can't find a reference. I'm usually pretty careful about that after seeing it occur in CLQ and friends.<br /><br />My version of the SCQ has the same issue but is required due to walking the chain to notify completion on bulk inserts. That's when producers contend and combine their work across threads to make progress. If a producer is set to wait instead of optimistically complete early, then the the combiner must notify that the element was added. This trade off was acceptable because the queues are drained immediately, so nepotism was an unlikely problem in the cache's scenario.Ben Maneshttps://www.blogger.com/profile/00834822013559658168noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-32628473755370293162016-03-29T10:51:30.552+01:002016-03-29T10:51:30.552+01:00In this code I already have a counting loop which ...In this code I already have a counting loop which is limited by `batch: Int` value and now reuse it by adding n.lazySet(null) before put an actor instance to relax by `async(b1, n1, true)` call that reschedule it in the thread pool.Andriy Plokhotnyukhttps://github.com/plokhotnyuk/actorsnoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-72767219417708217552016-03-29T05:58:26.252+01:002016-03-29T05:58:26.252+01:00I'm not sure I follow the Scala code, perhaps ...I'm not sure I follow the Scala code, perhaps I need more coffee.<br />The nepotism damage can be limited by breaking the infinite node chain into smaller chains, definitely. But this is trading the cost of setting a field with null to some sort of conditional (controlling when to set it to null) cost. Not sure it's a good trade, do you think it's worth it?Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-26122681767672474932016-03-28T18:02:15.784+01:002016-03-28T18:02:15.784+01:00Nitsan,
Great findings!
How do think, will it be ...Nitsan,<br />Great findings!<br /><br />How do think, will it be acceptable to reset not all but, some of references? leaving most of them untouched, like here: https://github.com/plokhotnyuk/actors/commit/9d5c3c760a2b4c8d5945b45286ff2e622b7b351e#diff-be05b8a29ce1716e869bdec699dd5c74R50Andriy Plokhotnyukhttps://github.com/plokhotnyuk/actorsnoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-77816134352462324512016-03-22T07:24:38.354+00:002016-03-22T07:24:38.354+00:00Correct, have a look at LinkedBlockingQueue and Co...Correct, have a look at LinkedBlockingQueue and ConcurrentLinkedQueue for further perspectives.Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-44120719199241060862016-03-22T07:23:23.623+00:002016-03-22T07:23:23.623+00:00In an array based queue the buffer is usually as l...In an array based queue the buffer is usually as long lived as the queue itself. It's reasonable to assume the buffer is promoted to old gen at some point. The references to values coming out of the queue are nulled and that's pretty much the end of it...Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-61945159504932449782016-03-22T02:42:00.036+00:002016-03-22T02:42:00.036+00:00The OpenJDK sources include this same pattern for ...The OpenJDK sources include this same pattern for LinkList.java -- http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/6d24852165ba might not have introduced the behaviour, but it at least added a comment (Help GC) indicating why it was done.darrennoreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-53200408480115239522016-03-21T22:39:22.138+00:002016-03-21T22:39:22.138+00:00How does this affect array-based queue implementat...How does this affect array-based queue implementations?phraktlehttps://www.blogger.com/profile/01615248705203068572noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-85306640174858345262016-03-21T15:37:21.424+00:002016-03-21T15:37:21.424+00:00It's an equivalence, the last just collects th...It's an equivalence, the last just collects the first few. iff being a transitive relationship I'm not sure how one can hold and the other fail.<br />(empty <=> head == tail) + (head.next == null) + (tail.value == null)<br />=> queue is empty <=> (head == tail && tail.next == null && tail.value == null)<br />It's perhaps not very clear, but I don't think it's wrong.<br />The statement: [head.next == null <=> queue is empty] is incorrect though, head.next is always null.Nitsanhttps://www.blogger.com/profile/10496299147100350513noreply@blogger.comtag:blogger.com,1999:blog-5171098727364395242.post-18777869446733762512016-03-21T15:28:57.295+00:002016-03-21T15:28:57.295+00:00The following invariants are maintained:
head == t...The following invariants are maintained:<br />head == tail <=> queue is empty<br />.<br />.<br />queue is empty <=> head == tail && tail.next == null && tail.value == null<br /><br />Doesn't sound too clear to me:<br />"head == tail if and only if queue is empty"<br />"queue is empty if and only if head == tail (again) AND tail.next == null AND ..."<br /><br />Both statements don't hold.Anonymoushttps://www.blogger.com/profile/09698480599641816888noreply@blogger.com