Разбираем выравнивание данных и структуру памяти в Rust

Мне нравится оптимизировать код — определение и исправление неэффективных участков кода приносит некое особое чувство удовлетворения в отличие от закидывания проблемы железом. Ведь последнее — пустая трата ресурсов и выбросов углерода!

В процессе моей работы я много раз оптимизировал использование памяти датафреймов Python. Не учитывая различные особенности, зачастую наиболее быстрым решением является понижающее приведение — к примеру, конвертация столбца нулей и единиц из int в bool. И хотя это срабатывает, недавно к своему удивлению я узнал, что булевы числа не всегда отображаются в качестве одиночных битов. Так как же отображаются типы данных в памяти?

Подобно тому, как аккуратно организованные стеллажи книг в библиотеке помогают легко найти нужную информацию, отображение данных в памяти может сильно повлиять на производительность и эффективность использования памяти вашего приложения.

Данная статья будет разбита на две части и посвящена отображению данных в приложениях.

В этой (первой) части мы разберем:

• что такое выравнивание данных и почему оно важно

• что такое структура памяти на нескольких примерах

• как оценивать использование памяти для встроенных и собственных типов данных в Rust

• различные сюрпризы, в зависимости от ваших прошлых знаний. Как и я, вы могли быть удивлены, что булевы числа не всегда занимают только 1 бит в памяти!

На этой ноте, пришло время погрузиться в то, как данные отображаются в памяти — поехали!

Как интерпретируются байты в памяти?

Компьютеры хранят данные в памяти в виде последовательности бит. Но сами по себе биты не несут какого‑либо значения. Типы используются программами для интерпретации этой последовательности во что‑то полезное программисту. К примеру, последовательность 10 100 011 может быть интерпретирована как 163 в случае целого числа без знака или -35 в случае целого числа со знаком.

Концепция выравнивания

Выравнивание — то, как именно биты располагаются в памяти. В теории, точное расположение последовательности бит в памяти не должно ни на что влиять, до тех пор пока сохраняются их порядок и непрерывность.

Но на практике железо устанавливает свои правила, касающиеся того, как данные в памяти читаются и записываются, делая выравнивание важным. Для начала, указатели всегда указывают на байты, а не произвольные биты — указатель позволяет ссылаться на байт N или N+1, но не на какой‑то бит между ними. Данные, начинающиеся на границе байта называются выровненными.

Есть еще одно правило — большая часть компьютеров читает данные чанками, также известными как слова. Слово — количество бит, которое процессор может обработать за одну инструкцию. Вы, возможно, слышали, что ваше устройство имеет 64-битную архитектуру, что означает, что ширина адреса памяти составляет 64 бита и устройство читает данные чанками по 64 бита.

Влияние не выровненных данных

Представьте, что у нас есть переменная типа i64 (8 байт). Когда данные выровнены, компьютер читает биты в первом 64-битном чанке (зеленый ряд ниже) для определения значения типа i64. Это выполняется за одну операцию чтения.

Но что если данные не выровнены, как на картинке ниже?

Для того, чтобы интерпретировать значение, нужно:

1. Прочитать биты первого слова

2. Применить маску, оставив только вторую половину

3. Прочитать биты второго слова

4. Применить маску, оставив только первую половину

5. Объединить биты из шагов 2 и 4

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

На примере выше мы можем видеть, как выравнивание создает основу производительных и стабильных приложений.

Выравнивание по степеням двойки

Большая часть основных встроенных типов «естественно» выровнена по своему размеру. u8 выровнен побайтово, i16 — по два байта, u32 — по четыре, а f64 — по 8 байт. Обратите внимание, что все это — степени двойки и это не совпадение. Многие современные компьютеры используют выравнивание по степеням двойки для оптимизации производительности.

Если адрес данных mod n равен 0, то данные выровнены по n‑байт. Так тип u32 считается выровненным, если его данные начинаются с первого или пятого байта слова. Для другого любого начального байта внутри слова данные u32 не выравнены.

Структура для оптимального использования памяти

В то время как выравнивание относится к тому, как биты организованы относительно границ байт в памяти, структура памяти относится к тому, как данные для разных полей организованы внутри типа.

Проводя аналогию с тетрисом, блок может быть выровнен только по определенным позициям в сетке. В то же время то, как блоки располагаются относительно друг друга это структура.

Отображение данных в памяти влияет на использование памяти типом данных и приложением в целом, что мы и увидим ниже.

Структура памяти для структуры

Предположим, у нас есть следующая структура:

#[repr(C)] struct Foo {     tiny: bool,     normal: u32,     small: u8,     long: u64,     short: u16, }

Компилятору необходимо определить структуру памяти для структуры Foo, а именно как разные поля расположены внутри нее.

Компилятор следует нескольким правилам для принятия решения:

1. Биты должны быть выровнены побайтово.

2. Встроенные типы данных “естественно” выравниваются по своему размеру (как упоминалось ранее, u16 — по два байта, f64 — по восемь).

3. Для сложных типов, составленных из нескольких других, выравнивание приравнивается к наибольшему из его составляющих.

