RAM의 신화

2024년 12월 19일RedditHacker News러시아어

RAM의 신화란 현대 컴퓨터 메모리가 완전한 랜덤 액세스 메모리처럼 동작한다는 믿음이다. 캐시는 작은 데이터에 대한 최적화로 여겨진다. 즉, L2에 들어가면 더 빨리 처리되고, 들어가지 않으면 방법이 없다는 식이다.

아마도 다음과 같은 코드가 데이터를 샤딩(분할)하는 가장 빠른 방법이라고 믿을 것이다(여기서는 Python을 의사 코드로 쓴다. 당신이 좋아하는 저수준 언어라고 생각해도 된다):

groups = [[] for _ in range(n_groups)]
for element in elements:
    groups[element.group].append(element)

확실히 이 코드는 선형(즉, 점근적으로 최적)이며, 어차피 무작위 인덱스를 접근해야 하므로 어떤 경우에도 캐시가 도움이 되지 않는다고 생각하기 쉽다.

현실에서는 그룹 수가 많을 때 이 방식은 많은 성능을 버리고 있으며, 어떤 점근적으로 더 느린 알고리즘들이 샤딩을 훨씬 더 빠르게 수행할 수 있다. 이들 알고리즘은 주로 디스크 기반 데이터베이스에서 쓰이지만, 놀랍게도 메모리(RAM) 내 데이터에도 유용하다.

위 알고리즘은 거의 매 반복마다 캐시 미스를 낸다. 캐시 미스를 막는 유일한 방법은 메모리 접근을 더 정렬된 순서로 만드는 것이다. 요소들이 미리 group 기준으로 정렬되어 있다면 아주 좋다. 그렇지 않다면, for 루프 전에 접근 순서를 정렬할 수 있다:

elements.sort(key = lambda element: element.group)

정렬에는 시간이 들지만, 그 대가로 for 루프에서의 캐시 미스를 완전히 제거한다. 데이터가 캐시에 들어가지 않을 만큼 크다면 이는 순이익이다. 보너스로, 개별 리스트를 만드는 대신 group-by 연산으로 대체할 수 있다:

elements.sort(key = lambda element: element.group)
groups = [
    group_elements
    for _, group_elements
    in itertools.groupby(elements, key = lambda element: element.group)
]

캐시를 의식한 정렬 알고리즘은 여럿 있지만, 인덱스가 정수일 뿐이라면 여기서는 기수 정렬(radix sort)이 가장 잘 맞는다. 기성 구현 중에서는 Rust에서 radsort가 가장 성능이 좋았다.

속도 향상

이것만으로도 큰 데이터에 대해 단순 알고리즘보다 이미 낫지만, 더 빠르게 만들 수 있는 요령이 많다.

많은 정렬 API는 실제로는 그렇지 않더라도 데이터가 제자리(in-place)에서 정렬되는 것처럼 보이게 하려 한다. 이는 정렬된 데이터를 특정 형식으로 메모리에 명시적으로 써야 함을 뜻한다. 하지만 우리가 필요한 것이 그룹을 순회하는 것뿐이라면, 제너레이터나 콜백을 사용해 이를 피할 수 있다:

# 32비트 인덱스를 가정
def radix_sort(elements, bits = 32):
    # 기본 사례: 정렬할 게 없거나 모든 인덱스가 동일
    if len(elements) <= 1 or bits <= 0:
        yield from elements
        return

    # 아직 보지 않은 인덱스의 최상위 바이트로 분할
    buckets = [[] for _ in range(256)]
    for element in elements:
        buckets[(element.index >> max(0, bits - 8)) & 0xff].append(element)

    # 버킷을 재귀적으로 정렬
    for bucket in buckets:
        yield from radix_sort(bucket, bits - 8)

개별 그룹을 그대로 내보내어 groupby 단계 자체를 없앨 수도 있다:

# 기본 사례: 정렬할 게 없거나 모든 인덱스가 동일
if bits <= 0:
    if elements:
        # 그룹!
        yield elements
    return

이 코드의 다음 문제는 append 시 버킷 배열을 계속 재할당한다는 점이다. 이는 불필요하게 자주 memcpy를 유발하고 캐시에 좋지 않다. 흔한 해결책은 미리 크기를 계산하는 것이다:

def get_bucket(element):
    return (element.index >> max(0, bits - 8)) & 0xff

sizes = Counter(map(get_bucket, elements))

# Python은 리스트에 실제로 예약 용량을 둘 수 없지만, 여기서는 `reserve`가 그렇게 한다고 치자. C++에서는
# `std::vector::reserve`, Rust에서는 `Vec::with_capacity`에 해당한다.
buckets = [reserve(sizes[i]) for i in range(256)]
for element in elements:
    buckets[get_bucket(element)].append(element)

