[concurrency-interest] PriorityQueue bug with mutable object

Marcelo Fukushima takeshi10 at gmail.com
Thu Jul 2 12:38:09 EDT 2009


the siftdown and siftup operations don't resort the entire heap, they
just fix the heap invariant

see http://en.wikipedia.org/wiki/Heapsort

On Thu, Jul 2, 2009 at 1:14 PM, Manuel Dominguez
Sarmiento<mads at renxo.com> wrote:
> 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
>>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>



-- 
http://mapsdev.blogspot.com/
Marcelo Takeshi Fukushima



More information about the Concurrency-interest mailing list