RFR: 7161229 - PriorityBlockingQueue keeps hard reference to last removed element
webrev: http://cr.openjdk.java.net/~dholmes/7161229/webrev/ When removing the last element from the PBQ the "sift down" logic would store it back in as array[0]. The simple fix is for the sift-down to be a no-op if the queue size is zero. The fix has been contributed by Doug Lea. We are taking this opportunity to synchronize PBQ with Doug's latest version at: http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concu... So in addition to the above functional fix there are a number of miscellaneous code and comment cleanups. The only non-trivial, but still very simple, change is to the drainTo method to make it more robust if the add() on the destination collection throws an exception. I am of course a Reviewer for this. I have provided the update to the LastElement test (as this is certainly related to the last element) but there are some reservations about examining the PBS internals this way. Unfortunately there is no good way to test for these kinds of retention issues. You either need a whitebox test like this, or need to rely on non-guaranteed GC and finalization behaviour. Thanks, David Holmes
Hi David, I think the test if (n > 0) { should not be in siftDown* but should be done at all callsites, by example in heapify, you can hoist the test outside of the loop. In dequeue, it's a matter of style but the 'else' is not needed anymore. Otherwise the changes looks ok for me. Rémi On 06/25/2012 06:26 AM, David Holmes wrote:
webrev:
http://cr.openjdk.java.net/~dholmes/7161229/webrev/
When removing the last element from the PBQ the "sift down" logic would store it back in as array[0]. The simple fix is for the sift-down to be a no-op if the queue size is zero.
The fix has been contributed by Doug Lea. We are taking this opportunity to synchronize PBQ with Doug's latest version at:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concu...
So in addition to the above functional fix there are a number of miscellaneous code and comment cleanups. The only non-trivial, but still very simple, change is to the drainTo method to make it more robust if the add() on the destination collection throws an exception.
I am of course a Reviewer for this.
I have provided the update to the LastElement test (as this is certainly related to the last element) but there are some reservations about examining the PBS internals this way. Unfortunately there is no good way to test for these kinds of retention issues. You either need a whitebox test like this, or need to rely on non-guaranteed GC and finalization behaviour.
Thanks, David Holmes
Hi Remi, On 25/06/2012 7:01 PM, Rémi Forax wrote:
Hi David, I think the test
if (n > 0) {
should not be in siftDown* but should be done at all callsites, by example in heapify, you can hoist the test outside of the loop.
I originally had it at the call-site (it already exists in a number of them) but Doug prefers it to be internalized. He wrote: "... a better strategy is to move the n > 0 check to the siftDown code itself, so (existing and potential) callers don't need the check. ... an explicit n > 0 check acts to hoist array index checks in loop so turns out to be faster in general."
In dequeue, it's a matter of style but the 'else' is not needed anymore.
Otherwise the changes looks ok for me.
Thanks, David
Rémi
On 06/25/2012 06:26 AM, David Holmes wrote:
webrev:
http://cr.openjdk.java.net/~dholmes/7161229/webrev/
When removing the last element from the PBQ the "sift down" logic would store it back in as array[0]. The simple fix is for the sift-down to be a no-op if the queue size is zero.
The fix has been contributed by Doug Lea. We are taking this opportunity to synchronize PBQ with Doug's latest version at:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concu...
So in addition to the above functional fix there are a number of miscellaneous code and comment cleanups. The only non-trivial, but still very simple, change is to the drainTo method to make it more robust if the add() on the destination collection throws an exception.
I am of course a Reviewer for this.
I have provided the update to the LastElement test (as this is certainly related to the last element) but there are some reservations about examining the PBS internals this way. Unfortunately there is no good way to test for these kinds of retention issues. You either need a whitebox test like this, or need to rely on non-guaranteed GC and finalization behaviour.
Thanks, David Holmes
On 06/25/2012 01:17 PM, David Holmes wrote:
Hi Remi,
On 25/06/2012 7:01 PM, Rémi Forax wrote:
Hi David, I think the test
if (n > 0) {
should not be in siftDown* but should be done at all callsites, by example in heapify, you can hoist the test outside of the loop.
I originally had it at the call-site (it already exists in a number of them) but Doug prefers it to be internalized. He wrote:
"... a better strategy is to move the n > 0 check to the siftDown code itself, so (existing and potential) callers don't need the check. "
This can be mitigated by modifying the doc comment to say that n should be strictly positive.
"... an explicit n > 0 check acts to hoist array index checks in loop so turns out to be faster in general."
also true if n > 0 is done at callsites and methods shiftDown* is inlined, but this is not something that is easy to guarantee because it depends on the complexity of the comparator implementation. so thumb up :)
In dequeue, it's a matter of style but the 'else' is not needed anymore.
Otherwise the changes looks ok for me.
Thanks, David
cheers, Rémi
On 25/06/2012 05:26, David Holmes wrote:
webrev:
http://cr.openjdk.java.net/~dholmes/7161229/webrev/
When removing the last element from the PBQ the "sift down" logic would store it back in as array[0]. The simple fix is for the sift-down to be a no-op if the queue size is zero.
The fix has been contributed by Doug Lea. We are taking this opportunity to synchronize PBQ with Doug's latest version at:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concu...
So in addition to the above functional fix there are a number of miscellaneous code and comment cleanups. The only non-trivial, but still very simple, change is to the drainTo method to make it more robust if the add() on the destination collection throws an exception.
I am of course a Reviewer for this.
I have provided the update to the LastElement test (as this is certainly related to the last element) but there are some reservations about examining the PBS internals this way. Unfortunately there is no good way to test for these kinds of retention issues. You either need a whitebox test like this, or need to rely on non-guaranteed GC and finalization behaviour. I looked through the changes to siftDown* and the other clean-ups and they look fine to me.
As this test doesn't set a security manager then I assume it doesn't really need L92-94. It is a bit icky to use reflection and pull out a private field but I don't think it's is easily tested otherwise. -Alan,
On 27/06/2012 2:35 AM, Alan Bateman wrote:
On 25/06/2012 05:26, David Holmes wrote:
webrev:
http://cr.openjdk.java.net/~dholmes/7161229/webrev/
When removing the last element from the PBQ the "sift down" logic would store it back in as array[0]. The simple fix is for the sift-down to be a no-op if the queue size is zero.
The fix has been contributed by Doug Lea. We are taking this opportunity to synchronize PBQ with Doug's latest version at:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concu...
So in addition to the above functional fix there are a number of miscellaneous code and comment cleanups. The only non-trivial, but still very simple, change is to the drainTo method to make it more robust if the add() on the destination collection throws an exception.
I am of course a Reviewer for this.
I have provided the update to the LastElement test (as this is certainly related to the last element) but there are some reservations about examining the PBS internals this way. Unfortunately there is no good way to test for these kinds of retention issues. You either need a whitebox test like this, or need to rely on non-guaranteed GC and finalization behaviour. I looked through the changes to siftDown* and the other clean-ups and they look fine to me.
Thanks Alan.
As this test doesn't set a security manager then I assume it doesn't really need L92-94.
The IllegalAccessException has to be caught as it is a checked exception from getDeclaredField(). I removed the AccessControlException though.
It is a bit icky to use reflection and pull out a private field but I don't think it's is easily tested otherwise.
The only other way is resorting to gc/finalization hacks - and that is even more icky in my opinion. If the field vanishes one day the test will fail and we'll know to update it. I've updated the webrev for reference: http://cr.openjdk.java.net/~dholmes/7161229/webrev.01/ but will go ahead with the push. Thanks, David
-Alan,
participants (3)
-
Alan Bateman
-
David Holmes
-
Rémi Forax