CPU Cache-Friendly Data Structures in Go: 10x Speed with Same Algorithm

주요 내용

캐시 미스는 L1 캐시 히트에 비해 코드를 60배 느리게 할 수 있음
False Sharing은 여러 코어가 같은 캐시 라인의 다른 변수를 업데이트할 때 발생
적절한 데이터 구조 패딩으로 특정 시나리오에서 5-10배 성능 개선 가능
고성능 시스템에서는 객체 지향 설계보다 데이터 지향 설계가 우수
캐시 효과는 하드웨어별로 다르므로 항상 벤치마크로 측정해야 함

중요한 숫자들

L1 캐시:    4 사이클     (~1ns)      32KB
L2 캐시:    12 사이클    (~3ns)      256KB
L3 캐시:    40 사이클    (~10ns)     8MB
RAM:        200+ 사이클  (~60ns)     32GB

캐시 라인 크기: 64 바이트 (x86_64에서)

RAM에서 읽기는 L1 캐시보다 약 60배 느립니다. 하나의 캐시 미스는 60번의 캐시 히트와 같습니다. 이것이 캐시 친화적인 코드가 더 빠르게 실행될 수 있는 이유이며, 특정 시나리오에서는 5-10배 향상될 수 있습니다.

False Sharing은 여러 CPU 코어가 같은 캐시 라인에 있는 다른 변수를 수정할 때 발생합니다. 이로 인해 캐시 라인 무효화가 코어 간에 전파되어 심각한 성능 저하를 야기합니다.

문제는 미묘합니다: 논리적으로는 독립적인 변수일 수 있지만, 물리적으로 메모리에 인접해 있다면 (64바이트 이내), 하나를 업데이트하면 그 라인의 다른 모든 변수의 캐시를 무효화합니다.

메트릭 수집 시스템에서 고 동시성 상황에서 10배 느린 성능을 발견했습니다. 문제는 여러 고루틴이 같은 캐시 라인에 압축된 다른 카운터들을 업데이트하고 있었습니다.

감지하려면 동시 접근 패턴으로 신중한 벤치마킹이 필요합니다. 성능 저하는 단일 스레드 테스트에서는 보이지 않고, 병렬 부하 하에서만 드러납니다.

문제: False Sharing으로 성능이 파괴됨

type Counters struct {
    requests  uint64 // 8 바이트
    errors    uint64 // 8 바이트 - 같은 캐시 라인!
    latency   uint64 // 8 바이트 - 같은 캐시 라인!
}
// 결과: 경합 상태에서 45ns/op

type Counters struct {
    requests  uint64
    _         [56]byte // 64바이트까지 패딩 (캐시 라인)
    errors    uint64
    _         [56]byte
    latency   uint64
    _         [56]byte
    timeouts  uint64
    _         [56]byte
}

// 결과: 7ns/op - 6.4배 빠름!

캐시 미스 측정 (Linux)

# 캐시 미스 프로파일링
perf stat -e cache-misses,cache-references ./myapp

# 상세 캐시 분석
perf record -e cache-misses ./myapp
perf report

# Go 벤치마크와 perf
go test -bench=. -benchtime=10s &
pid=$!
perf stat -p $pid -e L1-dcache-load-misses,L1-dcache-loads

데이터 지향 설계: Array of Structs vs Struct of Arrays

캐시 비친화적 - Array of Structs (AoS)

type Entity struct {
    ID       uint64    // 8 바이트
    X, Y, Z  float64   // 24 바이트
    Velocity float64   // 8 바이트
    Health   int       // 8 바이트
    Type     string    // 16 바이트
    // 총 64+ 바이트 per entity
}

type World struct {
    Entities []Entity // 각 entity가 다른 캐시 라인에 위치
}

func (w *World) UpdatePositions(dt float64) {
    for i := range w.Entities {
        // 64+ 바이트를 로드하지만 32바이트만 사용 (X,Y,Z,Velocity)
        // 캐시의 50%를 낭비!
        w.Entities[i].X += w.Entities[i].Velocity * dt
    }
}

// 벤치마크: 엔티티당 85ns

캐시 친화적 - Struct of Arrays (SoA)

