7.1 CPU와 파이프라인 — CPU는 코드를 순서대로 실행하지 않는다

명령어 수가 거의 같은 두 코드의 실행 시간이 수 배 갈리는 이유는 대부분 명령어의 개수가 아니라 흐름 — 분기 예측이 파이프라인을 채우는 데 성공하는가, 명령어들이 서로를 기다리는가 — 에 있다. 이 문서는 파이프라인·분기 예측·비순차 실행의 동작 모델을 세우고, 그 모델로 두 실측(정렬 여부만 다른 조건 합산, 누산기 개수만 다른 합산)의 수 배 차이를 진단한다.

학습 목표

• ISA와 마이크로아키텍처를 계약과 구현으로 구분하고, 같은 바이너리가 CPU 세대마다 다르게 수행되는 이유를 설명한다.
• 파이프라인 해저드(데이터·제어)와 분기 예측, 비순차 실행이 각각 어떤 성능 현상을 만드는지 설명한다.
• 정렬 여부에 따른 조건 합산의 시간 차이를 분기 예측 실패로, 누산기 분리의 효과를 의존 체인 완화로 진단하는 대조 실험을 설계한다.
• cycles·instructions·IPC·branch-misses를 함께 읽어 낮은 IPC의 경쟁 원인(프론트엔드 정체, 분기 실패, 의존 체인, 메모리 대기)을 좁힌다.
• branchless 변환이 이기는 조건과 지는 조건을 판별한다.

배경: 왜 이것이 존재하는가

명령어 하나를 처리하는 일은 여러 단계로 나뉜다 — 가져오고(fetch), 해석하고(decode), 실행하고(execute), 메모리에 접근하고, 결과를 기록한다. 한 명령어가 모든 단계를 마친 뒤에야 다음 명령어를 시작하는 설계는 회로 대부분이 늘 놀고 있다는 뜻이다. 세탁기와 건조기를 순서대로 쓰면서 세탁이 끝날 때까지 건조기를 비워 두는 것과 같다.

1990년대 이후의 모든 범용 CPU는 이 낭비를 세 방향으로 공격했다. 단계를 겹치고(파이프라인), 한 사이클에 여러 명령어를 발행하고(슈퍼스칼라), 순서에 묶이지 않고 준비된 명령어부터 실행한다(비순차 실행). 클럭 주파수가 발열 한계에 부딪힌 2000년대 중반 이후, 단일 코어 성능 향상의 대부분은 이 "겹치기"의 정교화에서 나왔다.

문제는 이 모든 장치가 소스 코드에 보이지 않는다는 것이다. 하드웨어는 순차 실행과 같은 결과를 보장하도록 설계되어 있으므로, 정확성 관점에서는 몰라도 된다. 그러나 성능 관점에서는 이 장치들이 언제 헛돌기 시작하는지가 곧 병목의 위치다. 1.1에서 명령어 수 기반 비용 모델(RAM 모델)이 실측과 수 배씩 어긋나는 것을 관찰했는데, 그 어긋남의 절반이 이 문서에 있다(나머지 절반인 메모리 계층은 7.2가 다룬다).

핵심 개념

ISA와 마이크로아키텍처 — 계약과 구현

ISA(Instruction Set Architecture)는 소프트웨어와 하드웨어 사이의 계약이다. 어떤 명령어가 존재하고, 각 명령어가 아키텍처 상태(레지스터, 메모리)를 어떻게 바꾸는지 정의한다. x86-64, ARMv8(AArch64), RISC-V가 ISA다. 마이크로아키텍처(microarchitecture)는 그 계약의 구현이다 — 파이프라인 단수, 실행 유닛 수, 분기 예측기, 캐시 구성. Intel의 세대별 코어, AMD Zen, Apple M 시리즈는 각각 다른 마이크로아키텍처다.

