Linux 파일시스템의 inode 설계를 Rust의 커스텀 배열에 적용해 보며, Vec 및 SmallVec와의 성능, 메모리 특성, 청크 기반 API의 장단점을 실험한 기록입니다.
.. 2026-04-22
Linux 파일시스템에 관한 강의를 듣다가, inode가 메타데이터를 저장하고 데이터 블록을 가리키는 방식에 특히 흥미를 느끼게 되었다. 나는 그 전체 설계가 매우 우아하다고 생각한다. 이 설계는 실제 저장 문제를 해결하며, 순수한 연속 접근보다는 파일시스템의 제약에 맞게 명확히 최적화된 배치를 사용한다. 한참 바라보다 보니 뻔하고도 좋지 않은 생각이 떠올랐다. 같은 저장 모델을 Rust의 커스텀 배열로 옮기면 어떨까?
SmallVec보다 빠를까? 네이티브
Vec보다 빠를까? 아니면 내가 이미 의심하고 있던 그대로, 캐시에 불리한 포인터 추적 기계가 될까?
더 높은 수준의 답은 코드를 쓰기 전부터 이미 분명했다. 연속 배열이 존재하는 데에는 이유가 있다. CPU 캐시가 존재하는 데에도 이유가 있다. 파일시스템 저장 배치와 메모리 내 배열 배치는 서로 매우 다른 문제를 해결한다. 하지만 어떤 아이디어는 아마 틀렸을 가능성이 크다는 걸 알기 때문에 오히려 구현해 볼 가치가 있다. 그런 아이디어는 막연한 추측을 멈추고, 기계가 정확히 어디서부터 불편해하는지 실제로 측정하게 만든다.
내가 원했던 형태는 이것이었다:
pub struct PagedSmallVec<
T,
const INLINE: usize,
const DIRECT: usize,
const CHUNK: usize,
> {
direct: [Option<Box<[MaybeUninit<T>; CHUNK]>>; DIRECT],
inline: [MaybeUninit<T>; INLINE],
len: usize,
}
계획은 단순했다. 처음 몇 개 원소는 작은 인라인 버퍼에 보관하고, 그것이 가득 차면 하나의 큰 연속 힙 할당 대신 고정 크기 직접 청크로 넘긴다. 나중에 이 실험이 가능성 있어 보인다면, inode 테이블처럼 이중 간접과 삼중 간접 계층으로 확장할 수도 있다.
개념적으로는 그럴듯하게 들린다. 작은 데이터는 인라인에 머물고, 인라인을 넘는 성장은 큰 연속 재할당을 피하며, 설계는 여러 간접 단계로 확장될 수 있다. CPU 위에서는 실제보다 이론상 더 똑똑하게 들리는 전형적인 아이디어다.
나는 의도적으로 첫 버전을 단순하게 유지했다. 그래서 이중 간접과 삼중 간접은 없다. 첫 단계에 조금이라도 가능성이 있는지만 보기에는 그 정도면 충분했다.
인라인 영역 이후의 뜨거운 인덱싱 경로는 기본적으로 이렇다:
let paged_index = index - INLINE;
let chunk_index = paged_index / CHUNK;
let offset = paged_index % CHUNK;
그다음 이것에서 읽는다:
self.direct[chunk_index][offset]
그래서 1단계는 개념적으로 복잡하지 않다. 단지 인라인 배열에 직접 청크 테이블을 더한 것뿐이다. 이는 성능이 나쁘다면, 그 이유가 논리가 지나치게 심오해서가 아니라는 뜻이다. 추가되는 모든 간접 참조, 분기, 조회가 실제 비용을 내고 있기 때문이다.
컨테이너를
MaybeUninit<T>로 뒷받침하는 순간, 이 프로젝트는 더 이상 “귀여운 자료구조 하나 써보기”가 아니고 “스스로를 속이지 않으면서 불변식을 유지하기”가 된다.
초기 버전들에는 예상 가능한 문제가 모두 있었다:
pub fn push(&mut self, val: T) {
self.write_slot(self.len, val);
self.len += 1;
}
fn write_slot(&mut self, index: usize, val: T) {
// ...
self.len += 1; // bug
}
이런 종류의 실수는 즉시 논리 상태를 망가뜨린다.
또한 다음과 같은 부분에서도 늘 있는 문제들이 있었다:
fn take_slot(&mut self, index: usize) -> T {
unsafe { self.inline[index].assume_init_read() }
}
이것이 안전하려면
index < len이어야 하고, 해당 슬롯은 초기화되어 있어야 하며, 길이 추적도 정확해야 한다.
그리고 drop은 이런 문제가 아주 빠르게 현실이 되는 또 다른 지점이다:
impl<T, const INLINE: usize, const DIRECT: usize, const CHUNK: usize> Drop
for PagedSmallVec<T, INLINE, DIRECT, CHUNK>
{
fn drop(&mut self) {
for i in 0..self.len {
// drop initialized slots only
}
}
}
이 버그들을 고치기 시작하자, 이 프로젝트의 unsafe 부분이 자잘한 구현 세부사항이 아니라는 점이 분명해졌다. 그것은 기반 그 자체였다. 길이 추적이 슬롯 하나만큼이라도 틀리면, 그 이후의 모든 것이 의심스러워진다.
첫 공개 API는 예상할 수 있는 그대로였다:
impl<T, const INLINE: usize, const DIRECT: usize, const CHUNK: usize>
PagedSmallVec<T, INLINE, DIRECT, CHUNK>
{
pub fn push(&mut self, val: T) { /* ... */ }
pub fn pop(&mut self) -> Option<T> { /* ... */ }
pub fn get(&self, index: usize) -> Option<&T> { /* ... */ }
pub fn remove(&mut self, index: usize) -> Option<T> { /* ... */ }
pub fn swap_remove(&mut self, index: usize) -> Option<T> { /* ... */ }
}
사용성 면에서는 괜찮았지만, 진짜 문제를 가리고 있었다. 이 구조는 본질적으로 연속적이지 않다. 그래서 내가 이것을
Vec와 똑같이 사용할 때마다, 표준 컨테이너에 유리한 접근 패턴으로 억지로 밀어 넣고 있었던 셈이다.
이 구조를
Vec<T>,
SmallVec<[T; N]>,
PagedSmallVec<T, INLINE, DIRECT, CHUNK>와 비교해
append_only,
append_pop,
full_iteration,
random_indexing,
remove,
swap_remove전반에서 벤치마크했고, 테스트 원소 타입으로는
u32,
[u8; 64],
String를 사용했다. 벤치마크 하니스도 저장소에 포함되어 있으며, 주로 plaintext benches/compare.rs 와 plaintext benches/push_u32.rs 에 있다.
대략적인 결과는 미묘하지 않았다.
일반적인 벡터 형태의 워크로드에서는
Vec가 대개 1등,
SmallVec가 대개 2등, 페이지드 구조가 대개 3등이었다.
u32같이 비용이 싼 스칼라 타입에서는 그 격차가 특히 처참했다. 제대로 생각해 보면 놀랄 일도 아니었다. 연속 배열은 CPU가 원하는 일을 정확히 수행한다. 예측 가능한 메모리 접근, 더 적은 포인터 이동, 더 적은 분기, 더 적은 캐시 미스. 내 페이지드 구조는
Vec가 단순한 포인터 산술로 도달할 수 있는 데이터에 닿기 위해, 청크 계산과 청크 조회 비용을 치르고 있었다.
u32마이크로벤치마크
더 깔끔한 신호를 얻기 위해,
u32append 경로 마이크로벤치마크를 plaintext benches/push_u32.rs 로 따로 분리했다. 이들은
N = 4096에서 실행되며
push,
push + pop,
extend_from_slice만 측정한다.
| Benchmark | Vec | SmallVec | PagedSmallVec<256> | PagedSmallVec<512> |
|---|---|---|---|---|
plaintext push_only_micro/u32 | ~1.55 Gelem/s | ~1.09 Gelem/s | ~0.46 Gelem/s | ~0.47 Gelem/s |
plaintext push_pop_micro/u32 | ~1.20 Gelem/s | ~0.85 Gelem/s | ~0.45 Gelem/s | ~0.46 Gelem/s |
plaintext extend_micro/u32 | ~17.58 Gelem/s | ~14.96 Gelem/s | ~0.82 Gelem/s | ~0.86 Gelem/s |
이 표는 트레이드오프를 매우 분명하게 보여준다.
Vec는 여전히 일반적인 append 형태 경로에서 여유 있게 이기고,
SmallVec도 여전히 매우 잘하며, 페이지드 레이아웃들은 서로끼리만 경쟁력이 있을 뿐 연속 레이아웃들과는 그렇지 않다. 하지만 청크 크기 결과는 유용하다.
512는 배치 append에서
256를 근소하게 앞서고, 단일 원소 마이크로벤치에서는 둘 다 사실상 같은 부류에 있다.
또한 plaintext examples/memory_profile.rs 에 작은 메모리 프로브를 추가하고, 1,000,000개의
u32값을 한 번에 구축하는 경우에 실행했다. 스택 사용량 수치는
size_of::<...>()에서 가져왔고, 피크 메모리 수치는
/usr/bin/time -l에서 가져왔다.
| Container | Stack footprint | Peak memory footprint |
|---|---|---|
plaintext Vec<u32> | 24 B | ~7.34 MB |
plaintext SmallVec<[u32; 32]> | 144 B | ~7.34 MB |
plaintext PagedSmallVec<u32, 32, 4096, 256> | 32,928 B | ~5.11 MB |
plaintext PagedSmallVec<u32, 32, 4096, 512> | 32,928 B | ~5.11 MB |
이 결과가 흥미로운 이유는 처리량 표가 나빴던 바로 그 이유 때문이다. 페이지드 레이아웃은 훨씬 더 큰 구조적 사용량을 선불로 치르지만, 이 한 번짜리 구축에서는 연속 재할당에서 오는 일부 피크 메모리 증가를 피하기도 한다. 즉, 이 설계는 공짜가 아니지만, 그 비용 또한 일차원적이지 않다. 순수 접근 속도와 컨테이너 크기에서 비용을 지불하고, 때로는 성장 동작 측면에서 무언가를 되돌려 받는다.
인덱스 접근 경로는 이렇게 생겼다:
pub unsafe fn get_unchecked(&self, index: usize) -> &T {
if index < INLINE {
return self.inline.get_unchecked(index).assume_init_ref();
}
let paged_index = index - INLINE;
let chunk_index = paged_index / CHUNK;
let offset = paged_index % CHUNK;
self.direct
.get_unchecked(chunk_index)
.as_ref()
.unwrap_unchecked()
.get_unchecked(offset)
.assume_init_ref()
}
이것이 랜덤 인덱싱에서 왜
Vec에 지는지 놀라운 이유는 전혀 없다. “단순한” 1단계 버전조차도 인라인 대 페이지드 분기, 뺄셈, 나눗셈, modulo, 청크 조회, 슬롯 조회를 포함한다. 이는 단순히 연속 메모리보다 일이 더 많다.
이 부분은 스스로를 속이기 쉬운 지점이라고 생각한다.
페이지드 저장소를 보면, “전체 버퍼가 아니라 청크를 움직이니까 중간 삭제가 더 싸지 않을까”라고 생각할 수도 있다.
실제로는 그렇지 않다.
순서를 보존하는
remove를 원한다면, 여전히 개념적으로는 전체 꼬리 부분을 밀어야 한다:
pub fn remove(&mut self, index: usize) -> Option<T> {
let removed = self.take_slot(index);
for i in (index + 1)..self.len {
let val = self.take_slot(i);
self.write_slot(i - 1, val);
}
self.len -= 1;
Some(removed)
}
이 역시 여전히 O(n)이며, 내 경우에는
Vec와
SmallVec보다 느렸다. 연속 컨테이너는 CPU에 훨씬 더 친화적인 배치에서 이동을 수행할 수 있기 때문이다.
swap_remove는 덜 끔찍했지만, 그렇다고 페이지드 구조가 갑자기 예상 밖의 승자가 되지는 않았다. 단지 불리함이 조금 덜해졌을 뿐이다.
처음으로 진짜 좋은 결과가 나온 것은, 이 구조를 반복적인
get(i)로 순회하는 일을 멈췄을 때였다.
원래 전체 순회 벤치마크는 이렇게 생겼다:
for i in 0..vec.len() {
sum += vec.get(i).unwrap().score();
}
이건 레이아웃에 맞지 않았다. 페이지드 구조의 순차 순회는 반복된 랜덤 인덱싱인 척하면 안 된다.
그래서 다음을 추가했다:
pub fn for_each_chunk(&self, mut f: impl FnMut(&[T])) {
for chunk in self.chunks() {
f(chunk);
}
}
그리고:
pub fn for_each_ref(&self, mut f: impl FnMut(&T)) {
self.for_each_chunk(|chunk| {
for value in chunk {
f(value);
}
});
}
이것이 상황을 많이 바꿨다. 전체 스캔을 청크 단위로 표현하자, 순차 순회에서는 구조가 훨씬 더 경쟁력 있어졌다. 그 시점부터 이 설계는 “나쁜 Vec”처럼 느껴지기보다 “자연스러운 API가 다른 별개의 구조”처럼 느껴지기 시작했다.
청크 순회가 유용하다는 것이 입증되자, 이를 직접 노출하는 것이 자연스러웠다:
pub struct ChunkIter<'a, T, const INLINE: usize, const DIRECT: usize, const CHUNK: usize> {
vec: &'a PagedSmallVec<T, INLINE, DIRECT, CHUNK>,
remaining: usize,
next_chunk_index: usize,
yielded_inline: bool,
}
그리고 append가 많은 작업을 위해 다음도 추가했다:
pub fn extend_from_slice(&mut self, values: &[T])
where
T: Clone,
{
// fill inline first, then write chunk by chunk
}
이것은
push()를 루프로 반복하는 것보다 이 레이아웃에 더 잘 맞았고, 비록 아직 극적인 성능 향상은 아니었더라도 마찬가지였다.
이 역시 또 하나의 중요한 교훈이었다. 좋은 API는 구조에 맞는 올바른 API이기만 하다면, 당장 표준 API를 이기지 못해도 여전히 좋은 API일 수 있다.
다음으로 집중하기에 append는 очевид한 지점이었기에, 다음을 추가했다:
tail_chunk_index: usize,
tail_offset: usize,
current_chunk_ptr: *mut MaybeUninit<T>,
아이디어는 논리적 꼬리 위치를 캐시하고, 현재 청크에 대한 raw pointer를 캐시하며, 다음 청크에 진입할 때만 그 청크를 할당하고, 정상 상태의 append를 이렇게 만드는 것이었다:
unsafe { (*self.current_chunk_ptr.add(self.tail_offset)).write(val) };
이것은 append가 많은 경로에서 도움이 되었다.
Vec를 이길 정도는 아니었지만, 매 쓰기마다 더 추상적인 청크 조회 로직을 반복해서 거치면서 발생하던 오버헤드를 일부 줄이기에는 충분했다.
또한 청크 크기를 const generic으로 바꾸고
64,
128,
256,
512를 벤치마크했다.
내가 발견한 것은 “클수록 항상 좋다”가 아니었다.
u32의 경우, 더 큰 청크는 종종 배치 append에 도움이 되었고 때로는 append 중심 워크로드에도 도움이 되었다. 예를 들어 plaintext extend_micro/u32 에서
256은 약
576 Melem/s에 도달했고
512는 약
609 Melem/s에 도달했다. 하지만 순수
push와
push+pop에서는
256이 더 나은 절충안으로 나타났다. plaintext push_only_micro/u32 에서는
256이 약
382 Melem/s이고
512는 약
342 Melem/s였으며, plaintext push_pop_micro/u32 에서는
256이 약
326 Melem/s이고
512는 약
314 Melem/s였다.
[u8; 64]의 경우, 더 큰 청크는 거의 그만큼 도움이 되지 않았고 일부 경로에서는 더 나빴다.
String의 경우, 차이는 더 작았고 워크로드 의존성이 더 컸다.
그래서 현재 컨테이너가 순수한 대량 append보다 여전히 push/pop 형태에 더 가깝기 때문에, 기본 청크 크기로는
256을 선택했다.
Vec를 이길 수 있는 곳
솔직한 대답은 이렇다. 일반적인 “평범한 벡터처럼 쓰기만 하면 되는” 경우는 아니다. 하지만 이런 청크 기반 레이아웃이
Vec를 능가하거나, 적어도 훨씬 더 강한 절충을 만들 수 있는 실제 워크로드는 존재한다.
첫 번째는 append가 많은 시스템으로, 큰 크기까지의 성장이 흔하고 반복적인 연속 재할당 비용이 실제로 중요할 때다. 예를 들면 큰 인메모리 로그, 이벤트 버퍼, 트레이싱 파이프라인, 혹은 주로 성장하고 가끔 flush하며 중간 랜덤 인덱싱은 거의 하지 않는 수집 큐가 있다. 이런 시스템에서는 성장 중 전체 버퍼 이동을 피하는 것이 절대적으로 가장 싼 인덱스 로드보다 더 중요할 수 있다.
두 번째는 청크 네이티브 처리다. 워크로드가 개별 원소가 아니라 실행 단위들로 자연스럽게 동작한다면, 이 레이아웃은 문제에 훨씬 더 잘 맞기 시작한다. 좋은 예는 버퍼를 청크별로 스캔하고, 변환을 적용하고, 청크를 직렬화하고, 청크를 압축하거나, 다른 단계로 청크를 넘기고 싶은 스트리밍 분석이나 배치 변환이다. 바로 그래서
for_each_chunk와 청크 이터레이터가 모든 것을
get(i)로 억지로 처리하려는 것보다 훨씬 더 자연스러운 API가 되었다.
세 번째는 할당자 압박 아래의 메모리 동작이다.
Vec는 더 큰 연속 영역을 저렴하게 계속 얻을 수 있을 때는 훌륭하지만, 매우 크거나 오래 사는 할당에서는 그 가정이 약해진다. 힙이 단편화되어 있거나 동시에 성장하는 버퍼가 많이 살아 있는 시스템에서는, 하나의 더 큰 연속 블록을 할당자에게 요청하고 그 안으로 모든 것을 복사하는 것보다 고정 크기 청크 하나를 더 할당하는 편이 더 나은 절충일 수 있다.
네 번째는 참조와 청크 안정성이다. 어떤 시스템이 청크 지역 슬라이스를 붙잡아 두고 싶거나, 페이지를 독립적으로 처리하고 싶거나, 단계 사이에서 부분적으로 찬 청크를 넘기고 싶다면, 성장 시 전체 백킹 버퍼가 재배치될 수 있는
Vec보다 이 구조가 훨씬 더 친화적이다. 다시 말해 작업 단위가 “원소”가 아니라 “청크”가 되는 순간, 이 설계는 이상해 보이기를 멈추고 의도적인 것으로 보이기 시작한다.
그래서 나는 이것을 “
Vec보다 낫다”라고 팔지는 않을 것이다. 대신 “연속 재할당이 실제 비용 중 하나인 append 중심, 청크 지향 워크로드에서는
Vec보다 낫다”라고 말할 것이다.
이 시점에서 내가 보기에 가장 큰 실수는 이 구조를
Vec를 얼마나 잘 흉내 내는지만으로 판단하는 것이다.
이 구조의 자연스러운 API는 주로
get,
remove, 랜덤 인덱싱이 아니다. 오히려
for_each_chunk, 청크 이터레이터, 배치 append, 청크 단위 변환에 더 가깝다. 바로 그 지점에서 레이아웃이 의미를 갖기 시작한다. 연속 메모리에 최적화된 접근 패턴으로 이 구조를 억지로 밀어 넣는 일을 멈추고 나서야, 이 실험은 훨씬 더 많은 정보를 주기 시작했다.
목표가
Vec를 이기는 것,
SmallVec를 이기는 것, 스칼라
push와
pop에서 이기는 것, 혹은 랜덤 인덱싱에서 이기는 것이라면, Rust에서 inode 스타일 배열 저장소는 나쁜 생각이다.
목표가 저수준 컨테이너 불변식을 이해하고, 포인터가 많은 레이아웃이 정확히 어디서 손해를 보는지 보고, 청크 네이티브 API를 실험하고, 연속 저장소가 어디서 왜 이기는지 배우는 것이라면, 이것은 매우 좋은 실험이다.
그래서 나의 최종 평가는 이렇다. 전통적인 벡터로 평가하면 잘 되지 않았지만, 실험으로 평가하면 아주 잘 되었다. 왜냐하면 이 실험은 트레이드오프를 무시할 수 없게 만들었기 때문이다. 그리고 솔직히 말해, 어쨌든 만들어 볼 가치가 있었던 나쁜 아이디어에서 얻을 수 있는 가장 유용한 결과는 대개 바로 그런 것이다.
전체 구현을 읽어보고 싶다면, GitHub의 코드가 여기 있다: borngraced/paged-small-vec.