Как и почему Option в Rust оптимизируется до 24 байт?

Меня удивило, что Option<Vec<T>> имеет такой же размер, как Vec<T>:

fn main() {
  println!(
    "u128: {} -> {}",
    size_of::<u128>(),
    size_of::<Option<u128>>()
  );
  println!(
    "vec: {} -> {}",
    size_of::<Vec<u16>>(),
    size_of::<Option<Vec<u16>>>()
  );
}

оценка равна

u128: 16 -> 32
vec: 24 -> 24

Так что

1. Как Rust представляет случай None для Option<Vec>? Похоже, что нормальные 24 байта Vec приходят из трех 8-байтовых полей: указателя, емкости в байтах и длины. Я предполагаю, что он использует нулевой указатель для None, но не уверен. Сможет ли Rust поддерживать такую же структуру памяти, если Vec будет содержать 2 указателя?

2. Почему Rust это делает? Для Option<u128> у нас явно есть выбор использовать N байтов, пока N > 16, а Rust выбирает N = 32. Это, конечно, имеет свои преимущества, например, мы можем получить доступ к i-му элементу Vec<Option<u128>> только с помощью битовых сдвигов (без умножений). Но если это идеально, разве Rust не должен сделать Option<Vec<T>> также 32 байта?

Версия Rust: rustc 1.83.0-nightly (1bc403daa 2024-10-11)

1. Option<Vec<_>>

Вы обнаружили нишевую оптимизацию использования памяти, поддерживаемую Vec. Более конкретно:

• Vec<T> содержит…
• RawVec<T>, который содержит…
• RawVecInner, который содержит оба…
  • Cap, usize, который никогда не может превышать isize::MAX (известно rustc через rustc_layout_scalar_valid_range_end)
  • Unique<u8>, который содержит…
  • NonNull<u8>. Документация для NonNull специально отмечает, что отсутствие NULL позволяет оптимизировать структуру памяти.

В результате Option::<Vec<_>>::None может быть представлено 0, где должен быть указатель (что отличается от действительной инстанции нулевого *const u8 указателя). В качестве альтернативы это может быть представлено значением, превышающим isize::MAX, где должен быть Cap. Остальные поля могут быть произвольными для такого значения. Компилятор получает возможность выбирать, какое представление использовать произвольно, но я бы предположил, что все нулевые байты будут оптимальными для производительности (легче распределять).

Я не уверен, что вы имеете в виду под Vec, который содержит два указателя. Добавление дополнительного указателя в Vec увеличило бы размер как Vec, так и Option<Vec<_>> на размер указателя.

2. Option<u128>

Сначала давайте предположим, что указатели занимают 8 байтов и выравнивание u128 составляет 16:

println!("{}", std::mem::size_of::<*const u8>()); // 8
println!("{}", std::mem::align_of::<u128>()); // 16

Рассмотрим значение vec![Some(0u128), Some(0u128)]. Для корректности оба значения u128 должны быть выровнены. По вашей логике, первый элемент в Vec должен занимать как минимум 17 байтов (16 для u128, 1 для дискриминанта enum). Следующее выровненное местоположение в памяти (множитель выравнивания) будет находиться на 32 байта от начала Vec. Поскольку Vec не имеет способа добавлять отступы между элементами, отступы должны попадать внутрь Option<u128>, что делает его 32 байта. На самом деле, размер является кратным выравниванию для всех типов.

Если вам интересно, ближайшим к 16-байтовому Option<u128> является Option<NonZeroU128>.

Но если это идеально, разве Rust не должен сделать Option<Vec> также 32 байта?

Как я уже упоминал, это проблема выравнивания, а не проблема производительности индексации. Vec имеет выравнивание 8, поэтому размер должен быть только кратным 8. Если вас беспокоит производительность индексации, всегда можно увеличить выравнивание:

/// Отказ от ответственности: фактическая производительность может варьироваться;
/// проконсультируйтесь с вашим бенчмарком перед принятием каких-либо решений об оптимизации!
///
/// Увеличение использования памяти на 33% снизит локальность кеша!
#[repr(align(32))]
struct FastVec<T>(Vec<T>);