Swift - 캐시 지역성(Cache Locality)이란

✅ CPU의 동작

CPU는 어떤 데이터를 사용하고자 하면 L1 -> L2 -> L3 -> RAM 순으로 찾아봅니다.

• Cache Hit: 캐시에 이미 있음 → 바로 가져다 씀 (빠름)
• Cache Miss: 캐시에 없음 → 더 느린 단계(결국 RAM)까지 내려가서 가져와야 함 → 그동안 CPU는 사실상 대기

이때 캐시가 무엇이냐면, CPU와 RAM 사이에는 속도 차이가 어마어마 하기 때문에 (CPU는 ns 단위로 연산하는데 RAM은 상대적으로 느림) 그 간극을 메우려고 중간에 캐시(SRAM) 를 둡니다.

 

CPU 레지스터  →  L1 캐시  →  L2 캐시  →  L3 캐시  →  RAM(메인 메모리)

빠름 ←────────────────────→ 느림

작음 ←─────────────────────→ 큼

 

CPU는 메모리를 1바이트씩 읽지 않고 하나의 뭉텅이로 가져옵니다. 이 뭉텅이를 우리는 캐시 라인(Cache line)이라고 하며 이때 두 가지 지역성이 성능에 영향을 끼칩니다.

• 공간 지역성(Spatial Locality): 방금 접근한 주소의 근처를 곧 접근할 가능성이 높다. 배열을 순서대로 순회하면 캐시 라인 하나를 가져올 때 다음 원소 여러 개가 공짜로 딸려옴.
• 시간 지역성(Temporal Locality): 방금 접근한 데이터를 다시 접근할 가능성이 높다. 루프 안에서 반복 사용되는 변수가 캐시에 머무는 경우.

성능의 차이는 꽤나 극단적입니다. 따라서 알고리즘 복잡도가 같더라도 메모리 접근 패턴에 따라 성능이 10배 이상 차이가 나기도 합니다.

 

✅ Array<Struct>와 Array<Class>

이 둘의 메모리 레이아웃은 전혀 다릅니다.

 

Struct 의 경우 Stack 에 데이터가 저장되며 해당 Stack은 연속적으로 데이터가 저장됩니다.

반면 Class의 경우 데이터는 Heap에 저장되며 Stack에는 오로지 참조에 대한 포인터가 저장되어 있으므로 데이터를 추가로 필요로 할때마다 캐시 미스가 발생할 가능성이 열려있습니다.

 

여기서 Class의 배열이 느려지는 이유를 알아보겠습니다.

 

첫째, Array<Class>는 배열의 원소를 확인할 때, Stack의 포인터를 읽고 포인터가 가리키는 실제 데이터를 찾으러가는 2단계의 과정을 거칩니다. 그 대상이 힙 어딘가라 캐시 미스 확률이 높습니다.

둘째, 캐시 라인에 담기는 "진짜 데이터"가 줄어듭니다. Class의 데이터 구조를 보면 진짜 우리가 필요로 하는 데이터 외에도 Reference count , 어떤 데이터인지에 대한 메타 데이터 등이 앞에 추가로 붙어 있습니다. 즉 한 묶음을 가지고 왔을 때 그 안에 든 "진짜 데이터"의 비율이 낮아진 다는 것이죠. 반대로 Struct의 경우 앞에 메타 데이터가 필요 없으니 오직 진짜 데이터 만으로 구성된 묶음이 생성됩니다.

셋째, 순회 중 참조를 잡을 때마다 Reference count 증감이 객체 데이터 밀도를 낮춥니다. Reference count의 증감은 헤더에 쓰기를 발생시키며 트리픽 손해가 발생합니다.

 

아래는 캐시 지역성을 설명하는 예제입니다.

 

let n = 4096
var grid = [[Double]](repeating: .init(repeating: 1, count: n), count: n)

// 1. 행 우선 (row-major) — 메모리 순서대로 접근
var sum = 0.0
for i in 0..<n {
    for j in 0..<n { sum += grid[i][j] }   // 빠름
}

// 2. 열 우선 (column-major) — 매번 n×8바이트씩 건너뜀
for j in 0..<n {
    for i in 0..<n { sum += grid[i][j] }   // 수 배 느림
}

 