이 구분이 중요한 이유는 두 가지다. 첫째, 같은 바이너리가 CPU마다 다른 성능 특성을 보이는 이유가 여기에 있다. 계약은 같지만 구현(예측기의 정확도, 동시 발행 폭, 캐시 크기)이 다르기 때문이다. 둘째, ISA가 보장하는 것은 관찰 가능한 아키텍처 상태의 순차적 일관성뿐이다. 그 결과를 만들기 위해 내부에서 명령어를 어떤 순서로, 몇 개씩, 얼마나 투기적으로 실행하는지는 전적으로 구현의 자유다. "CPU는 코드를 순서대로 실행한다"는 문장은 계약 수준에서만 참이다.

파이프라인 — 처리량과 지연의 분리, 그리고 해저드

파이프라인은 명령어 처리를 단계로 나눠 서로 다른 명령어의 서로 다른 단계를 같은 사이클에 겹친다. 5단계 파이프라인이 꽉 차 있으면 각 명령어의 지연(latency, 시작부터 완료까지)은 5사이클이지만 처리량(throughput)은 사이클당 1명령어다. 현대 고성능 코어의 파이프라인은 십수~수십 단계다.

파이프라인이 약속대로 흐르지 못하는 상황이 해저드(hazard)다.

• 데이터 해저드: 뒤 명령어가 앞 명령어의 결과를 입력으로 쓴다. b = a + 1; c = b * 2;에서 곱셈은 덧셈의 결과가 나올 때까지 진행할 수 없다. 우회 경로(forwarding)로 완화하지만, 의존 자체는 사라지지 않는다.
• 제어 해저드: 분기 명령어의 결과(어느 쪽으로 갈지)가 나오기 전까지, 다음에 가져올 명령어의 주소를 모른다. 파이프라인 앞단은 분기 결과가 확정되기 한참 전에 다음 명령어를 가져와야 하므로, 기다리면 그만큼 파이프라인에 거품이 생긴다.

분기 예측 — 기다리는 대신 베팅한다

제어 해저드에 대한 현대 CPU의 답은 기다리지 않는 것이다. 분기 예측기(branch predictor)가 과거 이력으로 분기 방향을 예측하고, 파이프라인은 예측된 경로의 명령어를 투기적으로(speculatively) 실행한다. 예측이 맞으면 비용은 사실상 0이다. 틀리면 잘못 가져온 명령어들을 전부 버리고(파이프라인 플러시) 올바른 경로에서 다시 시작한다 — 이 비용이 대략 십수~이십 사이클 자릿수다.

현대 예측기는 루프 종료 조건, 고정 패턴, 상관관계가 있는 분기를 매우 잘 학습해서 통상적인 코드의 예측 적중률은 95%를 훌쩍 넘는다. 예측기가 무력해지는 것은 분기 방향이 데이터의 무작위성을 그대로 따를 때다. 방향에 패턴이 없으면 어떤 이력 기반 예측기도 동전 던지기보다 나을 수 없다.

관찰 1 — 같은 코드, 데이터 순서만 바꿨더니 5배

고전 사례를 직접 재현한다. 0~255 값 1,600만 개에서 128 이상만 합산한다. 코드는 완전히 같고, 데이터가 정렬되어 있는지만 다르다. branchless 버전(조건을 마스크 산술로 변환)을 세 번째 후보로 추가한다. 측정 하네스는 1.1의 harness.mjs를 같은 디렉터리에 두고 사용한다.

// branch.mjs — node branch.mjs 로 실행 (harness.mjs 필요)
import { bench } from './harness.mjs';

const N = 1 << 24; // 16Mi 원소

const random = new Int32Array(N);
for (let i = 0; i < N; i++) random[i] = (Math.random() * 256) | 0;
const sorted = Int32Array.from(random).sort();

let sink = 0;

function branchSum(data) {
  let sum = 0;
  for (let i = 0; i < data.length; i++) {
    if (data[i] >= 128) sum += data[i];
  }
  return sum;
}

function branchlessSum(data) {
  let sum = 0;
  for (let i = 0; i < data.length; i++) {
    const v = data[i];
    sum += v & -(v >= 128); // 참이면 -1(전체 비트 1) 마스크, 거짓이면 0
  }
  return sum;
}

bench('branch, sorted    ', () => { sink = branchSum(sorted); });
bench('branch, random    ', () => { sink = branchSum(random); });
bench('branchless, sorted', () => { sink = branchlessSum(sorted); });
bench('branchless, random', () => { sink = branchlessSum(random); });
console.log('checksum', sink);

