JDK-6856821 : PriorityQueue does not honour priority of mutable objects
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 6u14
  • Priority: P4
  • Status: Closed
  • Resolution: Not an Issue
  • OS: windows_xp
  • CPU: x86
  • Submitted: 2009-07-02
  • Updated: 2011-02-16
  • Resolved: 2010-11-21
Description
FULL PRODUCT VERSION :
1.6.0_05-b13
HotSpot Client VM

ADDITIONAL OS VERSION INFORMATION :
Windows XP SP3 (not OS specific though)

A DESCRIPTION OF THE PROBLEM :
When a PriorityQueue contains objects with mutable state that affect compareTo(), or when compareTo() uses time-sensitive data to produce its result, polling objects does not honour the natural ordering of the elements at the time of the pop() operation.

The queue heap invariant is established every time an element is inserted (that it, the elements are re-sorted to maintain the heap invariant). However, on poll() the head is always returned before re-sorting.

We came across this bug while trying to use DelayQueue (which internally uses a PriorityQueue) to implement a priority queue + delay behaviour.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the attached executable test program.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
mutableF
mutableE
mutableD
mutableC
mutableB
mutableA

ACTUAL -
mutableA
mutableF
mutableE
mutableD
mutableC
mutableB


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.PriorityQueue;

public class Test {

	public static void main(String[] args) {

		Mutable mutableA = new Mutable("mutableA", 0);
		Mutable mutableB = new Mutable("mutableB", 1);
		Mutable mutableC = new Mutable("mutableC", 2);
		Mutable mutableD = new Mutable("mutableD", 3);
		Mutable mutableE = new Mutable("mutableE", 4);
		Mutable mutableF = new Mutable("mutableF", 5);

		PriorityQueue<Mutable> q = new PriorityQueue<Mutable>();
		q.add(mutableA);
		q.add(mutableB);
		q.add(mutableC);
		q.add(mutableD);
		q.add(mutableE);
		q.add(mutableF);

		// Mess with values
		mutableA.value = 600;
		mutableB.value = 500;
		mutableC.value = 400;
		mutableD.value = 300;
		mutableE.value = 200;
		mutableF.value = 100;

		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
	}

	private static class Mutable implements Comparable<Mutable> {

		private final String name;
		private int value;

		private Mutable(String name, int value) {
			this.name = name;
			this.value = value;
		}

		public int compareTo(Mutable o) {
			Integer thisValue = this.value;
			Integer otherValue = o.value;
			return thisValue.compareTo(otherValue);
		}

		public String toString() {
			return name;
		}
	}
}

---------- END SOURCE ----------

Comments
EVALUATION per http://cs.oswego.edu/pipermail/concurrency-interest/2009-July/006311.html And as others mentioned, this is Not A Bug. But it is implicitly an RFE. We don't provide a class that permits re-weightings. Part of the reason is algorithmic. In all the usual priority queue algorithms, you can't re-weight unless you can locate, which you don't want to have to do via sequential search. The usual way out of this is to embed inverse indices etc inside user elements, which we also cannot do. However, it would be possible to create separate indexing structure (maybe a hash table of some sort) for those usages that can tolerate extra time/space overhead for sake of extra functionality. This might be worth exploring someday.
21-11-2010

EVALUATION There is a lively discussion of this issue over on the concurrency-interest list: [concurrency-interest] PriorityQueue bug with mutable object http://cs.oswego.edu/pipermail/concurrency-interest/2009-July/006303.html
02-07-2009