LinkdList VS ArrayDeque

배경

BFS 자료구조에 대해서 공부를 하던 중 ArrayDeque라는 Deque인터페이스의 구현체에 대해 새로 알게되었다. 이전까지는 여러 자료에서 흔하게 사용되는 LinkedList를 사용하고 있었는데 무엇이 다른지 궁금하여 알아보게 되었다.

구조

각각의 구조가 어떤식으로 비교해보겠다.

• LinkedList - 여러개의 노드가 서로의 주소를 참조하여 연결된 방식이다.
• ArrayDeque - 내부적으로 가변 크기의 배열을 원형으로 사용하는 방식이다. LinkedList의 메모리 비효율을 해결하기 위해 등장.

차이점

두 클래스의 차이점을 이해하기 위해선 메모리의 물리적 구조를 알아야 한다. 쉽게 예시를 들어 비교를 해보겠다.

딱 알맞는 비교인지는 모르겠지만 단독주택 vs 아파트 라고 생각해보면 좋을것 같다.

단독주택 - LinkedList

LinkedList는 데이터를 새로 추가할 때마다 JVM 힙 영역의 빈 공간 아무 곳에나 노드를 만든다.

• 구조: [이전 주소 | 데이터 | 다음 주소]를 담은 객체이다.
• 탐색 방식: 다음 데이터를 찾기 위해 현재 노드에 적힌 주소를 보고 다시 메모리의 해당 주소로 이동해야 한다. 마치 이곳저곳에 흩어져 있는 주택들을 주소록만 보고 직접 다시 찾아가햐 하는 방식과 같다.

아파트 - ArrayDeque

ArrayDeque는 마찬가지로 JVM 힙 영역 내에서 물리적으로 딱 붙어 있는 연속된 공간을 통째로 할당받는다.

• 구조: 앞서 말했듯이 내부가 배열로 이루어져 있고, 처음과 끝이 연결된 원형 배열 구조다.
• 탐색 방식: 데이터가 메모리에 나란히 붙어 있어, 따로 메모리내에서 해당 주소로 찾아갈 필요없이 인덱스 계산만으로 다음 위치를 즉시 알 수 있다. 복도형 아파트처럼 일직선 복도에 있는 방들을 차례로 찾아가는 것과 같다. 이러면 다른 위치로 이동하기 위한 시간이 매우 줄어들게 된다.

CS레벨에서의 차이점

1. 캐시 라인의 물리적 이동

CPU가 RAM에서 데이터를 가져올 때, 현대에서는 최소 64바이트(캐시 라인) 단위로 데이터를 전송한다.

• ArrayDeque: 데이터가 물리적으로 연속되어 있다. 따라서 만약 4바이트의 정수를 담고 있다면, 연속되어 있기 때문에 한 번의 메모리 접근으로 16개의 연속된 데이터가 L1캐시로 한꺼번에 들어온다. 그다음의 15번의 연산은 RAM에 갈 필요 없이 cpu내부에서 처리된다.
• LinkedList: 노드가 힙 영역의 여기저기 흩어져 있다. 한번의 메모리 접근으로 64바이트를 가져와도, 그안에는 다음 노드의 주소값은 있지만 실제 다음 노드의 데이터는 없을 확률이 매우 크다. 따라서 다음 노드를 읽기위해선 RAM에 또 한번의 전기 신호를 보내야 한다.

2. 포인터 추적과 파이프라인 중단

현대 CPU의 경우 현재 명령이 끝나기 전에 다음 명령을 미리 준비할 수 있다.

• ArrayDeque: 배열은 인덱스 기반이기 때문에 CPU는 다음에 읽을 메모리 주소를 즉시 계산할 수 있다. 즉 미리 다음 데이터를 요청할 수 있어 파이프라인이 끊기지 않게 된다.
• LinkedList: 다음 노드의 위치를 알려면 반드시 현재 노드를 메모리에서 읽어와야만 한다. 노드를 읽어오기 전까지 cpu는 다음 주소가 어디인지 알 방법이 없다. 이로인해 cpu는 데이터를 기다리며 아무것도 못하는 파이프라인 중단 상태에 빠지게 된다.

3. 메모리 파편화와 관리 오버헤드

객체 헤더와 메타데이터

JVM에서 모든 객체는 약 12~16바이트의 객체 헤더를 갖는다.

• ArrayDeque: 내부가 배열이기 때문에 객체 헤더는 배열 자체에 딱 하나만 붙는다.
• LinkedList: 각 데이터마다 노드 객체를 생성한다. 따라서 데이터(4B) + 참조 주소값 2개(8~16B) + 객체 헤더(12~16B)까지 합치면 정수 하나를 저장하는데 약 40바이트 이상의 메모리를 쓴다. 배보다 배꼽이 더 큰 셈이다.

가비지 컬렉터의 부담

• ArrayDeque: 배열의 하나만 확인하면 끝이다. 메모리 할당, 해제속도, 가비지 컬렉션 측면에서 좋은 성능을 갖는다.
• LInkedList: 수만개의 노드를 만들면 GC는 이 수만개의 객체 생존 여부를 일일히 확인해야 한다.

전체 플로우 비교

BFS를 수행한다고 했을때 ArrayDeque와 LinkedList가 CPU와 메모리 레벨에서 어떻게 다르게 동작하는지 단계별로 비교하여 정리해보자.

1. 초기화 단계: 메모리 레이아웃 결정

• ArrayDeque
• LinkedList

2. 데이터 삽입 단계

BFS에서 인접 노드를 큐에 넣는 offer() 연산시의 동작이다.

3. 데이터 탐색 단계

큐에서 데이터를 꺼내 처리하는 poll() 과정에서 결정적인 성능 차이 발생.

• ArrayDeque
• LinkedList

4. 자원 회수 단계

코테에서 실행 시간 측정에는 JVM의 청소 시간도 포함된다.

• ArrayDeque: 데이터가 아무리 많아도 배열 객체는 딱 1개, 따라서 GC가 생존 여부를 확인하는 작업이 빠르게 끝남.
• LInkedList: 10만개의 데이터를 넣었다면, 10만개의 노드 객체가 힙에 쌓이게 된다. GC는 이 10만개의 주소를 일일히 추적하여 청소해야한다.

실제 성능 비교

데이터의 개수가 10만개 일때 아래와 같은 결과가 나오게 되었다.

데이터가 1000개 정도되는 환경의 경우는 큰 차이가 없을거로 예상되나 데이터가 10만개가 넘어가게 될 경우 ArrayDeque를 사용하는 것이 성능적으로 훨씬 이득이라는 것을 알 수 있었다.

기타 궁금점들

Q1. 배열 크기가 어떤식으로 계속 늘어나는가?

Q2. ArrayDeque가 LinkedList보다 무조건 좋은가?

Q3. 사용하는 메서드는 똑같은가?

Q4. 원형 배열'이라는 게 정확히 어떤 의미인가?

결론

코딩 테스트에서 자바로 BFS를 푼다면 Queue<T> q = new ArrayDeque<>(); 가 정답!

다음으로 찾아보면 좋을 것들.

• JVM 동작과정
• 가비지 컬렉션이 어떤식으로 동작하는지