측정 전에 확인할 것이 있다. 이 실험의 독립 변수는 "분기의 예측 가능성"인데, JIT이 분기를 조건부 이동(x86의 cmov, ARM의 csel)이나 벡터 명령으로 바꿔 버리면 변수 자체가 사라진다. Node.js 공식 빌드는 node --print-opt-code로 TurboFan이 생성한 기계어를 볼 수 있다. 이 환경(arm64)에서 branchSum의 최적화 코드에는 조건부 분기(b.ge)가 그대로 남아 있었다 — 실험은 유효하다. 결과는 다음과 같다(Node.js v24.14.0/V8 13.6, Apple M5 Pro, macOS 26.5).

측정 대상	중앙값	원소당
분기, 정렬	9.31 ms	0.55 ns
분기, 무작위	46.46 ms	2.77 ns
branchless, 정렬	7.62 ms	0.45 ns
branchless, 무작위	7.80 ms	0.46 ns

읽는 법: 분기 버전은 데이터 순서에 따라 5배 갈린다. 정렬된 데이터에서는 분기 방향이 "앞 절반은 거짓, 뒤 절반은 참"이라는 완벽한 패턴이라 예측기가 사실상 전부 맞힌다. 무작위 데이터에서는 절반이 예측 실패다. 차이 37.15ms를 예측 실패 횟수(약 절반인 840만 회)로 나누면 실패당 약 4.4ns — 4GHz대 클럭으로 환산하면 십수~이십 사이클로, 파이프라인 플러시 비용의 자릿수와 일치한다. branchless 버전은 분기가 없으므로 데이터 순서와 무관하게 일정하고, 무작위 데이터에서는 6배 승리지만 정렬된 데이터에서는 개선이 미미하다. 예측이 잘 되는 분기는 거의 공짜이기 때문이다.

주의할 것: 이것은 상관관계가 강하게 원인을 시사하는 실험이지, 아직 카운터로 입증한 것은 아니다. Linux라면 같은 구조의 C 구현에 perf stat -e branches,branch-misses를 붙여 무작위 버전에서 branch-misses가 원소 수의 절반 규모로 튀는 것을 직접 확인할 수 있다(아래 측정 어휘 절). 이때 C 컴파일러는 V8보다 공격적이라 실험이 더 쉽게 무효화된다 — 이 환경의 Apple clang 21은 같은 루프를 -O2에서 NEON 벡터 명령(uaddw 등)으로 바꿔 분기를 완전히 제거했고, -fno-vectorize를 줘야 csel(그래도 분기 없음)이, 조건 누적이 더 복잡한 형태여야 실제 분기가 남는다. 시간을 재기 전에 생성 코드(clang -O2 -S, Compiler Explorer)에서 분기·cmov/csel·벡터 중 무엇이 만들어졌는지 확인하는 절차가 이 실험의 일부인 이유다.

슈퍼스칼라와 비순차 실행 — 독립성이 곧 속도다

파이프라인이 단계를 겹친다면, 슈퍼스칼라(superscalar)는 폭을 늘린다. 현대 고성능 코어는 한 사이클에 명령어를 4~8개씩 해석·발행할 수 있다. 그런데 프로그램 순서대로만 발행하면 앞 명령어가 캐시 미스로 막히는 순간 뒤의 모든 명령어가 함께 선다. 비순차 실행(out-of-order execution)은 이를 해결한다 — 수백 개 명령어를 미리 들여다보는 창(instruction window)을 유지하고, 피연산자가 준비된 명령어부터 실행한 뒤, 결과는 프로그램 순서대로 커밋해 순차 의미론을 지킨다. 같은 레지스터 이름을 재사용해서 생기는 가짜 의존은 레지스터 리네이밍(register renaming)이 물리 레지스터를 새로 배정해 제거한다.

이 기계 전체의 연료는 명령어 수준 병렬성(ILP, instruction-level parallelism), 즉 서로 의존하지 않는 명령어의 공급이다. 코드가 긴 의존 체인 하나로 되어 있으면, 발행 폭이 8이어도 실행은 체인의 지연 시간에 묶여 직렬화된다.

