Efficiency of Java's Collection Stack data structure

Question

Today I was writing code to implement a Stack data structure using ArrayList in Java. I extended my code to compare the efficiency of the Stack I implemented against the Stack in Collection library and result surprised me a bit. I mean I was sure that my code would be far less efficient but there were many cases where my simple code performed better (if I understand correctly). Following is the code I wrote :-

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

import customexceptions.StackUnderflowException;

public class StackArray<T> {
    private int top=-1;
    private List<T> array = new ArrayList<T>();

    public void push(T object) {
        array.add(object);
        top++;
    }

    public T pop() throws StackUnderflowException {
        if (top == -1) {
            throw new StackUnderflowException();
        }
        return array.remove(top--);
    }

    public T peek() throws StackUnderflowException {
        if (top == -1) {
            throw new StackUnderflowException();
        }
        return array.get(top);
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public static void main(String[] args) throws StackUnderflowException {
        Random random = new Random();
        for (int pow=1; pow<25; pow++) {
            StackArray<Integer> intStack = new StackArray<>();
            int size = 1<<pow;
            int i;
            int randomInt = random.nextInt(10);
            long startTime = System.currentTimeMillis();
            for(i=1; i<=size; i++) {
                intStack.push(i * randomInt);
            }
            i--;

            while(!intStack.isEmpty()) {
                int popedValue = intStack.pop();
                assert popedValue == (i * randomInt);
                i--;
            }
            assert i == 0;
            intStack = null;
            long endTime = System.currentTimeMillis();
            System.out.println("Time taken StackArray for 2^" + pow 
                    + " ints = " + (endTime - startTime) + " ms") ;

            randomInt = random.nextInt(10);
            startTime = System.currentTimeMillis();
            Stack<Integer> collectionStack = new Stack<>();
            for(i=1; i<=size; i++) {
                collectionStack.push(i * randomInt);
            }
            i--;

            while(!collectionStack.isEmpty()) {
                int popedValue = collectionStack.pop();
                assert popedValue == (i * randomInt);
                i--;
            }
            assert i == 0;
            endTime = System.currentTimeMillis();
            System.out.println("Time taken by Collection Stack for 2^" +
                    pow + " int = " + (endTime - startTime) + " ms");
        }
    }
}

And below is the output I got for the same :-

Time taken StackArray for 2^1 ints = 0 ms
Time taken by Collection Stack for 2^1 int = 0 ms
Time taken StackArray for 2^2 ints = 0 ms
Time taken by Collection Stack for 2^2 int = 0 ms
Time taken StackArray for 2^3 ints = 0 ms
Time taken by Collection Stack for 2^3 int = 0 ms
Time taken StackArray for 2^4 ints = 0 ms
Time taken by Collection Stack for 2^4 int = 0 ms
Time taken StackArray for 2^5 ints = 1 ms
Time taken by Collection Stack for 2^5 int = 0 ms
Time taken StackArray for 2^6 ints = 0 ms
Time taken by Collection Stack for 2^6 int = 0 ms
Time taken StackArray for 2^7 ints = 0 ms
Time taken by Collection Stack for 2^7 int = 0 ms
Time taken StackArray for 2^8 ints = 0 ms
Time taken by Collection Stack for 2^8 int = 1 ms
Time taken StackArray for 2^9 ints = 0 ms
Time taken by Collection Stack for 2^9 int = 1 ms
Time taken StackArray for 2^10 ints = 0 ms
Time taken by Collection Stack for 2^10 int = 1 ms
Time taken StackArray for 2^11 ints = 0 ms
Time taken by Collection Stack for 2^11 int = 1 ms
Time taken StackArray for 2^12 ints = 2 ms
Time taken by Collection Stack for 2^12 int = 1 ms
Time taken StackArray for 2^13 ints = 3 ms
Time taken by Collection Stack for 2^13 int = 3 ms
Time taken StackArray for 2^14 ints = 5 ms
Time taken by Collection Stack for 2^14 int = 5 ms
Time taken StackArray for 2^15 ints = 3 ms
Time taken by Collection Stack for 2^15 int = 7 ms
Time taken StackArray for 2^16 ints = 9 ms
Time taken by Collection Stack for 2^16 int = 15 ms
Time taken StackArray for 2^17 ints = 12 ms
Time taken by Collection Stack for 2^17 int = 22 ms
Time taken StackArray for 2^18 ints = 7 ms
Time taken by Collection Stack for 2^18 int = 21 ms
Time taken StackArray for 2^19 ints = 16 ms
Time taken by Collection Stack for 2^19 int = 51 ms
Time taken StackArray for 2^20 ints = 28 ms
Time taken by Collection Stack for 2^20 int = 94 ms
Time taken StackArray for 2^21 ints = 58 ms
Time taken by Collection Stack for 2^21 int = 201 ms
Time taken StackArray for 2^22 ints = 111 ms
Time taken by Collection Stack for 2^22 int = 318 ms
Time taken StackArray for 2^23 ints = 2338 ms
Time taken by Collection Stack for 2^23 int = 2189 ms
Time taken StackArray for 2^24 ints = 5940 ms
Time taken by Collection Stack for 2^24 int = 3748 ms

In the above example you can find so many cases where my algorithm for Stack took less time in pushing and popping operation. Is there any specific reason for it? Or this is an erratic result? Or may be there is scope of improvement in Collection library?

methods in Stack are synchronized and it has an impact on performance and in general I've never seen java Stack was ever used anywhere. try to compare with Deque implemantations. It's better to use Deque if you need stack behaviour — ikos23, Apr 06 '16 at 14:53
`Stack` is obsolete. You may compare to a `LinkedList`, `ArrayDeque` or another JDK [`Deque`](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) implementations. They have `push()`, `peek()` and `poll()` (equivalent to pop()) methods — Alex Salauyou, Apr 06 '16 at 15:00
@SashaSalauyou It looks like the result is similar in case of ArrayDeque also. It seems that thread-safe could be one of the possible reasons. — Siddharth, Apr 06 '16 at 22:50
For a variety of reasons, the results you're getting are probably invalid. Read this question and its answers: [How do I write a correct micro-benchmark in Java](http://stackoverflow.com/q/504103/1441122). With an accurate benchmark, though, you'll probably find that the synchronization overhead of `Stack` slows it down. `ArrayDeque` is now the preferred collection to use for stack-like access. — Stuart Marks, Apr 07 '16 at 03:41
@StuartMarks thanks for your detailed comment. So more or less Nicolas's answer is correct. I will accept it as my answer. — Siddharth, Apr 08 '16 at 14:38

Nicolas Filotto · Accepted Answer · 2021-04-20T17:35:04.327

2

Your implementation is faster simply because Stack is thread safe and your implementation is not, so you have the overhead added by the synchronized blocks that you have in the class Stack that you don't have in your class.

edited Apr 20 '21 at 17:35

answered Apr 06 '16 at 14:51

Nicolas Filotto

43,537
11
94
122

1

I didn't downvote. I just said that you became a victim of herdike behavior ("other people downvoted, maybe I also should") Sometimes this happens on this site) – Alex Salauyou Apr 07 '16 at 05:06

Efficiency of Java's Collection Stack data structure

1 Answers1