About memory pressure, lock contention, and Data-oriented Design

메모리 압박, 락 경합, 그리고 데이터 지향 설계에 대하여

2026년 2월 23일 · 읽는 데 28분 · 키워드: rust, performance, lock, memory, data-oriented design Edit this page

성능에 관한 이야기를 하나 들려드리려고 합니다. 최근 저는 같은 방에서 “메모리 압박(Memory Pressure)”과 “락 경합(Lock Contention)”을 만났습니다. 이 둘을 알아차리는 데 꽤 시간이 걸렸죠. 전설에 따르면 이런 일은 희귀한 저수준 시스템에서만 벌어진다는데, 저는 그 전설을 반박하러 왔습니다. 탐험하는 과정에서 상위(고차) 스트림에서 웃긴 버그 하나도 고치게 되었고요. 운이 좋게도, 마지막에는 달콤한 디저트까지 있습니다! 이 이야기는 데이터 지향 설계(Data-oriented Design, DoD)를 소개하고, 그것이 실행 시간을 98.7% 개선하고 처리량을 7718.5%나 끌어올린 과정을 보여주기 위한 핑계이기도 합니다. 맛있는 이야기를 만들 재료가 다 모였네요. 자, 요리해 봅시다. bon appétit!

아름다운 어느 아침…#

디그마 디파이(Dygma Defy)를 켜고, 컴퓨터 잠금을 풀고, 동료들의 메시지를 확인하던 중, 갑자기 이런 메시지를 보게 됩니다:

누군가 방 목록(Room List)이 멈춘 것(frozen)도 겪고 있나요?

그렇죠. 몇 년 전부터 저는 Element에 고용되어 Matrix Rust SDK에서 일하고 있습니다. 완전하고 현대적이며 크로스플랫폼이고 빠른 Matrix 클라이언트나 봇을 만들고 싶다면, 이 SDK는 훌륭한 선택입니다. SDK는 많은 크레이트로 구성되어 있습니다. matrix_sdk_crypto처럼 스택 하단에 있어 개발자가 직접 쓰는 것을 목표로 하지 않는 것도 있고, 스택 상단 —가장 위는 사용자 인터페이스(UI)를 위한 matrix_sdk_ui— 에 위치한 것도 있습니다. 약간 의견이 들어가 있긴 하지만, 현대적인 Matrix 클라이언트라면 누구나 기대하는 고품질 기능을 제공하도록 설계되어 있습니다.

그 기능 중 하나가 방 목록(Room List)입니다. 방 목록은 메시징 앱에서 사용자가 가장 많은 시간을 보내는 곳 중 하나죠(타임라인, 즉 방의 메시지 목록과 함께). 이 컴포넌트에 대한 기대치는 대략 이렇습니다:

매우 빨라야 함,
모든 방을 나열해야 함,
방과 상호작용(열기, 읽지 않음 표시 등)해야 함,
방을 필터링할 수 있어야 함,
방을 정렬할 수 있어야 함.

오늘 관심 있는 부분은 여기입니다: 방을 정렬하기. 방 목록은… 방을 들고 있지 않습니다. 실제로는 _방에 대한 업데이트 스트림_을 제공합니다. 좀 더 정확히 말하면 Stream<Item = Vec<VectorDiff<Room>>>입니다. 이게 무슨 뜻일까요? 이 스트림은 방들의 “diff(차이)” 벡터를 내보냅니다. 저는 반응형 프로그래밍에 대한 시리즈도 쓰고 있으니, 더 읽어보고 싶으시면 참고하세요. 그게 아니라면, 지금 알아야 할 핵심만 설명하겠습니다.

VectorDiff 타입은 eyeball-im 크레이트에서 왔고, Matrix Rust SDK를 위해 반응형 프로그래밍의 튼튼한 기반으로 처음 만들어졌습니다. 생김새는 이렇게 생겼습니다:

rust
pub enum VectorDiff<T> {
    Append {
        values: Vector<T>,
    },
    Clear,
    PushFront {
        value: T,
    },
    PushBack {
        value: T,
    },
    PopFront,
    PopBack,
    Insert {
        index: usize,
        value: T,
    },
    Set {
        index: usize,
        value: T,
    },
    Remove {
        index: usize,
    },
    Truncate {
        length: usize,
    },
    Reset {
        values: Vector<T>,
    },
}

이것은 ObservableVector의 _변경_을 표현합니다. ObservableVector는 Vec와 비슷하지만, 변경에 구독할 수 있고, 그 결과로… 네… VectorDiff들을 받게 됩니다!

방 목록 타입은 여러 스트림을 하나의 스트림으로 합쳐 “방 목록”을 나타내는 단일 스트림을 만듭니다. 예를 들어 인덱스 3의 방에 새 메시지가 도착했다고 상상해 봅시다. 해당 방의 “미리보기”(방 이름 아래 표시되는 가장 최근 이벤트; 예: Alice: Hello!)가 바뀝니다. 그리고 방 목록은 방을 “최근성(recency)”(방에서 무언가가 발생한 시간) 기준으로 정렬합니다. “미리보기”가 바뀌면 “최근성”도 바뀌고, 따라서 그 방은 정렬되어 위치가 바뀝니다. 그러면 방 목록 스트림은 다음을 내보내길 기대합니다:

새 “미리보기” 때문에 VectorDiff::Set { index: 3, value: new_room },
이어서 방을 제거하기 위한 VectorDiff::Remove { index: 3 }, 그리고 즉시 뒤따라
방을 목록 맨 위에 넣기 위한 VectorDiff::PushFront { value: new_room }.

이 반응형 프로그래밍 메커니즘은 극도로 효율적임이 입증되어 왔습니다.

Le Comte

계산해 보니 VectorDiff<Room>의 크기는 72바이트입니다(대부분 Room이 실제 구조체 타입 위에 Arc를 포함하기 때문입니다). 업데이트로서는 꽤 작죠. 메모리 사용량이 작을 뿐 아니라, FFI 경계도 비교적 쉽게 넘어갈 수 있어 Swift나 Kotlin 같은 언어로 매핑하기도 좋습니다. 이런 언어들은 SwiftUI나 Jetpack Compose처럼 UI 컴포넌트를 제공하니까요.

물론입니다! 이 두 UI 컴포넌트는 VectorDiff를 List 컴포넌트의 업데이트 연산으로 매핑하기가 아주 직관적입니다. 둘은 실제로 (놀랄 만큼) 서로 꽤 비슷합니다1.

항상 훌륭한 옆길로 새는 동반자네요, 고맙습니다. 다시 문제로 돌아가죠:

방 목록에서 “frozen(멈춤)”은 무슨 뜻인가요?

방 목록이 그냥… 텅 비어 보인다는 뜻입니다. blank, empty, vide, vacía, vuoto, خلو… 뭐, 감 잡으셨죠.

무엇이 방 목록을 멈추게 만들 수 있나요?

가능성을 생각해 봅시다.

Le Factotum

제가 이 작업을 돕게 해주신다면 정말 기쁠 것 같습니다.

네트워크 동기화가 제대로 돌지 않아 방 목록이 멈춘 것처럼 보이는 건가? 음, 아니요. 여기선 모든 것이 정상입니다. 게다가 로컬 데이터도 표시돼야 하죠.
방 목록이 사용하는 “소스 스트림”들이 기대한 업데이트를 내보내지 못하는가? 아니요, 아주 잘 돌아갑니다.
“스트림 병합”이 어떤 이유로 깨졌나? 아니요, 멀쩡해 보입니다.
스트림 필터링? 오래전부터 건드린 적 없습니다.
정렬? 아, 어쩌면요. 여기는 뭔가 바뀐 게 있었던 것 같군요…

실제로 최근에 sorter 하나를 바꿨습니다. 방 목록 스트림이 어떻게 계산되는지 봅시다.

