Мне нравится оптимизировать код — определение и исправление неэффективных участков кода приносит некое особое чувство удовлетворения в отличие от закидывания проблемы железом. Ведь последнее — пустая трата ресурсов и выбросов углерода!
В процессе моей работы я много раз оптимизировал использование памяти датафреймов Python. Не учитывая различные особенности, зачастую наиболее быстрым решением является понижающее приведение — к примеру, конвертация столбца нулей и единиц из int
в bool
. И хотя это срабатывает, недавно к своему удивлению я узнал, что булевы числа не всегда отображаются в качестве одиночных битов. Так как же отображаются типы данных в памяти?
Подобно тому, как аккуратно организованные стеллажи книг в библиотеке помогают легко найти нужную информацию, отображение данных в памяти может сильно повлиять на производительность и эффективность использования памяти вашего приложения.
Данная статья будет разбита на две части и посвящена отображению данных в приложениях.
В этой (первой) части мы разберем:
что такое выравнивание данных и почему оно важно
что такое структура памяти на нескольких примерах
как оценивать использование памяти для встроенных и собственных типов данных в Rust
различные сюрпризы, в зависимости от ваших прошлых знаний. Как и я, вы могли быть удивлены, что булевы числа не всегда занимают только 1 бит в памяти!
На этой ноте, пришло время погрузиться в то, как данные отображаются в памяти — поехали!
Как интерпретируются байты в памяти?
Компьютеры хранят данные в памяти в виде последовательности бит. Но сами по себе биты не несут какого‑либо значения. Типы используются программами для интерпретации этой последовательности во что‑то полезное программисту. К примеру, последовательность 10 100 011 может быть интерпретирована как 163 в случае целого числа без знака или -35 в случае целого числа со знаком.
Концепция выравнивания
Выравнивание — то, как именно биты располагаются в памяти. В теории, точное расположение последовательности бит в памяти не должно ни на что влиять, до тех пор пока сохраняются их порядок и непрерывность.
Но на практике железо устанавливает свои правила, касающиеся того, как данные в памяти читаются и записываются, делая выравнивание важным. Для начала, указатели всегда указывают на байты, а не произвольные биты — указатель позволяет ссылаться на байт N или N+1, но не на какой‑то бит между ними. Данные, начинающиеся на границе байта называются выровненными.
Есть еще одно правило — большая часть компьютеров читает данные чанками, также известными как слова. Слово — количество бит, которое процессор может обработать за одну инструкцию. Вы, возможно, слышали, что ваше устройство имеет 64-битную архитектуру, что означает, что ширина адреса памяти составляет 64 бита и устройство читает данные чанками по 64 бита.
Влияние не выровненных данных
Представьте, что у нас есть переменная типа i64
(8 байт). Когда данные выровнены, компьютер читает биты в первом 64-битном чанке (зеленый ряд ниже) для определения значения типа i64
. Это выполняется за одну операцию чтения.
Но что если данные не выровнены, как на картинке ниже?
Для того, чтобы интерпретировать значение, нужно:
Прочитать биты первого слова
Применить маску, оставив только вторую половину
Прочитать биты второго слова
Применить маску, оставив только первую половину
Объединить биты из шагов 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
, а именно как разные поля расположены внутри нее.
Компилятор следует нескольким правилам для принятия решения:
Биты должны быть выровнены побайтово.
Встроенные типы данных “естественно” выравниваются по своему размеру (как упоминалось ранее,
u16
- по два байта,f64
- по восемь).Для сложных типов, составленных из нескольких других, выравнивание приравнивается к наибольшему из его составляющих.
Для начала мы рассмотрим выравнивание для структуры 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),
}
Имеет следующую структуру:
Каждый вариант структуры памяти рассчитывается независимо друг от друга:
Вариант | Размер (в байтах) | Выравнивание |
---|---|---|
| 4 | 4-byte |
| 8 | 4-byte (Its largest field is 4-byte aligned) |
| 4 | 4-byte |
Часть, отвечающая за вариант enum имела бы длину в 8 байт. Это необходимо, чтобы выделить достаточно памяти для любого из них.
Для отображения трех возможных значений дискриминатор имел бы тип u8. И хотя u8 выравнивается побайтово, ему придется следовать выравниванию наибольшего варианта enum (4 байта). Соответственно, к дискриминатору добавляется 3 байта заполнения.
Массивы
Массивы отображены в памяти как непрерывная последовательность байт без заполнения между элементами. Массив из элементов Shape
из enum выше выглядел бы следующим образом:
Заключение
Теперь у вас должно быть чуть лучшее представление о том, что такое выравнивание и структура памяти. Также, возможно, вам теперь чуть легче предугадать, как ваши данные располагаются в памяти в вашей программе.
Рассмотрев примеры выше, можно заметить, что структура памяти имеет большое влияние на использование памяти приложением в целом. Неэффективное отображение в памяти может быстро раздуть используемую память, особенно когда существует много экземпляров типа — например, в массиве.
Несмотря на это, компактность данных в памяти не всегда является оптимальным вариантом — как часто бывает в инженерном деле — у каждого подхода есть свои плюсы и минусы.
В следующей статье цикла мы посмотрим на другие доступные представления в Rust, когда их стоит использовать и почему иногда стоит использовать не самые эффективные с точки зрения использования памяти отображения.