[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 
re-sorting.

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
Director General
Renxo S.A.
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:
>>
>> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821
>>
>> 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.
>
> Regards,
> Mark Thornton
>



More information about the Concurrency-interest mailing list