배경

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개(816B) + 객체 헤더(1216B)까지 합치면 정수 하나를 저장하는데 약 40바이트 이상의 메모리를 쓴다. 배보다 배꼽이 더 큰 셈이다.

가비지 컬렉터의 부담

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

전체 플로우 비교

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

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

• ArrayDeque
  • new ArrayDeque<>() 호출 시, JVM은 힙 영역에 연속된 주소를 갖는 배열을 할당한다.
  • 메모리 상에 0x1000, 0x1004, 0x1008… 처럼 데이터가 연속적으로 들어가게 된다.
• LinkedList
  • new LinkedList<>() 호출시, 실제 데이터를 담을 공간은 아직 할당되지 않는다. 나중에 데이터가 들어올 때마다 메모리의 빈 공간에 노드 객체를 생성한다. 주소가 0x1000, 0x5500, 0x 9990.. 처럼 흩어지게 된다.

2. 데이터 삽입 단계

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

3. 데이터 탐색 단계

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

• ArrayDeque
  1. CPU가 0번 인덱스 데이터를 요청
  2. 메모리 컨트롤러에서 캐시 라인(64바이트) 단위로 주변 데이터를 한꺼번에 CPU캐시(L1,L2)로 실어나른다.
  3. 다음 poll() 실행 시 , 이미 데이터가 CPU 내부 캐시에 들어와 있기 떄문에 RAM까지 가지 않고 즉시 처리.
• LinkedList
  1. CPU가 현재 노드를 읽는다.
  2. 다음 노드로 가기 위해 현재 노드에 적힌 메모리 주소를 확인.
  3. 해당 주소는 물리적으로 멀리 떨어져 있기 때문에 캐시에 들어와 있지 않는다. CPU는 다시 RAM이라는 먼 곳까지 전기 신호를 보내 데이터를 가져올때까지 놀게 된다.(파이프라인 스톨)

4. 자원 회수 단계

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

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

실제 성능 비교

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

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

기타 궁금점들

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

• ArrayDeque는 기본 크기(16)로 시작해 배열이 꽉 차면 2배 크기로 새로운 배열을 만든다. 매번 늘리는 게 아니라 가끔 '대공사'를 하는 방식.

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

• ArrayDeque는 내부적으로 배열을 사용하기 때문에 null 요소를 저장할 수 없다. 만약 데이터에 null이 포함되어야 하는 특수한 경우라면 LinkedList를 사용해야 한다. 또한 중간에 요소를 삽입해야할 때는 LinkedList 를 사용해야한다.

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

• 둘 다 자바의 Queue 인터페이스를 구현하므로 offer(), poll(), peek() 메서드를 똑같이 사용한다.

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

• 배열의 인덱스가 끝에 도달했을때, 다음 데이터를 다시 0번 인덱스에 저장하는 방식. 이를 통해 배열의 앞부분이 비어 있다면 데이터를 뒤로 밀지 않고도 효율적으로 공간을 재사용할 수 있음.

결론

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

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

• JVM 동작과정
  • 메모리가 어떤식으로 할당되는지
• 가비지 컬렉션이 어떤식으로 동작하는지