[concurrency-interest] BlockingDeque and revised Deque

Doug Lea dl@cs.oswego.edu
Fri, 26 Nov 2004 10:15:24 -0500


We put preliminary versions of javadocs for the promised BlockingDeque
interface and related APIs accessible from:
  http://gee.cs.oswego.edu/dl/jsr166/prejsr166x/index.html

(Note: As is usually the case for javadocs for files that aren't yet
in their intended packages, some of the specs for inherited and
overridden methods don't show up right.)

This includes the revised API for Deque. The main difference from the
previous version is that we decided that it was worth the usability
advantages to create method synonyms for common FIFO and LIFO (queue
and stack) operations, rather than requiring "views". So there are now
sets of methods required to do the same thing (e.g., "removeFirst",
"remove", and "pop").  One reason is to make it easier and more
natural for people to finally stop using the awful (and unfixable due
to compatibility requirements) java.util.Stack class.

You can compare new and old Deque by comparing above javadocs URL to
the version still in http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166xdocs/

The javadocs also includes ArrayDeque, that is designed to go into
java.util (not java.util.concurrent), and is intended to be the
fastest available NON-thread-safe stack/queue/deque implementation.

We'll probably check these into jsr166x soon. But we'd first like to
hear any comments on the above, and have some further questions:

1. LinkedBlockingDeque vs ConcurrentLinkedDeque

The LinkedBlockingDeque class is intended to be the "standard"
blocking deque class. The current implementation has relatively low
overhead but relatively poor scalability. So if you need only FIFO
queue functionality, you are better off using LinkedBlockingQueue,
which has about the same overhead but better scalibility (i.e.,
maintains better performance under contention by many
threads). Supplying both LinkedBlockingQueue and LinkedBlockingDeque
allows people to trade off functionality for scalability, which seems
about right. (And maybe someday we'll come up with some clever
redesign that eliminates this performance difference.)

But we are no longer so sure about whether the ConcurrentLinkedDeque
class now in jsr166x is important enough to put into
java.util.concurrent.  (The alternative is just to make it available
in the long-promised package of random extra niche concurrency
classes, that still doesn't exist.) ConcurrentLinkedDeque has almost
the opposite performance profile as LinkedBlockingDeque: relatively
high overhead, but very good scalability. This would also make sense
to supply to allow tradeoffs, except that in concurrent applications,
it is not all that common to want a Deque that is thread safe yet does
not support blocking. And most of those that do are probably better
off with special-case solutions.

Does anyone know of a use case common enough to argue for
adding ConcurrentLinkedDeque to java.util.concurrent?

2. Views

While the new renamings and aliases in the new Deque interface make it
a lot more convenient, they lose one advantage of the old version --
to be able to use a Deque in a LIFO manner as a Queue via method
asLifo (similarly for BlockingQueue). We know there is at least one
existing use case for this (LIFO-based executors). But in keeping with
Collections framework conventions, these kinds of
adaptor-factory-methods probably ought to appear in the
java.util.Collections class (that contains already adaptors like
"immutableList"). The new methods would be something like:
  static Queue asLifoQueue(Deque d)
  static BlockingQueue asLifoBlockingQueue(BlockingDeque d)

Even though supposedly trivial, these kinds of adaptors are tedious to
write and too easy to get just barely wrong, so ought to be supplied.

But doing this mildly breaks a different convention, of keeping
java.util free of all references to java.util.concurrent. So
we are left with a small judgement call. Should we...

  1. Add both of these to java.util.Collections

  2. Create a similar java.util.concurrent.ConcurrentCollections class
     and define asLifoBlockingQueue in it, but add asLifoQueue to
     java.util.Collections

Any opinions? Option (2) seems better, but we want to minimize classes
added as part of maintenance/RFE process, and this one would have a
fairly weak rationale for even existing.

(Aside: It is too bad that you cannot put static methods in interfaces
in Java. Allowing this would make the proper placement obvious.)

-Doug