메모리 계층과 캐시 - 시간·공간 지역성·순회 순서와 거짓 공유 해석 (CS 기초 3장)

이 장에서 배우는 것

2장에서 CPU가 명령을 겹쳐 처리해도 입력을 기다릴 수 있음을 살폈다. 이번 장은 그 입력이 도착하는 메모리 경로를 다룬다. 선수지식은 배열의 인덱스와 중첩 반복문이다.

• 레지스터·캐시·주 메모리의 역할을 구분한다.
• 시간 지역성과 공간 지역성을 접근 패턴으로 설명한다.
• 같은 연산 횟수의 순회 순서 차이를 측정하고 한계를 해석한다.
• 복잡도가 같은 코드의 성능 차이를 메모리 배치와 거짓 공유 조건으로 진단한다.

개념

두 반복문이 같은 개수의 숫자를 더하는데 한쪽이 더 오래 걸린다. 연산 횟수를 다시 세어도 같아서 컴파일러나 서버 상태를 의심하게 된다. 그러나 숫자를 읽는 순서가 다르면 CPU가 기다리는 데이터의 경로도 달라진다. 접근 횟수와 접근 비용을 나누어 보는 것이 메모리 계층을 배우는 출발점이다.

값은 여러 저장 계층을 거쳐 온다

레지스터는 현재 명령이 사용하는 값과 상태를 다루고, 캐시는 앞으로 다시 쓸 가능성이 있는 메모리 내용을 가까이에 유지한다. 주 메모리는 실행 중인 프로그램의 더 큰 데이터 집합을 담는다. 이 계층들의 용량과 접근 특성은 다르지만 고정된 지연 숫자 하나로 모든 CPU를 설명할 수는 없다. 필요한 값이 가까운 계층에 있으면 더 먼 계층에서 가져오는 일을 줄일 수 있다는 관계가 핵심이다.

CPU 캐시는 일반적으로 개별 변수보다 큰 캐시 라인 단위로 메모리 내용을 가져온다. 한 원소를 읽을 때 이웃한 내용도 함께 가까워질 수 있으므로 다음 접근이 어디인지가 중요하다. 라인의 실제 크기와 캐시의 공유 범위는 CPU마다 확인해야 한다. 이 장의 계산에서는 이해를 돕기 위해 16바이트 라인을 가정하며 실제 장비의 상수라고 주장하지 않는다.

시간 지역성과 공간 지역성을 구분한다

시간 지역성은 최근 사용한 대상을 가까운 미래에 다시 사용하는 성질이다. 작은 표를 반복 조회하는 작업이 한 예다. 공간 지역성은 가까운 주소의 내용을 이어서 쓰는 성질이며 연속 배열을 순서대로 훑을 때 나타난다. 두 성질이 함께 나타날 수 있지만 같은 개념은 아니므로 무엇을 반복하고 얼마나 떨어진 주소로 이동하는지 따로 적는다.

행 순서로 저장된 표를 행 단위로 순회하면 연속 원소를 읽는다. 열 단위 순회는 다음 행의 같은 열로 건너뛰므로 한 번 가져온 이웃 데이터를 바로 쓰지 못할 수 있다. 다만 전체 데이터가 캐시에 충분히 들어가거나 하드웨어가 접근을 미리 준비하면 차이가 작을 수 있다. 접근 순서가 나쁘면 반드시 특정 배수만큼 느리다는 법칙은 없다.

작업 집합은 일정 구간에 실제로 반복 사용하는 데이터의 범위다. 프로그램 전체가 크더라도 자주 쓰는 부분이 작으면 재사용이 잘 일어날 수 있다. 반대로 원소마다 함께 필요하지 않은 큰 부가 정보를 붙이면 유효한 데이터가 가까운 저장 공간을 덜 효율적으로 사용한다. 크기만 줄이는 대신 같은 시점에 사용하는 필드를 모으는 설계도 후보가 된다.

거짓 공유는 값이 달라도 생긴다

두 작업자가 서로 다른 카운터를 갱신해도 두 카운터가 같은 캐시 라인에 놓일 수 있다. 여러 코어가 그 라인의 쓰기 권한을 번갈아 가져와야 하면 서로 무관한 값 때문에 데이터 이동이 늘어난다. 이처럼 논리적으로 공유하지 않는 값을 같은 라인에 두어 생기는 비용을 거짓 공유라고 부른다. 실제로 같은 카운터를 함께 수정하는 경우는 진짜 데이터 공유이므로 구분해야 한다.