rust
let stream = stream! {
    loop {
        // Wait for the filter to be updated.
        let filter = filter_cell.take().await;

        // Get the “raw” entries.
        let (initial_values, stream) = self.entries();

        // Combine normal stream updates with other room updates.
        let stream = merge_streams(initial_values.clone(), stream, other_updates);

        let (initial_values, stream) = (initial_values, stream)
            .filter(filter)
            .sort_by(new_sorter_lexicographic(vec![
                // Sort by latest event's kind.
                Box::new(new_sorter_latest_event()),
                // Sort rooms by their recency.
                Box::new(new_sorter_recency()),
                // Finally, sort by name.
                Box::new(new_sorter_name()),
            ]))
            .dynamic_head_with_initial_value(page_size, limit_stream);

        // Clearing the stream before chaining with the real stream.
        yield once(ready(vec![VectorDiff::Reset { values: initial_values }]))
            .chain(stream);
    }
}
.switch();

여기엔 많은 일이 벌어지고 있습니다. 안타깝지만 이 아름다운 예술작품2의 모든 것을 설명하진 않겠습니다.

.filter(), .sort_by(), .dynamic_head_with_initial_value()는 eyeball-im-util 크레이트의 메서드들입니다. 스트림을 필터링하고 정렬하는 등에 쓰이며, 본질적으로 Stream<Item = Vec<VectorDiff<T>>>를 다른 Stream<Item = Vec<VectorDiff<T>>>로 매핑합니다. 다시 말해, filtering이나 sorting 등을 “시뮬레이션”하기 위해 VectorDiff들을 실시간으로 바꿔 끼웁니다. Sort 고차 스트림으로 아주 구체적인 예를 봅시다(다음 예시는 주로 Sort 문서에서 가져온 것이지만, 제가 이 알고리즘을 썼으니 독자 여러분도 용서해 주시리라 믿습니다).

char 벡터가 있다고 해봅시다. 우리는 이 벡터에 대한 변경 스트림(유명한 VectorDiff)을 원합니다. 또한 _변경_만을 수정해 정렬된 벡터를 _시뮬레이트_하고 싶습니다. 해법은 다음과 같습니다:

rust
use std::cmp::Ordering;

use eyeball_im::{ObservableVector, VectorDiff};
use eyeball_im_util::vector::VectorObserverExt;
use stream_assert::{assert_next_eq, assert_pending};

// Our comparison function.
fn cmp<T>(left: &T, right: &T) -> Ordering
where
    T: Ord,
{
    left.cmp(right)
}

// Our vector.
let mut vector = ObservableVector::<char>::new();
let (initial_values, mut stream) = vector.subscribe().sort_by(cmp);
//                                                            ^^^
//                                                            |
//                                                            there

assert!(initial_values.is_empty());
assert_pending!(stream);

좋습니다. vector는 비어 있으니 구독으로 얻은 초기값도 비어 있고, stream은 pending 상태입니다3. 이제 장난감을 가지고 놀 시간 아닌가요?

rust
// Append unsorted values.
vector.append(vector!['d', 'b', 'e']);

// We get a `VectorDiff::Append` with sorted values!
assert_next_eq!(
    stream,
    VectorDiff::Append { values: vector!['b', 'd', 'e'] }
);
assert_pending!(stream);

// Let's recap what we have. `vector` is our `ObservableVector`,
// `stream` is the “sorted view”/“sorted stream” of `vector`:
//
// | index    | 0 1 2 |
// | `vector` | d b e |
// | `stream` | b d e |

지금까지는 좋습니다. 들어온 연산 하나에, 나가는 연산 하나. 더 복잡해지면 더 재미있죠:

rust
// Append multiple other values.
vector.append(vector!['f', 'g', 'a', 'c']);

// We get three `VectorDiff`s this time!
assert_next_eq!(
    stream,
    VectorDiff::PushFront { value: 'a' }
);
assert_next_eq!(
    stream,
    VectorDiff::Insert { index: 2, value: 'c' }
);
assert_next_eq!(
    stream,
    VectorDiff::Append { values: vector!['f', 'g'] }
);
assert_pending!(stream);

// Let's recap what we have:
//
// | index    | 0 1 2 3 4 5 6 |
// | `vector` | d b e f g a c |
// | `stream` | a b c d e f g |
//              ^   ^     ^^^
//              |   |     |
//              |   |     with `VectorDiff::Append { .. }`
//              |   with `VectorDiff::Insert { index: 2, .. }`
//              with `VectorDiff::PushFront { .. }`

vector 자체는 절대 정렬되지 않는다는 점을 주목하세요. 이것이 이런 VectorDiff 고차 스트림의 힘입니다: 가볍고 —무엇보다— 조합 가능합니다! 다시 말하지만 우리는 언제나 Stream<Item = Vec<VectorDiff<T>>>를 동일한 타입의 다른 스트림으로 매핑하고 있을 뿐입니다. 초기값을 제외하고 전체 컬렉션을 통째로 계산하지 않습니다. 오직 변경만 처리되며 그 변경이 계산을 촉발합니다. 여기에 Stream이 Future처럼 lazy(폴링될 때만 동작)라는 사실까지 더하면, 매우 효율적이 됩니다. 그리고…

Le Comte

… 제가 좋아하는 옆길 동반자로서 이런 디테일을 정말 깊이 감사히 여기지만, 혹시… 이제… 주제로… 돌아가야 하지 않을까요?

무슨 주제요? 아! 방 목록이 멈춘 문제! sorter는 범인이 아닙니다. 여기. 만족하셨나요? 짧게.

하지만 이런 디테일도 중요했습니다. 어느 정도는요. 읽는 길에 뭔가 배워가셨길 바랍니다. 다음으로는 sorter가 어떻게 동작하는지, 그리고 어떻게 그것이 메모리 압박과 락 경합의 원인이 될 수 있는지를 보겠습니다.

무작위성#

한 발 물러서서 저는 스스로에게 물었습니다: 정말 멈춘 게 맞나? 더 최악인 점: 저는 이 문제를 재현할 수가 없었습니다! 보고자들조차도 일관되게 재현하지 못했습니다. 음, 랜덤 문제? 다행히도 보고자 두 명이 집요했습니다. 결국 분석을 얻어냈습니다.

Android Studio에서 본 Element X의 메모리 분석(Element X는 Matrix Rust SDK 기반). 콜백 트리와 각 노드의 할당/해제 수를 보여줍니다. Jorge에게 감사!

그리고 세상에, eyeball_im_util::vector::sort::SortBy 타입에서 엄청난 메모리 할당이 보입니다. 정확히 322,042회, 총 743MiB입니다! 방 목록에 방이 몇 개인지 정확히 기억나진 않지만 대략 500~600개쯤일 겁니다.

원본 이미지 다운로드: AVIF, WebP, PNG.

방 목록은 멈춘 게 아니었습니다. 값을 내보내는 데 엄청나게 오래 걸렸던 겁니다. 폰에서는 가끔 최대 5분까지도요. 좋아요. 여기엔 해결해야 할 문제가 두 가지 있습니다:

왜 랜덤하게 나타나는가?
왜 이렇게 많은 메모리 할당/해제가 발생하는가?

두 번째 문제는 다음 섹션에서 논의하겠습니다. 이 섹션에서는 첫 번째 문제부터 시작하죠.

처음으로 돌아가 봅시다. eyeball_im_util::vector::sort::SortBy는 이렇게 사용됩니다:

rust
stream
    .sort_by(new_sorter_lexicographic(vec![
        Box::new(new_sorter_latest_event()),
        Box::new(new_sorter_recency()),
        Box::new(new_sorter_name()),
    ]))