관찰 2 — 누산기를 쪼갰더니 2.5배

합산 루프의 의존 체인을 대조 실험으로 분리한다. 부동소수점 덧셈은 결합법칙이 성립하지 않아 JIT이 누산 순서를 바꿀 수 없으므로, 의존 구조가 코드에 쓴 그대로 유지된다.

// ilp.mjs — node ilp.mjs 로 실행 (harness.mjs 필요)
import { bench } from './harness.mjs';

const N = 1 << 24;
const data = new Float64Array(N);
for (let i = 0; i < N; i++) data[i] = Math.random();

let sink = 0;

function sum1(a) {
  let s = 0;
  for (let i = 0; i < a.length; i++) s += a[i]; // 모든 덧셈이 한 체인
  return s;
}

function sum4(a) {
  let s0 = 0, s1 = 0, s2 = 0, s3 = 0;
  for (let i = 0; i < a.length; i += 4) {
    s0 += a[i];     // 네 체인이 서로 독립
    s1 += a[i + 1];
    s2 += a[i + 2];
    s3 += a[i + 3];
  }
  return s0 + s1 + s2 + s3;
}

bench('1 accumulator ', () => { sink = sum1(data); });
bench('4 accumulators', () => { sink = sum4(data); });
console.log('checksum', sink);

같은 환경의 결과: 단일 누산기 9.12ms, 누산기 4개 3.66ms — 2.5배 차이다. sum4는 명령어 수가 더 많다(루프 오버헤드는 줄지만 누산 변수 관리가 늘어난다). 그런데도 이긴다. sum1의 모든 덧셈은 직전 덧셈의 결과를 기다리는 하나의 체인이라, 처리 속도의 상한이 "부동소수점 덧셈 지연 × 원소 수"로 묶인다. sum4는 독립 체인이 4개라 비순차 실행 엔진이 덧셈 4개를 겹칠 수 있다. "명령어 수가 적은 코드가 빠르다"는 통념이 깨지는 지점이다 — IPC가 지배하는 구간에서는 명령어가 많아도 의존이 얕은 쪽이 이긴다.

두 관찰을 합치면 ch-1의 147배 실측 중 이 문서 몫의 절반이 설명된다. 연결 리스트 순회 node = node.next는 다음 로드의 주소가 직전 로드의 결과인 극단적 의존 체인이다. 분기 예측이 아무리 정확하고 발행 폭이 아무리 넓어도, 주소를 모르는 로드는 시작할 수 없다. 비순차 실행조차 숨길 수 없는 이 메모리 지연이 얼마나 큰지는 7.2에서 계층별 수치로 확인한다.

측정 어휘 — cycles, instructions, IPC, branch-misses

하드웨어 성능 카운터(PMU)는 이 문서의 모델을 검증하는 표준 도구다. Linux의 perf가 대표 인터페이스다(macOS는 PMU 접근이 제한적이라, 카운터 검증은 Linux 실기·VM 기준이다).

# 널리 지원되는 공통 이벤트만 사용한 기본 프로파일
perf stat -e cycles,instructions,branches,branch-misses ./a.out

카운터	말하는 것	말하지 못하는 것
cycles	소모한 시간(클럭 단위)	그 시간에 무엇을 기다렸는지
instructions	완료(retire)된 명령어 수	명령어당 실제 일의 양, 투기로 버려진 실행량
IPC (insn/cycle)	실행 자원이 얼마나 채워졌는지의 종합 지표	낮은 이유 — 분기 실패, 의존 체인, 프론트엔드 정체, 메모리 대기를 구분하지 못한다
branch-misses	분기 예측 실패 횟수	실패 1회의 비용, 전체 시간에서 차지하는 비중

낮은 IPC는 결론이 아니라 다음 실험을 고르는 출발점이다. branch-misses/branches 비율이 수 퍼센트를 넘으면 질문 1(명령 공급)로, 비율이 낮은데도 IPC가 바닥이면 질문 2(의존 체인)나 질문 3(메모리 대기)으로 좁힌다. 관찰 1·2처럼 가설 하나만 겨냥해 변수 하나를 바꾼 대조군(정렬 여부만, 누산기 수만)이 카운터보다 먼저다. 카운터는 그 대조 실험의 해석을 뒷받침하는 증거로 쓴다.