Для начала мы рассмотрим выравнивание для структуры Foo при использовании структуры памяти в стиле C, о чем и указывает нам атрибут #[repr(C)]. Позже мы глянем, чем оно отличается от нативных структур в Rust.

В C поля располагаются следующим образом:

• tiny — булево число, так что оно должно использовать только 1 бит, ведь так? Не совсем — согласно первому правилу, оно занимает 1 байт (8 бит). Если бы его длина составляла 1 бит, следующие за ним данные не были бы выровнены.

• normal занимает 4 байта и выровнено по 4 байта, согласно второму правилу. Так что мы не можем поместить данные сразу после tiny — нам нужно “заполнить” место после него тремя байтами, чтобы следовать выравниванию. На данный момент использование памяти составляет 1 + 3 + 4 = 8 байт.

• small занимает один байт и побайтово выровнено, так что может быть добавлено без дополнительных действий.

• long занимает 8 байт и выравнивается по 8 байт. Поскольку на данный момент мы используем 1 + 3 + 4 + 1 = 9 байт, нам потребуется 7 байт “заполнения”, чтобы обеспечить выравнивание в 8 байт для long.

• short занимает 2 байта и может быть добавлено сразу после long.

На данный момент использование памяти составляет (1 + 3) + 4 + (1 + 7) + 8 + 2 = 26 байт.

Наконец, сама структура Foo должна быть выравнена. Это нужно, чтобы данные после Foo также попадали в рамки выравнивания. Согласно третьему правилу, Foo использует выравнивание наибольшего поля long, то есть восемь байт. Соответственно, нам нужно 6 байт “заполнения”, чтобы “округлить” структуру памяти до 32 байт.

Ниже визуальное отображение результата.

Проверяем размер и выравнивание в Rust.

На данном этапе у вас мог появиться вопрос — а как нам проверить, действительно ли это так. В Rust это можно сделать с помощью структуры std::alloc::Layout.

Playground

Структура памяти в стиле Rust

Как вы могли заметить, отображение в стиле C требует, чтобы все поля были расположены в том же порядке, в котором они были объявлены, что приводит к предсказуемой, но не совсем оптимальной структуре памяти.

В то же время, отображение в стиле Rust (#[repr(Rust)]) не требует подобных строгих гарантий, позволяя компилятору оптимизировать расположение полей, делая его более компактным и эффективным. Это достигается сортировкой полей по их размеру в порядке убывания.

#[repr(Rust)]  // Omitting this line has the same effect struct Foo {     tiny: bool,     normal: u32,     small: u8,     long: u64,     short: u16, }

Вот так выглядит структура памяти Foo в отображении Rust:

Как видите, структура в стиле Rust значительно компактнее — требуется в 2 раза меньше памяти по сравнению с отображением в стиле C.

Объяснение структуры памяти для стандартных типов данных

Теперь, когда мы знаем, как размещаются в памяти собственные типы, что насчет других встроенных типов, а в особенности кортежей, массивов и enum?

Кортежи

В случае кортежей значения размещаются подобно полям структур — например, Foo и кортеж (bool, u32, u8, u64, u16) имели бы одинаковую структуру памяти.

Enums

Структура памяти enum состоит из двух частей — дискриминатора и варианта enum. Дискриминатор — индекс варианта enum и на практике имеет длину в один байт (если у вас больше 256 вариантов в enum, стоит задуматься о пересмотре дизайна…). Структура памяти для каждого из вариантов определяется независимо от других. Размер варианта enum соответствует размеру наибольшего из них, а выравнивание дискриминатора следует выравниванию наибольшего из вариантов.

К примеру, enum Shape ниже:

enum Shape {     Circle { radius: f32 },     Rectangle { width: f32, height: f32 },     Square(f32), }

Имеет следующую структуру:

Каждый вариант структуры памяти рассчитывается независимо друг от друга:

Часть, отвечающая за вариант enum имела бы длину в 8 байт. Это необходимо, чтобы выделить достаточно памяти для любого из них.

Для отображения трех возможных значений дискриминатор имел бы тип u8. И хотя u8 выравнивается побайтово, ему придется следовать выравниванию наибольшего варианта enum (4 байта). Соответственно, к дискриминатору добавляется 3 байта заполнения.

Массивы

Массивы отображены в памяти как непрерывная последовательность байт без заполнения между элементами. Массив из элементов Shape из enum выше выглядел бы следующим образом:

Заключение

Теперь у вас должно быть чуть лучшее представление о том, что такое выравнивание и структура памяти. Также, возможно, вам теперь чуть легче предугадать, как ваши данные располагаются в памяти в вашей программе.

Рассмотрев примеры выше, можно заметить, что структура памяти имеет большое влияние на использование памяти приложением в целом. Неэффективное отображение в памяти может быстро раздуть используемую память, особенно когда существует много экземпляров типа — например, в массиве.

Несмотря на это, компактность данных в памяти не всегда является оптимальным вариантом — как часто бывает в инженерном деле — у каждого подхода есть свои плюсы и минусы.

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