sort_by는 sorter, 즉 new_sorter_lexicographic를 받습니다. 이는 matrix_sdk_ui::room_list::sorters에 있는 함수로, “사전식(lexicographic) sorter”를 만드는 생성자입니다. 모든 sorter는 Sorter 트레이트를 구현해야 하는데, 다시 말해 matrix_sdk_ui에 있는 단순한 트레이트입니다:

rust
// Trait “alias”.
pub trait Sorter: Fn(&Room, &Room) -> Ordering {}

// All functions `F` are auto-implementing `Sorter`.
impl<F> Sorter for F
where
    F: Fn(&Room, &Room) -> Ordering {}

즉, &Room 두 개를 받아 Ordering을 반환하는 모든 함수는 sorter로 간주됩니다. 명확하죠. 그런데… 사전식 sorter는 무엇일까요?

Le Procureur

정말 new_sorter_lexicographic의 문서를 인용해야 하나요? 제 일이 비극으로 변하고 있습니다.

이 함수는 여러 sorter를 순서대로 실행하는 새 sorter를 만듭니다. n번째 sorter가 Ordering::Equal을 반환하면 다음 sorter를 호출합니다. 어떤 sorter가 Ordering::Greater 또는 Ordering::Less를 반환하는 즉시 멈춥니다.

이는 데카르트 곱에 대해 정의된 사전식 순서의 구현입니다.

요컨대 우리는 3개의 sorter를 실행하고 있습니다: 최신 이벤트, 최근성, 이름.

이들 sorter는 어떤 형태의 랜덤성도 사용하지 않습니다. 막다른 길이군요. 그렇다면 eyeball_im_util의 SortBy 자체를 봐야 할까요? 문서를 스크롤, 초기 패치를 읽고, 음, 이진 탐색 언급이 있네요, 코드로 점프, 아, 여기 코멘트를 보세요:

값의 _위치_를 찾을 때(예: 새 값을 어디에 삽입할까?), Vector::binary_search_by를 사용한다 — Vector가 정렬되어 있기 때문에 가능하다. 값의 _정렬되지 않은 인덱스_를 찾을 때는 Iterator::position을 사용한다.

Vector::binary_search_by 문서엔 랜덤성 얘기가 없습니다. 또 막다른 길.

Le Comte

방 목록은 멈춘 것처럼 보이지만 실제로는 비어 보입니다. 문제는 스트림이 업데이트를 받는 순간이 아니라, 스트림이 “생성될 때” —즉 업데이트를 받기 전에 초기 아이템을 처음 정렬할 때— 발생하는 거죠.

그리고 코멘트에서 “Vector가 정렬되어 있기 때문에 가능하다”고 했는데, 이는 어딘가의 “벡터”(버퍼)가 어떤 방식으로든 _정렬되었다_는 뜻입니다. 어떻게 생각하시나요?

아! 훌륭합니다. 맞습니다! SortBy의 생성자(또는 구현)를 보면 Vector::sort_by를 쓰고 있습니다. 그리고 이게 무엇에 의존하냐면… 두구두구… 퀵소트입니다! 경로를 따라가면 퀵소트를 위해 의사 난수 생성기(PRNG)를 만든다는 것도 보입니다.

후우. 드디어. 차 한 잔과 비스킷4 먹을 시간입니다.

제 추측은 이렇습니다. (의사)무작위로 생성되는 피벗 인덱스에 따라 비교 횟수가 실행마다 달라질 수 있습니다. 병적인 경우로 들어가 비교가 많아지면 메모리 압박이 커지고, 정렬이 느려지고, 그래서… 공포영화 음악을 깔며… ‘The Frozen Room List™’가 되는 거죠!

메모리 압박#

메모리 할당기는… 음… 메모리를 할당합니다. 이게 단순한 문제라고 생각한다면 그 불쾌한 생각은 빨리 거두세요: 무례한 사람 같으니! 메모리는 메모리 할당기가 사용하는 전략에 따라 관리됩니다. 유일한 정답은 없습니다. 각 할당기는 트레이드오프를 가집니다. 비슷한 작은 객체를 여러 번 연속으로 할당/재배치해야 하나요? 고정 크기 블록이 필요하나요, 동적 블록이 필요하나요 등등.

메모리 할당은 공짜가 아닙니다. 할당기 자체의 비용도 있고(커스텀 할당기로 완화할 수 있을지도 모르지만), 하드웨어 비용도 있는데, 이는 상대적으로 완화하기가 어렵습니다. 메모리는 힙, 즉 RAM (메인 메모리)에 할당됩니다( CPU 캐시: L1, L2…와 혼동하지 마세요). RAM은 좋지만 CPU에서 멀리 있습니다. 힙에 무언가를 할당하는 데는 _시간_이 걸리고…

Le Comte

잠깐만요. 힙에서 데이터를 가져오는 데 100~150나노초 정도라 들었는데요. 이게 어떻게 “비싸죠”? 어떻게 “멀다”는 거죠?

우리가 랜덤 접근(RAM의 R)과 여러 번의 간접 참조를 말하는 건 알겠지만, 그래도 엄청 빠른 것 아닌가요?

음… 판도라의 상자를 열지 말고, 높은 수준을 유지해 봅시다. 주의: 제가 제시할 숫자는 하드웨어에 따라 달라질 수 있지만, 중요한 건 스케일입니다.

작업	시간	“인간 스케일”
L1 캐시에서 가져오기	1ns	1분
분기 예측 실패	3ns	3분
L2 캐시에서 가져오기	4ns	4분
뮤텍스 lock/unlock	17ns	17분
메인 메모리에서 가져오기	100ns	1시간 40분
SSD 랜덤 읽기	16,000ns	11.11일

2020년의 다양한 작업에 대한 지연 시간(출처: UC Berkeley Colin Scott의 Latency Numbers Every Programmer Shoud Know).

두 번째 열의 시간은 나노초(1초의 10억 분의 1)이고, 세 번째 열은 스케일을 직관적으로 이해하기 위해 1ns를 1분으로 치환한 “인간화”된 시간입니다.

L1/L2 캐시와 메인 메모리 차이가 보이시나요? 1ns에서 100ns는, 1분에서 1시간 40분 차이와 같습니다. 그러니 네, 메모리에서 읽는 건 시간이 걸립니다. 그래서 가능한 할당을 줄이려 하는 거죠.

숫자가 불편하신가요? 1ns=1s로 시각화해 봅시다! 왼쪽은 CPU, 오른쪽은 L1 캐시, L2 캐시, 그리고 RAM입니다. “공”은 CPU와 L1/L2/RAM 사이에서 정보를 옮기는 데 걸리는 시간을 나타냅니다.

안타깝게도 우리 경우, 방 목록 초기 방들을 정렬하는 데 322,042번 할당하여 총 743,151,616비트를 할당했고, 할당 1회당 287바이트입니다. 물론 대충 냅킨 계산5하면 200ms 정도여야 합니다. ‘The Frozen Room List™’와는 거리가 멀죠. 하지만 더 많은 일이 벌어지고 있습니다6.

메모리 할당기 얘기를 기억하시나요? 할당기는 _단편화(fragmentation)_를 가능한 피하는 역할도 합니다. 메모리 “블록” 수는 무한하지 않습니다. 블록이 해제되고 나중에 새로 할당할 때, 이전 블록이 더는 उपलब्ध하지 않아 재사용 못 할 수도 있죠. 할당기는 단편화를 제어하면서 적절한 자리를 찾아야 합니다. 새 블록을 넣을 공간을 만들기 위해 기존 블록을 이동해야 할 수도 있습니다(연속된 블록을 갖는 게 종종 더 낫기 때문입니다).

이게 제가 말하는 메모리 압박입니다. 우리는 너무 빠르게 너무 많은 걸 요구하고 있고, Matrix Rust SDK에서 사용하는 메모리 할당기는 이런 사용 사례를 처리하도록 설계되지 않았습니다.

