[concurrency-interest] PriorityQueue bug with mutable object
Manuel Dominguez Sarmiento
mads at renxo.com
Thu Jul 2 12:14:20 EDT 2009
I understand this and in fact I was expecting that kind of response from
Sun. However since they accepted the bug I was lead to believe that it
might actually be a bug.
However, notice that poll() appears to re-sort the queue every time it
is invoked. The thing is that it returns the head of the queue before
re-sorting. Perhaps the re-sorting could be performed before returning
the head of the queue since it's going to be a performance hit anyway
(siftDown() is invoked by poll() after obtaining the head of the queue,
and it is this method that maintains the heap invariant).
Please review the bug report at
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821 - see how the
expected result is pretty close to the actual result, except for the
first poll(). When I tested this I expected mutability to not be taken
into account at all (as per HashMap, TreeSet, etc.) however the queue is
in fact re-sorted, except for the head which is always returned before
I believe that at least this behaviour should be documented. I'm not for
implementing nonsense features, however this use case almost seems to
work but not quite, which is somewhat confusing and it's what prompted
me to report the "bug" (?) in the first place.
Ing. Manuel Dominguez Sarmiento
e-mail: mads at renxo.com
Phone: +54 11 4719 6806, ext. 104
Mark Thornton wrote:
> Manuel Dominguez Sarmiento wrote:
>> Hi Doug,
>> I recently filed the following bug at Sun's bug database:
>> You might want to look into it since this class is used by many
>> concurrent classes and you're listed as one of its authors.
> That is not a bug --- the behaviour is as expected. TreeSet likewise
> does not work if the ordering of elements changes after insertion. Nor
> do any of the Map's work if the keys are mutable. Priority queues
> which allow the priority to change have an extra method to perform
> this mutation --- i.e. you have to explicitly inform the queue of each
> element whose priority is changing.
> Mark Thornton
More information about the Concurrency-interest