배열은 가장 기본적인 자료구조이면서, 코드의 빠르기가 값이 메모리에 어떻게 놓이느냐에 달려 있다는 것을 가장 잘 보여 주는 구조다. 이 글은 Java를 기준으로 배열의 내부 원리(연속 저장, 주소 산술), 동적 배열(ArrayList)이 크기를 늘리는 방식, 그리고 실무에서 무엇을 고를지(SoA로의 리팩터링, ArrayDeque, BitSet)를 설명한다.

토론 요약

  • 연속 저장 + 고정 크기 요소일 때 인덱스 접근은 O(1)이며 상수 계수가 작다.
  • Java 원시 타입 배열(int[], double[])은 값이 연속 저장되어 캐시 지역성이 좋고, 앞에서부터 차례로 훑는 선형 스캔이 빠르다.
  • 객체 배열(Object[], SomeClass[])은 “참조의 연속 저장”이므로 실제 객체는 힙 곳곳에 흩어진다. 값 하나를 읽으려면 배열에서 참조를 읽고 그 참조가 가리키는 곳으로 한 번 더 가야 해서(간접 참조) 메모리를 두 번 찾아가고, 캐시 미스도 늘어난다.
  • ArrayList는 내부적으로 배열을 쓰고, 배열이 꽉 차면 더 큰 새 배열을 할당한 뒤 System.arraycopy(한 배열의 칸들을 다른 배열로 통째로 복사하는 자바 표준 메서드)로 옮긴다. 많은 요소를 한꺼번에 연달아 넣기(배치 삽입) 전에 ensureCapacity로 자리를 미리 늘려 두면 이 비용이 준다.
  • 양끝 삽입/삭제는 ArrayDeque가 일반적으로 LinkedList보다 실제로 빠르다.
  • 컬럼형(필드별) 처리에는 SoA(Struct of Arrays — 필드마다 따로 배열을 두는 배치) 레이아웃과 BitSet 같은 전용 구조가 효과적이다.

심화 설명

왜 배열 인덱스 접근이 O(1)인가

메모리의 칸마다 번지수, 곧 메모리 주소가 붙어 있다. 배열은 요소들을 이 칸에 빈틈없이 이어 붙여 둔다. 그래서 배열 첫 칸의 주소(아래 그림의 base 주소)와 요소 하나의 크기만 알면, i번째 요소의 주소는 아래의 주소 산술로 한 번에 계산된다.

flowchart LR A[base 주소] -- + i × element_size --> B[요소 i의 주소]

CPU는 정수 덧셈/곱셈 한 번씩으로 주소를 계산한다. 알고리즘을 분석할 때 쓰는 단순화한 컴퓨터 모형(RAM 모델)은 「메모리의 어느 칸이든 읽는 데 같은 시간이 든다」고 가정하므로, 배열 접근은 n(배열의 요소 개수)과 무관한 상수, 곧 O(1)이 된다. 실제로는 캐시·TLB·페이지 폴트 때문에 접근마다 걸리는 시간이 다르다. 그래도 O(1)이라 부르는 것은, 시간 복잡도가 「n이 커질 때 연산 횟수가 어떻게 느는가」만 보는 도구이고 접근 한 번에 실제로 몇 나노초가 드는지는 따지지 않기 때문이다. 그 실제 시간 차이는 아래 「캐시 미스」 절과 벤치마크에서 다룬다.

참고: Java는 배열의 복잡도를 명시적으로 서술하지 않는다. 반면 C++ 언어의 표준 자료구조 모음(C++ STL)에 든 std::vector(자바의 ArrayList에 해당) 문서는 연속 저장과 랜덤 접근 O(1)을 공식으로 적어 둔다. Java의 원시 배열도 같은 원리라서 상수 시간 접근으로 이해한다.

배열 메모리 구조도

원시 타입 배열과 객체 배열은 메모리에 놓이는 모양이 근본적으로 다르다. 아래 그림에서 위쪽 「Stack」은 메서드가 실행되는 동안 지역 변수가 들어가는 JVM 스택이고, 「Heap」은 new로 만든 배열과 객체가 들어가는 힙이다. 지역 변수 arr에는 배열 자체가 아니라 배열을 가리키는 참조만 들어 있다. 칸 안의 0x1000 같은 값은 메모리 주소를 16진수로 적은 것으로, 설명을 위해 지어낸 예시 값이다.