그럼 해결책은?

Le Factotum

한 가지 접근을 제안해도 될까요? 어디서 할당/해제가 발생하는지 찾아봅시다. 그러면 할당 횟수나 할당되는 값의 크기(그리고 해제되는 값의 크기)를 줄여 할당기를 더 행복하게 만들 수 있을 겁니다. 가능한 해결책:

할당 값이 너무 커서 스택에 못 들어간다면, 가능하면 포인터를 반환할 수 있습니다.
전체 값이 필요 없을 수도 있으니, 일부 조각의 포인터만 반환할 수 있습니다.

훌륭한 아이디어입니다. 어떤 sorter가 문제를 만드는지 추적해 봅시다. 최근 수정된 sorter부터: latest_event. 요약하면 이 sorter는 두 방의 LatestEventValue를 비교합니다. 발상이란, 로컬 이벤트 —즉 아직 보내지지 않았거나 보내는 중인 이벤트— 를 나타내는 LatestEventValue를 가진 방이 방 목록 맨 위로 와야 한다는 겁니다. 좋습니다. 핵심 부분을 봅시다:

rust
pub fn new_sorter() -> impl Sorter {
    let latest_events =
        |left: &Room, right: &Room| (left.latest_event(), right.latest_event());

    move |left, right| -> Ordering { cmp(latest_events, left, right) }
}

정렬의 각 반복에서 Room::latest_event가 두 번 호출됩니다. 이 메서드는 다음과 같습니다:

rust
pub fn latest_event(&self) -> LatestEventValue {
    self.info.read().latest_event.clone()
}

아, 여기군요. info 값에 대해 read 락을 획득하고, latest_event 필드를 읽고, 값을 clone합니다. clone은 여기서 중요합니다. read 락을 오래 잡고 싶지 않거든요. 이게 범인입니다. LatestEventValue의 크기는 144바이트입니다(이벤트 자체의 크기는 동적이라 포함되지 않습니다).

더 가기 전에, 다른 sorter에도 비슷한 문제가 있는지 확인해볼까요? 다른 sorter들을 보니, 오!, recency sorter도 latest_event 메서드를 사용합니다! 젠장, 짜증나네요.

질문: LatestEventValue 전체가 필요한가요? 아마 아니겠죠!

latest_event sorter는 이 LatestEventValue가 _로컬_인지 여부만 알면 됩니다.
recency sorter는 LatestEventValue의 타임스탬프만 알면 됩니다.

그러니 두 sorter에서, 정렬 반복마다, 두 방에 대해 전체 값을 통째로 복사하는 대신, 더 구체적인 메서드를 만듭시다:

rust
pub fn latest_event_is_local(&self) -> bool {
    self.info.read().latest_event.is_local()
}

pub fn latest_event_timestamp(&self) -> Option<MilliSecondsSinceUnixEpoch> {
    self.info.read().latest_event.timestamp()
}

이렇게만 했는데 room_list 벤치마크 기준으로 처리량이 18% 개선됐습니다. 패치가 적용된 모습을 볼 수 있습니다. 이제 메모리 압박에 대한 승리를 선언할 수 있을까요?

Le Comte

실례지만, 저는 승리라고 생각하지 않습니다. 할당 크기는 줄였지만, 할당 횟수 자체는 줄이지 않았습니다.

음, 사실 latest_event_is_local은 bool을 반환합니다. 스택에 들어갑니다. latest_event_timestamp는 Option<MilliSecondsSinceUnixEpoch>를 반환하는데, MilliSecondsSinceUnixEpoch는 Uint이고, 그 자체가 f64입니다. 이것도 스택에 들어갑니다.

그래서 네, 할당 횟수는 크게 줄었을 겁니다. 처리량 18% 개선도 그걸 설명하죠. 하지만 보고자들은 5분 정도의 지연을 말했습니다. 남은 4분 6초는 어떻게 설명하죠? 여전히 용납할 수 없지 않나요?

맞습니다! 200ms(우리의 냅킨 계산) 이상은 여기서 용납 불가입니다. 메모리 압박은 중요한 문제였고 이제 해결됐지만, 유일한 문제는 아니었습니다.

락 경합#

꼼꼼한 독자라면 우리가 여전히 락을 다루고 있다는 걸 알아챘을 겁니다.

rust
self.info.read().latest_event.…
//        ^^^^^^
//        |
//        this read lock acquisition

322,042번 할당이 있었다는 걸 기억하시나요? 그건 기본적으로 latest_event 메서드 호출 횟수이고, 즉…

Le Comte

… 락이 322,042번 획득된다는 뜻이죠!

…

… 아닌가요?

… 맞습니다… 그리고 제발 중간에 끼어들지 말아주세요. 클라이맥스를 위해 긴장감을 쌓고 있었단 말입니다.

어쨌든 락을 피하는 건 쉽지 않습니다. 하지만 info 주변의 이 락은 특히 짜증납니다. 거의 모든 sorter가 호출하거든요! sorter는 Room에 대한 정보를 필요로 하고, 그 정보가 전부 info 필드에 들어 있으며, 그 info는 RwLock입니다. 흠.

전략을 바꿉시다. 한 발 물러서야 합니다:

sorter들이 이 데이터가 필요하다.
sorter를 실행해도 이 데이터는 바뀌지 않는다.
데이터가 바뀌면 sorter가 다시 실행될 것이다.

그렇다면, 미리 모든 sorter가 필요로 하는 데이터를 한 번에 가져와 단일 타입에 담을 수 있지 않을까요? 데이터가 바뀔 때(즉 sorter가 다시 실행되기 직전) 갱신하면 됩니다.

Le Procureur

여기서의 아이디어는 특정 레이아웃을 중심으로 데이터를 조직하는 것입니다. 데이터 레이아웃에 집중하는 목표는 CPU 캐시 친화적이 되도록 하는 것이죠. 이런 접근을 데이터 지향 설계(Data-oriented Design)라고 합니다.

맞습니다. 타입이 충분히 작다면 L1이나 L2 같은 CPU 캐시에 더 잘 들어갑니다. 얼마나 빠른지 기억하시나요? 1ns와 4ns로, 메인 메모리의 100ns보다 훨씬 빠릅니다. 게다가 락 경합과 메모리 압박을 완전히 제거할 수 있습니다!

데이터 지향 설계(DoD)를 더 배우고 싶다면 다음 발표들7을 강력 추천합니다.

Video: Data-Oriented Design and C++, by Mike Acton, at the CppCon 2014

어떤 프로그램이든 목적은 데이터 변환뿐이다. 콘솔 게임 개발이라는 성능 임계 도메인에서, 이 목표와 상충하는 C++의 일반적인 접근들을 다룬다. 또한 C++ 컴파일러에 내재된 한계와 그 한계가 데이터 변환에서 언어를 실용적으로 사용하는 데 어떻게 영향을 미치는지도 보여준다. 슬라이드 보기.

Video: Cpu Caches and Why You Care, by Scott Meyers, at the code::dive conference 2014

CPU 캐시와 그것이 프로그램 성능에 미치는 영향을 탐구한다.

자, 진지하게 가봅시다. 여기서 데이터 지향 설계를 시도해보죠. 우선 필요한 데이터를 모두 단일 타입에 넣습니다:

rust
pub struct RoomListItem {
    /// Cache of `Room::latest_event_timestamp`.
    cached_latest_event_timestamp: Option<MilliSecondsSinceUnixEpoch>,

    /// Cache of `Room::latest_event_is_local`.
    cached_latest_event_is_local: bool,

    /// Cache of `Room::recency_stamp`.
    cached_recency_stamp: Option<RoomRecencyStamp>,

    /// Cache of `Room::cached_display_name`, already as a string.
    cached_display_name: Option<String>,