거짓 공유의 전형적인 조건은 여러 CPU가 같은 라인을 공유하고 적어도 하나가 쓰기를 수행하는 것이다. 모든 작업이 읽기만 한다면 같은 종류의 쓰기 소유권 이동을 가정할 수 없다. 값을 띄워 놓는 패딩은 후보 해결책이지만 메모리 사용량을 늘리고 다른 지역성을 해칠 수 있다. 배치를 바꾸기 전에 공유 라인과 쓰기 경합의 근거를 찾는다.

명령이 사용하는 레지스터에서 캐시와 주 메모리로 경로가 이어진다. 캐시는 변수 하나가 아니라 라인 단위의 이웃 데이터를 가져온다.

직접 확인하기

실습은 Python 3 표준 라이브러리만 사용한다. 각 코드 블록을 별도 파일로 저장해 python3 파일명.py로 실행할 수 있다. 블록 사이에 공유하는 변수나 파일은 없다.

라인 단위 접근을 명시한 모형

line_bytes, element_bytes = 16, 4
for indexes in [list(range(8)), list(range(0, 32, 4))]:
    lines = [(i * element_bytes) // line_bytes for i in indexes]
    print("라인 순서", lines)
    print("서로 다른 라인", len(set(lines)))

실행 결과다. 시간 측정 비율과 환경 의존 값은 실행할 때 달라질 수 있다.

결과
----
라인 순서 [0, 0, 0, 0, 1, 1, 1, 1]
서로 다른 라인 2
라인 순서 [0, 1, 2, 3, 4, 5, 6, 7]
서로 다른 라인 8

주소 0에서 시작하는 정렬된 배열을 가정한 계산이다. 원소 여덟 개를 읽어도 순서대로 읽는 경우 두 라인이고 네 원소씩 건너뛰면 여덟 라인이다. 이 수는 서로 다른 라인 수이며 캐시 미스 횟수가 아니다. 실제 캐시의 초기 상태와 축출, 재접근을 모델링하지 않았기 때문이다.

line_bytes = 16
for offsets in [(0, 8), (0, 16)]:
    lines = [offset // line_bytes for offset in offsets]
    print(offsets, lines, "같은 라인", lines[0] == lines[1])

실행 결과다. 시간 측정 비율과 환경 의존 값은 실행할 때 달라질 수 있다.

결과
----
(0, 8) [0, 0] 같은 라인 True
(0, 16) [0, 1] 같은 라인 False

이 계산도 라인 크기 16바이트, 기준 주소가 라인 경계라는 모형이다. 오프셋 0과 8은 같은 라인이고 0과 16은 다른 라인이다. 서로 다른 라인에 있으면 이 두 위치 사이의 거짓 공유 조건 하나를 없앤 것이지 프로그램의 모든 경합을 없앤 것은 아니다. Python 객체의 실제 주소 배치를 이 숫자와 연결하지 않는다.

같은 합을 다른 순서로 계산한다

from array import array
from time import perf_counter
from statistics import median
n = 384
data = array("q", range(n * n))
def total(column_first):
    result = 0
    for outer in range(n):
        for inner in range(n):
            index = inner * n + outer if column_first else outer * n + inner
            result += data[index]
    return result
samples = {False: [], True: []}
answers = {}
for turn in range(6):
    order = [False, True] if turn % 2 == 0 else [True, False]
    for mode in order:
        start = perf_counter()
        answers[mode] = total(mode)
        samples[mode].append(perf_counter() - start)
print("합 일치", answers[False] == answers[True])
print("열/행 시간 비율", round(median(samples[True]) / median(samples[False]), 3))

실행 결과다. 시간 측정 비율과 환경 의존 값은 실행할 때 달라질 수 있다.

결과
----
합 일치 True
열/행 시간 비율 1.021

결과의 합이 같은지 먼저 확인한 뒤 중앙값의 비율을 읽는다. 실행 순서를 번갈아 둔 것은 먼저 실행한 쪽만 준비 비용을 부담하는 편향을 줄이기 위해서다. 이 코드는 Python 루프와 인덱스 계산 비용까지 포함하므로 순수한 캐시 지연 측정이 아니다. 비율이 1에 가깝거나 순서가 뒤집혀도 코드가 틀렸다는 뜻은 아니며, 실측만으로 캐시 미스 수를 단정할 수 없다.

from array import array
values = array("q", [10, 20, 30, 40])
print("원소 크기", values.itemsize)
print("내용 바이트", len(values) * values.itemsize)
print("바이트 뷰 길이", len(memoryview(values).cast("B")))

실행 결과다. 시간 측정 비율과 환경 의존 값은 실행할 때 달라질 수 있다.

결과
----
원소 크기 8
내용 바이트 32
바이트 뷰 길이 32

array는 같은 기본 수치 형식의 값을 조밀하게 저장하는 표준 라이브러리 컨테이너다. 출력한 내용 바이트는 원소 저장 부분만 나타내며 객체 전체 관리 비용을 포함하지 않는다. 일반 Python list는 정수 본체를 고정 폭으로 연속 저장하는 배열과 같지 않다. 따라서 list 실험에서 얻은 시간이나 객체 크기를 저수준 배열의 캐시 특성으로 그대로 옮기지 않는다.

환경별 차이

예제는 절대 지연 수치를 제시하지 않고 같은 실행 안의 시간 비율만 비교한다. Python 버전, CPU 종류와 실행 시 부하는 별도 검증 기록에 남긴다. 운영 환경의 병목을 판단하려면 데이터 크기를 실제 작업 집합에 맞추고 반복 실행의 분포를 함께 확인해야 한다. 아주 작은 입력에서는 함수 호출과 반복문 비용이 관심 대상보다 커질 수 있다.

거짓 공유를 재현하려면 실제 병렬 실행, 쓰기 위치 배치와 캐시 공유 범위를 함께 통제해야 한다. 이 장의 주소 계산은 조건을 설명하는 모형이며 현상을 하드웨어에서 재현했다고 주장하지 않는다. Linux 커널 문서는 거짓 공유를 조사할 때 자료 배치와 경합 근거를 같이 보도록 설명한다. 실제 성능 개선에서는 정확성 검증 뒤 배치 변경 전후의 처리량을 비교한다.

실무에서 자주 틀리는 것

같은 횟수면 실행 시간도 같다

증상은 같은 합을 구하는 두 반복문의 시간이 다른 것이다. 흔한 오진은 한쪽에 숨은 연산이 반드시 더 있다는 판단이다. 실제 원인은 접근 위치와 재사용 간격의 차이일 수 있다. 연산 횟수와 주소 이동 패턴을 따로 기록하고 입력 크기를 바꿔 비교한다. 단, Python 루프 결과를 캐시 미스만의 효과라고 단정하지 않는다.

캐시 라인 수를 미스 횟수로 읽는다

증상은 주소 계산으로 구한 라인 수와 성능 계측이 맞지 않는 것이다. 흔한 오진은 계측 도구가 틀렸다는 판단이다. 실제 원인은 초기 적재 상태, 재사용과 축출을 빼고 세었기 때문이다. 모형에 포함한 가정을 적고 실제 접근 순서와 캐시 계층의 측정 대상을 확인한다. 미리 가져오기까지 있는 하드웨어는 단순 집합 크기와 같지 않다.

다른 변수면 간섭하지 않는다

증상은 독립 카운터를 병렬로 갱신했는데 확장성이 나빠지는 것이다. 흔한 오진은 변수 이름이 다르므로 메모리 경합을 배제하는 판단이다. 실제 원인은 같은 캐시 라인에서 쓰기 권한이 오가는 것일 수 있다. 배치와 실행 CPU를 확인하고 분리 전후를 비교한다. 논리적 독립성과 물리적 배치는 별개다.

스스로 확인하기

문제와 해설

1. 16바이트 라인과 4바이트 원소의 모형에서 정렬된 배열의 인덱스 0부터 7까지 읽었다. 서로 다른 라인 수와 캐시 미스 횟수를 각각 판단하라.
2. 열/행 시간 비율이 1.02였다. 공간 지역성이라는 개념이 틀렸다고 말할 수 있는지 설명하라.
3. 같은 캐시 라인을 두 코어가 읽기만 하는 경우와 각각 다른 값을 쓰는 경우의 차이를 설명하라.

해설 1 라인은 두 개다. 미스 횟수는 초기 상태와 접근 시점의 축출 등을 모르므로 이 정보만으로 확정할 수 없다.

해설 2 그렇지 않다. 이 실험에는 Python 실행 비용과 작은 작업 집합 등 여러 조건이 섞인다. 비율 하나로 하드웨어 현상을 부정하거나 입증하지 않는다.

해설 3 읽기만 하면 쓰기 권한을 반복 이동시키는 조건이 없다. 서로 다른 값을 써도 같은 라인이라면 거짓 공유가 생길 수 있다.

참고 자료: Linux 커널 거짓 공유 문서 · Python array 문서 · Intel 멀티스레드 개발 가이드. 공식 자료는 사실 확인에만 사용했다. 설명·예제·문제·도식은 이 원고를 위해 새로 작성했다.

다음 장은 이 메모리 관점을 자료구조 선택에 적용한다. 배열·연결 리스트·해시맵의 복잡도 표에서 빠지는 비용을 함께 읽는다.