원시 타입 배열: int[] arr = {10, 20, 30};

graph TB subgraph Stack["Stack"] direction LR ARR["arr
(참조)"] end subgraph Heap["Heap Memory - 연속 저장"] direction LR H1["0x1000
10"] H2["0x1004
20"] H3["0x1008
30"] end ARR -->|가리킴| H1 H1 -->|연속| H2 H2 -->|연속| H3 style H1 fill:#2D5016,stroke:#fff,color:#fff style H2 fill:#2D5016,stroke:#fff,color:#fff style H3 fill:#2D5016,stroke:#fff,color:#fff
  • 배열의 모든 요소가 메모리상 인접하게 저장된다
  • 배열[i] 주소 = base(0x1000) + i × 4. 자바의 int 하나는 4바이트라서 칸이 4씩 늘어난다(Integer.BYTES가 4다)
  • 첫 요소를 읽을 때 CPU는 그 값이 든 덩어리(캐시 라인)를 통째로 캐시로 가져오므로 옆 요소들도 함께 들어온다 → 다음 요소를 읽을 때 캐시 히트일 확률이 높다

객체 배열: Item[] items = {new Item(...), new Item(...), new Item(...)};

그림의 id,price,ts는 Item 클래스의 필드 세 개다(ts는 timestamp, 곧 시각의 줄임말이다).

graph TB subgraph Stack["Stack"] direction LR ITEMS["items
(참조)"] end subgraph Heap["Heap Memory - 참조만 연속, 객체는 분산"] direction TB subgraph Refs["참조 배열
(연속 저장)"] R1["0x2000
Ref1→0x5100"] R2["0x2004
Ref2→0x8A00"] R3["0x2008
Ref3→0x3500"] end subgraph Obj["실제 객체
(분산 저장)"] O1["0x5100
Item1
id,price,ts"] O2["0x8A00
Item2
id,price,ts"] O3["0x3500
Item3
id,price,ts"] end end ITEMS -->|가리킴| R1 R1 -->|참조| O1 R2 -->|참조| O2 R3 -->|참조| O3 style R1 fill:#1E3A5F,stroke:#fff,color:#fff style R2 fill:#1E3A5F,stroke:#fff,color:#fff style R3 fill:#1E3A5F,stroke:#fff,color:#fff style O1 fill:#5D1A3A,stroke:#fff,color:#fff style O2 fill:#5D1A3A,stroke:#fff,color:#fff style O3 fill:#5D1A3A,stroke:#fff,color:#fff
  • 배열에는 참조만 연속으로 저장된다. 참조 한 칸은 4바이트로 그렸다. 64비트 컴퓨터용 JVM은 주소를 8바이트로 다루므로 참조도 원래 8바이트지만, 압축 참조가 켜져 있으면 4바이트다. 내 PC의 JDK 21에서 java -XX:+PrintFlagsFinal -version(JVM 옵션 값을 전부 찍는 명령)의 출력을 보니 UseCompressedOops가 true였다. Object[] 한 칸의 크기는 JDK 내부 클래스 sun.misc.Unsafe의 arrayIndexScale(Object[].class)로 재서 4바이트가 나왔고, -XX:-UseCompressedOops 옵션으로 압축 참조를 끄고 다시 재니 8바이트였다
  • 실제 객체는 힙의 여러 곳에 분산되어 저장된다
  • 요소를 읽을 때마다 멀리 떨어진 메모리로 건너뛰어야 한다 → 캐시 미스가 늘어난다
  • 참조를 읽고, 그 참조가 가리키는 객체를 다시 읽는 간접 참조 단계가 하나 더 든다

ArrayList의 내부 구조

graph TB subgraph Stack["Stack"] AL["list
(참조)"] end subgraph Heap["Heap Memory"] subgraph ALObj["ArrayList 객체"] SIZE["size: 3"] CAP["capacity: 10
(= elementData.length)"] ARRAY["elementData
(Object[] 참조)"] end subgraph MEM["elementData 배열
(인덱스 기반 접근)"] direction LR E0["[0]
Object Ref"] E1["[1]
Object Ref"] E2["[2]
Object Ref"] E3["[3]
null"] E4["[4]
null"] end end AL -->|가리킴| ALObj ARRAY -->|가리킴| E0 E0 -->|메모리상
인접| E1 E1 -->|메모리상
인접| E2 style SIZE fill:#3D5A30,stroke:#fff,color:#fff style CAP fill:#3D5A30,stroke:#fff,color:#fff style ARRAY fill:#3D5A30,stroke:#fff,color:#fff style E0 fill:#1E3A5F,stroke:#fff,color:#fff style E1 fill:#1E3A5F,stroke:#fff,color:#fff style E2 fill:#1E3A5F,stroke:#fff,color:#fff style E3 fill:#4A4A4A,stroke:#fff,color:#fff
  • ArrayList는 내부적으로 Object[] 배열을 쓴다(연결 리스트가 아니다)
  • size: 실제로 들어 있는 요소 개수. JDK에 든 ArrayList 클래스의 소스 코드(java/util/ArrayList.java, 아래에서 「JDK 소스」라 부른다)에 있는 private int size 필드다
  • capacity: 할당된 배열의 칸 수. 따로 있는 필드가 아니라 elementData.length다. 그림은 칸 10개 중 [0]~[4]만 그렸고, [5]~[9]도 null로 있다
  • size는 capacity를 넘지 않는다. 꽉 찬(size == capacity) 상태에서 add를 하면 그때 더 큰 배열로 늘린다(아래 「리사이즈」 절)
  • 접근 방식: elementData[i] - 인덱스로 바로 찾아가는 접근 (O(1))
  • 요소들 사이에 다음 요소를 가리키는 포인터/링크가 없다 - 배열이므로 연속 메모리의 인덱스로 접근한다

Java에서 연속 저장 가정이 깨지는 경우

  • 원시 타입 배열: 값이 연속 저장된다 → 캐시 친화적이고 선형 스캔이 빠르다.
  • 객체 배열(Object[], SomeClass[]): 배열에는 “참조”만 연속 저장되고, 실제 객체는 힙에 흩어져 있다 → 간접 참조 때문에 상수 계수가 커지고 캐시 미스도 늘어난다.
  • 불리언 대량 처리: boolean[] 대신 BitSet을 쓰면 비트 패킹(참/거짓 값 하나하나를 1바이트가 아니라 1비트에 모아 담는 방식)으로 메모리를 덜 쓰고, 합집합·교집합 같은 집합 연산을 비트 연산(AND · OR처럼 비트 단위로 한꺼번에 계산하는 것)으로 빠르게 한다.

캐시 미스(Cache Miss)란?

캐시 미스는 CPU가 필요한 데이터를 CPU 캐시에서 찾지 못하고, 더 느린 메인 메모리(RAM)에서 가져와야 할 때 생기는 현상이다. CPU 캐시는 L1 · L2 · L3라는 여러 층으로 되어 있다.

왜 캐시 미스가 중요한가? CPU는 데이터를 찾을 때 L1부터 찾고, 없으면 L2, L3, 메인 메모리 순으로 내려간다. 아래 숫자처럼 내려갈수록 느려진다. 사이클은 CPU 클럭의 박자 한 번이고, 나노초는 10억분의 1초다(µs · ns):

  • L1 캐시: ~4 사이클 (약 1-2 나노초)
  • L2 캐시: ~10-20 사이클
  • L3 캐시: ~40-75 사이클
  • 메인 메모리: ~200-300 사이클 (약 50-100 나노초)

캐시 미스 1회가 일어나면 L1에서 읽을 때보다 수십 배 오래 걸린다. 예를 들어, 1 나노초 작업 100개를 할 수 있는 시간에 메모리 접근 1회가 드는 것이다.

객체 배열에서 캐시 미스가 증가하는 이유

원시 배열 예시: int[] nums = {1, 2, 3, 4, ...};

메모리 레이아웃:
[주소: 1000] [1][2][3][4][5]...
         연속 저장됨

CPU가 nums[0]을 읽으면 옆의 nums[1], nums[2] 등도 같은 캐시 라인에 실려 캐시로 들어온다. 다음 반복에서 nums[1]을 읽을 때는 이미 캐시에 있으므로 캐시 히트다.

객체 배열 예시: Item[] items = {new Item(...), new Item(...), ...};

배열 레이아웃 (참조들만 연속):
[주소: 1000] [Ref1][Ref2][Ref3]...

실제 객체 위치 (힙에 흩어짐):
[주소: 5000] Item1 데이터
[주소: 8500] Item2 데이터
[주소: 3200] Item3 데이터  ← 캐시 미스!

「캐시 미스!」 표시는 예시로 하나에만 붙였다. Item1 · Item2도 서로 멀리 떨어져 있어 각각 캐시 미스가 날 수 있다. 배열은 연속이지만, 각 참조가 가리키는 실제 객체가 메모리 여기저기에 흩어져 있다. 반복문에서 items[i].price를 읽을 때마다 멀리 떨어진 새 메모리 주소로 건너뛰므로, 미리 가져다 둔 캐시 라인이 도움이 되지 않는다.

성능 측정 예시

아래 코드는 같은 데이터를 두 가지 모양으로 담고 가격 합계를 구하는 시간을 잰다. AoS(Array of Structs)는 필드 여러 개를 한 덩어리(구조체)로 묶고 그 덩어리를 배열로 늘어놓은 모양이다. 자바에는 구조체가 없으니 필드 세 개를 묶은 Item 클래스의 객체 배열이 AoS다. SoA(Struct of Arrays)는 거꾸로 필드마다 배열을 하나씩 둔다.

// AoS (Array of Structs) - 캐시 미스 많음
class Item {
    int id;
    double price;
    long ts;

    Item(int id, double price, long ts) {
        this.id = id;
        this.price = price;
        this.ts = ts;
    }
}
Item[] items = new Item[1000000];
for (int i = 0; i < items.length; i++) {
    items[i] = new Item(i, Math.random() * 1000, System.nanoTime());
}

// 가격 합계 계산 - 캐시 미스 빈번
double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < items.length; i++) {
    sum += items[i].price;  // 매번 객체 참조 → 캐시 미스 가능성
}
System.out.println("AoS time: " + (System.nanoTime() - start) / 1e6 + " ms");

// SoA (Struct of Arrays) - 캐시 미스 적음
int[] ids = new int[1000000];
double[] prices = new double[1000000];
long[] ts = new long[1000000];

// 값 채우기
for (int i = 0; i < 1000000; i++) {
    ids[i] = i;
    prices[i] = Math.random() * 1000;
    ts[i] = System.nanoTime();
}

// 가격 합계 - 메모리 접근이 규칙적
sum = 0;
start = System.nanoTime();
for (int i = 0; i < prices.length; i++) {
    sum += prices[i];  // 항상 연속 메모리 접근 → 캐시 히트 높음
}
System.out.println("SoA time: " + (System.nanoTime() - start) / 1e6 + " ms");

코드 한 줄씩 따라가기. AoS 쪽은 Item 객체 100만 개를 new로 만들어 배열에 담는다(Math.random() * 1000은 0 이상 1000 미만의 임의 가격이다). 그다음 반복문이 items[i].price를 차례로 더한다 — 배열에서 참조를 읽고, 그 참조가 가리키는 객체로 가서 price를 읽는다. SoA 쪽은 ids · prices · ts 세 배열을 따로 만들어 같은 값을 채우고, 합계는 prices 배열 하나만 앞에서부터 읽어 더한다. System.nanoTime()은 현재 시각을 나노초(10억분의 1초) 단위로 돌려주는 메서드다. start에 반복문을 시작하기 직전 시각을 담아 두고, 반복문이 끝난 뒤 System.nanoTime() - start로 그 사이 걸린 나노초를 구한다. 1밀리초는 100만(1e6) 나노초이므로, 그 값을 1e6으로 나누면 밀리초 단위로 바뀐다. AoS 코드와 SoA 코드 각각 이 방식으로 걸린 시간을 잰다.

실제 벤치마크 결과 (ArrayPerformance 기반, 100만 요소):

ArrayPerformance는 이 측정에 쓴 프로그램 이름인데, 그 코드는 이 글에 없다. 특히 첫 줄의 int[] 측정은 위 코드에 없는 측정이라 어떻게 쟀는지 확인하지 않았다. ns/elem은 요소 하나당 걸린 나노초(전체 시간 ÷ 100만)다.

유형 소요시간 ns/elem 상대성능
원시 배열 (int[]) 0.24 ms 0.24 ns 1배 (기준)
SoA (필드별 원시 배열) 1.26 ms 1.26 ns 5.25배 느림
객체 배열 AoS (Item[]) 1.67 ms 1.67 ns 6.96배 느림

분석:

  • 원시 배열: 메모리상 값이 연속 저장되어 캐시 라인 하나에 여러 요소가 실려 온다 → 가장 빠르다
  • SoA: 처음에는 「각 필드가 별도 배열이므로 여러 배열을 읽어야 해서 느리다」고 적었다. 그런데 위 합계 코드는 prices 배열 하나만 읽으므로 이 설명은 코드와 맞지 않는다. SoA 합계 코드도 연속 배열 하나를 읽으니 캐시를 잘 쓰는 모양인 것은 맞고, 실제로 AoS보다는 빨랐다. 그런데도 int[]보다 5배 느렸다. 눈에 띄는 차이는 prices가 double[]이라는 점이다 — double은 8바이트(Double.BYTES가 8)라서 같은 100만 개를 읽어도 int[]의 두 배 메모리를 읽는다. 다만 이것이 5배 차이의 원인인지는 측정 코드가 없어 확인하지 않았다
  • AoS: 객체 참조는 연속이지만 실제 데이터는 힙 곳곳에 흩어져 있다 → 캐시 미스가 잦다

결론: 배열의 “O(1) 접근”은 주소 계산 측면의 복잡도일 뿐, 실제 빠르기는 캐시 지역성에 크게 좌우된다. 지역성에는 두 가지가 있다 — 방금 읽은 칸의 옆 칸을 곧 읽는 공간 지역성(Spatial Locality)과, 방금 읽은 칸을 곧 다시 읽는 시간 지역성(Temporal Locality)이다. 원시 값 배열은 값이 붙어 있어서 저절로 공간 지역성이 좋지만, 객체 배열은 간접 참조 때문에 캐시 미스가 크게 늘 수 있다.

동적 배열 ArrayList의 리사이즈

new ArrayList<>()로 만들면 내부 배열은 빈 배열로 시작하고, 첫 add 때 칸 10개짜리 배열을 할당한다. 그 뒤 배열이 꽉 찬 상태에서 add를 하면 기존의 1.5배 크기 배열을 새로 할당하고 기존 요소를 전부 복사한다(JDK 소스의 grow()가 oldCapacity >> 1, 곧 절반만큼 늘리고 Arrays.copyOf로 옮기며, Arrays.copyOf는 안에서 System.arraycopy를 부른다). 요소 n개를 복사하므로 이 한 번은 O(n)이다. 평소 add는 상각 O(1)이지만, 이 복사 비용을 무시할 수는 없다.

벤치마크 결과 (ArrayListResizingBenchmark 기반, 100만 요소):

이 측정 프로그램의 코드도 이 글에는 없다. 세 줄 모두 add로 100만 개를 넣는 시간이다.

전략 소요시간 상대성능 설명
용량 미할당 (new ArrayList<>()) 46.77 ms 1배 (기준) 리사이즈 반복 → 메모리 할당/복사 오버헤드 누적
ensureCapacity 사용 18.71 ms 2.50배 빠름 사전 확보로 리사이즈 이벤트 최소화
생성자 용량 설정 (new ArrayList<>(1000000)) 11.46 ms 4.08배 빠름 미리 할당 → 리사이즈 0회 → 최고 성능

ensureCapacity와 생성자 용량 설정은 둘 다 미리 자리를 확보하는 방법인데 왜 1.6배쯤 차이가 났는지는, 측정 코드가 없어 확인하지 않았다.

권장사항:

  • 예상 크기를 알 경우: 생성자로 용량 지정 (new ArrayList<>(expectedSize)) - 4배 성능 이득
  • 예상 크기가 정확하지 않을 때: 대략의 어림값 N으로 ensureCapacity(N)을 부른 뒤 한꺼번에 넣는다 - 2.5배 성능 이득
  • 한꺼번에 많이 넣지 않고 가끔 하나씩 넣는 경우: 용량을 미리 잡지 않아도 상각 O(1)이라 충분할 수 있다

LinkedList vs ArrayList vs ArrayDeque

세 구현은 연산에 따라 시간 복잡도부터 다르고(아래 Head 삽입 표의 O(n)과 O(1)), 복잡도가 같은 연산에서도 상수 계수와 캐시 성능 때문에 실제 빠르기가 크게 다르다.

벤치마크 결과 (ListPerformanceBenchmark 기반, 10만 요소 × 1만 회 연산):

이 측정 프로그램의 코드도 이 글에는 없어서, 표마다 어떤 연산을 어떤 순서로 몇 번 했는지는 확인하지 않았다.

Head 삽입 (index 0에 삽입)

구현 소요시간 상대성능 복잡도
ArrayList 157.52 ms 1배 (기준) O(n) - 배열 시프팅(뒤 칸들을 한 칸씩 뒤로 미는 일)
ArrayDeque 3.54 ms 44.5배 빠름 O(1) - 원형 버퍼
LinkedList 1.78 ms 88.5배 빠름 O(1) - 포인터 갱신

양끝 큐 연산 (Queue 패턴)

구현 소요시간 상대성능
ArrayDeque 2.62 ms 1배 (최고)
LinkedList 5.58 ms 2.13배 느림

분석: 앞뒤 끝에서 넣고 빼는 Deque 패턴에서 ArrayDeque가 LinkedList보다 2배 빠르다. ArrayDeque의 원형 버퍼는 배열이라 캐시 친화적이고, LinkedList는 노드마다 참조를 따라가야 하기 때문이다.

랜덤 접근 (get by index)

구현 소요시간 상대성능
ArrayList 1.21 ms 1배 (최고)
LinkedList 612.64 ms 505배 느림

중간 삽입 (random position)

구현 소요시간 상대성능
ArrayList 96.34 ms 1배
LinkedList 1145.14 ms 11.89배 느림

LinkedList의 삽입이 O(1)인 것은 「넣을 자리의 노드를 이미 들고 있을 때」다. 중간의 i번째에 넣으려면 먼저 그 노드까지 찾아가야 한다. JDK 소스의 LinkedList.add(int index, E element)는 node(index)를 부르는데, 이 메서드는 앞이나 뒤 중 가까운 끝에서부터 next(또는 prev)를 하나씩 따라가 i번째 노드를 찾는다. 이 찾아가기가 O(n)이고, 노드가 힙에 흩어져 있어 캐시 미스도 잦다. ArrayList도 뒤 칸을 미는 O(n)이지만 이 측정에서는 12배쯤 빨랐다. JDK 소스의 ArrayList.add(int index, E element)는 뒤 칸 밀기를 System.arraycopy 한 번으로 한다 — 연속된 메모리 덩어리를 통째로 옮기는 일이라, 앞 절에서 본 것처럼 캐시의 도움을 받는다. 반면 LinkedList는 흩어진 노드를 참조로 하나씩 따라간다. 12배 차이가 정확히 이것 때문인지는 재지 않았다.

순회 반복 (iteration)

구현 소요시간 상대성능
ArrayList 5.40 ms 1배 (최고)
LinkedList 29.85 ms 5.53배 느림

종합 권장사항:

사용 패턴 추천 이유
랜덤 접근 주도 ArrayList 500배 이상 빠름
양끝 큐/덱 연산 ArrayDeque LinkedList보다 2배 빠르고 메모리 효율도 우수
첫 위치만 지속 삽입 LinkedList O(1)이나 임의 위치 섞이면 비추천
중간 삽입/삭제 빈번 알고리즘 재설계 표준 List로는 O(n) 불가피

「메모리 효율도 우수」는 이 글에서 잰 값이 아니다. 근거는 구조다 — JDK 소스의 LinkedList는 요소 하나마다 item · next · prev 필드를 가진 Node 객체를 하나씩 더 만들지만, ArrayDeque는 배열 한 칸에 참조 하나만 담는다.

「첫 위치만 지속 삽입」에 ArrayDeque가 아니라 LinkedList를 둔 근거는 위 Head 삽입 표다. 맨 앞에만 넣는 측정에서는 LinkedList(1.78 ms)가 ArrayDeque(3.54 ms)보다 빨랐다. 앞뒤를 섞어 넣고 빼는 큐 연산 표에서는 반대로 ArrayDeque가 빨랐다. 「알고리즘 재설계」는 아래 「결론/팁」의 마지막 줄처럼, 문제를 양끝에서만 넣고 빼도 되는 모양으로 바꾸거나 트리 같은 다른 구조를 쓰는 것을 말한다.

주의: 이론상 복잡도(Big-O)와 실제 빠르기(상수 계수 + 캐시)는 다르다. LinkedList는 O(1) 연산이라도 메모리 간접 참조 때문에 배열보다 느릴 수 있다.

SoA(Struct of Arrays) 리팩터링

AoS(Array of Structs: 객체 배열) 대신 각 필드를 별도의 원시 배열로 나눠, 한 필드만 쭉 읽는 컬럼형 처리를 빠르게 한다.

AoS (Array of Structs) - 캐시 미스 많음

class Item {
    int id;
    double price;
    long ts;

    Item(int id, double price, long ts) {
        this.id = id;
        this.price = price;
        this.ts = ts;
    }
}
Item[] items = new Item[1000000];
// 초기화...

// 특정 필드만 접근
double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < items.length; i++) {
    sum += items[i].price;  // 매번 객체 참조 → 캐시 미스 가능
}
System.out.printf("AoS time: %.2f ms (%.2f ns/elem)\n", 
    (System.nanoTime() - start) / 1e6, 
    (double)(System.nanoTime() - start) / items.length);

SoA (Struct of Arrays) - 캐시 히트 높음

class StructOfArrays {
    int[] ids;
    double[] prices;
    long[] timestamps;

    StructOfArrays(int n) {
        ids = new int[n];
        prices = new double[n];
        timestamps = new long[n];
    }
}

StructOfArrays data = new StructOfArrays(1000000);
// 초기화...

double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < data.prices.length; i++) {
    sum += data.prices[i];  // 연속 메모리 직접 접근 → 캐시 히트
}
System.out.printf("SoA time: %.2f ms (%.2f ns/elem)\n", 
    (System.nanoTime() - start) / 1e6, 
    (double)(System.nanoTime() - start) / data.prices.length);

