whynot4's Journal: The road to Hell is paved with good intentions

The Collections Framework in the Java 2 library is great. The API couldn't be any easier to use and it's easy to change implementations without having to do a lot of work retrofitting your code. I think that it fits most general programming needs.

However, there are a lot of problems with it too. For starters, there is no good built in implementation of a Stack. Yes, there is java.util.Stack , but that class extends java.util.Vector . This makes it easy to "forget" that you should use only push(Object o) and pop() by allowing you to use the methods in Vector like add(Object o, int index) and other non-Stack operations. This fact is pointed out in the book Effective Java and the author underscores that this was a bad design (inheritance violates encapsulation; composition preserves it).

The Collections Framework tries to do the right thing by providing 3 interfaces ( java.util.Set , java.util.List , and java.util.Map ). These interfaces have various implementations contained in the same package ( java.util.TreeSet , java.util.HashMap , java.util.LinkedList , etc.). All of these classes implement their named interfaces which is good and they all provide adequate functionality for most needs.

What is a real pain in the neck is that these containers (I say containers to mean all of those in the Collections Framework) are not synchronized out-of-the-box. It reduces overhead in high stress environments, but that does not assuage the inherent need for it. To make things a little better, there is a utility class called java.util.Collections that allows you to return a synchronized view of a container, but you can only access the container via the methods in the interface that said container implements.

What is the point of my rant? Since java.util.Stack does not meet my needs, I decided to re-implement a Stack using a java.util.LinkedList as the backing store. I chose java.util.LinkedList because it had methods that were best suited to do the job and it is reasonably fast for inserting and removing objects from the list. The problem was that the methods that I really need to implement the Stack in a straightforward way are not part of the java.util.List interface. I thought it would be okay and I took the hit. I successfully did that (any programmer worth their salt should be able to) and then moved on to a queue then a deque. It was during my testing of my queue that I got into a synchronization pitfall.

Let's suppose that I have one of my Queues managing several objects and let's say that I start two different Threads to manage objects entering and leaving the queue. Without synchronizing the object, I would most certainly have a corrupt data structure. So, I have to resort to manual synchronization. What's worse is that I have to obtain the lock on the data structure. Suddenly, my dream of a simple data structure with an easy to use API are gone.

I suppose I'll get over it. I may have to tweak those structures some, but I want to keep the usability of those structures at a very simple level. I can hide a lot of the synchronization issues under the API, but what does that do to my performance?