Speed of Collections, etc

[Robert Paris]

I need to store data and frequently remove/add them from and to the holder of the objects. What's the quickest/least memory-intensive for this:
Vector
List
Collection
ArrayList
Something else?
What if it has to be synchronized?

[Jim Yingst]

Probably LinkedList. Unless you're always adding/removing from the end of the list, which is unlikely. Or unless you also need to randomly access elements of the list a lot using get(int), rather than using an Iterator. Generally your best bet is to, as much as possible, refer to the object as a List rather than as a specific type of list (like LinkedList). That way if you decide to change the type later, it's easy.
What if it has to be synchronized?
List list = Collections.synchronizedList(new LinkedList());
This makes all individual methods synchronized. But to iterate over the list, you really need a synchronized block around the whole iteration:

    synchronized (list)
    {
      for (Iterator it = list.iterator(); it.hasNext(); )
      {
        Object element = it.next();
        // do something with element...
      }
    }

Or if the processing takes a long time, iterate over a copy of the original list, so you can free up the original for more access -

    List copy;
    synchronized (list) 
    {
      copy = new ArrayList(list); 
    }
    for (Iterator it = copy.iterator(); it.hasNext(); )
    {
      Object element = it.next();
      // do something with element...
    }

[Robert Paris]

Thanks Jim.
One question:
If I create my list like this:
List list = Collections.synchronizedList(new LinkedList());
Do I still need to synchronize on the list? (for example: synchronized( list ) { ... } )

[Jim Yingst]

Yes - all the code examples I showed were intended to go with the second case, where synchronization was required. The synchronizedMap() method gives you a wrapper that synchronizes individual method calls to the list - but it doesn't give you any protection against other threads messing with your list in between method calls. This is most commonly a problem when iterating, since there is always a gap between calling hasNext() and calling next(). Thus you must synchronize externally with a sync block when iterating. See the API for Collections.synchronizedList() and related methods.

[Robert Paris]

If I Iterate through the list inside a synchronized METHOD, is that enough? Or do I have to synchronize on the LIST or ITERATOR itself?
Example:
//SYNCHRONIZED LIST
List synchList = ...;
public synchronized void doSomething()
{
ListIterator it = synchList.listIterator();
...
}

[Robert Paris]

OH! One other question:
I'm guessing that just synchronizing the method won't do it since I've synchronized other thread's access to the method not the list (?). Or does it lock everything inside it?
Anyways, let's say I do this:
public synchronized void Blah()
{
synchronized( list )
{
...
}
}
Do I run a risk of deadlock? Since I opened a lock inside a lock?

[Peter Kristensson]

Hi.
In short: Yes, this would be a potential deadlock-situation.
In long:
Consider thread A is entering method Blah, getting the lock for the object containing Blah. So far, so good. Then thread B comes along, it uses the same list (same reference) at some other place in your program, and has locked this already.
Thread A is now waiting for thread B to release the lock on list, but at this point thread B tries to enter the method Blah (using same object as thread A), and is put in queue because thread A has the lock.
A waits for B and B waits for A. deadlock.
/Peter

[Robert Paris]

Hmmm... So what's the solution? I mean, there's other stuff going on inside that method that DOES need to be synchronized. but you're right, I also need to synchronize on the list because I'm iterating over it. So what's the solution here? Is there one?

[Peter den Haan]

A number of miscellaneous points.

As all the provisos already indicated, you're not giving us enough information on the things you need to do with the data to give an unequivocal answer. To add even more options to what Jim said, if the data is unique and especially if you need to remove items from the list by value, a HashSet may be the answer. We can keep on expanding this list until we've had every single container in the Collections framework. They all exist for good reasons and each has its own domain.

As Jim mentioned too, Collections.synchronizedCollection(); and friends almost never don't cut it when you need code to be threadsafe. It makes the collection threadsafe alright (although not the process of iterating over it), but that is unlikely to make your code threadsafe. You probably don't need synchronization on the little Collection methods, but on the coarser-grained, composite operations that you implement. In that case, a synchronized Collection won't buy you anything and just lure you into a false sense of security.

This is also the solution to your problem. You don't want to synchronize on more than one object at a time, as acquiring multiple locks immediately introduces the potential for deadlock. Just don't bother with synchronized Collections. Wrap the Collection inside your own object that does the high-level data manipulation, and synchronize that (synchronized methods tend to be more readable than synchronized blocks, so use them where you can).

Don't use Hashtable, Vector, Stack and Enumeration if you can help it. Their synchronization by and large just lowers performance, their APIs are confusing, they do site outside the Collections framework, and they are generally obsolete even though they aren't deprecated.

HTH
- Peter

[Peter Kristensson]

Declaring all your methods that uses the list synchronized should solve your problem, this would in fact guarantee that the list isn't used at any other point since the current thread has a lock on both the object and the list. This would of course require that you never use your list outside the object, or if you do make sure that it's a copy.
/Peter