코드 한 줄씩 따라가기. 두 코드 모두 // 초기화... 자리에서 값을 채운다고 보고 생략했다. AoS는 items[i].price로 객체를 거쳐 가격을 읽고, SoA는 StructOfArrays 생성자가 필드마다 길이 n짜리 배열을 만들어 두고 data.prices[i]로 가격 배열만 읽는다. 마지막 System.out.printf는 형식을 정해 출력하는 메서드다. %.2f 자리에 뒤의 값이 소수점 둘째 자리까지 들어가고, \n은 줄바꿈이다. 첫 값은 밀리초, 두 번째 값은 요소 하나당 나노초다. System.nanoTime()을 두 번 따로 부르므로 두 값은 아주 조금 다른 순간을 기준으로 계산된다.

성능 비교 (100만 요소 기준):

방식 소요시간 ns/elem 상대성능
AoS (Item[]) 1.67 ms 1.67 ns 1배 (기준)
SoA (필드별 배열) 1.26 ms 1.26 ns 1.33배 빠름

분석:

  • AoS: 배열에서 참조를 읽는다 → 그 참조가 가리키는 객체(힙)로 간다 → 객체 시작점에서 price가 몇 바이트 떨어져 있는지(오프셋)를 더한다 → 값을 읽는다 (여러 단계의 메모리 접근, 캐시 미스가 잦다)
  • SoA: 배열 인덱스로 바로 값을 읽는다 (직접 접근, 캐시 히트)
  • 100만 요소 기준 약 410µs 절감 (이런 반복이 쌓여 병목이 된 곳이라면 그 병목을 없앤다)