    /// Cache of `Room::is_space`.
    cached_is_space: bool,

    // Cache of `Room::state`.
    cached_state: RoomState,
}

impl RoomListItem {
    fn refresh_cached_data(&mut self, room: &Room) {
        self.cached_latest_event_timestamp = room.new_latest_event_timestamp();
        // etc.
    }
}

이 시점에서 RoomListItem의 크기는 64바이트로, 충분히 작습니다!

Le Factotum

요즘 L1/L2 캐시는 수 킬로바이트 크기입니다. 셸에서 sysctl이나 getconf를 실행해 하드웨어가 지원하는 캐시 정보를 확인해 보세요(예: “cache line” 또는 “cache line size”).

제 시스템에서는 L1(데이터) 캐시 크기가 65KB이고 캐시 라인 크기는 128바이트입니다.

이상적으로는 최소한 RoomListItem 하나가 캐시 라인에 들어가길 원합니다. 내부 패딩을 줄여 타입을 더 압축할 수 있다면 더 좋고요. L1에서 _캐시 미스_가 나면 CPU는 L2, 그 다음… 결국 메인 메모리까지 확인합니다. 그래서 캐시 미스 비용은 L1 조회 + 미스 + L2 조회 + … 입니다.

약간의 배관 작업을 하고 나서, 이 새로운 RoomListItem 타입은 방 목록 전반 —모든 필터와 모든 sorter— 에서 사용됩니다. 예를 들어 latest_event sorter는 이제 이렇게 생겼습니다:

rust
pub fn new_sorter() -> impl Sorter {
    let latest_events = |left: &RoomListItem, right: &RoomListItem| {
        (left.cached_latest_event_is_local, right.cached_latest_event_is_local)
    };

    move |left, right| -> Ordering { cmp(latest_events, left, right) }
}

락 획득은 더 이상 필터링이나 정렬 중에 일어나지 않고, 새 업데이트가 발생해 refresh_cached_data를 호출할 때만 일어납니다. 이제 벤치마크 결과를 봅시다.

Before:

text
$ cargo bench --bench room_list
RoomList/Create/1000 rooms × 1000 events
    time:   [53.027 ms 53.149 ms 53.273 ms]
    thrpt:  [18.771 Kelem/s 18.815 Kelem/s 18.858 Kelem/s]

After:

text
$ cargo bench --bench room_list
RoomList/Create/1000 rooms × 1000 events
           time:   [676.29 µs 676.84 µs 677.50 µs]
           thrpt:  [1.4760 Melem/s 1.4775 Melem/s 1.4787 Melem/s]
    change:
           time:   [-98.725% -98.721% -98.716%] (p = 0.00 < 0.05)
           thrpt:  [+7686.9% +7718.5% +7745.6%]
           Performance has improved.

쾅!

보고자들이 말한 5분 지연은 여기서 보이지 않지만, 랜덤했다고 했죠. 그럼에도 성능 영향은 엄청납니다:

18.8Kelem/s에서 1.4Melem/s로,
53ms에서 676µs로, 즉 같은 단위로 비교하면 0.676ms입니다. 78배 더 빠릅니다!
처리량은 7718.5%, 시간은 98.7% 개선됐습니다.

이제 승리를 선언해도 될까요?

Le Comte

겉보기엔 그렇습니다! 보고자들은 더 이상 문제를 재현하지 못했습니다. 해결된 것으로 보입니다! 프로파일러를 보면 벤치마크 실행에서 수백만 번의 할당이 줄어든 것이 보입니다(벤치마크는 셋업에서 할당이 많지만, 차이는 아주 뚜렷합니다).

데이터 지향 설계는 매력적입니다. 컴퓨터가 어떻게 동작하는지, 메모리와 CPU가 어떻게 동작하는지 이해하는 것은 알고리즘 최적화에 필수입니다. 우리가 적용한 변화는 작지만 성능 개선은 매우 컸습니다!

200ms를 넘으면 용납할 수 없다고 했죠. 676µs라면 목표를 달성했다고 봅니다. 냅킨 계산에서의 메인 메모리 접근 비용보다도 낮습니다. 이는 필터와 sorter에서 RAM을 더 이상 (적어도 무식한 방식으로는) 치지 않는다는 뜻이겠죠. 또한 L1/L2 캐시 접근(1~4ns)과 메인 메모리 접근(100ns)의 차이가 평균 40배쯤인데, 우리가 여기서 본 78배와 꽤 비슷합니다. L2보다 L1을 더 자주 친다는 संकेत일 수도 있고, 좋은 징후죠!

벤치마크의 Iteration Times와 Regression 그래프도 흥미롭습니다.

패치 전 Iteration Times. 점들이 어떤 “추세”도 따르지 않습니다. 프로그램이 불규칙하게 동작한다는 명확한 신호입니다.

패치 후 Iteration Times/Regression. 점들이 선형입니다.

두 번째 그래프가 제가 좋아하는 그래프입니다. 예측 가능하거든요.

Le Procureur

이 구체적인 경우, 더 성능을 올리기 어려운 이유는 RoomListItem이 sorter뿐 아니라 필터, 그리고 코드의 다른 곳에서도 쓰이기 때문입니다. 현재 RoomListItem 사용은 데이터 지향 설계 용어로 _Array of Structures_에 해당합니다. 결국 근본에는 Vec<RoomListItem>이 있으니까요. 효율적이지만 _Structure of Arrays_가 더 효율적일 수도 있습니다. 즉,

rust
struct RoomListItem {
    a: bool,
    b: u64,
    c: bool,
}

let rooms: Vec<RoomListItem>;

대신,

rust
struct RoomListItems {
    a: Vec<bool>,
    b: Vec<u64>,
    c: Vec<bool>,
}

let rooms: RoomListItems;

이 되는 거죠.

하지만 우리 상황에서는 적용하기 어렵습니다. sorter가 여러 필드를 걸쳐 순회하니까요. 다만 단일 루프에서 단 하나의 필드만 쓴다는 게 확실하다면, _Structure of Arrays_는 캐시 친화적입니다. CPU 캐시에 덜 많은 데이터를 로드합니다: 패딩이 줄고, 쓸모없는 바이트가 줄죠. 캐시 라인을 더 잘 활용하면 더 빠르게 실행될 가능성이 높고, CPU가 어떤 데이터가 캐시 라인에 로드될지 더 잘 예측해 성능을 더 끌어올릴 수도 있습니다!

참고로 제 역할이 문서 낭독이나 위키피디아 요약에만 국한되진 않습니다.

물론 당신은 가치 있죠! 이제, 깜짝 선물.

디저트#

물론 디저트를 잊으면 안 되죠! 너무 깊게 파고들진 않겠습니다. 패치에 필요한 잔혹한 디테일이 다 들어 있습니다. 요약하면 VectorDiff::Set이 SortBy에서 골치 아픈 버그를 만들 수 있다는 내용입니다. 기본적으로 벡터의 값이 업데이트되면 VectorDiff::Set이 방출됩니다. 그러면 SortBy는 새 VectorDiff를 계산해야 합니다:

값의 예전 위치를 계산하고,
새 위치를 계산한 다음,
그에 따라 적절한 VectorDiff들을 내보냅니다.

하지만 버퍼에서 예전 “값”이 즉시 제거되지 않았고, 항상 제거된 것도 아니었습니다. 이론적으로는 문제 없을 겁니다 —어쨌든 최적화였으니까요— 하지만… 스트림이 다루는 아이템들이 “얕은 클론(shallow clone)”이라면 이야기가 달라집니다. 얕은 클론은 값을 통째로 복사하지 않습니다. 새 값이 생기지만 상태는 원본과 동기화됩니다. 이런 일은 다음 같은 타입에서 일어납니다:

rust
#[derive(Clone)]
struct S {
    inner: Arc<T>
}

여기서 S를 clone한 뒤 inner 필드를 바꾸면, 원본 값도 함께 업데이트됩니다.

이렇게 해서, 체계적으로… 무한 루프를 만들 수 있었습니다. 재밌죠?

더 알고 싶다면 Fix an infinite loop when SortBy<Stream<Item = T>> handles a VectorDiff::Set where T is a shallow clone type 패치를 보세요.

이건 최적화를 서두르다 버그가 생길 수 있는 구체적인 예라고 생각합니다. 제가 “미리 최적화하면 안 된다”는 말은 아닙니다. 저는 오히려 “해야 한다” 쪽입니다. 다만 버그는 때로 아주 미묘하고, 이 버그는 이 알고리즘에서 지름길을 택하지 않았다면 피할 수 있었을 겁니다. 먼저 정확해야 하고, 그 다음 측정하고, 그 다음 개선해야 합니다.

읽는 동안 두어 가지라도 배워가셨고, 즐거우셨길 바랍니다.

리뷰와 피드백을 준 Andy Balaam과 Damir Jelić에게 감사드립니다!

SwiftUI에는 CollectionDifference.Change 열거형이 있습니다. 예를 들어 VectorDiff::PushFront는 Change.insert(offset: 0)과 같습니다. Jetpack Compose에는 MutableList 객체가 있습니다. 예를 들어 VectorDiff::Clear는 MutableList.clear()와 같습니다! ↩
이 Stream이 어떻게 Stream을 만들어내는지, 바깥 스트림과 안쪽 스트림이 어떻게 .switch()로 전환되는지, 우리가 그걸 어떻게 처음부터 구현했는지 정말 이야기하고 싶지만, 아마 다른 글에서 다루는 게 좋겠네요. 그동안 async_rx::Switch를 참고하세요. ↩
stream_assert를 아시나요? Stream에 대해 쉽게 assertion을 적용하려고 우리가 만든 또 다른 크레이트입니다. 아주 편리하죠. ↩
네, biscuit 맞습니다. ↩
Napkin Math 프로젝트를 강력 추천합니다. 또한 SRECON'19의 훌륭한 발표 Advanced Napkin Math: Estimating System Performance from First Principles by Simon Eskildsen도요. ↩
락 경합 기억하시나요? 잠시 기다려 보세요. 이 이야기의 이 단계에서 저는 아직 락 경합이 있다는 것도 몰랐습니다. ↩
발표 보는 걸 좋아하신다면, 제가 시청한 흥미로운 발표들을 모아둔 플레이리스트를 유지관리하고 있습니다. 또한 오래된 글 하루에 컨퍼런스 하나씩, 1년(2017)도 읽어보세요. ↩

❮초당 19k에서 4.2M 이벤트로: SQLite 쿼리 최적화 이야기

연락하기

About memory pressure, lock contention, and Data-oriented Design

메모리 압박, 락 경합, 그리고 데이터 지향 설계에 대하여

2026년 2월 23일 · 읽는 데 28분 · 키워드: rust, performance, lock, memory, data-oriented design Edit this page

아름다운 어느 아침…#

디그마 디파이(Dygma Defy)를 켜고, 컴퓨터 잠금을 풀고, 동료들의 메시지를 확인하던 중, 갑자기 이런 메시지를 보게 됩니다:

누군가 방 목록(Room List)이 멈춘 것(frozen)도 겪고 있나요?

매우 빨라야 함,
모든 방을 나열해야 함,
방과 상호작용(열기, 읽지 않음 표시 등)해야 함,
방을 필터링할 수 있어야 함,
방을 정렬할 수 있어야 함.

rust
pub enum VectorDiff<T> {
    Append {
        values: Vector<T>,
    },
    Clear,
    PushFront {
        value: T,
    },
    PushBack {
        value: T,
    },
    PopFront,
    PopBack,
    Insert {
        index: usize,
        value: T,
    },
    Set {
        index: usize,
        value: T,
    },
    Remove {
        index: usize,
    },
    Truncate {
        length: usize,
    },
    Reset {
        values: Vector<T>,
    },
}

새 “미리보기” 때문에 VectorDiff::Set { index: 3, value: new_room },
이어서 방을 제거하기 위한 VectorDiff::Remove { index: 3 }, 그리고 즉시 뒤따라
방을 목록 맨 위에 넣기 위한 VectorDiff::PushFront { value: new_room }.

이 반응형 프로그래밍 메커니즘은 극도로 효율적임이 입증되어 왔습니다.

Le Comte

항상 훌륭한 옆길로 새는 동반자네요, 고맙습니다. 다시 문제로 돌아가죠:

방 목록에서 “frozen(멈춤)”은 무슨 뜻인가요?

방 목록이 그냥… 텅 비어 보인다는 뜻입니다. blank, empty, vide, vacía, vuoto, خلو… 뭐, 감 잡으셨죠.

무엇이 방 목록을 멈추게 만들 수 있나요?

가능성을 생각해 봅시다.

Le Factotum

제가 이 작업을 돕게 해주신다면 정말 기쁠 것 같습니다.

네트워크 동기화가 제대로 돌지 않아 방 목록이 멈춘 것처럼 보이는 건가? 음, 아니요. 여기선 모든 것이 정상입니다. 게다가 로컬 데이터도 표시돼야 하죠.
방 목록이 사용하는 “소스 스트림”들이 기대한 업데이트를 내보내지 못하는가? 아니요, 아주 잘 돌아갑니다.
“스트림 병합”이 어떤 이유로 깨졌나? 아니요, 멀쩡해 보입니다.
스트림 필터링? 오래전부터 건드린 적 없습니다.
정렬? 아, 어쩌면요. 여기는 뭔가 바뀐 게 있었던 것 같군요…

실제로 최근에 sorter 하나를 바꿨습니다. 방 목록 스트림이 어떻게 계산되는지 봅시다.

rust
let stream = stream! {
    loop {
        // Wait for the filter to be updated.
        let filter = filter_cell.take().await;

        // Get the “raw” entries.
        let (initial_values, stream) = self.entries();

        // Combine normal stream updates with other room updates.
        let stream = merge_streams(initial_values.clone(), stream, other_updates);

        let (initial_values, stream) = (initial_values, stream)
            .filter(filter)
            .sort_by(new_sorter_lexicographic(vec![
                // Sort by latest event's kind.
                Box::new(new_sorter_latest_event()),
                // Sort rooms by their recency.
                Box::new(new_sorter_recency()),
                // Finally, sort by name.
                Box::new(new_sorter_name()),
            ]))
            .dynamic_head_with_initial_value(page_size, limit_stream);

        // Clearing the stream before chaining with the real stream.
        yield once(ready(vec![VectorDiff::Reset { values: initial_values }]))
            .chain(stream);
    }
}
.switch();

여기엔 많은 일이 벌어지고 있습니다. 안타깝지만 이 아름다운 예술작품2의 모든 것을 설명하진 않겠습니다.

rust
use std::cmp::Ordering;

use eyeball_im::{ObservableVector, VectorDiff};
use eyeball_im_util::vector::VectorObserverExt;
use stream_assert::{assert_next_eq, assert_pending};

// Our comparison function.
fn cmp<T>(left: &T, right: &T) -> Ordering
where
    T: Ord,
{
    left.cmp(right)
}

// Our vector.
let mut vector = ObservableVector::<char>::new();
let (initial_values, mut stream) = vector.subscribe().sort_by(cmp);
//                                                            ^^^
//                                                            |
//                                                            there

assert!(initial_values.is_empty());
assert_pending!(stream);

좋습니다. vector는 비어 있으니 구독으로 얻은 초기값도 비어 있고, stream은 pending 상태입니다3. 이제 장난감을 가지고 놀 시간 아닌가요?