투기 실행의 경계 — 버려진 실행도 흔적을 남긴다

투기 실행은 "틀리면 버리면 그만"이라는 전제 위에 서 있다. 아키텍처 상태(레지스터, 메모리)는 실제로 완벽하게 복원된다. 그러나 2018년 공개된 Spectre는 이 전제의 구멍을 드러냈다 — 투기적으로 실행됐다 버려진 로드도 캐시에는 흔적을 남기고, 그 흔적은 접근 시간 측정으로 읽을 수 있다. 공격자가 분기 예측기를 오도해 피해자 코드가 비밀 값에 의존하는 주소를 투기적으로 로드하게 만들면, 마이크로아키텍처 상태(캐시)가 비밀을 누설하는 측면 채널이 된다.

이 챕터의 관점에서 Spectre가 중요한 이유는 공격 기법이 아니라 구조다. 성능 최적화는 관찰 가능한 부작용을 만든다. 예측·투기·캐시는 전부 "아키텍처 상태만 같으면 된다"는 계약 아래 도입됐는데, 시간이라는 관찰 채널까지 계약에 넣으면 그 전제가 무너진다. 이후의 완화책들이 일부 워크로드의 성능을 되돌린 것은, 보안과 이 문서의 최적화 장치들이 같은 동전의 양면이기 때문이다.

실무 관점

분기는 개수가 아니라 예측 가능성으로 분류한다

"분기를 줄여라"는 조언은 절반만 맞다. 루프 종료 조건, 에러 처리의 happy path, 상태가 거의 바뀌지 않는 플래그 검사 — 이런 분기는 방향이 한쪽으로 쏠려 있거나 패턴이 있어 예측기가 거의 전부 맞히고, 비용도 거의 없다. 문제가 되는 것은 방향이 데이터의 무작위성을 따르는 분기다: 무작위 순서 데이터에 대한 값 비교, 해시 기반 분류, 압축·파싱에서 심볼마다 갈리는 경로. 최적화 전에 물을 것은 "분기가 몇 개인가"가 아니라 "이 분기의 방향을 과거 이력으로 맞힐 수 있는가"다.

branchless가 이기는 조건, 지는 조건

branchless 변환(조건을 산술·마스크·cmov류로)은 예측 실패 비용을 "양쪽 다 계산하는 비용"과 맞바꾼다. 유리한 조건과 불리한 조건이 명확하다.

• 이긴다: 분기가 예측 불가능하고(실패율이 높고), 양쪽 계산이 모두 싸고, 핫 루프 안에 있다. 관찰 1의 무작위 데이터가 정확히 이 조건이다(6배).
• 진다: 분기가 잘 예측되면 원래 비용이 거의 0이라 얻을 것이 없고, 한쪽 계산이 비싸면(함수 호출, 추가 메모리 접근) 안 가도 될 길을 매번 가는 비용이 예측 실패 비용을 넘는다. 조건부 이동은 두 입력이 모두 준비될 때까지 기다리므로 의존 체인을 늘려서, 예측이 잘 되는 상황에서는 분기(예측 성공 시 의존이 끊긴다)보다 오히려 느릴 수 있다.
• 그리고 자주, 컴파일러가 먼저 한다. 단순한 조건 누적·선택은 컴파일러와 JIT이 이미 cmov·csel·벡터화로 바꾼다. 수동 변환 전에 생성 코드를 확인하고, 변환 후에는 실제 데이터 분포로 측정해야 한다.

마이크로벤치마크의 함정 — 예측기는 벤치마크를 외운다

분기 예측기는 수천~수만 회 반복되는 마이크로벤치마크의 패턴을 학습할 수 있다. 벤치마크에서 잘 예측되던 분기가 실서비스의 다양한 입력에서는 실패할 수 있고, 그 반대도 있다. 또한 1.1에서 다룬 마이크로벤치마크의 한계에 더해, 이 문서 수준의 실험은 컴파일러가 실험 변수를 제거하는 문제가 추가된다. 대조 실험의 결론은 "이 코드, 이 데이터 분포, 이 컴파일 결과"에 한정해서 읽고, 실서비스 판단은 실제 워크로드의 프로파일로 한다.

