Addition of elements is taking less time in Vector when compared to ArrayList

[Ravi Kiran Va]

Hi ,
I am pratically seeing how much time it takes to add Elements when using a ArrayList and in case of a Vector
Here Pratically in the sense i am using System.currentTimeMillis();

Strangely , when i used ArrayList i got the Time Taken is 719 ,and when i used Vector , i got
the Time Taken for execution is 688

Please check my program and let me know why this is happening ,

In Case of a Vector :

Vector vect = new Vector(); 
long begin = System.currentTimeMillis();
	  for(int i=0; i<1000055;i++)
	  {
	  vect.add(new String("Kiran"));
	  }
long end = System.currentTimeMillis();
long result = end-begin;
System.out.println("The total time taken is "+result);

In Case of a ArrayList it is , i have jsut changed this line

Vector vect = new Vector();  to 
 List vect = new ArrayList();

The Outputs i obtained are :

In Case of a Vector :

The Begin time is1282650574015
The End time is1282650574640
The total time taken is 625

In Case of a ArrayList :


The Begin time is1282650607109
The End time is1282650607765
The total time taken is 656


Any Ideas , as why this is happening . Thank you .

[Wouter Oet]

Don't know what's causing that. However if you change the code to the following the results are as expected:

List<Integer> array = new ArrayList<Integer>();
List<Integer> vector = new Vector<Integer>(); 
final int MAX = 10000000;

long begin = System.currentTimeMillis();   
for(int i=0; i<MAX;i++)   
{   
	array.add(i);   
}   
long mid = System.currentTimeMillis();   
for(int i=0; i<MAX;i++)   
{   
	vector.add(i);   
}
long end = System.currentTimeMillis();   

System.out.println("ArrayList: " + (mid-begin));
System.out.println("Vector:    " + (end-mid));
    

[SumitPal Pal]

I got the code for Vector class and ArrayList class from JDK 1.6 and here is it give below.



Please also note that as Brian Goetz mentions always - micro benchmarks on the latest JVMs makes no sense since the current JVMs are so advanced in terms of optimizations that it is difficult to say what is happening underneath just by looking at the code and doing 1-2 runs.

My thinking is - the JVM has optimized the Vector code - so though it has Synchronized method - but since there is nothing related to Sync happening here - it has done Lock Elision and eliminated the Sync calls

see the code below from JDK - they look exactly similar - except for the fact that 1 algorithm uses 2 times the current capacity to allocate more space and the other does some simple multiplication and division ( which can cause some slowness - since multiplication by 2 is very fast )

Vector

public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}


private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}




ArrayList

public boolean add(E e)
{
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}



public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}