type World struct {
    IDs        []uint64
    Positions  [][3]float64 // X,Y,Z가 함께 위치
    Velocities []float64
    Healths    []int
    Types      []string
}

func (w *World) UpdatePositions(dt float64) {
    // Positions와 Velocities가 메모리에 연속적으로 배치됨
    // CPU는 캐시 라인당 8개의 위치를 로드!
    for i := range w.Positions {
        w.Positions[i][0] += w.Velocities[i] * dt
    }
}

// 벤치마크: 엔티티당 12ns - 7배 빠름!

Prefetching: CPU의 예측 돕기

// 선형 접근 - CPU prefetcher가 잘 작동
func SumLinear(data []int) int {
    sum := 0
    for i := 0; i < len(data); i++ {
        sum += data[i] // CPU는 data[i+1], data[i+2]... 미리 로드
    }
    return sum
}
// 엘리먼트당 2.1ns

// 무작위 접근 - Prefetcher가 도움이 안됨
func SumRandom(data []int, indices []int) int {
    sum := 0
    for _, idx := range indices {
        sum += data[idx] // 캐시 미스 가능성 높음
    }
    return sum
}
// 엘리먼트당 45ns - 20배 느림!

// 알려진 패턴에 대한 수동 prefetching
func ProcessWithPrefetch(nodes []*Node) {
    for i := 0; i < len(nodes)-4; i++ {
        // 현재 처리 중일 때 미래 노드 미리 로드
        _ = nodes[i+4].Value // Prefetch 트리거
        
        // 4개 반복 전에 미리 로드된 현재 노드 처리
        expensive(nodes[i])
    }
}

Hot/Cold 데이터 분리

문제: Hot과 Cold 데이터가 섞여있음

type User struct {
    ID       uint64    // HOT: 자주 접근
    Score    int       // HOT: 자주 접근
    Name     string    // COLD: 드물게 접근
    Email    string    // COLD: 드물게 접근
    Address  string    // COLD: 드물게 접근
    Bio      string    // COLD: 드물게 접근
    // 하나의 User = 100+ 바이트이지만 보통 16바이트만 필요
}

func TopUsers(users []User) []uint64 {
    // 정렬은 User당 100+ 바이트를 로드하지만 Score만 사용
    sort.Slice(users, func(i, j int) bool {
        return users[i].Score > users[j].Score // 캐시 thrashing!
    })
}

해결책: Hot과 Cold 데이터 분리

type UserHot struct {
    ID    uint64
    Score int
    Cold  *UserCold // Cold 데이터에 대한 포인터
}

type UserCold struct {
    Name    string
    Email   string
    Address string
    Bio     string
}

// 이제 정렬은 User당 24바이트만 접근
// 캐시 미스 4배 감소!

NUMA 인식 할당

// NUMA 토폴로지 확인
// $ numactl --hardware
// node 0 cpus: 0-23
// node 1 cpus: 24-47

// 고루틴을 특정 CPU에 고정
func PinToCPU(cpuID int) {
    runtime.LockOSThread()
    
    var cpuSet unix.CPUSet
    cpuSet.Zero()
    cpuSet.Set(cpuID)
    
    tid := unix.Gettid()
    unix.SchedSetaffinity(tid, &cpuSet)
}

// NUMA 인식 워커 풀
type NUMAPool struct {
    workers [][]chan Task // workers[numa_node][worker_id]
}

func (p *NUMAPool) Submit(task Task) {
    // Task를 NUMA 노드에 해시하여 데이터 지역성 확보
    node := hash(task.Key) % len(p.workers)
    worker := rand.Intn(len(p.workers[node]))
    p.workers[node][worker] <- task
}

func (p *NUMAPool) StartWorker(numaNode, workerID int) {
    // 특정 NUMA 노드의 CPU에 고정
    cpuID := numaNode*24 + workerID
    PinToCPU(cpuID)
    
    for task := range p.workers[numaNode][workerID] {
        processTask(task)
    }
}

분기 예측 친화적 코드

문제: 예측 불가능한 분기

