Удивительная оптимизация размера enum в компиляторе Rust

Enum — одна из самых популярных фич Rust. Тип enum может иметь одно из значений в заданном множестве вариантов.

/// Foo имеет значение или 32-битного integer, или символа. enum Foo {     Int(u32),     Char(char), }

Значениями типа Foo могут быть или integer (например, вариант Foo::Int(3) с полезной нагрузкой 3), или символы (например, вариант Foo::Char('A') с полезной нагрузкой 'A'). struct можно считать AND-комбинациями их полей, а enum — OR-комбинациями их вариантов.

Этот пост посвящён удивительной оптимизации, выполняемой компилятором Rust с представлением в памяти значений enum, чтобы они занимали меньше места в памяти (спойлер: это не нишевая оптимизация). В общем случае, уменьшение размера значений может привести к ускорению программ, потому что значения передаются в регистрах CPU и в одну линию кэша CPU умещается больше значений.

Обычно размер enum равен размеру самой большой его полезной нагрузки плюс несколько дополнительных байтов для хранения тэга, указывающего, к какому варианту относится значение. В случае показанного выше типа Foo полезные нагрузки обоих вариантов занимают 4 байта, и нам понадобится ещё как минимум один дополнительный бит под тэг. Из-за требования выравнивания типов (type alignment, я не буду рассказывать о нём подробно) Rust использует под тэг 4 байта. То есть общий размер становится равным 8 байтам:

assert_eq!(std::mem::size_of::<Foo>(), 8);

(Все примеры кода можно запустить в Rust Playground.)

Чтобы объяснить оптимизацию, полезно и интересно будет разобраться, как представлены в памяти различные значения enum. Вот функция, выводящая представление любого значения Rust в сырых байтах:

/// Выводим представление в памяти значения типа T. fn print_memory_representation<T: std::fmt::Debug>(t: T) {     print!("type={} value={t:?}: ", std::any::type_name::<T>());     let start = &t as *const _ as *const u8;     for i in 0..std::mem::size_of::<T>() {         print!("{:02x} ", unsafe {*start.offset(i as isize)});     }     println!(); }

(Эта функция написана на основе поста десятилетней давности с Reddit.)

Давайте выполним её для нашего enum Foo.

print_memory_representation(Foo::Int(5)); // type=Foo value=Int(5): 00 00 00 00 05 00 00 00 //                        |-- tag --| |- value -|  print_memory_representation(Foo::Char('A')); // type=Foo value=Char('A'): 01 00 00 00 41 00 00 00  //                           |-- tag --| |- value -|

Первым делом стоит отметить .что память компьютера имеет формат little endian, то есть младшие байты идут первыми. В 32-битном шестнадцатеричном виде число 5 выглядит, как 0x00000005, но в little endian оно представлено, как 05 00 00 00.

Из этого мы можем понять. что первые 4 байта — это тэг. Варианту integer был назначен тэг 0, а варианту-символу — тэг 1. Вторая группа из 4 байтов — это обычные значения полезной нагрузки. Стоит отметить, что заглавная буква «A» в шестнадцатеричном виде имеет в ASCII значение 41, поэтому и представлена в памяти, как 41 00 00 00.

Нишевая оптимизация

Наряду с общей схемой тэгов существует одна известная оптимизация размеров enum, называемая нишевой оптимизацией (niche optimization). Эта оптимизация работает для типов, в которых полезную нагрузку имеет только один из вариантов. Хорошим примером будет встроенный тип option:

enum Option<char> {     None,     Some(char), }

Исходя из анализа тэгов в предыдущем разделе, мы можем предположить, что enum будет иметь размер 8 байтов (самая большая нагрузка составляет 4 байта плюс 4 байта на тэг). Но на самом деле значения этого типа суммарно занимают в памяти всего 4 байта:

assert_eq!(std::mem::size_of::<Option<char>>(), 4);

