데이터를 가장 효율적으로 담는 구조가 무엇일까? 그것은 ‘배열(Array)‘이다. 배열이 가장 효율적으로 데이터를 담을 수 있는 데이터 구조인 이유는 메모리에 바로 접근(Direct Access)할 수 있기 때문이다.
배열의 가장 핵심적인 특징은 데이터가 메모리 공간에 ‘연속적으로’ 배치된다는 점이다. 정수형(int) 배열을 선언하면 컴퓨터는 전체 크기만큼의 연속된 빈 메모리 공간을 한 번에 확보한다. 데이터가 파편화되어 있지 않기 때문에, 배열은 첫 번째 원소의 시작 주소만 알면 단순한 수식을 통해 나머지 모든 원소의 위치를 즉시 계산해낸다.
시스템 입장에서 이 수학 공식은 x86-64 아키텍처의 LEA (Load Effective Address) 같은 단일 어셈블리 명령어 하나로 직결된다. CPU 내부의 연산 장치는 베이스 레지스터에 저장된 시작 주소에 인덱스와 데이터 크기를 곱해 더하는 작업을 단 한 번의 클럭 사이클 만에 끝낸다. 배열의 인덱스가 1이 아닌 0부터 시작하는 이유 역시, 이 오프셋(Offset) 계산 과정에서 발생하는 불필요한 뺄셈 연산을 없애 CPU의 사이클 낭비를 막기 위한 극단적인 하드웨어 최적화의 결과다.
몰랐던 사실: ‘0x…‘로 시작하는 메모리 주소와 가상 메모리 디버깅 과정에서 메모리 주소를 출력해보면 0x7fff…와 같은 형태를 마주하게 된다. 컴퓨터는 근본적으로 2진수로 데이터를 처리하지만, 이를 사람이 읽기 편하게 2진수 4자리를 1개의 문자로 압축하는 16진수(Hexadecimal)를 사용한다. 주소 앞에 붙는 0x는 단순히 “이 뒤에 오는 문자열은 16진수 숫자입니다"라고 명시하는 프로그래밍 언어의 관례일 뿐이란다..
여기서 중요한 건 우리가 보는 이 주소가 실제 물리적 RAM의 핀 위치가 아니라는 점이다. 이는 OS가 프로세스마다 독립적으로 부여하는 가상 메모리(Virtual Memory) 주소다. 즉, 배열이 ‘연속적이다’라는 말은 가상 메모리 공간에서 연속적이라는 뜻이다. 내부적으로 OS는 이 가상 주소를 물리 주소로 변환해야 하는데, 배열은 데이터가 촘촘히 모여있기 때문에 이 변환 정보를 캐싱해두는 TLB(Translation Lookaside Buffer)의 적중률(Hit Rate)을 극대화한다. 메모리 곳곳에 흩어져 있는 연결 리스트(Linked List) 구조가 페이지(Page) 경계를 넘나들며 TLB Miss를 유발하는 것과 극명히 대비되는 부분이다.
캐시 라인과 프리패칭 단순한 주소 계산을 넘어, 현대 하드웨어 아키텍처에서 배열이 압도적인 성능을 내는 이유는 ‘공간적 지역성(Spatial Locality)‘을 활용한 CPU 캐싱에 있다. CPU는 메인 메모리에서 데이터를 가져올 때 4바이트(int) 단위로 쪼개서 가져오지 않는다. 한 번 접근할 때 보통 64바이트 크기의 캐시 라인(Cache Line) 블록을 통째로 캐시에 올려둔다.
배열의 0번 인덱스 데이터를 읽었다면, 하드웨어는 1번, 2번, 3번 데이터가 포함된 64바이트 블록을 이미 초고속 L1 캐시에 가져다 놓은 상태가 된다. 다음 인덱스를 요청할 때 CPU는 느린 메인 메모리까지 갈 필요 없이 캐시에서 데이터를 즉시 꺼내온다. 더 나아가 현대 CPU의 하드웨어 프리패처(Hardware Prefetcher)는 배열을 순차적으로 읽는 코드 패턴을 스스로 분석하여, 코드가 아직 요청하지도 않은 다음 메모리 블록들을 백그라운드에서 캐시로 미리 끌어다 놓는다. 데이터의 위치를 예측할 수 없는 구조에서는 절대 누릴 수 없다.
배열은 크기가 고정되어 있고 중간에 데이터를 끼워 넣거나 삭제할 때 뒤의 요소들을 모두 밀거나 당겨야 하는 O(n)의 데이터 이동 비용이 발생한다. 하지만 이러한 배열을 담은 메모리의 연속성이 제공하는 O(1) 성능과 CPU 캐시 친화적인 특징 덕분에 배열은 여전히 고성능 소프트웨어를 지탱하는 가장 완벽한 기본 자료구조로 쓰인다. 현대 하드웨어 아키텍처가 메모리의 연속성을 어떻게 다루는지 이해한다면, 배열은 진정 보통놈이 아니다.