위 두 코드의 연산 횟수는 완전히 동일합니다. 하지만 2번의 경우 접근할 때마다 가져오려는 데이터의 근처가 아니 다른 캐시라인을 건드리게 되며 이로 인해 공간 지역성이 죽게 됩니다.

 

Swift에서의 타입 선택과 지역성

Swift의 Dictionary/Set은 지역성 관점에서 좋지 않습니다.

해싱을 사용하는 특성 상 해싱의 경우 원소를 넣을 위치를 원소 값 자체로 계산합니다. 따라서 원소들은 연속적이지 않은 특성을 가지며 결과는 넓게 퍼뜨려집니다. 물론 결과가 한 군데 몰리면 collision이 발생하기 때문에 일부로 이러는 경향이 있지만 이로 인해 지역성이 깨지게 되며 캐시 미스가 발생하게 됩니다. 따라서 원소 수가 적다면 Array를 선형 탐색하는게 더 빠릅니다.

(Big-O 만 보고 Set(O(1))을 고르는 것이 아니라 개수가 작으면 흩어진 O(1)보다 붙어 있는 O(n)이 빠를 수 있다)

 

동시성과 만나는 지점: False sharing

이 지역성이 오히려 독이 되는 케이스도 존재합니다

서로 다른 스레드가 각자 다른 변수를 사용하는데 그 변수들이 우연히 같은 캐시 라인에 붙어 있다면 코어끼리 캐시라인 소유권을 계속 뺏고 뺏기면서 락도 없는데 성능이 무너집니다. 우리는 이걸 False sharing 이라 부릅니다

// 나쁜 예: counts[0]과 counts[1]이 같은 캐시 라인에 인접
var counts = [Int](repeating: 0, count: coreCount)
// 스레드 i가 counts[i]만 증가시켜도 라인 핑퐁 발생

// 대응: 캐시 라인 크기만큼 패딩해서 코어별 슬롯을 분리
struct PaddedCounter {
    var value: Int = 0
    let padding: (Int, Int, Int, Int, Int, Int, Int,
                  Int, Int, Int, Int, Int, Int, Int, Int) = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
}   // 128바이트로 맞춤

 

병렬화의 목적은 코어 4개가 동시에 따로따로 일해서 4배 빨라지는 효과를 보는 것이 장점입니다. 하지만 Flase sharing이 발생하면 넷은 사실상 그 묶음 하나를 두고 줄 서서 순서대로 주고받게 됩니다. 동시성이 사라지는 것이죠.

 

Actor가 상태 접근을 직렬화 하는게 여태 Data Race를 방지하기 위함 으로만 알고 있었습니다. 하지만 이렇게 보니 한 시점에 한 코어만 그 상태의 캐시 라인을 만지게 하도록 보장한다는 점에서 이런 라인 경합 자체도 구조적으로 줄여준다는 장점을 가지고 있습니다.

 

이제 다시 위의 패딩 코드를 확인해보면 패딩은 각 카운데 뒤에 Padding을 잔뜩 붙여 카운터 하나가 묶음 하나를 통째로 차지하게 만드는 것입니다.

이렇게 하면 각 코어의 카운터가 서로 다른 묶음에 들어가며 서로의 묶음을 건들지 않죠. 이제야 넷이 따로 일하게 됩니다.

 

결론적으로 Swift에서 struct를 선호하는 이유에는 스택할당만이 있는 것이 아닙니다. 컬렉션에 담겼을 때 값 타입은 버퍼에 연속 배치되어 공간 지역성이 좋고, 참조 타입은 포인터 간접 참조 + Reference Count 트래픽 + 힙 분산으로 캐시 미스가 누적되죠. 이게 바로 실측 성능 차이의 본체입니다.

 

let scores = [Int](repeating: 3, count: 1_000_000)
var total = 0

for i in 0..<scores.count {
    total += scores[i]
}

 

위의 코드에서 scores[i]는 공간적 지역성 입니다. Array<Int>는 원소가 버퍼에 연속 저장되므로 scores[0]에 접근하는 순간 캐시 라인 하나가 통째로 올라오고, 이후 15번의 접근은 메모리까지 가지 않고 캐시에서 해결됩니다.

