- 들어가며 — 같은 복잡도, 다른 속도
- 메모리 계층 — 속도의 절벽
- 캐시 라인 — 캐시는 낱개로 옮기지 않는다
- 데이터 지역성 — 배열 vs 링크드 리스트
- 접근 패턴이 전부다 — 행 우선 vs 열 우선
- 분기 예측 — CPU는 미래를 추측한다
- 거짓 공유 — 보이지 않는 경쟁
- 배열의 구조 — SoA vs AoS
- 예측 가능한 접근 패턴이 핵심이다
- 언제 신경 쓰고 언제 무시할까
- 마치며
- 참고 자료
들어가며 — 같은 복잡도, 다른 속도
알고리즘 수업은 우리에게 시간 복잡도로 코드를 판단하라고 가르칩니다. O(n)은 O(n²)보다 빠르다, 상수 배수는 무시하라. 이 관점은 대체로 옳고 유용합니다. 하지만 실무에서 성능을 파고들다 보면 이상한 벽에 부딪힙니다. 분명 같은 O(n)인데, 한 코드가 다른 코드보다 10배, 때로는 50배 빠릅니다. 두 코드 모두 원소를 한 번씩만 훑는데도 말입니다.
이 차이는 알고리즘이 아니라 하드웨어에서 옵니다. 현대 CPU는 우리가 상상하는 단순한 계산기가 아닙니다. 여러 층의 캐시, 분기를 미리 추측하는 예측기, 여러 명령을 겹쳐 실행하는 파이프라인으로 가득한 복잡한 기계입니다. 이 기계의 작동 방식을 이해하고 그것에 맞춰 코드를 쓰는 태도를 **메커니컬 심퍼시(mechanical sympathy)**라고 부릅니다. 원래 F1 드라이버 재키 스튜어트가 "기계를 이해하는 드라이버가 더 빨리 달린다"는 뜻으로 쓴 말인데, 소프트웨어에도 그대로 적용됩니다.
이 글은 하드웨어에 우호적인 코드가 왜 빠른지, 그리고 어떻게 그런 코드를 쓰는지를 다룹니다. 핵심 주제는 캐시, 데이터 지역성, 분기 예측, 거짓 공유, 그리고 데이터 배치입니다.
메모리 계층 — 속도의 절벽
성능을 이해하는 출발점은 메모리가 하나가 아니라는 사실입니다. CPU와 주 메모리(RAM) 사이에는 여러 층의 캐시가 있고, 각 층은 속도와 크기가 극적으로 다릅니다. 위로 갈수록 빠르고 작으며, 아래로 갈수록 느리고 큽니다.
계층 대략 지연 상대 속도 크기
------------------------------------------------------------
레지스터 ~0.3 ns 1배 (기준) 수백 바이트
L1 캐시 ~1 ns 약 3배 느림 32~64 KB
L2 캐시 ~4 ns 약 10배 느림 256KB~1MB
L3 캐시 ~12 ns 약 40배 느림 수~수십 MB
주 메모리 ~100 ns 약 300배 느림 수~수백 GB
SSD ~100,000 ns 약 30만배 수백 GB~수 TB
이 표에서 가장 중요한 것은 층 사이의 간격이 절벽처럼 가파르다는 점입니다. L1 캐시에서 데이터를 읽는 것과 주 메모리에서 읽는 것은 대략 100배 차이입니다. CPU 입장에서 100ns는 영원과도 같습니다. 그 시간이면 수백 개의 명령을 실행할 수 있으니까요.
이 지연을 사람의 시간 감각으로 비유하면 실감이 납니다.
CPU 1 사이클을 1초라고 하면:
L1 캐시 접근 = 약 3초
L2 캐시 접근 = 약 10초
L3 캐시 접근 = 약 40초
주 메모리 접근 = 약 5분
SSD 접근 = 약 며칠
즉 CPU가 주 메모리를 기다리는 것은, 사람으로 치면 커피 한 잔 하러 갔다 오는 셈입니다. 그래서 현대 성능 최적화의 상당 부분은 "계산을 줄이는 것"이 아니라 "메모리 대기를 줄이는 것", 즉 데이터를 최대한 캐시 안에 두는 것입니다. 계산은 이미 충분히 빠릅니다. 느린 것은 데이터를 가져오는 일입니다.
캐시 라인 — 캐시는 낱개로 옮기지 않는다
캐시를 이해하는 핵심 개념이 캐시 라인(cache line)입니다. CPU가 메모리에서 데이터를 캐시로 가져올 때, 우리가 요청한 그 한 바이트만 가져오는 것이 아닙니다. 대신 그 바이트를 포함하는 고정 크기의 덩어리를 통째로 가져옵니다. 이 덩어리가 캐시 라인이고, 대부분의 현대 CPU에서 64바이트입니다.
int(4바이트) 하나를 요청해도:
메모리: [.. 요청한 int를 포함하는 64바이트 라인 통째로 ..]
|
v
캐시: [64바이트 라인 전체가 올라온다]
즉 근처의 데이터 60바이트도 "덤으로" 캐시에 들어온다
이 사실이 엄청난 결과를 낳습니다. 어떤 데이터에 접근하면, 그 옆에 있던 데이터들이 공짜로 캐시에 함께 올라옵니다. 그래서 메모리에서 서로 가까이 붙어 있는 데이터를 연달아 접근하면, 대부분이 이미 캐시에 있어서 매우 빠릅니다. 반대로 메모리 여기저기에 흩어진 데이터를 접근하면, 매번 새 캐시 라인을 가져와야 해서 느립니다.
이것이 다음에 이야기할 데이터 지역성의 물리적 근거입니다. "가까이 있는 데이터를 연달아 쓰라"는 조언은 결국 "캐시 라인 하나로 여러 번 재미를 보라"는 뜻입니다.
데이터 지역성 — 배열 vs 링크드 리스트
데이터 지역성의 힘을 가장 극명하게 보여주는 예가 배열과 링크드 리스트의 비교입니다. 교과서적으로 둘은 트레이드오프가 있습니다. 배열은 임의 접근이 빠르고 삽입이 느리며, 링크드 리스트는 삽입이 빠르고 임의 접근이 느립니다. 하지만 실제 순회 성능을 재보면, 링크드 리스트가 배열보다 훨씬 느린 경우가 많습니다. 심지어 삽입/삭제가 잦은 상황에서도 배열이 이기는 일이 흔합니다. 이유는 캐시입니다.
배열: 원소가 메모리에 연속으로 붙어 있다
[e0][e1][e2][e3][e4][e5][e6][e7] ...
└── 캐시 라인 하나에 여러 원소가 함께 온다 ──┘
순회 시 대부분 캐시 히트 → 빠름
링크드 리스트: 노드가 메모리 여기저기 흩어져 있다
[node2] ......... [node0] ..... [node3] ... [node1]
각 노드로 갈 때마다 포인터를 따라 점프
대부분 캐시 미스 → 느림 (매번 메모리 왕복)
배열은 원소들이 메모리에 연속으로 배치됩니다. 그래서 배열을 처음부터 끝까지 훑으면, 캐시 라인 하나가 여러 원소를 담아 오므로 대부분의 접근이 캐시 히트입니다. 게다가 CPU는 이 순차적 패턴을 감지해 다음에 필요할 데이터를 미리 가져오는 프리페치(prefetch)까지 합니다.
링크드 리스트는 다릅니다. 각 노드는 힙 여기저기에 흩어져 할당되고, 노드끼리는 포인터로만 연결됩니다. 그래서 리스트를 순회하려면 포인터를 따라 메모리의 이곳저곳으로 점프해야 합니다. 노드마다 새 캐시 라인을 가져와야 하고, 심지어 다음 노드가 어디 있는지는 현재 노드를 읽어야만 알 수 있어서 프리페치도 어렵습니다. 결과는 캐시 미스의 연속입니다.
핵심 교훈은 이것입니다. 빅오 표기법은 접근 횟수만 세지만, 실제 속도는 그 접근이 캐시 히트인지 미스인지에 크게 좌우됩니다. 순차적으로 순회하는 작업이라면, 연속 메모리를 쓰는 배열(또는 벡터, 동적 배열)이 대부분 승리합니다.
접근 패턴이 전부다 — 행 우선 vs 열 우선
같은 데이터라도 어떤 순서로 접근하느냐에 따라 속도가 크게 갈립니다. 2차원 배열을 순회하는 고전적인 예를 봅시다. 대부분의 언어(C, 파이썬 넘파이 기본 등)는 2차원 배열을 행 우선(row-major)으로 메모리에 저장합니다. 즉 한 행의 원소들이 메모리에 연속으로 놓입니다.
import numpy as np
A = np.zeros((10000, 10000))
# 방식 1: 행 우선으로 순회 (메모리 순서와 일치)
total = 0.0
for i in range(10000):
for j in range(10000):
total += A[i][j] # 안쪽 루프가 연속 메모리를 훑는다 → 빠름
# 방식 2: 열 우선으로 순회 (메모리 순서와 어긋남)
total = 0.0
for j in range(10000):
for i in range(10000):
total += A[i][j] # 매 접근이 한 행 크기만큼 점프 → 캐시 미스 폭증
두 코드는 정확히 같은 원소를, 정확히 같은 횟수만큼 더합니다. 알고리즘적으로 완전히 동일합니다. 그런데 실제로는 방식 1이 방식 2보다 몇 배 빠릅니다. 언어와 크기에 따라 5배에서 10배 이상 차이가 나기도 합니다.
이유는 캐시 라인입니다. 방식 1은 안쪽 루프가 메모리에 연속으로 놓인 한 행을 순서대로 훑으므로, 캐시 라인 하나가 여러 원소를 담아 와 대부분 히트합니다. 방식 2는 안쪽 루프가 열을 따라 내려가는데, 행 우선 저장에서 같은 열의 원소들은 메모리상 한 행 크기(여기서는 1만 개)만큼 떨어져 있습니다. 그래서 접근마다 새 캐시 라인을 가져와야 하고, 가져온 라인의 나머지 63바이트는 쓰이지도 못한 채 버려집니다.
교훈은 명확합니다. 데이터를 저장된 순서대로 접근하라. 다차원 배열이라면 메모리 레이아웃(행 우선인지 열 우선인지)을 알고, 가장 안쪽 루프가 연속 메모리를 훑도록 루프 순서를 맞춰야 합니다. 이 단순한 원칙 하나가 종종 어떤 알고리즘 개선보다 큰 성능 향상을 줍니다.
분기 예측 — CPU는 미래를 추측한다
현대 CPU가 빠른 또 하나의 비결은 파이프라이닝입니다. CPU는 명령을 하나 끝내고 다음을 시작하는 것이 아니라, 여러 명령을 조립 라인처럼 겹쳐서 처리합니다. 그런데 여기에 문제가 있습니다. if 같은 분기를 만나면, CPU는 조건의 결과가 나오기 전에 "다음에 어느 쪽 명령을 파이프라인에 넣을지" 결정해야 합니다.
그래서 CPU는 분기 예측기(branch predictor)를 씁니다. 과거의 패턴을 보고 "이번 분기는 아마 참(또는 거짓)일 것"이라고 추측해, 그쪽 명령을 미리 파이프라인에 채워 실행을 시작합니다. 추측이 맞으면 아무 손해 없이 빠르게 진행합니다. 하지만 틀리면, 미리 채워 실행하던 명령들을 전부 버리고(파이프라인 플러시) 올바른 쪽부터 다시 시작해야 합니다. 이 벌칙이 수십 사이클에 달합니다.
이 사실은 유명한 관찰로 이어집니다. 정렬된 데이터를 처리하는 것이 정렬되지 않은 데이터를 처리하는 것보다 빠를 수 있다는 것입니다.
# 큰 배열에서 임계값보다 큰 값만 합산
threshold = 128
total = 0
for x in data:
if x >= threshold: # 이 분기의 예측 가능성이 속도를 좌우한다
total += x
만약 data가 정렬되어 있다면, 이 분기는 한동안 계속 거짓이다가 어느 지점부터 계속 참이 됩니다. 예측기는 이 규칙적인 패턴을 쉽게 학습해 거의 항상 맞힙니다. 반대로 data가 무작위라면, 분기 결과가 예측 불가능하게 튀어서 예측기가 절반쯤 틀립니다. 매 오예측마다 파이프라인이 플러시되어, 같은 코드가 몇 배 느려질 수 있습니다.
여기서 얻는 실무적 통찰이 몇 가지 있습니다. 첫째, 예측 가능한 분기는 싸고 예측 불가능한 분기는 비쌉니다. 둘째, 때로는 분기 자체를 없애는 것(분기 없는 코드, branchless)이 유리합니다. 예를 들어 조건에 따라 값을 더할지 말지를, 분기 대신 산술로 표현하면 오예측 벌칙을 피할 수 있습니다.
# 분기 대신 산술로 (오예측 없음)
# (x >= threshold) 는 True/False = 1/0 으로 취급됨
total += x * (x >= threshold)
물론 분기 없는 코드가 항상 빠른 것은 아니고, 가독성을 해칠 수 있으므로 무조건 적용할 것은 아닙니다. 핵심은 뜨거운 루프(hot loop) 안의 예측 불가능한 분기가 숨은 성능 도둑일 수 있다는 인식입니다.
거짓 공유 — 보이지 않는 경쟁
멀티스레드 코드에서 특히 교묘한 성능 함정이 거짓 공유(false sharing)입니다. 여러 스레드가 서로 다른 변수를 각자 수정하고 있어서 논리적으로는 아무 충돌이 없는데도, 성능이 급격히 떨어지는 현상입니다. 범인은 다시 캐시 라인입니다.
앞서 봤듯 캐시는 64바이트 라인 단위로 움직입니다. 그런데 CPU 코어마다 자기 캐시가 있고, 여러 코어가 같은 데이터를 캐시할 때는 일관성(coherence)을 유지해야 합니다. 한 코어가 어떤 캐시 라인을 수정하면, 다른 코어가 가진 같은 라인의 사본은 무효화(invalidate)됩니다.
문제는 서로 다른 변수라도 우연히 같은 캐시 라인 안에 있으면, 마치 같은 데이터를 두고 다투는 것처럼 취급된다는 것입니다.
스레드 A가 counter[0]을, 스레드 B가 counter[1]을 수정한다고 하자.
두 변수가 같은 64바이트 캐시 라인 안에 있으면:
[ counter[0] | counter[1] | ... 같은 64바이트 라인 ... ]
^A 수정 ^B 수정
A가 쓸 때마다 B의 캐시 라인이 무효화되고,
B가 쓸 때마다 A의 캐시 라인이 무효화된다.
두 스레드는 논리적으로 독립인데도 캐시 라인을 핑퐁하며 서로를 느리게 만든다.
이것이 거짓 공유입니다. 진짜로 데이터를 공유하는 것이 아니라(각자 다른 변수), 캐시 라인을 공유하기 때문에 생기는 가짜 경쟁입니다. 증상은 고약합니다. 코드는 완벽히 정확하게 동작하지만, 스레드를 늘려도 성능이 오르지 않거나 오히려 떨어집니다.
해결책은 문제의 변수들을 서로 다른 캐시 라인으로 밀어내는 것입니다. 흔히 패딩(padding)을 넣어 각 스레드의 데이터가 독립된 캐시 라인을 차지하게 만듭니다.
해결: 각 스레드의 데이터 사이에 패딩을 넣어 라인을 분리
[ counter[0] + 패딩(라인 채움) ][ counter[1] + 패딩 ]
스레드 A 전용 라인 스레드 B 전용 라인
이제 서로의 라인을 건드리지 않으므로 핑퐁이 사라진다
거짓 공유는 눈에 잘 안 보여서 진단이 까다롭습니다. 멀티스레드로 만들었는데 확장이 안 된다면, 스레드들이 만지는 데이터가 우연히 같은 캐시 라인에 몰려 있지 않은지 의심해 볼 만합니다.
배열의 구조 — SoA vs AoS
데이터를 메모리에 어떻게 배치하느냐를 설계 수준에서 다루는 주제가 배열의 구조체(Array of Structures, AoS)와 구조체의 배열(Structure of Arrays, SoA)입니다. 같은 데이터를 담더라도 이 둘은 캐시 효율이 크게 다릅니다.
AoS는 우리가 자연스럽게 떠올리는 방식입니다. 각 개체를 구조체로 만들고, 그 구조체들을 배열에 담습니다.
AoS (구조체의 배열):
struct Particle { float x, y, z; float mass; ... };
Particle particles[N];
메모리: [x0 y0 z0 m0][x1 y1 z1 m1][x2 y2 z2 m2] ...
한 입자의 모든 필드가 붙어 있다
SoA는 반대로, 필드별로 따로 배열을 만듭니다.
SoA (배열의 구조체):
struct Particles { float x[N]; float y[N]; float z[N]; float mass[N]; };
메모리: [x0 x1 x2 x3 ...][y0 y1 y2 ...][z0 z1 z2 ...] ...
같은 필드끼리 연속으로 붙어 있다
왜 이 차이가 중요할까요. 어떤 작업이 특정 필드만 대량으로 훑는 경우를 생각해 봅시다. 예를 들어 모든 입자의 x 좌표만 갱신하는 물리 시뮬레이션 루프가 있다고 합시다.
AoS에서는 x 좌표들이 메모리상 서로 떨어져 있습니다(사이에 y, z, mass가 끼어 있으니까). 그래서 x만 훑어도 캐시 라인에는 안 쓰는 y, z, mass가 함께 딸려 오고, 캐시 공간이 낭비됩니다. 반면 SoA에서는 x 좌표들이 한 배열에 연속으로 붙어 있어서, 캐시 라인이 x로만 꽉 차 옵니다. 캐시가 알뜰하게 쓰이고 순차 접근이라 프리페치도 잘 됩니다. 또한 SoA는 SIMD(한 명령으로 여러 데이터 처리) 벡터화에도 유리합니다.
x 좌표만 대량 처리할 때:
AoS: 캐시 라인에 x 하나 + 낭비되는 y,z,mass → 캐시 효율 낮음
SoA: 캐시 라인이 x 로만 꽉 참 → 캐시 효율 높음, SIMD 친화적
다만 SoA가 항상 옳은 것은 아닙니다. 한 개체의 모든 필드를 한꺼번에 자주 다룬다면(예: 입자 하나를 통째로 읽어 처리), AoS가 오히려 그 개체의 필드들을 한 캐시 라인에 모아 두어 유리합니다. 핵심은 접근 패턴입니다. "필드 단위로 훑는가, 개체 단위로 훑는가"를 보고 배치를 정해야 합니다. 게임 엔진, 물리 엔진, 데이터 처리 시스템에서 SoA가 자주 선택되는 이유는, 이런 시스템의 뜨거운 루프가 대개 특정 필드만 대량으로 훑기 때문입니다.
예측 가능한 접근 패턴이 핵심이다
지금까지의 이야기를 관통하는 하나의 원리가 있습니다. CPU와 캐시는 예측 가능한 순차적 접근을 사랑하고, 무작위적이고 흩어진 접근을 싫어한다는 것입니다.
CPU에는 하드웨어 프리페처(prefetcher)가 있습니다. 이것은 메모리 접근 패턴을 관찰하다가, 규칙적인 순차 접근을 감지하면 다음에 필요할 데이터를 미리 캐시로 끌어옵니다. 그래서 배열을 순서대로 훑는 것 같은 예측 가능한 패턴에서는, 데이터가 필요해지기 전에 이미 캐시에 도착해 있습니다. 프리페처의 도움으로 메모리 지연이 거의 숨겨집니다.
반대로 접근이 무작위이면 프리페처가 패턴을 못 읽어 도움을 주지 못합니다. 포인터를 이리저리 따라가는 자료구조(링크드 리스트, 트리, 해시 테이블의 체이닝)나, 인덱스가 뒤죽박죽인 접근은 프리페처를 무력화합니다.
여기서 실무 원칙들을 정리할 수 있습니다.
- 순차적으로 접근하라. 가능하면 데이터를 저장된 순서대로 훑어라.
- 연속 메모리를 선호하라. 흩어진 노드보다 연속된 배열이 캐시와 프리페처 모두에 유리하다.
- 접근 패턴에 맞게 데이터를 배치하라. 자주 함께 쓰는 데이터는 가까이(같은 캐시 라인에) 두고, 필드 단위로 훑으면 SoA를 고려하라.
- 뜨거운 루프의 분기를 예측 가능하게 만들어라. 필요하면 정렬하거나 분기를 없애라.
- 멀티스레드에서는 거짓 공유를 피하라. 스레드별 데이터를 다른 캐시 라인으로 분리하라.
이 원칙들은 모두 하나의 태도로 수렴합니다. 코드를 짤 때 데이터가 메모리에서 어떻게 배치되고 어떤 순서로 접근되는지를 의식하는 것. 그것이 메커니컬 심퍼시의 실천입니다.
언제 신경 쓰고 언제 무시할까
여기까지 읽고 "그럼 모든 코드를 이렇게 최적화해야 하나" 싶을 수 있지만, 그렇지 않습니다. 메커니컬 심퍼시는 항상 적용하는 규칙이 아니라, 필요할 때 꺼내 쓰는 도구입니다.
대부분의 코드는 성능이 병목이 아닙니다. 가독성과 정확성이 훨씬 중요하고, 섣부른 저수준 최적화는 코드를 복잡하게 만들 뿐입니다. 도널드 커누스의 유명한 말처럼 "섣부른 최적화는 모든 악의 근원"입니다. 그래서 첫 번째 원칙은 언제나 측정입니다. 프로파일러로 실제 뜨거운 지점을 찾고, 거기에만 집중해야 합니다.
메커니컬 심퍼시가 진짜 중요해지는 곳은 명확합니다. 방대한 데이터를 반복 처리하는 뜨거운 루프, 게임·물리·그래픽스의 실시간 렌더링, 고빈도 거래나 대규모 데이터 처리처럼 지연이 곧 비용인 시스템입니다. 이런 곳에서는 알고리즘 복잡도를 이미 다듬은 뒤에도 캐시 최적화로 몇 배의 추가 이득을 얻을 수 있습니다.
균형 잡힌 태도는 이렇습니다. 평소에는 명확하고 단순한 코드를 쓰되, 하드웨어가 어떻게 동작하는지는 이해하고 있는 것. 그래야 정말 성능이 필요한 순간에, 어디를 어떻게 손봐야 할지 알 수 있습니다. 메커니컬 심퍼시는 모든 코드에 적용하는 강박이 아니라, 필요한 순간에 발휘하는 안목입니다.
마치며
같은 시간 복잡도의 코드가 실제로는 수십 배 차이 나는 이유는, 컴퓨터가 교과서 속 추상적 계산기가 아니라 캐시와 파이프라인과 예측기로 가득한 물리적 기계이기 때문입니다. 메모리 계층에는 속도의 절벽이 있고, 캐시는 라인 단위로 움직이며, 데이터 지역성이 순회 속도를 좌우하고, 분기 예측이 뜨거운 루프의 성패를 가르며, 거짓 공유가 멀티스레드의 확장을 가로막고, 데이터 배치(AoS와 SoA)가 캐시 효율을 결정합니다.
메커니컬 심퍼시는 이 기계의 마음을 헤아려 코드를 쓰는 태도입니다. 데이터를 연속으로 두고, 순차적으로 접근하고, 분기를 예측 가능하게 하고, 접근 패턴에 맞춰 배치하는 것. 이 모든 것은 결국 "하드웨어가 좋아하는 방식으로 데이터를 다루라"는 하나의 원리로 요약됩니다.
빅오 표기법은 여전히 소중한 출발점입니다. 하지만 그것만으로는 설명되지 않는 성능의 세계가 그 아래에 있습니다. 그 세계를 이해하는 개발자는, 같은 알고리즘으로도 훨씬 빠른 코드를 씁니다. 기계를 이해하는 드라이버가 더 빨리 달리듯이 말입니다.
참고 자료
- Mechanical Sympathy (Martin Thompson 블로그): https://mechanical-sympathy.blogspot.com/
- What Every Programmer Should Know About Memory (Ulrich Drepper): https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
- Latency Numbers Every Programmer Should Know: https://gist.github.com/jboner/2841832
- Data-Oriented Design (Richard Fabian): https://www.dataorienteddesign.com/dodbook/
- Agner Fog — Software optimization resources: https://www.agner.org/optimize/
현재 단락 (1/124)
알고리즘 수업은 우리에게 시간 복잡도로 코드를 판단하라고 가르칩니다. O(n)은 O(n²)보다 빠르다, 상수 배수는 무시하라. 이 관점은 대체로 옳고 유용합니다. 하지만 실무에서 ...