ArrayDeque vs LinkedList as Queue

[Oleksii Movchan]

Hello.

I found next line in ArrayDeque javadoc:

"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue".

So, is there a way to check this statement?

System.currentTimeMillis() doesn't work at all: two runs in a row and two opposite results.

[Campbell Ritchie]

But System.currentTimeMillis() is working. That is a typical result when you try performance speeds. Before you try any timings, make sure to run several runs so not less than 10⁴ operations are done in succession. That will instigate the Just in Time compilation. Then take several different timings because it is quite common for apparently opposite timings to occur like that. Also alternate them: sometimes run AD first and sometimes LL.

[Norm Radder]

Can you post your code so we can run some tests?

[Stephan van Hulst]

You should use a microbenchmark framework like JMH. It deals with very complex performance testing issues that require deep understanding of the JVM. Check out the samples to get an idea.

[Oleksii Movchan]

Norm Radder wrote:Can you post your code so we can run some tests?

To my surprise, when I deleted other methods from my TimeCounter class, it somehow started to run as it should = ArrayDeque is almost always faster than LinkedList.
Probably the problem was that before calculating AD vs LL, in the same code I was calculating ArrayList vs LinkedList, and it would made impact on the performance.

Could you help me please with the file attachment procedure? I can't do it neither with *.java files, nor *.zip
And can't find [spoiler] button to post it as a code.

[Norm Radder]

There is a button above the input box labeled: Code
Post the code via copy and paste, select it and press the Code button.
And it should look like this:

   int x = 1;

[Oleksii Movchan]

I saw it, but there are three files so I think it's a bit strange to post it this way without spoilers. Anyway, here they are.

import java.io.IOException;
import java.text.DecimalFormat;
import java.util.*;

public class ListsComparisonTest {
	private static final int ELEMENTS_AMOUNT = 1000;
	private static final int COLLECTION_SIZE = 1000000;

	
	public static void main(String[] args) throws IOException {

		LinkedList<Double> lList = new LinkedList<>();
		ArrayDeque<Double> deque = new ArrayDeque<>();
		
		DecimalFormat df = new DecimalFormat("###.####");
		try {
			
			double dequeTime = 0;
			double linkedTime = 0;
		
			System.out.println("ArrayDeque vs LinkedList");
			System.out.println("Push and pop " + ELEMENTS_AMOUNT + " elements 1000 times in empty structures: ");
			for (int i = 0; i < 1000; i++) {
				linkedTime += TimeCounter.addFirstTime(lList, ELEMENTS_AMOUNT) + TimeCounter.removeLastTime(lList, ELEMENTS_AMOUNT);
				dequeTime += TimeCounter.addFirstTime(deque, ELEMENTS_AMOUNT) + TimeCounter.removeLastTime(deque, ELEMENTS_AMOUNT);
			}	
			System.out.println("LL: " + df.format(linkedTime));
			System.out.println("AD: " + df.format(dequeTime));
			
			System.out.println();
			
			dequeTime = 0;
			linkedTime = 0;

			for (int i = 0; i < COLLECTION_SIZE; i++) {
				lList.add((double)i);
				deque.add((double)i);
			}
			System.out.println("Push and pop " + ELEMENTS_AMOUNT + " elements 1000 times in " + COLLECTION_SIZE + " sized structures: ");
			for (int i = 0; i < 1000; i++) {
				linkedTime += TimeCounter.addFirstTime(lList, ELEMENTS_AMOUNT) + TimeCounter.removeLastTime(lList, ELEMENTS_AMOUNT);
				dequeTime += TimeCounter.addFirstTime(deque, ELEMENTS_AMOUNT) + TimeCounter.removeLastTime(deque, ELEMENTS_AMOUNT);
			}	
			System.out.println("LL: " + df.format(linkedTime));
			System.out.println("AD: " + df.format(dequeTime));
			
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}
}

import java.util.*;
import java.io.IOException;

public class TimeCounter {
	public static double addFirstTime(LinkedList<Double> list, int n) {
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			list.addFirst(1.0);
		}
		double time = timer.stop();
			
		return time;
	}
	
	public static double addFirstTime(Deque<Double> deque, int n) {
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			deque.addFirst(1.0);
		}
		double time = timer.stop();
			
		return time;
	}

	public static double addLastTime(LinkedList<Double> list, int n) {
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			list.addLast(1.0);
		}
		double time = timer.stop();
			
		return time;
	}
	
	public static double addLastTime(Deque<Double> deque, int n) {
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			deque.addLast(1.0);
		}
		double time = timer.stop();
			
		return time;
	}

	public static double removeFirstTime(LinkedList<Double> list, int n) throws IOException {
		if (n > list.size()) {
			throw new IOException("N is bigger than list.size()! Program terminated");
		}
		
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			list.removeFirst();
		}
		double time = timer.stop();
			
		return time;
	}
	
	public static double removeFirstTime(Deque<Double> deque, int n) throws IOException {
		if (n > deque.size()) {
			throw new IOException("N is bigger than list.size()! Program terminated");
		}
		
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			deque.pop();
		}
		double time = timer.stop();
			
		return time;
	}

	public static double removeLastTime(LinkedList<Double> list, int n) throws IOException {
		if (n > list.size()) {
			throw new IOException("N is bigger than list.size()! Program terminated");
		}
		
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			list.removeLast();
		}
		double time = timer.stop();
			
		return time;
	}
	
	public static double removeLastTime(Deque<Double> deque, int n) throws IOException {
		if (n > deque.size()) {
			throw new IOException("N is bigger than list.size()! Program terminated");
		}
		
		Timer timer = new Timer();
		for (int i = 0; i < n; i++) {
			deque.removeLast();
		}
		double time = timer.stop();
			
		return time;
	}
	
}

public class Timer {
	private final long start;
	
	public Timer() {
		start = System.currentTimeMillis();
	}

	public double stop() {
		double stop = System.currentTimeMillis();
		return (stop - start) / 1000.0;
	}
}

[Norm Radder]

The first thing I see is the autoboxing of the double to Double:

       list.addFirst(1.0);

Create a Double object to use instead using a double.