성능과 메모리 효율 관점에서 JDK 의 ArrayDeque, Stack, LinkedList 비교

0. 목표

Java의 ArrayDeque와 Stack을 비교 분석한다. 이후 우리는 필요한 경우 ArrayDeque를 활용해 더 빠르고 메모리 효율성이 더 높일 수 있게된다.

1. ArrayDeque과 Stack 성능 및 메모리 효율 비교

1.a 기본적인 자료 구조와 API 디자인

ArrayDeque과 Stack은 모두 원소들의 집합을 저장하고 관리하는 데 배열(array)을 사용합니다. 그러나 두 클래스 사이에는 중요한 차이점이 있습니다.

Stack은 스택의 맨 위에서만 원소를 추가/제거할 수 있는 설계를 가지고 있습니다. 반면에 ArrayDeque는 Deque 인터페이스를 구현하기 떄문에 양쪽 끝에서 원소를 추가하거나 제거할 수
있습니다.
이러한 추상자료구조 ADT(Abstract Data Type)을 "dequeue(double-ended queue)"라고 불립니다. ArrayDeque의 이러한 유연성은 더 효율적인 알고리즘 작성에 이용될 수
있습니다.

1.b 스레드 안전성, 및 동기화 오버헤드

Stack은 동기화된 Vector 클래스를 확장하고 동기화 작업으로 인한 오버헤드로 작업이 느려집니다.
실제로 JDK의 Vector 클래스 코드를 살펴보면 synchronized 키워드를 광범위하게 사용하는 것을 볼 수
있습니다. 이는 멀티스레드 환경에서 데이터의 안전성을 보장하기 위해 필요하지 성능 저하가 발생합니다.
반면에 ArrayDeque는 동기화 메커니즘을 사용하지 않아 동기화에 따른 오버헤드가 발생하지 않습니다.

1.c 메모리 사용량

ArrayDeque는 일반적으로 Stack보다 더 적은 메모리를 사용합니다. Stack(이는 Vector에 의해 지원됨)이 성장해야 할 때, 기본설정으로 배열의 크기를 두 배로 늘립니다.
반면에 ArrayDeque는 배열의 크기를 50% 증가시킵니다.
배열의 크기를 두 배로 늘리는 것은 처음에는 효율적인 것처럼 보일 수 있지만, 원소가 계속 추가되지 않으면 빠르게 사용되지 않는 공간이 많이 생길 수 있습니다.

또한, Stack이 확장하는 Vector 클래스는 ArrayDeque에 비해 인스턴스 변수를 추가로 몇개 더 가지고 있습니다.
대부분 int 타입의 변수이지만 많은 인스턴스를 생성한다면 당연히 메모리 오버헤드가 증가합니다.
이처럼 ArrayDeque는 Stack에 비해 더 가벼워 메모리 관리에 이점이 있습니다.

1.d 동기화 오버헤드

Stack 클래스는 동기화되어 있으며, 관련한 추가적인 오버헤드를 가지고 있습니다. 이 동기화 정보 역시 메모리를 차지하여 ArrayDeque에 비해 각 Stack 작업의 오버헤드를 증가시킵니다.
반면에, ArrayDeque는 제거된 원소에 대한 참조를 즉시 null 처리합니다. 이로 인해 Vector에서보다 더 빨리 가비지 컬렉션될 수 있습니다.

1.e 정리

• 이 모든 것들은 해당 자료구조를 놓고 봤을 때에 불과하며 실제 메모리 사용량은 유즈케이스, JVM 구현체, 작업 패턴 등에 따라 다를 수 있습니다.
• 그래도 일반화 시키자면 스레드 안전성이 필요하고 그에 따른 성능 비용을 지불할 의향이 있는 경우에는 Stack을 사용해도 무관합니다.
• 하지만 단일 스레드 환경이거나, 스레드 안전성이 보장되어 있거나, 외부 동기화가 사용되는 경우에는 일반적으로 ArrayDeque가 더 나은 성능을 제공할 수 있습니다.
• 그리고 일반적으로 ArrayDeque는 Stack에 비해 메모리 효율성이 더 높습니다.

2. 동기화할 때 속도가 느려지는 방식

동기화하면 다음과 같은 이유로 성능을 느리게 만들 수 있습니다.

2.a 이유

1. Lock Overhead: 동기화를 사용하면 특정 섹션의 코드에 대한 동시 접근을 제어하기 위해 잠금(lock) 메커니즘이 필요합니다. 잠금을 얻고, 보유하고, 릴리스하는 것은 모두 오버헤드를 만듭니다.
   잠금을
   얻는데 경쟁이 있는 경우(즉, 여러 스레드가 동일한 잠금을 얻으려고 시도하는 경우) 이 오버헤드는 특히 크게 될 수 있습니다.
2. Context Switching: 스레드가 잠금을 얻을 수 없고 대기해야 하는 경우, 운영 체제는 다른 스레드로 전환(context switch) 감행 할 수도 있습니다. 이러한 컨텍스트 스위칭은 비용이
   많이
   드는
   작업이며, 이로 인해 성능이 저하될 수 있습니다.
3. Memory Synchronization: 동기화를 사용하면, 메모리는 다양한 CPU 코어나 스레드 사이에서 일관성을 유지하기 위해 동기화되어야 합니다. 이는 메모리 장벽(memory barrier)이라는
   비용이
   많이 드는 연산을 수행하도록 하여, 캐시된 데이터의 복사본이 최신 상태로 유지되도록 합니다.

2.b 정리

