Branch Prediction, Prefetching, and Data-Oriented Design TODO

Algorithms · Day 40 / 100 · C. Concurrency & Performance Engineering (Day 36-51)

Concept

To keep the pipeline full, modern CPUs predict a branch's direction and target, and a misprediction costs a fair number of cycles to discard the wrongly-executed instructions and refill. Hardware prefetchers detect sequential access or a constant stride pattern and pull cache lines in ahead of time, so predictable access patterns run much faster than pointer-chasing ones. Data-oriented design is a methodology that reshapes data layout around this hardware reality — using an array of fields (SoA) instead of an array of objects (AoS), or grouping fields that are accessed together so more of each fetched cache line actually gets used. Techniques that eliminate branches altogether (conditional moves, branchless computation, sorting the input) live in the same territory. In the end, for code of the same complexity, performance is governed more by memory access pattern and predictability than by instruction count.

When measured performance differs by multiples despite identical complexity, the cause is usually cache misses and branch mispredictions — missing this sends hot-loop optimization in the wrong direction from the start.

Code & Formula

# 브랜치 예측·프리페치·데이터 지향 설계 — AoS(객체 배열) vs SoA(필드별 배열)로 캐시 활용률이 어떻게 달라지는지 구조로 보여준다.
# SoA 는 "합계를 구할 필드"만 연속 메모리로 붙어 있어, 프리페처가 stride 패턴을 예측하기 쉽고 캐시 라인 낭비가 적다.

class Particle:
    __slots__ = ("x", "y", "hp", "team")
    def __init__(self, x, y, hp, team):
        self.x, self.y, self.hp, self.team = x, y, hp, team

# AoS: 객체 배열 — hp 만 훑어도 x, y, team 까지 같은 캐시 라인에 끌려 들어와 낭비된다.
aos = [Particle(x=i, y=i * 2, hp=100 - i, team=i % 2) for i in range(8)]

def sum_hp_aos(particles):
    return sum(p.hp for p in particles)  # 접근 패턴: 객체마다 점프하며 hp 필드만 뽑아씀 (포인터 추적에 가까움)

# SoA: 필드별 배열 — hp 만 쓰는 질의는 hp 배열 하나만 순차로 읽으면 끝난다(=예측 가능한 stride 접근).
soa = {
    "x": [i for i in range(8)],
    "y": [i * 2 for i in range(8)],
    "hp": [100 - i for i in range(8)],
    "team": [i % 2 for i in range(8)],
}

def sum_hp_soa(fields):
    return sum(fields["hp"])  # 접근 패턴: 연속 배열 순차 스캔 (하드웨어 프리페처가 가장 좋아하는 패턴)

# 조건부 분기 없이 마스크 곱으로 team==0 인 hp 합만 뽑는 예 — 분기 예측 실패를 아예 피하는 기법의 축소판.
def sum_hp_team0_branchless(fields):
    return sum(hp * (1 - team) for hp, team in zip(fields["hp"], fields["team"]))

aos_total = sum_hp_aos(aos)
soa_total = sum_hp_soa(soa)
team0_total = sum_hp_team0_branchless(soa)

print("AoS sum(hp):", aos_total)
print("SoA sum(hp):", soa_total, " <- 같은 결과, 다만 hp 배열만 순차 접근하면 됨")
print("결과 일치:", aos_total == soa_total)
print("branchless sum(hp) where team==0:", team0_total)

docs/code/algorithms/algorithms-40.py

Exercise

Run the same conditional-branch loop over a sorted array and a randomly-ordered array, measure the execution time difference, and confirm with a profiler like perf that the branch-miss and cache-miss counters actually differ.

Practical Connection

In code that iterates over large numbers of the same struct, like an indexer's event-processing loop or an order book matching engine, laying data out as contiguous arrays instead of a pointer graph alone can make a large difference in throughput.

Where it lands in Jayverse

• Verex: profile the CLOB matching engine's hot loop with perf for branch-miss/cache-miss counters before assuming instruction count explains latency. Restructure the order/position struct as SoA if pointer-chasing shows up.
• Devnet: lay out any indexer's per-event derived state as contiguous arrays, not object graphs. Applies directly to the Ponder-style reorg indexer already planned for devnet.
• gitboard: add branch-miss/cache-miss counters to the matching engine's benchmark dashboard, not just wall-clock latency. Per this page, those are the actual explanatory variables when performance differs by multiples at equal complexity.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

브랜치 예측·프리페치·데이터 지향 설계 TODO

Algorithms · Day 40 / 100 · C. 동시성·성능 엔지니어링 (Day 36–51)

개념

