[Java] Stack보다는 ArrayDeque를 쓰자. Stack과 Vector의 문제점

Stack을 쓰지 말라

 

프로그래밍에 조금만 익숙하다면 Stack과 Queue라는 자료구조를 알 것이다. 각각 LIFO(Last In First Out), FIFO(First In First Out)가 필요한 상황에 흔히 사용된다.

java.util의 Stack은 Vector를 상속받아 구현되었는데 Vector는 대표적인 자바의 레거시 클래스로 Stack 또한 이 단점을 그대로 가지고 있다.

 

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

Deque<Integer> stack = new ArrayDeque<Integer>();

 

javadoc에도 더 완전하고 견고한 LIFO stack 기능은 Deque의 구현체들에 의해 제공되니 이 클래스(Stack)보다 Deque의 구현체들을 사용하기를 권고한다. 그 이유를 알아보자.

 

 

Stack이 상속하는 Vector의 문제점

 

Stack이 상속하는 Vector의 가장 큰 문제점은 주요 메서드들이 각각 동기화를 진행한다는 것이다.

 

// add, addElement, get 등 주요 public 메서드들이 synchronized 키워드를 달고 있다.
public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}

 

동기화를 진행하므로 작업들이 멀티쓰레딩 환경에서 안전하고 좋은 것 아닌가? 하는 생각이 들 수 있다.

그러나 대부분의 상황에서는 그렇지 않다.

 

멀티스레딩 환경에서 안전하게 수행해야 하는 작업은 보통 이러한 메서드 하나를 호출하는 것으로 끝나지 않는다. 사용자가 필요에 따라 여러 작업을 thread-safe 하게 묶어서 수행할 수 있어야 성능적인 튜닝이 가능하다. 위와 같은 Vector의 구조에서는 Iterator를 통해 내부의 여러 값들을 참조할 때 각각을 get 하는 과정에서 락을 얻는 과정이 일일이 수행된다.

 

단일 스레드에서는 성능 차이가 얼마나 날까?

필자의 환경에서 적당한 예열을 거친 뒤 유사한 동작을 수행하는 ArrayList와 Vector에 1억 개의 add를 수행해본 결과는 아래와 같다.

 

Vector<Integer> vector = new Vector<>();
for (int i = 0; i < 100_000_000; i++) {
    vector.add(i);
} // 3484ms

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100_000_000; i++) {
    arrayList.add(i);
} // 2319ms

 

거의 1.5배의 속도 차이가 발생하며 이는 vector의 동기화 작업 때문일 것으로 예상된다.

Stack은 Vector의 메서드를 그대로 사용하며 동기화 관련 문제가 그대로 발생한다.

 

// java.util.Stack
public E push(E item) {
    addElement(item);

    return item;
}

 

 

Stack만의 문제점

 

설상가상으로 Stack 자체적으로도 부족한 점이 존재한다.

Stack 대신 사용하기를 권장하는 ArrayDeque의 경우 생성자를 통해 초기 Array의 크기를 지정해줄 수 있으나 Stack은 오직 하나의 생성자를 가지며 용량에 대한 설정이 불가하다.

Stack을 생성하면 Vector의 초기 용량인 10을 그대로 사용하게 되며 크기가 큰 Stack을 자주 생성해 사용할 경우 성능적으로 손해를 보게 된다.

 

 

 

Stack 대신 ArrayDeque, 그리고 멀티스레드에서

 

자바의 하위 호환을 위해 Vector와 Stack 클래스는 영원히 남아있을 것이다.

LIFO 기능을 사용하고자 한다면 단일 스레드에선 ArrayDeque를 사용하자.

ArrayDeque는 불필요한 동기화 없이 offerLast 메서드와 pollLast 메서드로 Stack의 기능을 완벽히 대체할 수 있다.

 

멀티 스레드에서 Stack을 사용해야 한다면 ArrayDeque에 데코레이팅을 하거나 LinkedBlockingDeque 또는 ConcurrentLinkedDeque를 사용하기를 권장한다.

LinkedBlockingDeque는 한 번에 단일 스레드에서만 데이터 접근이 가능하도록 하며 

ConcurrentLinkedDeque는 여러 스레드에서 접근이 가능하나 효율적인 lock-free 알고리즘을 사용해 우선순위가 낮은 스레드가 락을 점유하는 상황이나 데드락에 걸리는 상황을 막아준다.

 

 

참고문헌

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Stack.html

https://www.baeldung.com/java-array-deque

https://www.baeldung.com/java-lifo-thread-safe#thread_safe_impl_stack