LIFO 구조와 ArrayDeque

Ref: https://www.pexels.com/ko-kr/photo/298825/

 

 

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.

더욱 완전하고 일관된 LIFO 스택 작업은 Deque 인터페이스 및 해당 구현을 사용하여 구현하는 것이다.

ref: https://docs.oracle.com/javase/8/docs/api/

 

공식 문서를 보면 LIFO 구조를 구현할 때, Stack이 아닌 Deque를 사용하라고 한다. 그래서 Stack의 어떤 문제점 때문에 Deque를 사용해야 하는지 그 장점은 무엇인지 알아보고자 한다.

 

💥 Stack의 문제점

 

🚨 성능 한계

 

아래는 Stack 클래스 원본 코드다.

 

package java.util;

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

    public Stack() {
    }

    public E push(E item) {
        addElement(item);

        return item;
    }

    public synchronized E pop() {
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }

    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

}

 

Stack 클래스는 Vector 클래스를 확장하고 있으며, 메서드들마다 synchronized 키워드가 붙어 있다. 따라서 멀티 스레드 환경에서 Thread-safe를 보장한다. 그렇다면 동기화도 진행해 주니 좋은 것 아닌가 하는 생각이 든다. 그러나 대부분의
상황에서는 그렇지 않다.

 

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

 

실제 테스트에서도 1억회 add 작업은 ArrayList를 사용했을 때 Vector보다 1.5배 빨랐다. 따라서, 단일 스레드에서는
성능이 눈에 띄게 떨어진다.

 

여기서 알 수 있는 단점을 정리하면 다음과 같다.

 

• 단일스레드 환경에서 성능 떨어짐
• Vector의 synchronized 구조로 인해 성능 튜닝 힘듦

 

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

스택으로 사용할 때는 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다.

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

 

🚨 Can't Resize

ArrayDeque의 경우 생성자를 통해 초기 배열의 크기를 지정할 수 있으나 Stack은 오직 하나의 생성자를 가지며 용량에 대한 설정이 불가하다. 그래서 Stack은 Vector의 초기 용량인 10을 그대로 사용하게 되며 크기가 큰 Stack을 자주 생성해 사용할 경우 성능적으로 손해를 보게 된다.

 

반면, ArrayDeque는 초기 용량은 16이지만 doubleCapacity()라는 메서드에서 용량이 다 찼을 경우, 더블링을 수행한다. 그래서 용량에 제한이 없다.

 

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable {

    transient Object[] elements; // non-private to simplify nested class access

    transient int head;

    transient int tail;

    public ArrayDeque() {
        elements = new Object[16];
    }

    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1; //Doubling
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }  
    
}

 

📢 결론

 

LIFO 구조를 사용하고자 한다면 단일 스레드에선 ArrayDeque를 사용하자

 

만약, 멀티스레드 환경에서 ArrayDeque를 사용하고 싶다면 synchronized를 데코레이팅하거나 LinkedBlockingDeque
또는 ConcurrentLinkedDeque를 사용하는 것을 권장한다.

 

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

 

References:

 

https://jaehee329.tistory.com/27

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

 

https://devlog-wjdrbs96.tistory.com/245

[Java] ArrayDeque 클래스란 무엇일까?