현대 CPU는 파이프라인을 비우지 않으려고 분기의 방향과 목적지를 예측하며, 예측이 틀리면 잘못 진행한 명령을 버리고 다시 채우는 데 상당한 사이클을 낭비한다. 하드웨어 프리페처는 순차 접근이나 일정한 stride 패턴을 감지해 캐시 라인을 미리 가져오므로, 예측 가능한 접근은 포인터를 따라가는 접근보다 훨씬 빠르다. 데이터 지향 설계는 이 하드웨어 특성에 맞춰 자료 배치를 바꾸는 방법론으로, 객체 배열(AoS) 대신 필드별 배열(SoA)을 쓰거나 함께 접근되는 필드를 모아 가져온 캐시 라인에서 실제로 쓰는 바이트 비율을 높인다. 분기 자체를 없애는 기법(조건부 이동, 분기 없는 계산, 입력 정렬)도 같은 맥락에 있다. 결국 같은 복잡도의 코드라도 성능은 명령어 개수보다 메모리 접근 패턴과 예측 가능성에 좌우된다.

복잡도가 동일한데 실측이 몇 배 차이 나는 경우 원인은 대개 캐시 미스와 분기 오예측이며, 이걸 모르면 핫 루프 최적화의 방향을 처음부터 잘못 잡는다.

코드 · 수식

# 브랜치 예측·프리페치·데이터 지향 설계 — AoS(객체 배열) vs SoA(필드별 배열)로 캐시 활용률이 어떻게 달라지는지 구조로 보여준다.
# SoA 는 "합계를 구할 필드"만 연속 메모리로 붙어 있어, 프리페처가 stride 패턴을 예측하기 쉽고 캐시 라인 낭비가 적다.

class Particle:
    __slots__ = ("x", "y", "hp", "team")
    def __init__(self, x, y, hp, team):
        self.x, self.y, self.hp, self.team = x, y, hp, team

# AoS: 객체 배열 — hp 만 훑어도 x, y, team 까지 같은 캐시 라인에 끌려 들어와 낭비된다.
aos = [Particle(x=i, y=i * 2, hp=100 - i, team=i % 2) for i in range(8)]

def sum_hp_aos(particles):
    return sum(p.hp for p in particles)  # 접근 패턴: 객체마다 점프하며 hp 필드만 뽑아씀 (포인터 추적에 가까움)

# SoA: 필드별 배열 — hp 만 쓰는 질의는 hp 배열 하나만 순차로 읽으면 끝난다(=예측 가능한 stride 접근).
soa = {
    "x": [i for i in range(8)],
    "y": [i * 2 for i in range(8)],
    "hp": [100 - i for i in range(8)],
    "team": [i % 2 for i in range(8)],
}

def sum_hp_soa(fields):
    return sum(fields["hp"])  # 접근 패턴: 연속 배열 순차 스캔 (하드웨어 프리페처가 가장 좋아하는 패턴)

# 조건부 분기 없이 마스크 곱으로 team==0 인 hp 합만 뽑는 예 — 분기 예측 실패를 아예 피하는 기법의 축소판.
def sum_hp_team0_branchless(fields):
    return sum(hp * (1 - team) for hp, team in zip(fields["hp"], fields["team"]))

aos_total = sum_hp_aos(aos)
soa_total = sum_hp_soa(soa)
team0_total = sum_hp_team0_branchless(soa)

print("AoS sum(hp):", aos_total)
print("SoA sum(hp):", soa_total, " <- 같은 결과, 다만 hp 배열만 순차 접근하면 됨")
print("결과 일치:", aos_total == soa_total)
print("branchless sum(hp) where team==0:", team0_total)

docs/code/algorithms/algorithms-40.py

연습

정렬된 배열과 무작위 배열에 같은 조건 분기 루프를 돌려 실행 시간 차이를 재고, perf 같은 프로파일러로 branch-miss와 cache-miss 카운터가 실제로 다른지 확인하라.

실무 · Verex 연결

인덱서의 이벤트 처리 루프나 오더북 매칭 엔진처럼 같은 구조체를 대량 순회하는 코드에서는, 포인터 그래프 대신 연속 배열로 배치하는 것만으로 처리량이 크게 달라진다.

Jayverse에서의 위치

• Verex: 명령어 수가 지연을 설명한다고 가정하기 전에 CLOB 매칭 엔진의 핫 루프를 perf로 프로파일링해 branch-miss/cache-miss 카운터를 본다. 포인터 체이싱이 드러나면 주문/포지션 구조체를 SoA로 재구성한다.
• Devnet: 인덱서의 이벤트별 파생 상태를 객체 그래프가 아니라 연속 배열로 배치한다. devnet에 이미 계획된 Ponder식 리오그 인덱서에 바로 적용된다.
• gitboard: 매칭 엔진 벤치마크 대시보드에 벽시계 지연뿐 아니라 branch-miss/cache-miss 카운터도 추가한다. 이 페이지에 따르면 동일한 복잡도에서 성능이 몇 배씩 차이 날 때 실제 설명 변수는 이것이다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.