Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Language IDEs » Java Development Tools (JDT) » Linked list Performance issues(Linked lists are performing worse than arrays in traversal and incrementing and integer)
Linked list Performance issues [message #1516551] Fri, 19 December 2014 00:06 Go to next message
Daniel Rigby is currently offline Daniel RigbyFriend
Messages: 2
Registered: December 2014
Junior Member
Simply put, using the linked list template in java they're performing worse than arrays on my machine, also my custom linked list implementation is performing up to 20-30 times worse than both the array and the template.

Simply i'm doing about 1 million iterations of traversing a an array/list and incrementing and integer.

The output is:
Linked List Template: 22501000
Linked List Duration: 368034000
Array Duration: 12162000
Array is faster by: 355872000seconds by 2900%.

The code:
main.java
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;


public class main {

	public static void main(String[] args) 
	{
		long startTime = 0, endTime = 0, linkedListDuration = 0, arrayDuration = 0, templateDuration = 0;
		Random random = new Random();
		final int size = 1000000;
		Integer lah;
		LinkedList<Integer> linkedList = new LinkedList();
		SuperLinkedList sll = null, head = null;
		Integer[] superArray = new Integer[size];
		for(int i = 0; i < size; i++)
		{
			if(head == null)
			{
				sll = new SuperLinkedList(random.nextInt());
				head = sll;
			}
			else
			{
				sll.next = new SuperLinkedList(random.nextInt());
				sll.next.previous = sll; 
				sll.next.next = null;
				sll = sll.next;
			}
			superArray[i] = random.nextInt();
			linkedList.add(new Integer(random.nextInt()));
		}
		
		//Time traversal of array
		startTime = System.nanoTime();
		for(int i = 0; i < size; i++)
		{
			lah = superArray[i];
			lah++;
			//System.out.println("Data is:" + superArray[i]);
		}
		endTime = System.nanoTime();
		arrayDuration = endTime - startTime;

		
		//Time traversal of Linked List Template
		startTime = System.nanoTime();
		Integer integer = null;
		for(ListIterator<Integer> listIter = linkedList.listIterator(); listIter.hasNext();)
		{
			integer = listIter.next();
			integer++;
			//System.out.println("Data is:" + integer);
		}
		
		endTime = System.nanoTime();
		templateDuration = endTime - startTime;
		
		
		//Time traversal of LinkedList
		startTime = System.nanoTime();
		for(SuperLinkedList cll = head; cll.next != null;cll = cll.next)
		{
			//System.out.println("Data is: " + cll.integer);
			cll.integer++;
		}
		endTime = System.nanoTime();
		linkedListDuration = endTime - startTime;
		
		System.out.println("Linked List Template: " + templateDuration);
		System.out.println("Linked List Duration: " + linkedListDuration);
		System.out.println("Array Duration: " + arrayDuration);
		if(arrayDuration > linkedListDuration)
		{
			System.out.println("Linked List is faster by: " + (arrayDuration - linkedListDuration) + 
					"seconds by " + ((arrayDuration - linkedListDuration) / linkedListDuration * 100) 
					+ "%.");
		}
		else
		{
			System.out.println("Array is faster by: " + (linkedListDuration - arrayDuration) + 
					"seconds by " + ((linkedListDuration - arrayDuration) / arrayDuration * 100) 
					+ "%.");
		}
		

	}

}


SuperLinkedList.java
public class SuperLinkedList 
{
	public SuperLinkedList(Integer newInteger)
	{
		integer = newInteger;
	}
	public void increment()
	{
		integer++;
	}
	public Integer integer;
	public SuperLinkedList previous, next;
}
Re: Linked list Performance issues [message #1518796 is a reply to message #1516551] Sat, 20 December 2014 08:43 Go to previous messageGo to next message
Daniel Rigby is currently offline Daniel RigbyFriend
Messages: 2
Registered: December 2014
Junior Member
Anyone know why this is the case? On an intel machine and windows i believe the code shows that linked lists are faster and my implementation is slightly faster than the template version,

In theory linked list should be faster since it only needs to access an address pointer compared to finding the address of the array then doing arithmetic to calculate the element of the array to be accessed.
Re: Linked list Performance issues [message #1519329 is a reply to message #1518796] Sat, 20 December 2014 15:57 Go to previous messageGo to next message
David Wegener is currently offline David WegenerFriend
Messages: 1445
Registered: July 2009
Senior Member
On 12/20/2014 02:43 AM, Daniel Rigby wrote:
> Anyone know why this is the case? On an intel machine and windows i
> believe the code shows that linked lists are faster and my
> implementation is slightly faster than the template version,
>
> In theory linked list should be faster since it only needs to access an
> address pointer compared to finding the address of the array then doing
> arithmetic to calculate the element of the array to be accessed.
A couple of points.
First, this is not a Java programming forum. It is a forum for
questions about the JDT tools provided by Eclipse. For general Java
questions, you should seek out a Java forum. I believe that there are
some suggestions in the sticky posts at the top of the Newcomers forum.

Second, your test is a really simplistic performance test. The Java VM
provides many types of optimizations that are going to kick in at
different times while your code is running. A more robust performance
test would include a warm up period that allows the VM to optimize the
code and prevent adding noise to the test like waiting for class loaders
to load classes, etc.
Re: Linked list Performance issues [message #1519685 is a reply to message #1519329] Sat, 20 December 2014 20:41 Go to previous message
Stephan Herrmann is currently offline Stephan HerrmannFriend
Messages: 1853
Registered: July 2009
Senior Member
Rephrasing David's second piece of advice: in the times of JIT compilers performing heuristic based optimizations, micro benchmarks like the one shown in this post must be interpreted with great caution. They usually don't give a lot of information regarding the performance of real world programs.

But again: this really isn't a question regarding the tool JDT.
Previous Topic:Compile Error
Next Topic:4K version of Eclipse
Goto Forum:
  


Current Time: Thu Oct 10 02:38:00 GMT 2024

Powered by FUDForum. Page generated in 0.03799 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top