통념: "IPC가 낮으면 메모리 병목이다"

낮은 IPC는 분기 실패로 파이프라인이 반복해서 비워질 때도, 긴 의존 체인이 실행을 직렬화할 때도, 프론트엔드가 명령어를 공급하지 못할 때도 나타난다. 관찰 1의 무작위 분기 버전과 관찰 2의 단일 누산기 버전은 둘 다 캐시에 순차 접근하는데도(메모리는 병목이 아닌데도) 낮은 IPC를 보인다. IPC 하나로 원인을 확정하는 보고서는 대조 실험이나 원인별 카운터(branch-misses, 캐시 미스 계열)로 보강될 때까지 가설 목록으로 취급한다.

더 깊이

프론트엔드도 병목이 된다

지금까지의 서술은 실행(백엔드) 쪽 병목이지만, 명령어를 가져오고 해석해 공급하는 프론트엔드가 먼저 마르는 경우도 있다: 거대한 함수 본문과 인라인 폭발로 명령어 캐시(i-cache)를 넘치는 경우, 점프가 많아 fetch가 조각나는 경우. 코드 크기가 성능에 영향을 주는 이유이고, "인라인은 공짜"가 아닌 이유다. x86 계열은 가변 길이 명령어 해석 비용을 줄이려 해석된 마이크로옵(μop)을 캐시하는 구조를 쓴다 — ISA의 명령어와 실제 실행 단위가 1:1이 아니라는 것도 계약과 구현이 분리된 예다.

분기 예측기가 학습하지 못하는 것

현대 예측기(TAGE 계열)는 수백~수천 비트의 전역 이력으로 상관관계를 잡아내지만, 학습에는 한계가 있다 — 이력 길이를 넘는 주기의 패턴, 예측기 용량을 넘는 수의 활성 분기(거대한 인터프리터 디스패치 루프가 고전적 사례), 그리고 진짜 무작위. "정렬하면 빨라진다"는 관찰 1의 결론도 데이터를 정렬해 두는 비용이 본 계산보다 싸다는 조건에서만 실용적이다.

SIMD — ILP의 연장선

독립적인 같은 연산이 데이터 병렬로 존재한다면, 명령어 하나로 여러 데이터를 처리하는 SIMD(벡터) 명령이 다음 단계다. 관찰 1의 C 버전에서 clang이 자동으로 벡터화했듯, 컴파일러는 조건까지 마스크 연산으로 바꿔 벡터화한다. 이 챕터에서는 존재와 효과(수 배의 처리량)만 잡아 둔다 — intrinsics와 자동 벡터화 조건은 범위 밖이다. 참고로 GPU는 이 방향의 극단이다: 지연을 숨기는 비순차 실행 대신, 수천 스레드의 처리량으로 지연을 덮는 설계로, 단일 체인의 지연이 중요한 워크로드에는 맞지 않는다.

정리

• ISA는 계약이고 마이크로아키텍처는 구현이다. 순차 실행은 관찰 가능한 결과에 대한 약속일 뿐, 실제 실행은 파이프라인·슈퍼스칼라·비순차·투기 위에서 흐른다.
• 예측이 잘 되는 분기는 거의 공짜고, 데이터의 무작위성을 따르는 분기는 실패당 십수~이십 사이클을 치른다. 같은 코드가 데이터 순서만으로 5배 갈린 이유다.
• 비순차 실행의 연료는 독립 명령어다. 긴 의존 체인은 발행 폭과 무관하게 실행을 직렬화하며, 명령어 수가 많아도 의존이 얕은 쪽이 이길 수 있다.
• branchless 변환은 예측 실패 비용과 양쪽 계산 비용의 교환이다. 측정 전에 생성 코드를 확인해 컴파일러가 실험 변수를 제거하지 않았는지 본다.
• IPC와 단일 카운터는 결론이 아니라 다음 대조 실험을 고르는 출발점이다.

확인 문제

