Best Java thread-safe locking mechanism for collections?

What would be the least-slow thread-safe mechanism for controlling multiple accesses to a collection in Java?

I am adding objects to the top of a collection and i am very unsure what would be the best performing collection. Would it be a vector or a queue? I originally thought an ArrayList would be fast but i ran some experiments and it was very slow.

EDIT: In my inser开发者_StackOverflow社区tion testing a Vector delared using volatile seems to be the fastest?

See collections in java.util.concurrent.

The best algorithms avoid shared state as much as possible. It sounds like you are new to multi threaded programming in java. Why not just pick something that you know will be correct.... Then see how much synchronisation there is, then see if that is a problem...then see if you can find a faster way to do it.

The exact operations used should determine what is used. However, since the container is largely an abstract type, write it so it works -- reliably -- then profile, ensure functional requirements, optimize as needed, blah blah :)

Normally, my main use for a "concurrent collection" is a Queue that is used to transfer objects between threads. In this case I start with ConcurrentLinkedQueue if for no other reason than liking the "lock-free" algorithm (this doesn't mean it will be faster though :-).

Generally a Queue and/or LinkedList is a good data-structure to append to the end. Depending upon the circumstances including specific usage patterns including: thread contention, number of items removed, how items are removed, etc, a "fast-kill" of all but the start/end might be accomplished faster with a clear (part of AbstractQueue) and item re-addition -- ConcurrentLinkedQueue allows both head and tail inspection/manipulation. However, I would urge "keeping it simpler", writing to a "specific interface contract" and "just use the current approach" until there is strong evidence that a functional-requirement is not met.

As far as the performance, it really depends upon the particular use-case/operations data-structure characteristics and data-structure implementation. ArrayList may very will be slower than Vector in some cases, and is indeed documented to be. If this performance makes the difference though, something sounds fishy. The article at Java Best Practices – Vector vs ArrayList vs HashSet contains a nice read. Pay attention to the comments as well.

Edit: Remember that a "concurrent" data-structure generally only implies that a single operation (method call) is atomic (and perhaps not all operations in odd cases!). It may still be required to implement a large-scoped synchronization or other approach to achieve the required level of thread-safety. That is, a h.putIfAbsent(k,v) (from ConcurrentHashMap) is not the same as a if (!h.containsKey(k)) { h.put(k, v); } -- as a case-in-point, an issue like this applies to the "clear then add" approach mentioned above.

Happy coding.

Perhaps write your own implementation of a LinkedList?

The one in the java collection only holds a current pointer I believe. You can have one that holds head and tail...

You can also wrap it inside of a Collections.synchronizedList(...)

Uh, if I understand comment "Vector using volatile" correctly, you may not quite understand what synchronization means. Volatile would only apply to reference to Vector; and since Vector itself is synchronized it would be redundant.

But fundamentally do you really think that performance differences due to synchronization (for container access) matter enough for you to worry? If you do, you should be able to see the effect with profiling (hot spots in access and/or mutation). I am not saying there aren't cases where this can occur, but they are not particularly common.

ConcurrentSkipListMap/Set -- but you have to know how/WHEN to use it. CopyOnWriteArrayList is another wonderful solution (again need to know why you use it).

EDIT: In my insertion testing a Vector delared using volatile seems to be the fastest?

That's just uncool and totally not useful.