rust
// Append unsorted values.
vector.append(vector!['d', 'b', 'e']);

// We get a `VectorDiff::Append` with sorted values!
assert_next_eq!(
    stream,
    VectorDiff::Append { values: vector!['b', 'd', 'e'] }
);
assert_pending!(stream);

// Let's recap what we have. `vector` is our `ObservableVector`,
// `stream` is the “sorted view”/“sorted stream” of `vector`:
//
// | index    | 0 1 2 |
// | `vector` | d b e |
// | `stream` | b d e |

지금까지는 좋습니다. 들어온 연산 하나에, 나가는 연산 하나. 더 복잡해지면 더 재미있죠:

rust
// Append multiple other values.
vector.append(vector!['f', 'g', 'a', 'c']);

// We get three `VectorDiff`s this time!
assert_next_eq!(
    stream,
    VectorDiff::PushFront { value: 'a' }
);
assert_next_eq!(
    stream,
    VectorDiff::Insert { index: 2, value: 'c' }
);
assert_next_eq!(
    stream,
    VectorDiff::Append { values: vector!['f', 'g'] }
);
assert_pending!(stream);

// Let's recap what we have:
//
// | index    | 0 1 2 3 4 5 6 |
// | `vector` | d b e f g a c |
// | `stream` | a b c d e f g |
//              ^   ^     ^^^
//              |   |     |
//              |   |     with `VectorDiff::Append { .. }`
//              |   with `VectorDiff::Insert { index: 2, .. }`
//              with `VectorDiff::PushFront { .. }`

Le Comte

… 제가 좋아하는 옆길 동반자로서 이런 디테일을 정말 깊이 감사히 여기지만, 혹시… 이제… 주제로… 돌아가야 하지 않을까요?

무슨 주제요? 아! 방 목록이 멈춘 문제! sorter는 범인이 아닙니다. 여기. 만족하셨나요? 짧게.

무작위성#

Android Studio에서 본 Element X의 메모리 분석(Element X는 Matrix Rust SDK 기반). 콜백 트리와 각 노드의 할당/해제 수를 보여줍니다. Jorge에게 감사!

원본 이미지 다운로드: AVIF, WebP, PNG.

왜 랜덤하게 나타나는가?
왜 이렇게 많은 메모리 할당/해제가 발생하는가?

두 번째 문제는 다음 섹션에서 논의하겠습니다. 이 섹션에서는 첫 번째 문제부터 시작하죠.

처음으로 돌아가 봅시다. eyeball_im_util::vector::sort::SortBy는 이렇게 사용됩니다:

rust
stream
    .sort_by(new_sorter_lexicographic(vec![
        Box::new(new_sorter_latest_event()),
        Box::new(new_sorter_recency()),
        Box::new(new_sorter_name()),
    ]))

rust
// Trait “alias”.
pub trait Sorter: Fn(&Room, &Room) -> Ordering {}

// All functions `F` are auto-implementing `Sorter`.
impl<F> Sorter for F
where
    F: Fn(&Room, &Room) -> Ordering {}

즉, &Room 두 개를 받아 Ordering을 반환하는 모든 함수는 sorter로 간주됩니다. 명확하죠. 그런데… 사전식 sorter는 무엇일까요?

Le Procureur

정말 new_sorter_lexicographic의 문서를 인용해야 하나요? 제 일이 비극으로 변하고 있습니다.

이는 데카르트 곱에 대해 정의된 사전식 순서의 구현입니다.

요컨대 우리는 3개의 sorter를 실행하고 있습니다: 최신 이벤트, 최근성, 이름.

값의 _위치_를 찾을 때(예: 새 값을 어디에 삽입할까?), Vector::binary_search_by를 사용한다 — Vector가 정렬되어 있기 때문에 가능하다. 값의 _정렬되지 않은 인덱스_를 찾을 때는 Iterator::position을 사용한다.

Vector::binary_search_by 문서엔 랜덤성 얘기가 없습니다. 또 막다른 길.

Le Comte

후우. 드디어. 차 한 잔과 비스킷4 먹을 시간입니다.

메모리 압박#

Le Comte

잠깐만요. 힙에서 데이터를 가져오는 데 100~150나노초 정도라 들었는데요. 이게 어떻게 “비싸죠”? 어떻게 “멀다”는 거죠?

우리가 랜덤 접근(RAM의 R)과 여러 번의 간접 참조를 말하는 건 알겠지만, 그래도 엄청 빠른 것 아닌가요?

작업	시간	“인간 스케일”
L1 캐시에서 가져오기	1ns	1분
분기 예측 실패	3ns	3분
L2 캐시에서 가져오기	4ns	4분
뮤텍스 lock/unlock	17ns	17분
메인 메모리에서 가져오기	100ns	1시간 40분
SSD 랜덤 읽기	16,000ns	11.11일

2020년의 다양한 작업에 대한 지연 시간(출처: UC Berkeley Colin Scott의 Latency Numbers Every Programmer Shoud Know).

두 번째 열의 시간은 나노초(1초의 10억 분의 1)이고, 세 번째 열은 스케일을 직관적으로 이해하기 위해 1ns를 1분으로 치환한 “인간화”된 시간입니다.

그럼 해결책은?

Le Factotum

할당 값이 너무 커서 스택에 못 들어간다면, 가능하면 포인터를 반환할 수 있습니다.
전체 값이 필요 없을 수도 있으니, 일부 조각의 포인터만 반환할 수 있습니다.

rust
pub fn new_sorter() -> impl Sorter {
    let latest_events =
        |left: &Room, right: &Room| (left.latest_event(), right.latest_event());

    move |left, right| -> Ordering { cmp(latest_events, left, right) }
}

정렬의 각 반복에서 Room::latest_event가 두 번 호출됩니다. 이 메서드는 다음과 같습니다:

rust
pub fn latest_event(&self) -> LatestEventValue {
    self.info.read().latest_event.clone()
}

질문: LatestEventValue 전체가 필요한가요? 아마 아니겠죠!

latest_event sorter는 이 LatestEventValue가 _로컬_인지 여부만 알면 됩니다.
recency sorter는 LatestEventValue의 타임스탬프만 알면 됩니다.

그러니 두 sorter에서, 정렬 반복마다, 두 방에 대해 전체 값을 통째로 복사하는 대신, 더 구체적인 메서드를 만듭시다:

rust
pub fn latest_event_is_local(&self) -> bool {
    self.info.read().latest_event.is_local()
}

pub fn latest_event_timestamp(&self) -> Option<MilliSecondsSinceUnixEpoch> {
    self.info.read().latest_event.timestamp()
}

Le Comte

실례지만, 저는 승리라고 생각하지 않습니다. 할당 크기는 줄였지만, 할당 횟수 자체는 줄이지 않았습니다.

맞습니다! 200ms(우리의 냅킨 계산) 이상은 여기서 용납 불가입니다. 메모리 압박은 중요한 문제였고 이제 해결됐지만, 유일한 문제는 아니었습니다.

락 경합#

꼼꼼한 독자라면 우리가 여전히 락을 다루고 있다는 걸 알아챘을 겁니다.

rust
self.info.read().latest_event.…
//        ^^^^^^
//        |
//        this read lock acquisition

322,042번 할당이 있었다는 걸 기억하시나요? 그건 기본적으로 latest_event 메서드 호출 횟수이고, 즉…

Le Comte

… 락이 322,042번 획득된다는 뜻이죠!

…

… 아닌가요?

… 맞습니다… 그리고 제발 중간에 끼어들지 말아주세요. 클라이맥스를 위해 긴장감을 쌓고 있었단 말입니다.

전략을 바꿉시다. 한 발 물러서야 합니다:

sorter들이 이 데이터가 필요하다.
sorter를 실행해도 이 데이터는 바뀌지 않는다.
데이터가 바뀌면 sorter가 다시 실행될 것이다.