이러한 부분들이 동기화된 작업이 그러지 않은 작업보다 느린 이유입니다. 동기화를 아예 사용하지 않아야 한다는 의미는 아닙니다.
동기화는 데이터의 일관성을 보장하고, 동시에 발생하는 수정으로부터 데이터를 보호하는 중요한 역할을 수행합니다. 따라서 동기화가 필요한 상황에서는 성능 저하를 필요한 비용으로 계산하고 적절히 사용해야 합니다.
하지만
동기화가 필요하지 않은 상황에서는 불필요하게 동기화를 사용하여 성능을 저하시키는 것은 피해야 합니다.

3. 메모리 장벽이란?

3.a 정의

메모리 장벽(memory barrier, 또는 메모리 펜스(memory fence)라고도 함)은 컴퓨터에서 사용되는 하드웨어나 소프트웨어 명령입니다. 이는 CPU의 명령 실행 순서를 조절하여, 병렬 처리나
최적화에 의해 발생하는 문제를 방지하는 역할을 합니다.

3.b 설명

메모리 장벽은 메모리 작업의 순서를 보장하여, 특정 메모리 작업이 다른 작업 전에 반드시 완료되도록 합니다. 예를 들어, 스레드 A가 메모리 위치 X에 쓰기를 수행하고, 그 후에 스레드 B가 X를 읽는다고
가정해보겠스비다. 여기에서 스레드 A의 쓰기 작업이 완료되기 전에 스레드 B가 읽기 작업을 수행하면, 일관성이 깨질 수 있습니다. 이 경우, 메모리 장벽을 사용하면 스레드 A의 쓰기가 완료된 후에 스레드 B의
읽기가
이루어지도록 보장할 수 있습니다.

3.c 활용

멀티프로세서나 멀티스레드 환경에서는 여러 명령이 동시에 실행되거나, 컴퓨터의 최적화 알고리즘에 의해 명령의 실행 순서가 변경될 수 있습니다. 실제로 우리가 많이 사용하는
여러 JVM 구현체들도 이러한 최적화 메커니즘을 활용합니다. JLS를 보면 실제로 JLS(자바 언어 스펙)에서는 이런 최적화 메커니즘을 금지 하지 않아 JVM 구현체에 따라 실행 순서를 바꿀 수 있습니다.
이런 경우, 두 명령이 접근하는 메모리의 일관성을 유지하기 어렵게 되는데, 메모리 장벽은 이런 문제를 해결합니다.

4. Memory : 자료 구조 별 메모리 비용

Java 자료 구조의 메모리 비용에서 두 가지를 고려해볼 수 있습니다. 하나는 자료 구조 자체의 메모리 비용과 자료 구조에 저장된 객체들의 메모리 비용입니다.

저의 유즈케이스에서는 push 와 pop 작업을 많이 했습니다. 원소는 Boolean을 사용했습니다.

Boolean

Java의 Boolean 객체는 약 16바이트를 차지합니다(객체 오버헤드, 불린 값, 패딩을 포함).

LinkedList<Boolean>

LinkedList의 각 노드는 Boolean 객체와 다음 노드와 이전 노드를 가리키는 두 개의 포인터로 구성됩니다.

LinkedList 오버헤드 : 노드 사용으로 인한 오버헤드. LinkedList의 각 노드는 객체 자체에 대한 24바이트의 오버헤드와 다음 및 이전 참조에 대해 각각 추가 8바이트(보통 64bit OS)를
가지므로 총 40바이트를 차지합니다.

총합: 따라서 LinkedList의 각 Boolean은 대략 56바이트를 차지합니다 (Boolean 객체에 대한 16바이트 + LinkedList 노드에 대한 40바이트).

Stack<Boolean>:

Java의 Stack은 본질적으로 벡터로, 배열과 유사합니다.

Stack 오버헤드: Stack에 대한 오버헤드는 단순히 배열 오버헤드이며, 이는 상대적으로 작고 배열의 크기에 따라 증가하지 않습니다.

총합: 따라서 Stack의 각 Boolean은 대략 16바이트를 차지합니다(배열 오버헤드는 최소이므로 Boolean 객체만 계산).

ArrayDeque<Boolean>

ArrayDeque는 배열을 기반으로 하며, 양쪽 끝에서 효율적으로 삽입하고 제거할 수 있기 때문에 Stack보다 약간 더 복잡합니다.

ArrayDeque 오버헤드: ArrayDeque에 대한 오버헤드도 단순히 배열 오버헤드입니다.

총합: 따라서 ArrayDeque의 각 Boolean은 대략 16바이트를 차지합니다.

정리

결론적으로, Boolean 객체를 저장하는 경우, LinkedList<Boolean>는 원소 별 약 56바이트를 차지하는 반면, Stack<Boolean>와
ArrayDeque<Boolean> 모두 Boolean 당 약 16바이트를 차지합니다.

따라서 LinkedList를 사용하면 Stack 또는 ArrayDeque를 사용하는 것보다 Boolean 당 약 40바이트 더 많은 메모리를 차지하게 됩니다.

그러나 이들은 대략적인 추정치이며, 실제 메모리 사용량은 JVM 구현, 패딩, 객체 헤더의 오버헤드와 같은 여러 요소에 의해 영향을 받을 수 있다는 점을 기억해야 합니다.

또한 자료 구조를 선택할 때 메모리 효율성만을 기준으로 선택하는 것은 최선의 방법이 아닐 수 있습니다. 여러분은 자료 구조를 선택할 때
시간 복잡도와 특정 사용 사례의 요구 사항과 같은 요소들도 고려해야 합니다.

5. 출처

• JLS(Java Language Specification) Chapter 17. Threads and Locks
• Vector.java
• Stack.java
• ArrayDequeue.java