func CountCondition(data []int) int {
    count := 0
    for _, v := range data {
        if v > 128 { // 무작위 데이터 = 50% 오예측
            count++
        }
    }
    return count
}
// 무작위 데이터: 엘리먼트당 8.2ns

해결책 1: 정렬 후 처리

func CountConditionSorted(data []int) int {
    sort.Ints(data) // 이제 분기가 예측 가능!
    
    count := 0
    for _, v := range data {
        if v > 128 { // 처음은 모두 false, 나중은 모두 true
            count++
        }
    }
    return count
}
// 정렬 오버헤드에도 불구하고: 엘리먼트당 3.1ns

해결책 2: 분기 없는 버전

func CountConditionBranchless(data []int) int {
    count := 0
    for _, v := range data {
        // 분기 없음, 산술 연산만
        count += int((uint(v) >> 7) & 1)
    }
    return count
}
// 항상 빠름: 엘리먼트당 2.3ns

캐시 친화적 해시 테이블

// 표준 map - 무작위 메모리 접근
m := make(map[uint64]uint64)
// 캐시 미스 많음

// 캐시 친화적 Robin Hood 해싱
type RobinHoodMap struct {
    buckets []bucket
    mask    uint64
}

type bucket struct {
    key      uint64
    value    uint64
    distance uint8 // 이상적인 위치로부터의 거리
    occupied bool
}

func (m *RobinHoodMap) Get(key uint64) (uint64, bool) {
    idx := key & m.mask
    distance := uint8(0)
    
    // 선형 탐사 = 캐시 친화적 접근 패턴
    for {
        b := &m.buckets[idx]
        
        if !b.occupied {
            return 0, false
        }
        
        if b.key == key {
            return b.value, true
        }
        
        // Robin Hood: 나쁜 키들은 멀리 여행하지 않음
        if b.distance < distance {
            return 0, false
        }
        
        idx = (idx + 1) & m.mask
        distance++
    }
}

// 벤치마크 (1M 조회):
// map[uint64]uint64:    95ns/op
// RobinHoodMap:         32ns/op - 3배 빠름!

실제 프로덕션 예제: 분석 파이프라인

Before: 객체 지향 설계

type Event struct {
    Timestamp time.Time
    UserID    uint64
    Action    string
    Value     float64
    Tags      map[string]string
}

func ProcessEvents(events []Event) {
    for _, e := range events {
        // 각 event 접근 = 잠재적 캐시 미스
        if e.Action == "purchase" {
            updateRevenue(e.Value)
        }
    }
}

After: 데이터 지향 설계

type EventBatch struct {
    Timestamps []int64   // Unix timestamps
    UserIDs    []uint64
    Actions    []uint8   // string 대신 enum
    Values     []float64
    
    // Tags는 별도 저장 (cold 데이터)
    TagIndices []uint32
    TagKeys    []string
    TagValues  []string
}

func ProcessEventsBatch(batch *EventBatch) {
    // 캐시 친화적 방식으로 actions 처리
    for i, action := range batch.Actions {
        if action == ActionPurchase {
            updateRevenue(batch.Values[i])
        }
    }
}

// 결과:
// Before: 450ns per event, 78% 캐시 미스
// After:  31ns per event, 12% 캐시 미스
// 14.5배 향상!

SIMD 친화적 레이아웃

// SIMD 처리를 위한 적절한 정렬
type Vec3 struct {
    X, Y, Z float32
    _       float32 // 16바이트 정렬을 위한 패딩
}

// SIMD로 한 번에 4개의 벡터 처리
func AddVectors(a, b []Vec3, result []Vec3) {
    // 컴파일러가 이 루프를 벡터화할 수 있음
    for i := 0; i < len(a); i++ {
        result[i].X = a[i].X + b[i].X
        result[i].Y = a[i].Y + b[i].Y
        result[i].Z = a[i].Z + b[i].Z
    }
}

// 64바이트 정렬 강제
type AlignedBuffer struct {
    _ [0]byte // 정렬을 위한 마법
    data [1024]float64
}

var buffer = new(AlignedBuffer)
// 64바이트 정렬 보장

캐시 성능 벤치마킹

