Discussions

News: Minding the Queue: JDK 1.5 Queue Support

  1. Minding the Queue: JDK 1.5 Queue Support (11 messages)

    Until Java 5, we were rolling our own Queues. Now Sun has added a java.util.Queue interface with various implementations (including a retrofitted LinkedList). This article discusses some of the queues, including Priority Queues, Blocking Queues, Delay Queues, and Synchronous Queue.

    Do you think you will see a need for these new data structures?

    Minding the Queue: Java 1.5 Adds a New Data Structure Interface
  2. Better late than never .. but it should have been in 1.0 ;-)

    Peace,

    Cameron Purdy
    Tangosol, Inc.
    Coherence: Shared Memories for J2EE Clusters
  3. Minding the Queue: JDK 1.5 Queue Support[ Go to top ]

    Until Java 5, we were rolling our own Queues . . . Do you think you will see a need for these new data structures?
    I think you answered your own question when you said that up until now people have been rolling their own.

    I'm guessing that this has been born from Doug Lea's oswego utilities (although there, they're called Channels rather than Queues, so you have SynchronousChannel etc.) I for one would like to say thanks to Doug for his work, which I have found extremely useful.
  4. It would have been nice if Sun had provided us with a stable priority queue implementation as well. One nice property of such a queue is that if all the enqueued elements have the same priority, the queue behaves as a normal (FIFO) queue. It's easy to implement a stable priority queue in terms of a non-stable one, but still.

    Alexis
  5. It would have been nice if Sun had provided us with a stable priority queue implementation as well. One nice property of such a queue is that if all the enqueued elements have the same priority, the queue behaves as a normal (FIFO) queue.
    It isn't only the java.util package that could be prone to starvation. Also unreliable by design are the JVM's prioritized thread scheduling and unordered monitor wait sets. I agree with you that the work arounds are easy enough, but the default semantics of Java synchronization should be more friendly to application developers. I suspect Sun goofed in the rush to make implementation easier for JVM inventors.
  6. It would have been nice if Sun had provided us with a stable priority queue implementation as well.
    I think the work-around that JavaDoc mentions might be wrong. I don't believe it would work in practice since neither Arrays.sort() nor Arrays.binarySearch() has a documented guarantee of how ties are resolved. Anyway, the JavaDoc says this:

    "If you need ordered traversal, consider using Arrays.sort(pq.toArray())."
  7. Clearing up a bit of confusion[ Go to top ]

    Brian,

    Hi. I wrote both PriorityQueue and Arrays. Arrays.sort *is* documented to be a stable sort. In this case it doesn't matter, as PriorityQueue.toArray returns the elements in an unspecified order. The documented workaround is correct (i.e., it allows you to traverse the elements of a priority queue in sorted order, as advertised) but it does not provide a stable priority queue. You can implement that atop an ordinary priority queue by adding a tiebreaker field (probably a long) and using it in your comparison method. But most people don't need this functionality, and it costs. The general design philosophy for JSR-166 was "don't make people pay for it unless they need it."

        Regards,

        Josh
  8. But most people don't need this functionality, and it costs. The general design philosophy for JSR-166 was "don't make people pay for it unless they need it.
    Agree. That's why we need both non-stable and stable priority queue implementions.
  9. That's why we need both non-stable and stable priority queue implementions.
    What is the philosophy that led to some queues offering fairness and others not? Eg, ArrayBlockingQueue is optionally fair, while LinkedBlockingQueue isn't.
  10. Re: Missing stable priority queue implementation[ Go to top ]

    The Java doc states that Arrays.sort() is stable, which offers certain guarantees as to how the comparison ties will be resolved... This takes care of issues with a sort by multiple criteria, or a sort with a subsequent re-sort (in a GUI). What am I missing here?
  11. Example of sorted queue vs. stable queue[ Go to top ]

    What am I missing here?
    Suppose I enqueue the following elements in this order:

      A3, B2, C2, D1

    (A3 means element A with priority 3)

    q.toArray() will return the elements in no particular order because according to the API spec., "The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order". Thus, the array can return the elements in this order (or any other order):

      C2, B2, A3, D1

    Applying a stable sort yields:

      D1, C2, B2, A3

    But a stable priority queue would have dequeued the elements in the following order:

      D1, B2, C2, A3
  12. Minding the Queue: JDK 1.5 Queue Support[ Go to top ]

    Until Java 5, we were rolling our own Queues.
    Those of us with a real-time/concurrent background realised two things: naked monitors are too low-level for constructing systems, and the "interesting" effects that come from what Java doesn't specify about Thread behaviour.

    Fortunately Doug Lea's Concurrency classes are an implementation of standard known good practice for real-time/concurrent systems, and also took account of the "specification" of the Java memory model.

    Since I've been using Lea's classes very successfully since 1999, I'm delighted to see they are in J2SE, and, yes, they will continue to be very useful.