1. 프로파일에서 어떤 루프의 IPC가 0.5, branch-misses/branches 비율이 0.1%로 나왔다. "분기 예측은 문제없으니 캐시 미스가 원인"이라고 결론 내리기 전에, 이 증거와 양립하는 다른 가설 하나와 그것을 검증할 최소 대조 실험을 설계하라.

정답과 해설

양립 가설: 긴 데이터 의존 체인이 실행을 직렬화하고 있다(예: 단일 누산기 누적, 포인터 추적, 직전 결과에 의존하는 갱신). 분기도 캐시도 문제없이 낮은 IPC를 만든다. 대조 실험: 의존 체인만 바꾼 버전을 만든다 — 누산기를 2·4개로 쪼개거나, 의존을 인위로 끊은 변형과 비교한다. 체인을 쪼갠 버전에서 시간이 유의미하게 줄면 의존 체인 가설의 증거다. 반대로 변화가 없으면 메모리 대기 가설로 넘어가 working set 크기를 바꾸는 실험(7.2)을 설계한다.

2. 동료가 핫 루프의 if를 비트 마스크 산술로 바꾸는 PR을 올리며 "분기 제거로 최적화"라고 설명했다. 벤치마크는 무작위 입력으로 6배 개선을 보인다. 머지 전에 확인해야 할 것 두 가지를 근거와 함께 제시하라.

정답과 해설

첫째, 실서비스 입력의 분기 예측 가능성이다. 벤치마크의 무작위 입력은 branchless에 가장 유리한 조건이고, 실제 데이터가 쏠려 있거나 패턴이 있으면 원래 분기는 거의 공짜라 개선이 사라지고, 마스크 산술이 의존 체인을 늘려 오히려 느려질 수 있다. 실제 분포의 입력으로 재측정해야 한다. 둘째, 변환 전 코드의 생성 코드다. 컴파일러·JIT이 이미 cmov·csel·벡터화로 분기를 제거했다면 이 PR은 가독성만 잃고 얻는 것이 없다. 생성 코드 확인(Compiler Explorer, --print-opt-code)이 판단 근거가 된다.

3. 연결 리스트 순회가 배열 순회보다 수십 배 느린 현상에서, "분기 예측 실패 때문"이라는 가설을 기각하는 데 쓸 수 있는 증거를 이 문서의 도구로 제시하라.

정답과 해설

리스트 순회의 분기는 node !== null 하나로, 마지막 반복을 빼고는 항상 같은 방향이라 예측기가 사실상 전부 맞힌다. perf가 있다면 branch-misses가 원소 수 대비 무시할 수준임을 확인하면 된다. 카운터 없이도 기각할 수 있다 — 분기 구조는 같고 노드 배치(생성 순서 연결 vs 무작위 연결)만 다른 대조군에서 수십 배가 갈리므로(1.1의 실측), 원인은 분기가 아니라 메모리 접근 패턴 쪽이다. 남는 가설 — 주소가 직전 로드 결과에 의존해 비순차 실행이 지연을 겹쳐 숨길 수 없다는 것 — 은 7.2의 메모리 계층 수치로 검증한다.

참고 자료

• John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach 6th ed. (2017), Ch. 3 — 파이프라인, 분기 예측, 비순차 실행의 표준 서술. 이 문서의 개념 뼈대를 검증하는 기준 문헌이다.
• Agner Fog, The microarchitecture of Intel, AMD and VIA CPUs — 실제 CPU들의 파이프라인·예측기·실행 유닛 구성의 실측 기반 정리. 특정 CPU에서 명령어 지연·처리량의 자릿수를 확인할 때 참조한다.
• Intel, Intel 64 and IA-32 Architectures Optimization Reference Manual — x86 마이크로아키텍처와 최적화 지침의 공식 서술.
• Paul Kocher et al., Spectre Attacks: Exploiting Speculative Execution (2019) — 투기 실행이 마이크로아키텍처 상태에 남기는 흔적의 구조적 원인. 이 문서에서는 §1–2의 구조 서술만 참조한다.
• perf Examples (Brendan Gregg) — perf stat/record의 실전 사용법과 카운터 해석 사례.