언제 SoA를 사용할 것인가?

  • 특정 필드만 반복 접근하는 컬럼형 처리
  • 대용량 데이터에서 필드 몇 개만 써서 집계하거나(예: 가격 합계) 골라낼 때(예: 가격이 100 넘는 것만 고르기)
  • 캐시 성능이 중요한 고성능 코드

주의사항:

  • 한 요소의 여러 필드를 함께 읽는 일이 잦으면 AoS가 더 나을 수 있다
  • SoA는 구현이 복잡해진다 (필드별 배열을 따로 관리해야 한다)
  • 메모리 이점: SoA는 읽는 필드의 배열만 메모리에서 가져오면 된다. AoS는 price만 읽어도 같은 객체의 id · ts가 함께 캐시 라인에 실려 올 수 있다

실무 적용 예제

배치 삽입 전 용량 예약

// 방법 1 — 만들 때 용량을 정한다
List<Integer> list = new ArrayList<>(100_000);
for (int i = 0; i < 100_000; i++) list.add(i);

// 방법 2 — 이미 만든 리스트에 나중에 용량을 늘린다
ArrayList<Integer> list2 = new ArrayList<>();
list2.ensureCapacity(100_000);
for (int i = 0; i < 100_000; i++) list2.add(i);

두 방법 중 하나를 쓴다. 100_000은 10만이다 — 자바는 숫자 사이에 밑줄을 넣어 자릿수를 읽기 쉽게 적을 수 있고, 밑줄은 값에 영향이 없다. 방법 1은 처음부터 칸 10만 개짜리 배열을 할당해서 넣는 동안 리사이즈가 일어나지 않는다. 방법 2에서 변수 타입을 List가 아니라 ArrayList로 둔 것은, ensureCapacity가 List 인터페이스에는 없고 ArrayList 클래스에만 있는 메서드라서다. List 타입 변수로 부르면 컴파일 오류가 난다.

