Vector is faster

[Yosi Hendarsjah]

I used this code below to test the speed difference between ArrayList and Vector. ArrayList is said to be faster than Vector. I tried this class on Sparc/Solaris and Windows 2000/Pentium4. In Solaris ArrayList was faster, but in Windows it's Vector.
Can anybody explain this?

import java.util.*;
public class speedtest
{
public static void main(String[] args) 
{
int size = Integer.parseInt(args[0]);
ArrayList arlist = new ArrayList();
Vector vector = new Vector();
List list;

if (args[1].equals("a")) {
list = arlist;
} else {
list = vector;
}
long l = System.currentTimeMillis();

for (int i = 0; i < size; i++) {
list.add("");
}
for (int i = size - 1; i > -1; i--) {
list.remove(i);
}

l = System.currentTimeMillis() - l;

System.out.println("time = " + l);
}

}  

[SJ Adnams]

that is a bit wierd.
I guess it could be the time taken to resize the Arrays, what happens if you instantiate the objects with the size parameter

 .. = new ArrayList(size); 

also how big is size? "big" 10^8 or something?
Sorry, don't have a sparc box to test this with..
Simon

[David Weitzman]

If I run it with 5100000 iterations(which is pretty close to what I can fit in memory without expanding the heap) and run them twice, the difference is never greater than 300 milliseconds. So this won't be a real problem in production, but nonetheless an explanation may be in order. Looking at the Vector and ArrayList source, I only see one difference in the add() method.
Here's a quote from Vector:

    int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);

From ArrayList:

    int newCapacity = (oldCapacity * 3)/2 + 1;

So apparently they decided to ease-up on memory hunger for ArrayList and only increase size by 50%.

[John Smith]

Looking at the Vector and ArrayList source, I only see one difference in the add() method.
Another difference, of course, is that the add() method of the Vector is synchronized, so you would expect it to be slower than that of ArrayList.
I used this code below to test the speed difference between ArrayList and Vector. ArrayList is said to be faster than Vector. I tried this class on Sparc/Solaris and Windows 2000/Pentium4. In Solaris ArrayList was faster, but in Windows it's Vector. Can anybody explain this?
I got the same (unexpected) result with your code, but I don't think it is a meaningful test. Replace list.add("") with list.add("" + i), and the List will perform slightly better, as expected.

[David Weitzman]

list.add("" + i) will waste a lot of time allocating objects, but it won't tell you much about the performance of the container. Nothing about adding an item to the end of a list will be affected by the value of those objects.
As for synchronization, the cost these days isn't so bad when there's no contention. For all we know Hotspot notices that the variable is local and never passed out-of-thread so it removes the synchronization entirely. As hard as it is to write good microbenchmarks and understand the results, it's even harder when you don't understand what the software you're benchmarking actually does behind the scenes.
If you presize an ArrayList or Vector when you're about to add many thousands of elements I would expect the ArrayList to be slightly faster in java 1.4.2, but I'm not on a computer where I can test that right now.

[Jim Yingst]

I agree with David on all points. Testing on Windows 2000 with presizing the List, ArrayList comes out slightly ahead of Vector. I think tht the critical difference is the resizing code - an ArrayList grows by a factor of 3/2, while Vector grows by 2. Which means in general the ArrayList will use less memory, but will have to resize more often. It's a memory/speed tradeoff. ArrayList favors memory while Vector favors speed. Slightly. Vector is also slowed by synchronization, but David is correct that this generally isn't a big deal.
So, why is the performance different on different machines? I'm guessing that compared to Windows, Solaris either has a faster malloc or memcopy, or slower synchronization. So that one way or another, on Solaris the effect of synchronization is more significant than the effect of resizing. Though there are probably also variations between different Solaris setups, and different Windows versions, so others here may well get a different result than Yosi did. I doubt we can state a reliable general result here. Most of the time, it's not going to be worth worrying about the performance difference between ArrayList and Vector. And on the rare occasions it really makes a difference, I suppose you'll just have to test on the machine you wish to use.
And I agree with David that if you can presize the ArrayList, it should always be faster (or at least, no slower than) Vector. Thoughte difference is usually minor.
Regardless, I recommand avoiding Vector and just using ArrayList for consistency. There's no real need for Vectors any more; usually they just cause people to waste time deciding which List to use. A more important question is usually, should you use an ArrayList or a LinkedList?

[Howard Kushner]

IMHO the deciding factor between Vector and ArrayList should whether multihreaded access is a consideration. The performance difference is so misicule as to be nearly irrelevant. Considering also that part of the value propostition of Java is platform independence, why worry about windoze vs unix variants?
If you are looking for raw performance, you need to use assembly language or just program right down on bare metal.
I am not saying that performance is unimportant. I am saying that there is not a really big payoff in this particular example.
When performance becomes an issue in an application, I would suggest that we go for the biggest bottlenecks first.
So that's my two cents worth.
Regards,

[Jim Yingst]

I mostly agree with Howard; looking at the differences between Unix and Windows performance in this situation is kind of interesting, for some of us anyway, but usually not very important; it should usualy come only after profiling ina real-life situation establishes that the code in questin is an actual bottleneck. My only disagreement with Howard here is that I think even mutlithreaded acess is often not a good reason to use Vector, because in many cases the synchronization inside Vector is at too low a level; you often really need a synch block at a higher level instead. E.g:

for (int i = 0; i < vec.size(); i++) 
    doSomethingWith(vec.get(i));

If this is used in a multithreaded situation, it's often not good enough to know that both size() and get() are synchronized; you also need to make sure no threads slice in between the size() and the get() such that the size suddenly changes and you accidentally get an ArrayIndexOutOfBoundsException, or something similar. Here the "thread safety" of the Vector class provides a false sense of security which can do more harm than good; better to teach people to just use ArrayList and then put in sync themselves at whatever level is really appropriate.
Having siad that, yes it's true that there are times when Vector really does provide all the sync you need. Though in this case, Collections.synchronizedList() does the same thing, though it's a little bit slower. So I'd say, just forget about Vector entirely unless you're really sure what you're doing; even then, it's seldom worthwhile. And in an ideal world you'd just confuse the newbie programmers who have never been taught about Vector at all. (I wish.)

[Howard Kushner]

Gotta agree with Jim, 'cause we'll probably delegate to the poor little ole collection anyway.
Sigh...
I s'pose that's why we have all these cool collections classes and more importantly the interfaces to which we can code.
Well - back to the Yankees and the Marlins!
Regards,