Задача 21. Контейнеры в памяти.

Часть 2: какие они на самом деле? Сложность: 3

Когда вы запрашиваете память - что вы знаете о том, что вы получите и во что в действительности это вам обойдется ? Сколько памяти используют стандартные контейнеры - теоретически, практически и в коде, который будет написан вами сегодня

вечером ?

Вопрос для новичка

1. Когда вы запрашиваете п байтов памяти с использованием new или mall ос, в самом ли деле вы используете п байтов памяти? Поясните, почему.

Вопрос для профессионала

2. Сколько памяти используют различные стандартные контейнеры для хранения одинакового количества объектов одного и того же типа т?

Решение

Что попросишь, то получишь?

1. Когда вы запрашиваете п байтов памяти с использованием new или malice, в самом ли деле вы используете п байтов памяти? Поясните, почему.

Когда вы запрашиваете п байтов памяти с использованием new или malloc, в действительности вы используете как минимум п байтов памяти, поскольку обычно диспетчер памяти должен добавить определенное количество памяти сверх запрошенной вами. Обычно это накладные расходы, связанные с внутренними сфуктурами диспетчера памяти, размером и выравниванием объектов в памяти.

Рассмотрим накладные расходы, связанные с внутренними структурами диспетчера памяти. В универсальной схеме распределения памяти (т.е. с не фиксированными размерами блоков) диспетчер памяти должен помнить о том, какой размер имеет каждый вьщеленный блок, чтобы знать, какое количество памяти должно быть освобождено при вызове оператора delete или функции free. Обычно диспетчер памяти хранит это значение в начале реально выделяемого блока памяти, возвращая вам указатель на "вашу" область памяти, которая располагается непосредственно после необходимой области памяти, зарезервированной для служебной информации (см. рис. 21.1). Конечно, это означает, что должна быть выделена дополнительная память для сохранения размера блока, т.е. для числа, достаточного для хранения значения, равного максимально возможному корректному запросу памяти; обычно для этой цели достаточно числа, размер которого равен размеру указателя. При освобождении блока диспетчер памяти получает переданный ему вами указатель, вычитает из него количество байтов системной информации, считывает раз.мер блока и выполняет его освобождение.

Конечно, в схеме с фиксированным размером блока (которая возвращает блоки памяти данного заранее известного размера) хранение дополнительной информации о размере блока не требуется, поскольку размер блока и так всегда известен.

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

Указатель, возвращаемый

new или mai loc

Реально выделенный буфер

Системная информация

Запрошенная вами память Рис. 21.1. Типичное выделение п байтов памяти

С одной стороны, на некоторых платформах выдвигается требование того или иного расположения объектов определенных типов данных в памяти (например, некоторые платформы требуют размещения указателей по адресам, кратным 4), и в случае несоблюдения этих требований программа оказывается либо неработоспособной, либо скорость ее работы существенно снижается. Такое требование к размещению данных называется выравниванием (alignment) и приводит к необходимости затрат дополнительной памяти для заполнения промежутков внутри объекта и, возможно, за концом данных объекта. Выравнивание затрагивает даже обычные старые встроенные массивы С, поскольку вносит свой вклад в значение, возвращаемое si zeof (struct). На рис. 21.2 показана разница между внутренним заполнением и заполнением после конца объекта (хотя оба дают свой вклад в значение sizeof (struct)).

тбайтов== sizeof (object)

п байтов == размер каждого элемента данных + возможное внутреннее выравнивание

Заполнение

Рис. 21.2. Размещение в памяти массива п-байтовых объектов с т-байтовым выравниванием (обратите внимание, что sizeof(object)==m)

Например:

пример 21-1: предполагается, что si zeof(long) == 4, и все значения long требуют выравнивания по

4-байтовой границе

struct xl {

char cl; Смешение О, размер - 1 байт

Байты 13: 3 заполняющих байта long 1; Байты 4-7: 4 байта на 4-байтовой границе char с2; Байт 8: 1 байт

Байты 9-11: заполняющих байтов (см. текст) }; sizeof(XI) == 12

В обозначениях рис. 21.2, в данном примере п== 1+3 + 4 + 1 ==9 и m == si zeof (xl) == 12. Заметим, что в значение si zeof (xl) вносят вклад все заполнители - как внутренние, так и внешние. Может показаться, что внешнее заполнение за

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

концом объекта имишне, но оно необходимо, например, когда вы работаете с массивом объектов х1, располагающихся в памяти один за другим, чтобы обеспечить выравнивание данных типа long по 4-байтовой границе. Такое выравнивание за концом данных зачастую удивляет людей, впервые сталкивающихся с размещением данных в памяти. Особенно может удивить следующий результат перестановки полей структуры:

Пример 212: измененная структура из примера 21-1

struct Х2 {

long 1; Байты 0-3

char cl; Байт 4

char с2; Байт 5

Байты 6-7: 2 заполняющих байта }; sizeof(x2) == 8

Теперь члены -данные действительно располагаются в памяти непрерывно (п == 6), но все еще имеется дополнительное пространство за концом объекта. Это делает размер объекта равным m == si zeof (х2) == 8. Это заполнение за концом объекта оказывается наиболее заметным при создании массива объектов х2. Заполняющие щестой и седьмой байты показаны на рис. 21.2 нсзаштрихованными квадратами.

Кстати, именно поэтому при написании стандарта было достаточно трудно сформулировать требование "последовательного расположения" элементов vector в том же смысле, что и массивы. На рис. 21.2 память рассматривается как непрерывная, несмотря на наличие областей неиспользуемой памяти. Так что же в действительности означает "последовательное расположение"? По cyfn, последовательно расположены отдельные блоки памяти размером si zeof (struct), й такое определение вполне работоспособно, поскольку sizeof (struct) включает дополнительную заполняющую память.

Стандарт С++ гарантирует, что вся память, выделенная оператором new или функцией malloc, будет надлежащим образом выровнена для всех возможных объектов, которые вы можете захотеть в ней сохранить, а это означает, что оператор new и функция malloc должны удовлетворять самому строгому типу выравнивания на данной платформе.

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

Память и стандартные контейнеры: теория

Теперь мы перейдем к главному вопросу данной задачи.

2. Сколько памяти используют различные стандартные контейнеры для хранения одинакового количества объектов одного и того же типа т?

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

• Внутреннее представление, используемое vector<T> для хранения данных, представляет собой непрерывный С-массив объектов типа т, так что никаких дополнительных расходов памяти на хранение элементов у этого контейнера нет

Компилятор не может самостоятельно выполнить перестановку данных из примера 21-i к виду из примера 21-2. Стандарт требует, чтобы все данные, располагающиеся в одной и той же группе public, protected или private располагались компилятором в указанном порядке. Если же вы предваряете ваши данные спецификаторами доступа, то компилятор может выполнить перестановку в пределах групп данных, разделенных спецификаторами доступа для улучшения размещения. Это является одной из причин, по которой некоторые программисты предпочитают предварять каждый член-данные спецификатором доступа.