[jdom-interest] About JDOM performance

[Alex Rosen]

> So if a single listtype is to be used a linked list must be
> the choice.

That's a bold statement...

I wrote a quick program to compare the standard ArrayList and LinkedList
implementations. While this is a quick and dirty test, it should be at least in
the right ballpark. It shows that ArrayList is pretty consistently faster than
LinkedList, for almost all operations - but only by about 10%. Note that test
#2 is designed specifically for LinkedList (add and remove from the front
only), but ArrayList is still slightly faster.

But more importantly, they're both extremely fast. Overall, 500,000 list
operations only took about 500ms for either implementation. So, I don't think
it matters too much which list you use (at least for speed - don't know about
memory consumption).

Alex

D:\z\Test2>java -version
java version "1.3.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.0-C)
Java HotSpot(TM) Client VM (build 1.3.0-C, mixed mode)

D:\z\Test2>java ListTest linked
Testing LinkedList
Time for add: 160 ms
Time for add+remove: 190 ms
Time for add+remove 2: 201 ms
Time for access: 30 ms
Time for access 2: 70 ms
Time for total ***: 651 ms

Time for add: 120 ms
Time for add+remove: 180 ms
Time for add+remove 2: 200 ms
Time for access: 10 ms
Time for access 2: 70 ms
Time for total ***: 580 ms

Time for add: 121 ms
Time for add+remove: 190 ms
Time for add+remove 2: 190 ms
Time for access: 10 ms
Time for access 2: 70 ms
Time for total ***: 581 ms

Time for add: 120 ms
Time for add+remove: 181 ms
Time for add+remove 2: 200 ms
Time for access: 10 ms
Time for access 2: 70 ms
Time for total ***: 581 ms


D:\z\Test2>java ListTest array
Testing ArrayList
Time for add: 140 ms
Time for add+remove: 180 ms
Time for add+remove 2: 181 ms
Time for access: 30 ms
Time for access 2: 50 ms
Time for total ***: 581 ms

Time for add: 110 ms
Time for add+remove: 170 ms
Time for add+remove 2: 180 ms
Time for access: 20 ms
Time for access 2: 61 ms
Time for total ***: 541 ms

Time for add: 100 ms
Time for add+remove: 180 ms
Time for add+remove 2: 190 ms
Time for access: 10 ms
Time for access 2: 60 ms
Time for total ***: 540 ms

Time for add: 110 ms
Time for add+remove: 171 ms
Time for add+remove 2: 180 ms
Time for access: 20 ms
Time for access 2: 50 ms
Time for total ***: 531 ms
-------------- next part --------------
import java.util.*;

public class ListTest
{
	public static void main(String[] args)
	{
		boolean linked = (args.length > 0 && args[0].equals("linked"));
		if (linked)
			System.out.println("Testing LinkedList");
		else
			System.out.println("Testing ArrayList");

		test(linked);
		test(linked);
		test(linked);
		test(linked);
	}

	private static void test(boolean linked)
	{
		//// Test add

		long start = System.currentTimeMillis();
		
		List list = createList(linked);
		for (int i = 0; i < 100000; i++)
		{
			if (Math.random() < .2)
				list = createList(linked);
			list.add(new Double(Math.random()));
		}
		if (list.size() < 0) // Make sure HotSpot doesn't optimize away anything (just in case)
			System.exit(1);

		long inter = interval("add", start);

		//// Test add and remove from front

		list = createList(linked);
		for (int i = 0; i < 100000; i++)
		{
			if (Math.random() < .2)
				list = createList(linked);
			list.add(0, new Double(Math.random()));
			if (Math.random() < .5)
				list.remove(0);
		}
		if (list.size() < 0) // Make sure HotSpot doesn't optimize away anything (just in case)
			System.exit(1);

		inter = interval("add+remove", inter);

		//// Test add and remove from middle

		list = createList(linked);
		for (int i = 0; i < 100000; i++)
		{
			if (Math.random() < .2)
				list = createList(linked);
			list.add(new Double(Math.random()));
			if (Math.random() < .5)
				list.remove((int)(Math.random() * list.size()));
		}
		if (list.size() < 0) // Make sure HotSpot doesn't optimize away anything (just in case)
			System.exit(1);

		inter = interval("add+remove 2", inter);

		//// Test access via Iterator

		list = createList(linked);
		for (int i = 0; i < 10; i++)
			list.add(new Double(Math.random()));

		double d = 0.0;
		for (int i = 0; i < 10000; i++) // Note: 10x fewer iterations, since we access all 10 values.
		{
			Iterator iter = list.iterator();
			while(iter.hasNext())
			{
				Double d2 = (Double)iter.next();
				d += d2.doubleValue();
			}
		}
		if (d < 0.0) // Make sure HotSpot doesn't optimize away anything (just in case)
			System.exit(1);

		inter = interval("access", inter);

		//// Test access via random access

		list = createList(linked);
		for (int i = 0; i < 10; i++)
			list.add(new Double(Math.random()));

		d = 0.0;
		for (int i = 0; i < 100000; i++)
		{
			Double d2 = (Double)list.get((int)(Math.random() * list.size()));
			d += d2.doubleValue();
		}
		if (d < 0.0) // Make sure HotSpot doesn't optimize away anything (just in case)
			System.exit(1);

		inter = interval("access 2", inter);
		interval("total ***", start);
		System.out.println();
	}

	private static List createList(boolean linked)
	{
		if (linked) 
			return new LinkedList(); 
		else
			return new ArrayList();
	}

	private static long interval(String label, long start)
	{
		long end = System.currentTimeMillis();
		long diff = end - start;
		System.out.println("Time for " + label + ": " + diff + " ms");
		return end;
	}
}