Stack 클래스는 진짜 느릴까?

혁콩·2024년 4월 29일

Java 자료구조 알고리즘

왜why

목록 보기

3/3

들어가며

자바의 신 2권엔 컬렉션에 관한 내용들이 있다.
그 중, Stack 클래스 부분에 다음과 같은 내용이 있다.

단순히 LIFO 기능을 원하는 것이라면 ArrayDeque 클래스를 사용해라.
다만, 스레드 안정성이 필요하다면 Stack 클래스 사용을 고려해라.

Stack 클래스가 ArrayDeque 클래스보다 더 느리게 동작한다는데, 왜 그럴까?

왜 느릴까?

이는 Stack 클래스의 내부 구현 때문인데,

public class Stack<E> extends Vector<E> {
	...
}

Stack 클래스는 Vector 클래스를 상속받는다. Vector 클래스를 들어가보면 다음과 같이 synchronized 키워드를 통해 Thread-safe하게 구현되어 있는 것을 볼 수 있다.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
	...
    
    public synchronized void copyInto(Object[] anArray) {
        ...
    }

    public synchronized void trimToSize() {
        ...
    }

    public synchronized void ensureCapacity(int minCapacity) {
		...
    }
    ...
}

때문에 Stack 클래스는 동시성 이슈로부터 자유로울 수 있지만, 단일 스레드 환경에서 또한 락을 다루는 과정이 추가되어 ArrayDeque에 비해 느린 것이다.

진짜 느릴까?

두 클래스 간 속도 차이가 얼마나 나는지를 확인해보자.

    private static void checkStack() {
        Stack<Integer> stack = new Stack<>();
        long start = System.currentTimeMillis();
        for (int i=0;i<100_000_000;i++) {
            stack.push(i);
            stack.pop();
        }
        long end = System.currentTimeMillis();

        System.out.println("Stack : " + (end-start));
    }

단순한 push/pop 연산을 1억번 반복하는 코드를 작성했다.

여러 번 실행해도 약 2초정도의 시간이 걸린다.

    private static void checkArrayDeque() {
        ArrayDeque<Integer> ad = new ArrayDeque<>();
        long start = System.currentTimeMillis();
        for (int i=0;i<100_000_000;i++) {
            ad.push(i);
            ad.pop();
        }
        long end = System.currentTimeMillis();

        System.out.println("ArrayDeque : " + (end-start));
    }