하지만 이 방법은 두 번 순회가 필요하므로, 이상적으로는 코드를 단일 패스로 유지하고 싶다. 인덱스가 무작위라면, 둘 다 얻을 수 있다. 각 버킷의 크기를 len(elements) / 256으로 추정 하고 그만큼 예약하자. 과소추정하면 남는 것들이 생기는데, 이는 작은 별도 저장소에 보관한다:

class Bucket:
    reserved: list
    leftovers: list

    def __init__(self, capacity):
        self.reserved = reserve(capacity) # 의사 코드
        self.leftovers = []

    def append(self, element):
        if len(self.reserved) < self.reserved.capacity(): # 의사 코드
            self.reserved.append(element)
        else:
            self.leftovers.append(element)

    def __len__(self):
        return len(self.reserved) + len(self.leftovers)

    def __iter__(self):
        yield from self.reserved
        yield from self.leftovers

확률 분포가 여기서 도움이 된다. 입력이 크면 leftovers로 넘치는 요소의 비율은 극히 작다. 따라서 메모리 오버헤드는 아주 작고, leftovers로 푸시할 때의 재할당도 빠르며, 버킷팅(그리고 버킷 순회)은 캐시 친화적이다.

간단한 마이크로 최적화로는 한 번만 할당하고, 반환된 메모리를 여러 청크로 나누어 사용하는 것이다. 이는 malloc을(또는 벡터 생성을) 여러 번 호출하는 것을 피한다. 할당은 꽤 느리며, 이런 방식은 그 영향을 싸게 줄여 준다.

작은 입력에서는 단순 알고리즘으로 전환하는 것이 성능을 높인다. 𝒪(n log n) 코드의 영향이 그 구간에서 더 두드러지기 때문이다. 다만 radix_sort는 재귀적이므로, 매 재귀 단계에서 이 체크를 수행할 수 있어 큰 데이터에서도 이득을 볼 수 있다:

# 기본 사례: 단순 알고리즘을 쓸 만큼 충분히 작음
if len(elements) <= CUTOFF or bits <= 8:
    counts = [0] * 256
    for element in elements:
        counts[element.index & 0xff] += 1

    groups = [[] for _ in range(256)]
    for element in elements:
        groups[get_bucket(element)].append(element)

    for group in groups:
        if group:
            yield group
    return

최적의 CUTOFF는 기계에 크게 의존한다. 캐시 각 계층과 RAM의 상대 속도, 캐시 크기, 데이터 타입 등에 따라 달라진다. 64비트 정수 기준으로, 최적값이 50k, 200k, 1M인 머신들을 봤다. 이를 결정하는 가장 좋은 방법은 런타임에서 벤치마킹하는 것이다. 데이터베이스 같은 장시간 실행되는 소프트웨어라면 충분히 수용 가능한 접근이다.

벤치마크

간단한 벤치마크를 보자.

입력 데이터는 무작위 64비트 정수 배열이다. 이를 단순 곱셈 해시로 그룹화하고, 버킷에 대해 간단한 분석을 수행한다. 예를 들어 각 버킷의 최소값들을 더한다고 하자. (실제 파이프라인에서는 그 아래 단계에서 또 다른 캐시 친화적 알고리즘으로 버킷들을 소비할 것이다.)

다음 두 구현을 비교한다:

1. 단순 알고리즘(할당 최적화 포함).
2. 위 최적화를 모두 적용하고 최적 커트오프를 사용한 기수 정렬 기반 그룹화.

평균 그룹 크기는 10이다.

코드는 GitHub에 있다.

최적화된 알고리즘의 상대 효율은 데이터가 커질수록 증가한다. 단순 알고리즘과 최적화된 알고리즘 모두 결국 일정한 처리량에 수렴한다. 머신에 따라 그 향상 폭은 극한에서 2.5×에서 9×까지 다양하다.

결과는 다음과 같다(A, Y, M은 서로 다른 장치를 의미):

그럴 만한 가치가 있을까? 성능이 절대적으로 필요하고 샤딩이 파이프라인에서 큰 비중을 차지한다면, 당연히 쓰는 것이 좋다. 예를 들어 나는 주어진 데이터셋에 대해 충돌 없는 해시를 찾는 데 이 방법을 사용한다. 하지만 모든 최적화와 마찬가지로, 코드 복잡도 증가가 감수할 만한지 따져봐야 한다.

최소한 빅데이터를 다룬다면, 이 요령을 기억해 두는 것이 좋다.

또 하나의 교훈이 있다. 디스크 상의 데이터를 다룰 때, 단순히 메모리 매핑해 일반적인 메모리 내 알고리즘을 돌려서는 안 된다는 것을 누구나 안다. 그렇게 하는 것이 불가능한 것은 아니지만, 성능은 나쁠 것이다. 여기서의 교훈은 이것이 RAM과 캐시에도 그대로 적용된다는 점이다. 데이터가, 이를테면 32 MiB를 넘는다면, 데이터 분할이나 외부 메모리 알고리즘으로의 전환을 진지하게 고려해야 한다.