반면, total은 시간적 지역성입니다. 매 반복마다 같은 변수를 읽고 쓰니 한번 캐시에 올라간 뒤 루프 내내 캐시에 머물죠.

아래는 시간적 지역성을 의도적으로 설계한 예입니다.

// 시간적 지역성이 없는 코드 — 같은 f(n)을 반복 계산하며 매번 먼 메모리를 순회
func fib(_ n: Int) -> Int {
    n < 2 ? n : fib(n - 1) + fib(n - 2)
}

// 시간적 지역성을 만든 코드 — 최근 결과가 작은 배열에 모여 캐시에 상주
var memo = [Int](repeating: -1, count: 91)
func fibMemo(_ n: Int) -> Int {
    if n < 2 { return n }
    if memo[n] != -1 { return memo[n] }   // 방금 쓴 데이터를 곧 다시 씀
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2)
    return memo[n]
}

 

위는 메모제이션을 활용한 코드로 캐시 관점에서 memo 배열을 만들어 반복 접근하는 구조 자체가 시간적 지역성을 활용한 형태입니다.

 

공간 지역성의 경우는 stride 접근을 예시로 들 수 있습니다.

// 좋음: 연속 접근 — 캐시 라인당 16개 원소 활용
for i in 0..<n { sum += data[i] }

// 나쁨: 16칸씩 건너뛰기 — 매 접근마다 새 캐시 라인, 라인당 1개만 사용
for i in stride(from: 0, to: n, by: 16) { sum += data[i] }

 

두 번째 코드의 경우 첫 번째에 비해 연산이 1/16 임에도 불구하고 실행 시간은 거의 비슷합니다.

이는 한번의 접근 당 캐시 라인 하나를 통째로 가져와 8바이트만 쓰고 버리기 때문에 메모리 대역폭 소비량이 첫 번째와 동일하기 때문입니다.

지역성을 무시한 코드가 일으키는 성능 문제

첫째, 같은 복잡도인데 코드가 수 배 ~ 수십 배 느려집니다. 열 우선 순회, 큰 stride, linkedList식의 pointer chasing이 전형적입니다.

Big-O로 안잡히는 비용이라 코드 리뷰로는 잡히지 않지만 프로파일링 하면 느린 형태로 나타나고 instruments를 확인하면 CPU가 바쁜게 아닌 메모리를 기다리며 stall 되어 있습니다. 

 

둘째, 데이터가 커질 때 성능이 계단식으로 무너집니다. Working Set이 L1에 들어갈 땐 빠르다가 L2를 넘고 마지막 캐시를 넘는 순간 그래프가 뚝뚝 끊깁니다.

 

셋째, iOS에서는 프레임 드랍과 발열로 직결됩니다.

예를 들면 스크롤 중 셀마다 class 인스턴스 그래프를 따라 가며 데이터를 조립하면, 

 

넷째, 멀티스레드에서는 flase sharing으로 역효과가 납니다. 스레드별 카운터를 한 배열에 인접 배치 하면 각자 자기 것만 쓰는데도 캐시 라인 소유권 핑퐁이 발생해 코어를 늘릴수록 오히려 느려지는 스케일링 역전이 발생합니다.

 

다섯번째, 간접 참조 누적 비용. [SomeClass], [any Protocol], 딕셔너리 남용 처럼 원소마다 힙 점프가 붙는 구조는 순회할때마다 미스 가능성이 곱해집니다. 여기에 Swift 특유의 refcount 쓰기 트래픽까지 더해져서 struct 배열로 바꿨더니 몇 배 빨라졌다 는 실체가 대부분 이겁니다.

 

이렇게 오늘은 캐시 지역성에 대해 알아봤습니다

감사합니다.

 

출처

https://developer.apple.com/videos/play/wwdc2016/416/

https://saurabhs.org/wwdc-notes/wwdc-16-understanding-swift-performance

https://arpitbhayani.me/blogs/cpu-cache-locality/

https://raygun.com/blog/cache-locality-impact-application-performance/

https://medium.com/@joao_vaz/caches-and-the-problem-of-false-sharing-a-primer-in-c-17-1177ad07a625

https://medium.com/@linhairui19/struct-vs-class-understanding-swift-performance-part-1-f46a6811c8f2

https://swiftrocks.com/memory-management-and-performance-of-value-types.html