파서/컴파일러에서 흔한 문자열 사용 패턴을 전제로, 16바이트 예산 안에서 차용/소유, 작은 문자열 최적화, 정적 승격을 모두 지원하는 고성능 문자열 타입 Yarn의 레이아웃 트릭과 구현 아이디어를 설명한다.
저는 재미로 컴파일러를 만듭니다. 어쩔 수가 없어요. 그래서 파서도 많이 씁니다. 시스템 프로그래밍에서는 보통 메모리를 재사용하기보다 공유하려고 하는 것이 좋기 때문에, 제 AST 타입들은 대체로 이렇게 생겼습니다.
pub enum Expr<'src> {
Int(u32)
Ident(&'src str),
// ...
}
Rust
식별자를 파싱할 때마다 이름을 새 String에 복사하지 않고 입력 소스 문자열에서 빌려옵니다. 이렇게 하면 추가 할당과 복사를 피하고, 표현에 필요한 워드(머신 워드)도 한 개 줄일 수 있습니다. 컴파일러는 메모리를 많이 먹는 편이므로, 날씬한 표현을 고르는 것이 도움이 됩니다.
불행히도, 따옴표로 둘러싼 문자열에는 그리 쉽지 않습니다. 대부분의 문자열(예: "all my jelly babies")은 식별자처럼 소스에 “그대로” 들어 있지만, 이스케이프가 들어간 문자열은 그렇지 않습니다. 예컨대 \n은 소스 코드에서는 바이트 [0x5c, 0x6e]로 인코딩되어 있지만, 문자열 리터럴의 실제 “디코드된” 값에서는 각 이스케이프가 단일 바이트 0x0a로 치환됩니다.
보통의 해법은 Cow<str>입니다. 더 흔한, 이스케이프가 없는 버전에서는 Cow::Borrowed를 써서 추가 할당과 복사를 피할 수 있고, 이스케이프가 있는 경우에는 이스케이프를 디코드해 String에 담아 Cow::Owned로 감쌉니다.
예를 들어, 이스케이프를 포함할 수 있는 따옴표 문자열을 가진 언어의 파서를 작성한다고 합시다. 문자열 "all my jelly babies"는 입력 소스 코드를 빌려오는 바이트 문자열로 표현될 수 있으므로 Cow::Borrowed 변형을 쓰게 됩니다. 대부분의 언어에서 이스케이프는 드뭅니다. 그래서 대부분의 문자열은 이 경우에 해당합니다.
또 다른 예로 "not UTF-8 \xff"라는 문자열이 있다면, 실제 바이트열 값은 소스 코드에 있는 바이트열과 다릅니다.
// 소스에 들어 있는 바이트.
hex: 6e 6f 74 20 55 54 46 2d 38 20 5c 78 66 66
ascii: n o t U T F - 8 \ x f f
// 문자열이 표현하는 바이트.
hex: 6e 6f 74 20 55 54 46 2d 38 20 ff
ascii: n o t U T F - 8
평문
이스케이프는 상대적으로 드물기 때문에, 파서가 다루는 대부분의 문자열은 할당 비용을 치를 필요가 없습니다.
하지만 우리는 여전히 그 추가 워드만큼은 지불합니다. Cow<str>는 24바이트(명시하지 않는 한, 모든 바이트 수는 64비트 시스템 기준)인데, 이것은 &str보다 8바이트 더 큽니다. 심지어 이 값은 문자열 데이터 자체(11바이트)보다도 큽니다.
문자열의 대부분이 짧다면(이는 AST 파서에서 흔치 않지 않습니다), 상당한 오버헤드를 치르게 됩니다.
수년간 저는 이 용례를 처리하기 위해 다양한 맥락에서 여러 최적화된 문자열 타입을 구현해왔습니다. 그리고 마침내 제가 아는 모든 요령을 모아 byteyarn이라는 라이브러리에 담았습니다. 이 라이브러리는 다음과 같은 멋진 특성을 내세웁니다.
Yarn은String에 비해 여러 유용한 속성을 제공하는 고도로 최적화된 문자열 타입입니다:
- 항상 포인터 두 개 폭이므로, 함수에 들어가고 나올 때 항상 레지스터로 전달됩니다.
- 64비트 아키텍처에서 15바이트까지의 작은 문자열 최적화(SSO).
- 소유 버퍼일 수도, 차용 버퍼일 수도 있습니다(
Cow<str>처럼).- 알려진 정적 문자열에서 구성되었다면 수명을
'static으로 승격할 수 있습니다.
이러한 특성이 어떻게 세심한 레이아웃 최적화를 통해 달성되는지 공유하고자 합니다.
우리 문자열이 사용될 방식에 대해 다음과 같은 가정을 하겠습니다:
String은 C++의 std::string을 본뜬 것으로, 증가 가능한 버퍼이며 상각 선형 시간의 append를 제공합니다. 즉, 버퍼에 바이트 n개를 덧붙일 때 memcpy 비용도 n바이트만큼 든다는 뜻입니다.
이 속성은 유용하지만 자주 필요하지는 않습니다. 예컨대 Go의 문자열은 불변이며, 큰 문자열을 만들어야 할 때는 strings.Builder를 쓰라고 권장합니다. 이는 사실상 Rust의 String과 같습니다. Java도 문자열에 대해 유사한 이야기를 가지고 있어서, java.lang.String을 매우 압축된 표현으로 다룰 수 있습니다.
Rust에서는 이런 종류의 불변 문자열을 Box<str>로 표현하며, 이는 String보다 8바이트 더 작습니다. String에서 Box<str>로 변환하는 것은 단지 기반 할당 크기를 capacity에서 len으로 바꾸는 realloc() 호출(종종 저렴합니다1)일 뿐입니다.
따라서 이 가정은 우리가 포인터와 길이만 저장하면 된다는 뜻이고, 이는 메모리 발자국의 최저선을 16바이트로 둡니다.
텍스트 형식을 다시 파싱한다고 가정해 봅시다. 많은 구조적 요소가 텍스트 입력을 문자 그대로 참조하게 됩니다. 이스케이프가 없는 문자열 리터럴뿐 아니라 식별자도 그렇습니다.
Box<str>는 차용 데이터를 담을 수 없습니다. 범위를 벗어날 때 반드시 할당자에게 자신의 포인터를 해제하라고 지시하기 때문입니다. 위에서 본 Cow<str>는 소유일 수도 있는 데이터를 균일하게 다루게 해주지만, 최소 24바이트의 오버헤드를 가집니다. 이는 더 작아질 수 없습니다. 왜냐하면 Cow<str>는 24바이트짜리 String 값을 담을 수 있기 때문입니다.
하지만 우리는 capacity를 저장하고 싶지 않습니다. Cow<str>의 그 추가 워드 오버헤드를 피할 수 있을까요?
부분 문자열이 아니지만 작은 문자열을 생각해 봅시다. 예컨대 "Hello, world!\n" 같은 문자열 리터럴을 파싱할 때, 끝의 \n(바이트 0x5c 0x6e)은 개행 바이트(0x0a)로 바꿔야 합니다. 즉, 길이가 14바이트인 아주 작은 힙 할당을 처리해야 하며, 이 크기는 그것을 가리키는 &str보다도 작습니다.
한 글자짜리2 문자열은 더 나쁩니다. Box<str>의 오버헤드는 큽니다.
Box<str> 구조체 자체는 포인터 필드(8바이트)와 길이 필드(또한 8바이트)를 가집니다. 저장된 모든 비트를 드러내면, 길이는 0x0000_0000_0000_0001입니다. 0이 참 많죠!즉, 데이터가 단지 “한 바이트”인 문자열 "a"가 총 24바이트의 메모리를 차지하게 됩니다.
아주 작은 문자열의 경우에는 아예 할당을 피할 수도 있고, 길이 필드의 그 많은 0들을 효과적으로 활용할 수도 있습니다.
Yarn 타입의 예산을 16바이트로 유지하고 싶다고 합시다. (*mut u8, usize) 쌍 안에 데이터를 더 넣을 여지가 있을까요?
페르미 추정의 손가락을 한번 꺾어 봅시다
usize는 64비트이므로, &str의 길이는 0에서 18446744073709551615, 대략 18엑사바이트까지 될 수 있습니다. 참고로, 2023년 현재 전 세계 RAM 총량은 “수백 엑사바이트” 정도가 합리적인 대략치입니다(예: 40억 대의 스마트폰이 각각 4GB를 가진다고 치면). 현실적으로 서버 블레이드에 넣을 수 있는 RAM 최대치는 테라바이트 단위입니다(게이밍 장비의 8개 DIMM 정도와는 비교도 안 되죠).
비트를 하나 덜 쓰는, 즉 63비트를 쓴다면 표현 가능한 최대 메모리는 절반인 9엑사바이트가 됩니다. 하나 더 빼면 이제 4엑사바이트입니다. 여러분이 문자열에 넣고 싶을 리 없는, 상상을 초월하는 메모리죠. 위키백과는 위키미디어 공용의 미디어가 약 428TB에 달한다고 합니다(문서 텍스트와 그 이력은 고작 10TB).
아, 하지만 당신은 32비트 머신을 위해 프로그래밍하고 있다고 말할지 모릅니다(요즘이라면 저가형 휴대폰, 임베디드 마이크로컨트롤러, 혹은 WASM 정도를 뜻하겠죠).
32비트 머신에서는 조금 더 까다롭습니다. 이제 usize는 32비트이고, 최대 문자열 크기는 4기가바이트입니다(32비트 시대를 기억한다면 이 제한이 익숙하게 들릴 겁니다). “기가바이트”는 실제로 문자열에 담길 법한 메모리 양입니다.
그래도 32비트 머신에서 1GB(비트를 두 개 훔친다면)는 꽤 많은 데이터입니다. 주소 공간 하나에 그런 크기의 문자열은 네 개밖에 둘 수 없고, 전 세계의 모든 32비트 할당자는 그런 크기의 할당을 거부할 것입니다. 문자열이 주소 공간 전체 크기에 필적한다면, 여러분만의 문자열 타입을 직접 만들어야 합니다.
결론적으로 모든 &str에는 합리적으로 사용되지 않는다고 가정할 수 있는 비트가 두 개 있습니다. 공짜 부동산.3
Rust에는 특정 타입에 대해 유효하지 않은 비트 패턴인 “니치(niche)” 개념이 있고, 컴파일러는 이를 enum의 자동 레이아웃 최적화에 사용합니다. 예컨대 참조는 null일 수 없으므로, 포인터 비트 패턴 0x0000_0000_0000_0000은 절대 사용되지 않습니다. 이 비트 패턴이 바로 “니치”입니다. 다음을 보세요:
enum Foo<'a> {
First(&'a T),
Second
}
Rust
이런 형태의 enum은 두 변형을 구분하는 값을 저장하기 위해 “추가” 공간이 필요하지 않습니다. Foo의 비트가 모두 0이면 Foo::Second이고, 그렇지 않으면 Foo::First이며 페이로드는 Foo의 비트 패턴에서 그대로 만들어집니다. 이는 우연히도 Option<&T>가 “널 가능 포인터”의 유효한 표현이 되는 이유이기도 합니다.
더 일반적인 형태도 있습니다. bool은 한 바이트로 표현되며, 그중 두 비트 패턴만 유효합니다. 나머지 254개의 잠재적 비트 패턴은 니치입니다. 최근 Rust 버전에서는 POSIX 파일 디스크립터가 항상 음이 아닌 int이기 때문에 RawFd는 올-원(all-ones) 비트 패턴을 니치로 가집니다.
길이에서 비트 두 개를 훔침으로써 우리는 네 개의 니치를 확보했습니다. 본질적으로 다음과 같은 enum을 수작업으로 만든 셈입니다.
enum Yarn {
First(*mut u8, u62),
Second(*mut u8, u62),
Third(*mut u8, u62),
Fourth(*mut u8, u62),
}
Rust
곧 명확해지겠지만, 우리는 특히 길이의 상위 비트를 훔칠 겁니다. 그래야 길이를 복구할 때 상위 0 두 비트를 시프팅해 집어넣는 두 번의 시프트4만 하면 되기 때문입니다. 아래는 우리 문자열 타입이 기반으로 삼을 저수준 타입에 이를 실제로 구현한 코드입니다.
#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
ptr: *mut u8,
len: usize,
}
impl RawYarn {
/// 원시 구성요소에서 RawYarn을 생성합니다: 2비트 종류(kind),
/// 길이, 그리고 포인터.
fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) -> Self {
assert!(len <= usize::MAX / 4, "그렇게 큰 문자열을 가질 리가 없어요");
RawYarn {
ptr,
len: (kind as usize & 0b11) << (usize::BITS - 2) | len,
}
}
/// kind를 다시 추출합니다.
fn kind(self) -> u8 {
(self.len >> (usize::BITS - 2)) as u8
}
/// (kind에 상관없이) 슬라이스를 추출합니다.
unsafe fn as_slice(&self) -> &[u8] {
slice::from_raw_parts(self.ptr, (self.len << 2) >> 2)
}
}
Rust
이 타입에 Copy를 붙였고, 몇몇 함수는 값을 통째로 받도록 했습니다. 이유는 두 가지입니다.
Yarn 자체가 Copy인 변종이 하나 있습니다(이 글에서는 다루지 않습니다).
이 타입은 두 워드 크기의 구조체이므로, 대부분의 아키텍처에서 레지스터 두 개로 전달될 자격이 있습니다. 저수준 코드에서 값을 통째로 전달하면 레지스터에 유지되도록 유도하는 데 도움이 됩니다. 다만 이건 언제나 가능한 건 아니며, 곧 “SSO”를 논할 때 보게 됩니다.
kind 0은 “차용 데이터”, kind 1은 “힙 할당 데이터”라고 정해봅시다. 이를 이용해 소멸자를 호출해야 하는지 기억할 수 있습니다.
pub struct Yarn<'a> {
raw: RawYarn,
_ph: PhantomData<&'a str>,
}
const BORROWED: u8 = 0;
const HEAP: u8 = 1;
impl<'a> Yarn<'a> {
/// 차용 데이터로부터 새 yarn을 만듭니다.
pub fn borrowed(data: &'a str) -> Self {
let len = data.len();
let ptr = data.as_ptr().cast_mut();
Self {
raw: RawYarn::from_raw_parts(BORROWED, len, ptr),
_ph: PhantomData,
}
}
/// 소유 데이터로부터 새 yarn을 만듭니다.
pub fn owned(data: Box<str>) -> Self {
let len = data.len();
let ptr = data.as_ptr().cast_mut();
mem::forget(data);
Self {
raw: RawYarn::from_raw_parts(HEAP, len, ptr),
_ph: PhantomData,
}
}
/// 데이터를 추출합니다.
pub fn as_slice(&self) -> &str {
unsafe {
// SAFETY: 고유 소유 데이터이거나,
// self보다 오래 사는 'a 수명의 차용 데이터에서 초기화됨.
str::from_utf8_unchecked(self.raw.as_slice())
}
}
}
impl Drop for Yarn<'_> {
fn drop(&mut self) {
if self.raw.kind() == HEAP {
let dropped = unsafe {
// SAFETY: 이것은 Yarn::owned()에서 분해했던
// 박스를 재구성하는 것일 뿐입니다.
Box::from_raw(self.raw.as_mut_slice())
};
}
}
}
impl RawYarn {
unsafe fn as_slice_mut(&mut self) -> &mut [u8] {
// as_slice와 거의 동일합니다. 위의 Box::from_raw()가
// 타입체크되도록 하기 위한 것입니다.
}
}
Rust
이렇게 하면 바이트 수가 절반인 Cow<str>에 매우 유사한 타입을 얻게 됩니다. 심지어 Yarn의 수명을 늘리는 코드도 쓸 수 있습니다:
impl Yarn<'_> {
/// 바인딩된 수명을 제거합니다. 필요하다면 할당합니다.
pub fn immortalize(mut self) -> Yarn<'static> {
if self.raw.kind() == BORROWED {
let copy: Box<str> = self.as_slice().into();
self = Yarn::owned(copy);
}
// 위에서 만든 힙 할당을 소멸자가 지워버리지 않도록,
// 이전 yarn은 폐기해야 합니다.
let raw = self.raw;
mem::forget(self);
Yarn::<'static> {
raw,
_ph: PhantomData,
}
}
}
Rust
남은 두 개의 니치는 작은 문자열을 최적화하는 데 쓸 수 있습니다.
C++의 std::string도 “대부분의 문자열은 작다”는 가정을 합니다. 표준 라이브러리의 libc++ 구현에서는, 23바이트 이하의 std::string은 힙을 전혀 쓰지 않습니다!
C++ 구현은 포인터, 길이, 용량 필드의 대부분을 작은 문자열을 위한 저장 버퍼로 재활용하는 방식으로, 이른바 “작은 문자열 최적화(SSO)”를 합니다. libc++에서는 SSO 모드에서 std::string의 길이가 한 바이트에 들어가므로, 나머지 23바이트를 저장소로 쓸 수 있습니다. 용량(capacity)은 전혀 저장하지 않습니다. SSO 문자열의 용량은 항상 23이기 때문입니다.
RawYarn에는 니치가 두 개 더 있으므로, 그중 하나를 “작은” 표현에 할당해 봅시다. 작은 모드에서는 kind가 2이며, 오직 16번째 바이트만 길이가 됩니다.
이 때문에 길이의 상위 두 비트를 스크래치 공간으로 썼던 것입니다. 모드가 무엇이든 이 비트를 쉽게 추출할 수 있거든요5. 다만 기존의 몇 가지 RawYarn 메서드는 수정이 필요합니다.
#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
ptr: MaybeUninit<*mut u8>,
len: usize,
}
const SMALL: u8 = 2;
impl RawYarn {
/// 원시 구성요소에서 RawYarn을 생성합니다: 2비트 종류(kind),
/// 길이, 그리고 포인터.
fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) {
debug_assert!(kind != SMALL);
assert!(len <= usize::MAX / 4, "그렇게 큰 문자열을 가질 리가 없어요");
RawYarn {
ptr: MaybeUninit::new(ptr),
len: (kind as usize & 0b11) << (usize::BITS - 2) | len,
}
}
/// (kind에 상관없이) 슬라이스를 추출합니다.
unsafe fn as_slice(&self) -> &[u8] {
let (ptr, adjust) = match self.kind() {
SMALL => (self as *const Self as *const u8, usize::BITS - 8),
_ => (self.ptr.assume_init(), 0),
};
slice::from_raw_parts(ptr, (self.len << 2) >> (2 + adjust))
}
}
Rust
SMALL이 아닌 경우에는 예전처럼 두 번 시프트하지만, SMALL인 경우에는 len 필드의 상위 바이트를 가져와야 하므로 추가로 usize::BITS - 8만큼 더 아래로 시프트해야 합니다. len의 하위 바이트에 우리가 무엇을 끼적였든, 이렇게 하면 항상 길이만 얻을 수 있습니다.
또한 SMALL 모드인지 여부에 따라 다른 포인터 값을 써야 합니다. 이 때문에 as_slice는 참조를 인자로 받아야 합니다. 슬라이스 데이터가 직접 self 안에 있을 수도 있기 때문입니다!
그리고 이제 ptr이 MaybeUninit이 된 이유는 다음 코드에서 분명해집니다.
작은 문자열을 만들 수 있는 방법도 제공해야 합니다.
const SSO_LEN: usize = size_of::<usize>() * 2 - 1;
impl RawYarn {
/// 새 작은 yarn을 만듭니다. `data`는 `len` 바이트만큼 유효해야 하며,
/// `len`은 `SSO_LEN`보다 작아야 합니다.
unsafe fn from_small(data: *const u8, len: usize) -> RawYarn {
debug_assert!(len <= SSO_LEN);
// 초기화되지 않은 포인터 값(!!)과, 상위 바이트에
// `small`과 `len`이 포장된 길이를 가진 yarn을 만듭니다.
let mut yarn = RawYarn {
ptr: MaybeUninit::uninit(),
len: (SMALL as usize << 6 | len)
<< (usize::BITS - 8),
};
// 데이터를 새 yarn으로 memcpy합니다.
// `yarn` 변수에 직접 씁니다. 길이의 상위 바이트는 덮어쓰지 않습니다.
// 왜냐하면 `len`이 16 이상이 될 수 없기 때문입니다.
ptr::copy_nonoverlapping(
data,
&mut yarn as *mut RawYarn as *mut u8,
data,
);
yarn
}
}
Rust
SSO 문자열의 정확한 최대 크기는 위에서 제시한 것보다 약간 더 미묘하지만, 요지는 같습니다. RawYarn::from_small이 포인터 값을 MaybeUninit으로 감춘 이유는, 곧바로 그 자리를 쓰레기로 덮어쓸 것이기 때문입니다. 그 경우 그것은 더 이상 포인터가 아닙니다.
이제 가능한 경우, 우리의 공개 Yarn 타입이 새로운 작은 표현을 사용하도록 업데이트할 수 있습니다.
impl<'a> Yarn<'a> {
/// 차용 데이터로부터 새 yarn을 만듭니다.
pub fn borrowed(data: &'a str) -> Self {
let len = data.len();
let ptr = data.as_ptr().cast_mut();
if len <= SSO_LEN {
return Self {
raw: unsafe { RawYarn::from_small(len, ptr) },
_ph: PhantomData,
}
}
Self {
raw: RawYarn::from_raw_parts(BORROWED, len, ptr),
_ph: PhantomData,
}
}
/// 소유 데이터로부터 새 yarn을 만듭니다.
pub fn owned(data: Box<str>) -> Self {
if data.len() <= SSO_LEN {
return Self {
raw: unsafe { RawYarn::from_small(data.len(), data.as_ptr()) },
_ph: PhantomData,
}
}
let len = data.len();
let ptr = data.as_ptr().cast_mut();
mem::forget(data);
Self {
raw: RawYarn::from_raw_parts(HEAP, len, ptr),
_ph: PhantomData,
}
}
}
Rust
이제 문자 하나로부터 직접 Yarn을 구성하는 것도 가능합니다!
impl<'a> Yarn<'a> {
/// 차용 데이터로부터 새 yarn을 만듭니다.
pub fn from_char(data: char) -> Self {
let mut buf = [0u8; 4];
let data = data.encode_utf8(&mut buf);
Self {
raw: unsafe { RawYarn::from_small(len, ptr) },
_ph: PhantomData,
}
}
}
Rust
(참고: Yarn::immortalize()는 업데이트할 필요가 없습니다. 왜일까요?)
지금까지로, 우리는 작은 문자열에 대해서는 할당을 요구하지 않는 “소유일 수도 있는” 문자열을 얻었습니다. 하지만 아직 니치가 하나 더 남아 있습니다…
Rust의 문자열 상수는 흥미롭습니다. 컴파일 시점에 실제로 감지할 수 있기 때문입니다6.
남은 마지막 니치, 3을 문자열 상수에서 온 데이터를 나타내는 데 사용할 수 있습니다. 이렇게 하면 그것을 불사(immortalize)할 때 박싱할 필요가 없습니다.
const STATIC: u8 = 3;
impl<'a> Yarn<'a> {
/// 차용 데이터로부터 새 yarn을 만듭니다.
pub fn from_static(data: &'static str) -> Self {
let len = data.len();
let ptr = data.as_ptr().cast_mut();
if len <= SSO_LEN {
return Self {
raw: unsafe { RawYarn::from_small(len, ptr) },
_ph: PhantomData,
}
}
Self {
raw: RawYarn::from_raw_parts(STATIC, len, ptr),
_ph: PhantomData,
}
}
}
Rust
이 함수는 Yarn::borrowed와 동일하지만, data는 반드시 정적 수명이어야 하고, RawYarn::from_raw_parts()에 STATIC을 전달한다는 점만 다릅니다.
이전 모든 코드를 작성한 방식 덕분에, 이는 Yarn::immortalize()나 저수준 RawYarn 코드에서 어떤 특수 지원도 필요로 하지 않습니다.
실제 byteyarn 라이브러리는 format!()과 동일한 문법의 yarn!() 매크로를 제공합니다. 이것이 yarn을 만드는 주요 방법입니다. yarn!("this is a literal")이 힙 할당 문자열이 아니라 항상 STATIC 문자열을 내도록 아주 신중히 작성되어 있습니다.
불행히도, 지금까지의 작성 방식 때문에 Option<Yarn>은 24바이트입니다. Yarn보다 한 워드 더 큽니다. 하지만 아직 None 변형을 끼워 넣을 만한 작은 틈이 남아 있습니다. 우리가 선택한 판별자 덕분에, len이 0인 경우는 오직 빈 BORROWED 문자열뿐입니다. 그러나 이것이 유일한 0은 아닙니다. 상위 바이트가 0x80인 경우, 이는 빈 SMALL 문자열입니다. 단순히 다른 빈 문자열이 결코 구성되지 않도록 요구하기만 한다면(RawYarn::from_raw_parts()를 unsafe로 표시하고 길이 0을 전달하지 말라고 명시), len이 절대 0이 아님을 보장할 수 있습니다.
따라서 len을 NonZeroUsize로 바꿀 수 있습니다.
#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
ptr: MaybeUninit<*mut u8>,
len: NonZeroUsize, // (!!)
}
impl RawYarn {
/// 원시 구성요소에서 RawYarn을 생성합니다: 2비트 종류(kind),
/// "0이 아닌" 길이, 그리고 포인터.
unsafe fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) {
debug_assert!(kind != SMALL);
debug_assert!(len != 0);
assert!(len <= usize::MAX / 4, "그렇게 큰 문자열을 가질 리가 없어요");
RawYarn {
ptr: MaybeUninit::new(ptr),
len: NonZeroUsize::new_unchecked(
(kind as usize & 0b11) << (usize::BITS - 2) | len),
}
}
}
Rust
이 타입은 0이 모두인 비트 패턴이 니치라는 사실을 Rust 컴파일러가 특별히 알고 있어서, Option<Yarn>도 16바이트가 되도록 해줍니다. 또한 Option<Yarn>의 올-제로 비트 패턴이 None이라는 편리한 성질도 가집니다.
byteyarn 소개 문구는 우리가 만든 것을 이렇게 설명합니다:
Yarn은String에 비해 여러 유용한 속성을 제공하는 고도로 최적화된 문자열 타입입니다:
- 항상 포인터 두 개 폭이므로, 함수에 들어가고 나올 때 항상 레지스터로 전달됩니다.
- 64비트 아키텍처에서 15바이트까지의 작은 문자열 최적화(SSO).
- 소유 버퍼일 수도, 차용 버퍼일 수도 있습니다(
Cow<str>처럼).- 알려진 정적 문자열에서 구성되었다면 수명을
'static으로 승격할 수 있습니다.
물론 트레이드오프도 있습니다. 처음에 세웠던 가정들이 성립해야 할 뿐 아니라, 사이클 수 성능보다는 메모리를 상대적으로 더 신경 써야 합니다. 문자열 길이를 읽는 같은 기본 연산조차 더 많은 수학(하지만 추가 분기 없이)을 필요로 하기 때문입니다.
실제 Yarn 구현은 여기서보다 조금 더 복잡합니다. 일부는 모든 저수준 부기(북키핑)를 한 곳에 모아두기 위함이고, 일부는 Yarn을 Box<str>의 사실상 대체물로 쓸 수 있게 하는 인체공학적 API를 제공하기 위함입니다.
이 후드 아래의 엿보기가 교묘한 레이아웃 해킹으로 무엇을 달성할 수 있는지에 대한 새로운 감탄을 드렸기를 바랍니다.
그 결과, realloc()의 크기 변화가 사이즈 클래스를 바꾸지 않는다면 이는 노옵(no-op)이 되며, 특히 할당자가 Rust가 제공하는 현재 크기 정보를 활용할 수 있는 경우 그렇습니다.↩
이후 이 글에서 “character”는 “32비트 유니코드 스칼라”를 의미합니다.↩
또 이런 지적도 가능하겠죠. Rust와 C는 포인터 오프셋 타입(isize와 ptrdiff_t)보다 큰 크기의 할당을 허용하지 않는다고요. 실무적으로 이는 상위 비트가 언어 자체의 규칙에 따라 항상 0이라는 뜻입니다.
맞습니다. 하지만 우리는 비트를 두 개 훔쳐야 하고, 이것이 지극히 합리적인 바람임을 보여주고 싶었습니다. 64비트 정수는 우스울 정도로 큽니다.↩
(x << 2) >> 2를 다음과 같이 컴파일합니다.movabs rax,0x3fffffffffffffff
and rax,rdi
ret
x86 어셈블리
바이트 단위로 따지면, 이는 인텔 가변 길이 인코딩에서 14바이트가 듭니다. 두 번의 시프트가 코드 크기를 약간 더 줄일 거라고 생각할 수도 있지만, 그렇지 않습니다. 입력이 rdi로 들어오고 rax에 놓여야 하기 때문입니다.
그런데 RISC-V에서는 두 번 시프트가 실제로 더 저렴하다고 판단하는 듯하며, x & 0x3fff_ffff_ffff_ffff를 다시 두 번 시프트로 최적화하기도 합니다.↩