Что же происходит? Компилятор Rust знает, что хотя char занимает до 4 байтов в памяти, не каждое значение из этих 4 байтов будет валидным значением char. Символ имеет всего примерно 221 валидных значений (по одному для каждой кодовой точки Unicode), а 4 байта поддерживают 232 различных значений. Компилятор выбирает один из этих недопустимых паттернов битов в качестве ниши, и представляет значение enum без использования тэгов. Вариант Some он представляет идентично char, а вариант None представляет с использованием ниши.

Возникает интересный вопрос: какую конкретно нишу использует Rust? Чтобы разобраться, давайте выведем представление в памяти:

let a: char = 'A' print_memory_representation(a); // type=char value='A': 41 00 00 00   print_memory_representation(Some(a)); // type=Option<char> value=Some('A'): 41 00 00 00   let none: Option<char> = None; print_memory_representation(none); // type=Option<char> value=None: 00 00 11 00 

Как мы видим, представления 'A' и Some('A') в памяти идентичны. Rust представляет None при помощи 32-битного числа 0x00110000. Можно поискать и убедиться, что это число ровно на единицу больше максимальной валидной кодовой точки Unicode.

Что-то ещё, кроме нишевой оптимизации?

Я считал, что Rust больше не выполняет никаких оптимизаций, поэтому был приятно удивлён, когда обнаружил ещё одну.

Контекст кода — вложенные enum. Начнём с внутреннего enum

enum Inner {     A(u32),     B(u32), }

Если взглянуть на представление в памяти, то там всё будет так, как мы и ожидали: 8 байтов, в первых 4 байтах хранится тэг, а в последних — полезная нагрузка.

assert_eq!(std::mem::size_of::<Inner>(), 8);  print_memory_representation(Inner::A(2)); // type=Inner value=A(2): 00 00 00 00 02 00 00 00  //                        |-- tag --| |- value -|  print_memory_representation(Inner::B(3)); // type=Inner value=B(3): 01 00 00 00 03 00 00 00  //                        |-- tag --| |- value -|

А теперь добавим ещё одно enum, содержащее Inner в качестве полезной нагрузки:

enum Outer {     C(u32),     D(Inner), }

Я думал, что значения этого типа будут иметь размер 12 байтов — 8 байтов под максимальную полезную нагрузку Inner плюс 4 байта под тэг. Но это оказалось не так: значения занимали всего 8 байтов!

assert_eq!(std::mem::size_of::<Outer>(), 8);

Что здесь происходит?

Для начала давайте проверим, как значения типа Outer::C выглядят в памяти:

print_memory_representation(Outer::C(5)); // type=Outer value=C(5): 02 00 00 00 05 00 00 00 //                        |-- tag --| |- value -|

Мы уже видим что-то странное: Rust решил использовать тэг номер 2 для Outer::C , а не начинать с 0, как он делал это в случае Inner::A. Теперь взглянем на Outer::D:

print_memory_representation(Outer::D(Inner::A(2))); // type=Outer value=D(A(2)): 00 00 00 00 02 00 00 00  //                           |-- tag --| |- value -|  print_memory_representation(Outer::D(Inner::B(3))); // type=Outer value=D(B(3)): 01 00 00 00 03 00 00 00  //                           |-- tag --| |- value -|

Представление значения Outer::D(inner) идентично представлению inner!

Предполагаю, что компилятор Rust рассуждал так:

• Первые 4 байта Inner образуют тэг, значениями которого могут быть только 0 или 1. В нём можно хранить гораздо больше значений, как и в случае нишевой оптимизации.

• Полезная нагрузка для каждого другого варианта Outer не больше, чем любая из полезных нагрузок Inner. В частности, если значения Inner имеют вид <Inner tag><Inner payload>, то полезная нагрузка для всех других вариантов Outer умещается внутри <Inner payload>.

Таким образом, мы можем представить значения Outer в виде <Outer tag><Outer remainder>

• Если <Outer tag> соответствует какому-то из  <Inner tag>, то значение равно Outer::D, а полезная нагрузка представляет собой полный паттерн битов <Outer tag><Outer remainder>.

• В противном случае, значение — это ещё один вариант, а полезная нагрузка — это <Outer remainder>.