덱 패턴 처리

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);
dq.addLast(2);
dq.removeFirst();
dq.removeLast();

한 줄씩 따라가면 덱의 내용은 addFirst(1) 뒤 [1], addLast(2) 뒤 [1, 2], removeFirst() 뒤 [2], removeLast() 뒤 []가 된다. 앞에서도 뒤에서도 넣고 뺄 수 있고, 내부가 원형 버퍼라 어느 쪽이든 요소를 밀지 않는다.

결론/팁

  • 읽기 중심·랜덤 접근: ArrayList + ensureCapacity. 읽기는 ArrayList의 O(1) 인덱스 접근을 쓰고, 읽기 전에 데이터를 채울 때 ensureCapacity로 자리를 미리 잡아 리사이즈를 줄인다는 뜻이다.
  • 양끝 삽입/삭제: ArrayDeque.
  • 첫 위치만 지속 삽입/삭제: LinkedList(임의 위치가 섞이면 비추천).
  • 컬럼형 처리: SoA(필드별 원시 배열) + 필요 시 BitSet.
  • 중간 삽입/삭제가 매우 빈번하고 대용량: 표준 리스트로는 근본적으로 O(n). 양끝에서만 넣고 빼도 되게 문제를 바꿀 수 있으면 덱을 쓰고, 아니면 특화 구조(트리, 스킵 리스트 — 정렬된 데이터를 여러 층의 연결 리스트로 빠르게 찾는 구조, 갭 버퍼 — 커서 위치에 빈 공간을 두어 그 자리에서 삽입·삭제를 빠르게 하는 구조) 고려.

참고 문서(공식)

자신만의 철학을 만들어가는 중입니다.
최상단으로 이동했습니다!
확대 이미지

댓글남기기

다른 포스트

[Concept] 발전소에서 우리 집 220V까지: 자석을 돌려 교류를 만들고 변압기로 전압을 바꾼다

파워 페이지는 「벽 콘센트에서 220V 교류가 들어온다」에서 시작한다. 그 220V가 왜 교류인지, 왜 220V인지는 직류와 교류에서 팠다. 그 글은 「발전기는 돌면서 교류를 만든다」와 「변압기는 감은 수의 비율만큼 전압을 바꾼다」까지만 보고 끝났다. 그 글의 「아직 안 본 것」에...

그래프에서 보기 update 2026-10-23 12:00 - · -