기존에는 PS를 Python으로 준비하다가 유레카 과정을 통해서 자바를 다시 학습하면서
코딩테스트를 준비하고 있습니다.
Java의 클래스에는 이미 Stack이 있는데 굳이 ArrayDeque를 사용하는 경우가 많고,
실제로 Java 진영에서도 권장하는 방법입니다.
그 이유가 궁금해서 고찰해 본 내용을 정리했습니다.
배경 지식
해당 결론에 대해서 바로 설명하기 전에, 혹시 모를 수 있는 부분들에 대해 간략히 설명하고 가겠다.
스택(Stack)이란, LIFO(Last In First Out) 구조로 되어있는 자료구조를 의미한다.
이를 구현하기 위해서 Java 언어에서는 보통 Stack과 ArrayDeque 클래스를 통해서 구현하곤 하는데
왜 Stack을 구현한 Stack 클래스가 있는데도 ArrayDeque를 통해서 구현할까?
그 이유는 3가지가 있다.
우선 첫 번째로, ArrayDeque는 필요에 따라 배열의 크기를 동적으로 조절하는 것이다.
초기 크기를 초과하면 새로운 배열을 할당하고 기존 요소를 자동으로 복사하여 성능 저하를 최소화한다.
매번 수동으로 개발자가 직접 배열 크기를 관리하지 않아도 되기 때문에, 번거로움이 매우 줄어든다.
두 번째로는, ArrayDeque는 Java의 표준 라이브러리(java.util)에 포함되어 있어 별도의 외부 라이브러리를 설치하거나, 직접 자료구조를 구현할 필요가 없다.
앞선 두 개는 그냥 ArrayDeque의 장점이지, Stack 클래스와의 차별점은 아니다.
그럼 가장 중요한 세 번째 이유는 Stack 클래스는 Vector를 기반으로 하여서,
동기화가 필요하지 않은 상황에서 불필요한 오버헤드가 발생할 수 있는데 ArrayDeque 그렇지 않다는 점이다.
그렇다면, Stack이 Vector 기반이라서 오버헤드가 발생한다는 얘기는 무슨 의미일까?
Stack의 문제점
Stack의 장점이었지만 지금 상황에서의 단점은 바로, Vector 기반이라는 점이다
Java의 Stack 클래스는 위에서 언급한 것처럼 Vector 클래스를 상속하여 구현된 클래스이다.
Vector 클래스는 동기화(synchronized)된 클래스로 멀티스레드 환경에서 안전하게 사용될 수 있도록 설계되었다.
하지만 오히려 이 점이, PS 같이 일반적으로 단일 스레드 환경에서 불필요한 오버헤드를 초래한다.
왜냐하면 모든 메서드 호출이 동기화 메커니즘을 거치기 때문에 성능 저하가 발생한다.
그렇다면, Vector 클래스의 동기화는 무슨 의미일까?
Vector 클래스의 동기화
동기화란, 여러 스레드가 동시에 접근할 때 발생할 수 있는 데이터 불일치 문제를 방지하도록 설계된 것을 의미한다.
특정 코드 블록이나 메서드가 한 번에 하나의 스레드만 접근할 수 있도록 하는 메커니즘이다.
운영체제에 대해서 배워본 적이 있다면, 뭔가 낯익은 느낌이 들지 않는가?
바로 뮤텍스락, 세마포어와 비슷한 개념을 자바에서 구현해서 동기화 문제를 해결한 것이다.
(자바는 멀티스레딩이 가능한 언어이다)
Vector에서 동기화를 어떻게 구현했는지 좀 더 설명하자면,
대부분의 메서드를 synchronized 키워드로 선언되어 있다.
synchronized 키워드는 해당 메서드가 실행될 때 객체의 잠금(lock)을 획득하도록 한다.
그래서 잠금이 걸린 동안 다른 스레드는 이 메서드를 실행할 수 없다.
예시) 메서드 전체에 걸린 경우
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
예시) 특정 블록에만 걸린 경우
public boolean contains(Object o) {
synchronized (this) {
return indexOf(o, 0) >= 0;
}
}
위와 같이 synchronized 키워드와 같이 동기화를 위한 방법들을 통해서 Vector 클래스는
여러 스레드가 동시에 같은 자원에 접근하고 수정할 수 있는 멀티스레드 환경에서 inconsistency나 race condition이 발생할 수 있는 문제를 방지한다.
예시: 멀티스레드 환경에서의 Vector 사용 예시
import java.util.Vector;
public class Main {
private static Vector<Integer> vector = new Vector<>();
public static void main(String[] args) {
Thread t1 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 1000; i++) {
vector.add(i);
}
}
});
Thread t2 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 1000; i++) {
vector.add(i);
}
}
});
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Vector size: " + vector.size());
}
}
위 예시 코드에서 두 개의 스레드가 동시에 vector에 접근해 값을 추가하고 있다.
하지만 위와 같은 장치들 덕분에 두 스레드가 안전하게 vector에 접근하고 수정할 수 있어서 에러가 발생하지 않는다.
하지만 얘기의 본론으로 돌아가서,
단일 스레드 환경에서는 멀티스레드를 위한 기능인 동기화 기능이 오히려 오버헤드를 발생시키는 원인이 된다.
그래서 PS와 같이 시간효율성을 따지는 경우에는 ArrayDeque을 사용하는 것이 더 효율적이다.
결론
결국, 멀티스레드 환경에서 안전성을 위해 동기화 기능을 구현한 Vector를 상속받은 Stack 구조는
단일 스레드 환경에서 오히려 오버헤드가 발생해서 ArrayDeque를 사용하는 것이 더 좋다는 얘기이다.
글을 읽으면서 만약 이해가 부족했거나 동기화에 대해서 더 자세히 알고 싶다면
운영체제의 멀티스레드 환경에서 동기화 문제, 특히 뮤텍스락과 세마포어에 대해서 학습하길 권장한다.
😊벌써 금요일이네요! 긴 글 읽어주셔서 감사하고 주말 잘 보내세요