func BenchmarkCacheLineSize(b *testing.B) {
    // 실험적으로 캐시 라인 크기 감지
    data := make([]int64, 1024*1024)
    
    for stride := 1; stride <= 128; stride *= 2 {
        b.Run(fmt.Sprintf("stride_%d", stride), func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                // stride 간격으로 메모리 접근
                for j := 0; j < len(data); j += stride {
                    data[j]++
                }
            }
        })
    }
    // stride=8 (64바이트)에서 급격한 성능 저하 = 캐시 라인 크기
}

Go에서 캐시 친화적 코드 작성 규칙

Hot 데이터 압축: 자주 접근하는 필드를 같은 캐시 라인에 배치
동시 접근을 위한 패딩: 고루틴 데이터를 캐시 라인 단위로 분리
링크드 리스트보다 배열: 순차 접근 > 무작위 접근
더 작은 타입 사용: 범위가 허용하면 int64 대신 int32
처리 전에 정렬: 예측 가능한 분기와 접근 패턴
할당 풀링: 메모리 재사용 = hot 캐시
프로파일링, 추측하지 말기: perf, pprof, 벤치마크 사용

성능 최적화 레시피

1. 프로파일: perf로 캐시 미스 찾기
2. 구조 재정렬: Hot path를 위해 AoS → SoA
3. 패딩: False sharing 제거
4. 압축: 자주 접근하는 데이터 그룹화
5. Prefetch: 선형 접근 패턴
6. 측정: 벤치마크로 검증

프로덕션 성과 (특정 워크로드):
- 분석 파이프라인: 배치 처리에서 최대 14배 향상
- 게임 물리 엔진: 충돌 감지에서 8배 향상
- 데이터베이스 인덱싱: 순차 스캔에서 11배 향상
- 이런 향상은 워크로드별로 다르며 하드웨어에 따라 변함

기억하세요: 최신 CPU는 빠릅니다. 메모리는 느립니다. 그 격차는 매년 커집니다. 캐시 친화적 코드는 조기 최적화가 아니라 필수 최적화입니다.

보안 고려사항

메모리 정렬 트릭은 타이밍 사이드 채널을 노출할 수 있으니 주의
캐시 기반 공격 (Spectre, Meltdown)은 예측 가능한 메모리 접근 패턴을 이용
민감한 애플리케이션에서는 보안과 성능의 트레이드오프 고려
암호화 연산을 위해 상수 시간 알고리즘 사용
버퍼 오버플로우를 방지하기 위해 모든 배열 경계 검증

테스팅 전략

캐시 최적화 테스팅:

마이크로 벤치마크로 특정 최적화 측정
다양한 CPU 아키텍처에서 테스트 (Intel, AMD, ARM)
현실적인 데이터 크기와 접근 패턴으로 측정
성능 카운터를 사용해 캐시 히트율 검증
다양한 코어 수로 테스트하여 false sharing 감지

테스트 예제

func TestCacheFriendlyStructure(t *testing.T) {
    tests := []struct {
        name     string
        size     int
        expected time.Duration
    }{
        {"small_data", 1000, 100 * time.Microsecond},
        {"medium_data", 100000, 10 * time.Millisecond},
        {"large_data", 10000000, 1 * time.Second},
    }
    
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            data := generateTestData(tt.size)
            
            start := time.Now()
            processCacheFriendly(data)
            elapsed := time.Since(start)
            
            if elapsed > tt.expected {
                t.Errorf("처리 시간 %v, 예상 < %v", elapsed, tt.expected)
            }
            
            // 정확성 검증
            result := verifyCacheFriendlyResult(data)
            assert.True(t, result.IsValid())
        })
    }
}

func BenchmarkFalseSharing(b *testing.B) {
    // 패딩 있음/없음으로 테스트
    b.Run("with_false_sharing", func(b *testing.B) {
        c := &CountersUnpadded{}
        b.RunParallel(func(pb *testing.PB) {
            for pb.Next() {
                atomic.AddUint64(&c.requests, 1)
            }
        })
    })
    
    b.Run("with_padding", func(b *testing.B) {
        c := &CountersPadded{}
        b.RunParallel(func(pb *testing.PB) {
            for pb.Next() {
                atomic.AddUint64(&c.requests, 1)
            }
        })
    })
    
    // 패딩된 버전이 훨씬 빨라야 함
}