Le Procureur

데이터 지향 설계(DoD)를 더 배우고 싶다면 다음 발표들7을 강력 추천합니다.

Video: Data-Oriented Design and C++, by Mike Acton, at the CppCon 2014

Video: Cpu Caches and Why You Care, by Scott Meyers, at the code::dive conference 2014

CPU 캐시와 그것이 프로그램 성능에 미치는 영향을 탐구한다.

자, 진지하게 가봅시다. 여기서 데이터 지향 설계를 시도해보죠. 우선 필요한 데이터를 모두 단일 타입에 넣습니다:

rust
pub struct RoomListItem {
    /// Cache of `Room::latest_event_timestamp`.
    cached_latest_event_timestamp: Option<MilliSecondsSinceUnixEpoch>,

    /// Cache of `Room::latest_event_is_local`.
    cached_latest_event_is_local: bool,

    /// Cache of `Room::recency_stamp`.
    cached_recency_stamp: Option<RoomRecencyStamp>,

    /// Cache of `Room::cached_display_name`, already as a string.
    cached_display_name: Option<String>,

    /// Cache of `Room::is_space`.
    cached_is_space: bool,

    // Cache of `Room::state`.
    cached_state: RoomState,
}

impl RoomListItem {
    fn refresh_cached_data(&mut self, room: &Room) {
        self.cached_latest_event_timestamp = room.new_latest_event_timestamp();
        // etc.
    }
}

이 시점에서 RoomListItem의 크기는 64바이트로, 충분히 작습니다!

Le Factotum

제 시스템에서는 L1(데이터) 캐시 크기가 65KB이고 캐시 라인 크기는 128바이트입니다.

rust
pub fn new_sorter() -> impl Sorter {
    let latest_events = |left: &RoomListItem, right: &RoomListItem| {
        (left.cached_latest_event_is_local, right.cached_latest_event_is_local)
    };

    move |left, right| -> Ordering { cmp(latest_events, left, right) }
}

Before:

text
$ cargo bench --bench room_list
RoomList/Create/1000 rooms × 1000 events
    time:   [53.027 ms 53.149 ms 53.273 ms]
    thrpt:  [18.771 Kelem/s 18.815 Kelem/s 18.858 Kelem/s]

After:

text
$ cargo bench --bench room_list
RoomList/Create/1000 rooms × 1000 events
           time:   [676.29 µs 676.84 µs 677.50 µs]
           thrpt:  [1.4760 Melem/s 1.4775 Melem/s 1.4787 Melem/s]
    change:
           time:   [-98.725% -98.721% -98.716%] (p = 0.00 < 0.05)
           thrpt:  [+7686.9% +7718.5% +7745.6%]
           Performance has improved.

쾅!

보고자들이 말한 5분 지연은 여기서 보이지 않지만, 랜덤했다고 했죠. 그럼에도 성능 영향은 엄청납니다:

18.8Kelem/s에서 1.4Melem/s로,
53ms에서 676µs로, 즉 같은 단위로 비교하면 0.676ms입니다. 78배 더 빠릅니다!
처리량은 7718.5%, 시간은 98.7% 개선됐습니다.

이제 승리를 선언해도 될까요?

Le Comte

벤치마크의 Iteration Times와 Regression 그래프도 흥미롭습니다.

패치 전 Iteration Times. 점들이 어떤 “추세”도 따르지 않습니다. 프로그램이 불규칙하게 동작한다는 명확한 신호입니다.

패치 후 Iteration Times/Regression. 점들이 선형입니다.

두 번째 그래프가 제가 좋아하는 그래프입니다. 예측 가능하거든요.

Le Procureur

rust
struct RoomListItem {
    a: bool,
    b: u64,
    c: bool,
}

let rooms: Vec<RoomListItem>;

대신,

rust
struct RoomListItems {
    a: Vec<bool>,
    b: Vec<u64>,
    c: Vec<bool>,
}

let rooms: RoomListItems;

이 되는 거죠.

참고로 제 역할이 문서 낭독이나 위키피디아 요약에만 국한되진 않습니다.

물론 당신은 가치 있죠! 이제, 깜짝 선물.

디저트#

값의 예전 위치를 계산하고,
새 위치를 계산한 다음,
그에 따라 적절한 VectorDiff들을 내보냅니다.

rust
#[derive(Clone)]
struct S {
    inner: Arc<T>
}

여기서 S를 clone한 뒤 inner 필드를 바꾸면, 원본 값도 함께 업데이트됩니다.

이렇게 해서, 체계적으로… 무한 루프를 만들 수 있었습니다. 재밌죠?

더 알고 싶다면 Fix an infinite loop when SortBy<Stream<Item = T>> handles a VectorDiff::Set where T is a shallow clone type 패치를 보세요.

읽는 동안 두어 가지라도 배워가셨고, 즐거우셨길 바랍니다.

리뷰와 피드백을 준 Andy Balaam과 Damir Jelić에게 감사드립니다!

SwiftUI에는 CollectionDifference.Change 열거형이 있습니다. 예를 들어 VectorDiff::PushFront는 Change.insert(offset: 0)과 같습니다. Jetpack Compose에는 MutableList 객체가 있습니다. 예를 들어 VectorDiff::Clear는 MutableList.clear()와 같습니다! ↩
이 Stream이 어떻게 Stream을 만들어내는지, 바깥 스트림과 안쪽 스트림이 어떻게 .switch()로 전환되는지, 우리가 그걸 어떻게 처음부터 구현했는지 정말 이야기하고 싶지만, 아마 다른 글에서 다루는 게 좋겠네요. 그동안 async_rx::Switch를 참고하세요. ↩
stream_assert를 아시나요? Stream에 대해 쉽게 assertion을 적용하려고 우리가 만든 또 다른 크레이트입니다. 아주 편리하죠. ↩
네, biscuit 맞습니다. ↩
Napkin Math 프로젝트를 강력 추천합니다. 또한 SRECON'19의 훌륭한 발표 Advanced Napkin Math: Estimating System Performance from First Principles by Simon Eskildsen도요. ↩
락 경합 기억하시나요? 잠시 기다려 보세요. 이 이야기의 이 단계에서 저는 아직 락 경합이 있다는 것도 몰랐습니다. ↩
발표 보는 걸 좋아하신다면, 제가 시청한 흥미로운 발표들을 모아둔 플레이리스트를 유지관리하고 있습니다. 또한 오래된 글 하루에 컨퍼런스 하나씩, 1년(2017)도 읽어보세요. ↩

❮초당 19k에서 4.2M 이벤트로: SQLite 쿼리 최적화 이야기

메모리 압박, 락 경합, 그리고 데이터 지향 설계에 대하여

About memory pressure, lock contention, and Data-oriented Design

메모리 압박, 락 경합, 그리고 데이터 지향 설계에 대하여

아름다운 어느 아침…#

무작위성#

메모리 압박#

락 경합#

디저트#

연락하기

추천

더 보기

관련 추천 글

abseil / 성능 힌트

내부 들여다보기: Android 17의 락 프리 MessageQueue

해시드 정렬은 보통 해시 테이블보다 빠르다

Rust의 std와 parking_lot 뮤텍스: 누가 승자일까?

About memory pressure, lock contention, and Data-oriented Design

메모리 압박, 락 경합, 그리고 데이터 지향 설계에 대하여

아름다운 어느 아침…#

무작위성#

메모리 압박#

락 경합#

디저트#

연락하기

추천

더 보기

관련 추천 글

abseil / 성능 힌트

내부 들여다보기: Android 17의 락 프리 MessageQueue

해시드 정렬은 보통 해시 테이블보다 빠르다

Rust의 std와 parking_lot 뮤텍스: 누가 승자일까?