최적화별 성능 향상 표

최적화 기법	성능 향상	적용 대상	복잡도
False Sharing 제거	2-10배	동시 카운터	낮음
데이터 구조 압축	1.5-3배	Hot 데이터 경로	중간
Array of Structs → Struct of Arrays	3-15배	배치 처리	높음
Prefetching	1.2-2배	예측 가능한 접근	낮음
분기 예측	2-5배	조건부 로직	중간

언어 간 비교

이러한 최적화는 Go에만 국한되지 않지만, Go의 런타임 특성이 영향을 미칩니다:

최적화 효율	Go	Rust	Java	C++
False Sharing	높음 (GC 스캔)	중간	높음 (GC 압력)	중간
데이터 압축	높음 (GC 오버헤드)	낮음 (수동 메모리)	높음 (객체 오버헤드)	낮음 (제로 비용)
분기 예측	중간 (비슷한 CPU)	높음 (직접 제어)	낮음 (JIT 최적화)	높음 (LLVM)

Go의 가비지 컬렉터는 메모리 접근 패턴에 오버헤드를 추가합니다. 캐시 친화적 코드는 지역성을 개선하여 GC 압력을 줄이므로 컬렉터의 일을 쉽게 합니다. 이 이중 이점이 이러한 최적화가 수동 메모리 관리 언어보다 Go에서 더 큰 영향을 미치는 이유입니다.

원문: Serge Skoredin의 Go에서 CPU 캐시 친화적인 데이터 구조

Posted 2025-12-31

eeeuns

CPU Cache-Friendly Data Structures in Go: 10x Speed with Same Algorithm

주요 내용

목차

중요한 숫자들

문제: False Sharing으로 성능이 파괴됨

캐시 미스 측정 (Linux)

데이터 지향 설계: Array of Structs vs Struct of Arrays

캐시 비친화적 - Array of Structs (AoS)

캐시 친화적 - Struct of Arrays (SoA)

Prefetching: CPU의 예측 돕기

Hot/Cold 데이터 분리

문제: Hot과 Cold 데이터가 섞여있음

해결책: Hot과 Cold 데이터 분리

NUMA 인식 할당

분기 예측 친화적 코드

문제: 예측 불가능한 분기

해결책 1: 정렬 후 처리

해결책 2: 분기 없는 버전

캐시 친화적 해시 테이블

실제 프로덕션 예제: 분석 파이프라인

Before: 객체 지향 설계

After: 데이터 지향 설계

SIMD 친화적 레이아웃

캐시 성능 벤치마킹

Go에서 캐시 친화적 코드 작성 규칙

성능 최적화 레시피

보안 고려사항

테스팅 전략

테스트 예제

최적화별 성능 향상 표

언어 간 비교

CPU Cache-Friendly Data Structures in Go: 10x Speed with Same Algorithm

주요 내용

목차

중요한 숫자들

False Sharing: 조용한 살인자

문제: False Sharing으로 성능이 파괴됨

해결책: 패딩으로 False Sharing 방지

캐시 미스 측정 (Linux)

데이터 지향 설계: Array of Structs vs Struct of Arrays

캐시 비친화적 - Array of Structs (AoS)

캐시 친화적 - Struct of Arrays (SoA)

Prefetching: CPU의 예측 돕기

Hot/Cold 데이터 분리

문제: Hot과 Cold 데이터가 섞여있음

해결책: Hot과 Cold 데이터 분리

NUMA 인식 할당

분기 예측 친화적 코드

문제: 예측 불가능한 분기

해결책 1: 정렬 후 처리

해결책 2: 분기 없는 버전

캐시 친화적 해시 테이블

실제 프로덕션 예제: 분석 파이프라인

Before: 객체 지향 설계

After: 데이터 지향 설계

SIMD 친화적 레이아웃

캐시 성능 벤치마킹

Go에서 캐시 친화적 코드 작성 규칙

성능 최적화 레시피

보안 고려사항

테스팅 전략

테스트 예제

최적화별 성능 향상 표

언어 간 비교