C++ является разумным выбором, когда от программы требуется производительность и приближенность к железу, с сохранением удобства написание самой программы. Именно поэтому знание того, как объекты располагаются в памяти и то, на что и как это влияет является необходимым знанием для любого C++ программиста, который попал в наши ряды не по ошибке. Поэтому настоящую и следующую статью я хочу посвятить рассмотрению расположения объектов в памяти при различных условиях. Хочется сразу предупредить: многое из того,  что будет описано ниже является архитектурно зависимым и не является частью стандарта C++. В рамках статьи я проводил тесты со следующими связками: MSVC 2013 amd64 на Core i7 4771K и clang(Apple LLVM version 5.0) amd64 на Core i5-2415M, далее, я буду просто упоминать с чем проводился тест: с MSVC или clang. В статье пойдёт речь о выравнивании и почему мы должны заботиться о нём, а также о размещении объектов классов в памяти в наиболее простых случаях. В следующей статье мы рассмотрим, то как виртуальность влияет на размещение объектов и чем это может нам аукнуться.

Выравнивание

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

Разумеется, эта плоская модель прочно обосновалась в умах программистов и поэтому у многих из них возникает резонный вопрос: если мы имеем линейную структуру, в которой мы можем адресовать каждый байт, то о каком выравнивании идёт речь? Зачем оно? Действительно, если мы можем адресовать любой байт, то нет смысла в выравнивании, т.к. в чём может быть разница между получением байта по адресу, скажем, 0x0004 и 0x0005? Всё это так, но проблема заключается в том, что подобное, “плоское”, представление о памяти есть ни что иное как высокоуровневая модель памяти безотносительно её внутренней реализации(которая внутри является матрицей битов, если говорить о современных, распространённых образцах). Так вот, на одном из уровней абстракции физическую память можно представить как набор банков памяти, каждый из которых хранит часть данных. Совокупность банков составляет, собственно, весь модуль памяти. Банки могут быть разного размера и их количество может варьироваться, но их суть и назначение неизменны: каждый банк хранит часть данных и может возвращать определённое количество данных в единицу времени. Банки могу выдавать по 1-у, 2-м, 4-м и т.д. байтам, в зависимости от реализации.

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

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

Исходя из картинки выше можно увидеть, что Банк 1 может содержать 1-й, 4-й, 8-й и т.д байты. Соответственно, если у нас есть некий объект, который занимает более одного байта, то он будет распределён между несколькими банками памяти. Предположим, что мы поместили объект типа int(4 байта, архитектура с обратным порядком байт) – 0xDEADBEEF:

Таким образом, наш объект занял все первые байты имеющихся в наличии банков, т.е. всю первую строку. Теперь, когда процессор обратиться к памяти, то ей просто потребуется считать первую строку наших банков, чтобы получить искомое. Память может выдавать только по одной строке за раз, она не может читать первый байт из Банка 1, второй из Банка 2 и т.п. Только одну строку в единицу времени. И тут мы подходим к проблеме с выравниванием, если наш int выровнен как положено(по границе 4 байтов), то его считывание всегда будет занимать не более одной единицы времени. Что же будет, если мы поместим int по не выровненному адресу?

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

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

Кто-то может возразить: да не будет ваш Core i7 читать по 4 байта – это просто убьёт  производительность, современные процессоры читают сразу всю линию кэш. Безусловно, но если посмотреть внимательно, то вы поймёте, что это мало что меняет. Если к данным обращаются по не выровненным адресам, то есть большой шанс, что наши данные пересекут не просто границы строк банков, но и границы кэш линий, а это значит, что нам придётся

• Прочитать 2 кэш линии из памяти вместо одной, прежде чем мы сможем начать работать с данными
• При каждом обращении к кэш, нам придется обращаться к двум линиям, а потом “собирать” наш объект

Всё это не лучшим способом влияет на производительность.

Итак, теория это конечно хорошо, но что мы имеем на практике? Действительно ли мы имеем реальные проблемы с производительностью? Я провёл несколько тестов с помощью clang, MSVC и следующего кода:

#include <iostream>
#include <chrono>
#include <numeric>
#include <vector>

size_t testAligned(std::vector<long long>& vec);
size_t testUnaligned(std::vector<long long>& vec);

const size_t c_Count = 50000000;

int main()
{
    std::vector<long long> vec(c_Count);
    std::iota(begin(vec), end(vec), 0);
    size_t alignedTime = testAligned(vec);
    size_t unalignedTime = testUnaligned(vec);
    std::cout << "The difference is: " << 100. - 
        (static_cast<double>(alignedTime)/unalignedTime)*100.0 << std::endl;
    return 0;
}

const size_t c_Times = 20;

size_t testAligned(std::vector<long long>& vec)
{
    size_t elapsed = 0;
    long long* testee = &vec[0];
    for(size_t i = 0; i < c_Times; ++i)
    {
        auto start = std::chrono::high_resolution_clock::now();
        for(size_t i = 0; i < c_Count - 15; i += 15)
            testee[i] *= 2;
        elapsed += (std::chrono::high_resolution_clock::now() - start).count();
    }
    std::cout << "Elapsed aligned: " << elapsed/c_Times << std::endl;
    return elapsed/c_Times;
}

size_t testUnaligned(std::vector<long long>& vec)
{
    size_t elapsed = 0;
    char* vecPtr = reinterpret_cast<char*>(&vec[0]);
    long long* testee = reinterpret_cast<long long*>(vecPtr + 2);
    for(size_t i = 0; i < c_Times; ++i)
    {
        auto start = std::chrono::high_resolution_clock::now();
        for(size_t i = 0; i < c_Count - 15; i += 15)
            testee[i] *= 2;
        elapsed += (std::chrono::high_resolution_clock::now() - start).count();
    }
    std::cout << "Elapsed unaligned: " << elapsed/c_Times << std::endl;
    return elapsed/c_Times;
}

В результате, с MSVC я получил ~5% разницу, и с clang разница была порядка 10%. Нельзя сказать, что результат получился внушительный, но и отметать его тоже нельзя. Итак, теория подтверждается практикой – доступ по не выровненным адресам может навредить производительности. Правда, судя по тем статьям, что я читал по теме, с каждым годом разница всё уменьшается и велик шанс не иметь её вовсе в ближайшем будущем, для x86 архитектуры, разумеется.

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

Составные объекты

Даже если вы никогда не балуетесь с адресами и чётко соблюдаете выравнивание, вы всё еще можете получить  сюрприз связанный с выравниванием. Этот “сюрприз” связан с тем, как представляются структуры(или же классы) в памяти. Для наглядности, давайте рассмотрим структуру, которая содержит три символьных(char) идентификатора валюты, один интегральный(int) идентификатор и два вещественных(double) числа, которые показывают как две валюты относятся к третьей(эти подробности не важны, они приведены просто для придания хоть какого-то смысла этой структуре). Логичным шагом было бы сгруппировать наши значения так, чтобы близкие по назначению объекты располагались рядом; вот, что из этого получилось:

struct Currency
{
    char firstCurrency;
    double firstValue;
    char secondCurrency;
    double secondValue;
    char baseCurrency;
    int baseCurrencyId;
};

Если посчитать “руками”, то размер этой структуры равен 23 байта, но на деле это не так. На деле, на моих машинах, он равен 40 байтам! Откуда же берётся такая разница? Всё дело в пресловутом выравнивании: если firstValue будет расположен по адресу следующему сразу за firstCurrency, то получится, что объект типа double(8 байтов) расположен по не выровненному адресу, а компилятор не может этого допустить. Поэтому, сразу после firstCurrency добавляется так называемое заполнение (padding) незначительной информацией(сиречь мусором), которое гарантирует, что каждый член структуры будет выровнен по правильному адресу. Вот как можно изобразить нашу структуру в памяти:

Штриховкой показано заполнение; разный цвет определяет разные типы данных, здесь и далее.

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

struct CurrencyOpt
{
    double firstValue;
    double secondValue;
    int baseCurrencyId;
    char firstCurrency;
    char secondCurrency;
    char baseCurrency;
};

Путём простой смены порядка полей структуры, нам удалось сократить размер оной с 40, до 24, что составляет 40%-й выигрыш в размере! Вот как наша новая структура будет выглядеть в памяти:

К сожалению еще один байт мы отвоевать не сможем: т.к. структуры могут располагаться в памяти друг за другом(массив) и в таком случае, 23-х байтная структура очень быстро сломает выравнивание всех не-однобайтовых полей объектов структуры, начиная уже со второго объекта. Поэтому сама структура тоже должна быть выровнена по границе. Но по какой? Может показаться, что достаточно выровнять структуру по четной границе, но это не так. Структура должна быть выровнена согласно наиболее строгому требованию к выравниванию, которое берётся исходя из состава полей структуры. В нашем случае наиболее требователен к выравниванию является тип double, а значит структура должна быть выровнена по границе 8 байтов. Это легко проверить: просто добавим еще 3 байта в нашу структуру:

struct CurrencyExcessive
{
    double firstValue;
    double secondValue;
    int baseCurrencyId;
    char firstCurrency;
    char secondCurrency;
    int baseCurrency;
};

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

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

struct CurrencyPair
{
    std::pair<char, double> firstCurrency
    std::pair<char, double> secondCurrency;
    std::pair<char, int> baseCurrency;
};

Что даёт нам те же 40 байтов.

Помимо “раздутости”, еще одной проблемой, которая подстерегает многих новичков, является попытка заполнения структуры через memcpy() или схожую функцию из данных полученных, скажем, из сети. Делая так, вы должны помнить про заполнение, которое может быть разным на различных архитектурах.

У этой проблемы существует решение, которого, тем не менее, нет в стандарте: структуры можно упаковать так, чтобы не было никакого заполнения вообще. Тогда можно использовать memcpy()/memmove() без каких либо опасений. Если интересно, то можете посмотреть в сторону #pragma pack

Старые добрые данные

Со времени появления C++ в нём существует такое понятие как POD(Plain Old Data)-класс. Хотя я буду употреблять термин класс, в данном параграфе, он может быть легко заменён на структуру, или даже на объединение(где применимо). Если не вдаваться в детали(к ним мы перейдём позже), то POD-класс, это такой класс, размещение которого совместимо с размещением обычной C-структуры. Другими словами, POD-класс является наследием C и служит мостом, между C++ и C. Более того, т.к. C это наиболее близкий к железу язык, то все объекты структур в оном представляют собой, по-сути, просто набор байт, который можно эффективно сериализовывать и копировать. Поэтому у POD-классов, в C++, существуют 2 основные роли: интероперабельность с C(вообще говоря не только с C, но я с другими примерами не встречался) и дополнительная производительность при копировании и сериализации.

Итак, мы разобрались зачем нужны POD-классы, теперь пришло время привести правила, соблюдая которые, мы можем создавать подобные классы. В современном C++, POD-классом является такой класс, который:

• Является тривиальным
• Обладает стандартным размещением

Тривиальность

Класс считается тривиальным, если он является тривиально копируемым и имеет тривиальный конструктор по умолчанию.

Тривиально копируемый класс определяется следующим образом:

• Класс не должен иметь нетривиального конструктора копирования
• Класс не должен иметь нетривиального конструктора перемещения
• Класс не должен иметь нетривиального оператора копирования
• Класс не должен иметь нетривиального оператора перемещения
• Деструктор класса должен быть тривиальным

Тривиальным, конструктор(деструктор и operator=), считается если он явно не объявлен или же, если он объявлен с =default и выполняются следующий условия:

• Класс не имеет виртуальных функций
• Класс не имеет виртуальных базовых классов
• Класс не имеет нестатических членов, которые является нетривиальными

Последнее требование это своего рода рекурсия, которая, в целом, очевидна. Тип A может принадлежать к категории X, только если все подтипы A принадлежат к данной категории.

Если не вдаваться в подробности с виртуальностью, то все остальные требования выглядят вполне логично: тривиальным класс является только в том случае, если с ним можно без опаски оперировать низкоуровневыми функциями, типа memcpy. Ведь наличия любого из вышеназванных методов класса может означать наличие ресурса(например указателя), которые нельзя просто скопировать в другой объект.

К счастью, нам нет нужды зубрить эти правила и даже если правила вызубрены, мы всегда можем подстраховаться и спросить компилятор: является ли наш класс тривиальным? Этой цели служит специальная метафункция: std::is_trivial<T>

Метафункция не является привычной C++ функцией. Это класс(или структура), которая на основании типа(или типов) выдаёт результат. Вызовом такой функции считается получение значения. Т.е. вызов вышеупомянутой функции будет выглядеть следующим образом: std::is_trivial<T>::value.

Примеры:

struct Trivial
{
    int a;
    int b;

    //Функции не запрещены
    int mul()
    {
        return a*b;
    }
};

struct TrivialDefault
{
    int a;
    int b;

    TrivialDefault() = default;
    ~TrivialDefault() = default;
    //Удалять методы нам никто не запрещал!
    TrivialDefault(const TrivialDefault&) = delete;
    TrivialDefault(TrivialDefault&&) = default;
    TrivialDefault& operator=(const TrivialDefault&) = default;
    TrivialDefault& operator=(TrivialDefault&&) = delete;

};

struct TrivialComposition
{
    Trivial a;
    TrivialDefault b;
};

struct TrivialDerived : public Trivial, public TrivialDefault
{
    //Статические члены не запрещены
    static int c;
};

struct TrivialDerivedPrivate : private TrivialDerived
{
    int d;
};


struct NonTrivialVirtual
{
    int a;
    int b;
    virtual void foo()
    {
    }
};

struct NonTrivialVirtualBase : public virtual Trivial
{
    int c;
};

struct NonTrivialComposition
{
    NonTrivialVirtaul a;
};

struct NonTrivialDtor
{
    ~NonTrivialDtor()
    {
    }
};

Как известно – “что не запрещено, то разрешено” и именно поэтому мы можем использовать функции и статические переменные, да и много чего еще, ведь это не запрещено правилами.

Будьте внимательны, на момент написания метафункция std::is_trivial полностью правильно работала только в clang!

Стандартное размещение

Класс обладает стандартным размещением, если следующие обязательства соблюдены:

1. Класс не содержит нестатических членов с нестандартным размещением
2. Класс не имеет виртуальных функций и виртуальных базовых классов
3. Все нестатические члены класса имеет один и тот же уровень доступа(private, public или protected)
4. Класс не имеет базовых классов с нестандартным размещением
5. Только один класс, во всей иерархии, содержит нестатические члены. Т.е. либо это один из базовых классов, либо сам класс.
6. Класс не может иметь первым нестатическим членом объект, который имеет тип одного из базовых классов.
7. Класс не может содержать ссылки в качестве нестатических членов.

На мой взгляд, некоторые части данного списка нуждаются в пояснении: например пункт 3, про уровень доступа: компилятор может использовать разный уровень доступа, для разного расположения приватных и публичных членов. Именно поэтому появилось такое правило, чтобы оставить некоторую свободу компилятору. Пункт 5, также, является следствием разночтения компиляторов в расположении базовых классов вкупе с самим классом. Разные компиляторы могут располагать данные в разном порядке и чтобы не сломать весь этот зоопарк правило было добавлено. Ниже вы увидите, как MSVC и clang размещают объекты по разному, когда и в базовом классе и в наследнике есть данные, и соблюдаются некоторые условия.

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

Пункт 7, в этом плане, несколько отличается – он не является следствием разночтения компиляторов. Суть его заключается в том, что если все остальные правила соблюдены и мы создаём объект базового класса в нашем классе, то это означает что базовый класс не содержит нестатических членов. Это, в свою очередь, означает, что над этим базовым классом выполняется одна из наиболее простых оптимизаций: базовый класс не будет занимает ни единого байта в потомке(empty base optimization). Это приводит нас к ситуации, когда адрес базового класса и адрес первого нестатического члена того же типа одинаковы, но они, по идее, должны является разными сущностями. С применением этой оптимизации мы совместили два объекта в один и, в сущности, нарушили прави��а описанные в пункте 5.10 стандарта C++.

Как и в случае с тривиальностью, C++ имеет метафункцию для определение является ли размещение структуры стандартным: std::is_standard_layout<T>

Примеры:

struct StandardEmpty
{
};

struct Standard
{
protected:
    int a;
    int b;
};

struct StandardDerived: public StandardEmpty, Standard
{
    static int c;
};

struct StandardDerivedMembers : public StandardEmpty
{
    int c;
    StandardEmpty empty;
};

struct NonStandard
{
    int& r;
};

struct NonStandardMember
{
    NonStandard nonStadard;
};

struct NonStandardFirstMember : public StandardEmpty
{
    StandardEmpty empty;
    int c;
};

struct NonStandardVirtual 
{
    virtual void foo()
    {
    }
};

struct NonStandardVirtualBase: public virtual Standard
{
};

struct NonStadardMembersInBoth: public Standard
{
    int d;
};

struct NonStadardDifferentAccess
{
    int a;
private:
    int b;
protected:
    int c;
};

Наследование

Мы рассмотрели простейшие случаи, которые, в целом, повторяют функционал структур из С, теперь пришло время обратиться к тому, что добавляет C++ в плане размещения объектов в памяти. Первое, что отличает C-структуры от классов в C++ это наличие методов в последнем. Но влияют ли как-то методы на размещение объектов в памяти? Конечно нет, ведь если бы каждый метод занимал место в каждом объекте, то нам бы никакой памяти не хватило. Т.к. метод не является изменяемым, то и нет никакого смысла хранить его в каждом объекте: экземпляр каждого метода хранится в одном экземпляре и место его хранения иррелевантно для нас. Может, правда, показаться, что метод класса столь же прост, как и обычная функция, но это не так. Например, указатель не свободную функцию всегда равен размеру “обычного” указателя согласно архитектуре, с указателем на метод всё гораздо сложнее и предсказать его размер, в общем случае, не представляется возможным – это зависит от реализации. Подробнее можно почитать тут.

Следующим различием является наличие наследования в C++. Давайте разберёмся, что это нам даёт: если класс А, наследует класс Б, то фактически это будет означать наличие объекта класса Б как под-объекта в классе А. Это очень грубое определение, и не совсем соответствует действительности и мы сейчас рассмотрим почему.

Во-первых, мы уже видели, что компилятор может оптимизировать базовый класс, который не содержит собственных членов так, что он не будет занимать ни единого байта в своём потомке. Для “во-вторых” нужно рассмотреть пример. Допустим у нас есть три класса Base, Derived и Composed, каждый из которых содержит определенный набор членов и Derived является наследником Base, а Composed содержит объект Base явно:

class Base
{
    int base;
    char otherB;
};

class Derived : public Base
{
    char derived;
    int otherD;
};

class Composed
{
    Base base;
    char composed;
    int otherC;
};

Т.к. MSVC2013 слегка “туповат” и даёт одинаковое размещение для Derived и Composed, поэтому sizeof(Derived) == sizeof(Composed) == 16. Для нас этот случай не интересен, поэтому мы рассмотрим то, как разместил наши объекты clang, который даёт sizeof(Derived) == 12 и sizeof(Composed) == 16:

Как можно видеть из рисунка, clang воспользовался тем, что Base оканчивается объектом типа char и Derived начинается со схожего объекта и расположил их таким образом, чтобы не вставлять заполнение, которое тут избыточно. С другой стороны, в случае с Composed, мы имеем явный объект конкретного типа, с которым “играть” нельзя и поэтому он вставляется “как есть”, со своим заполнением, которое препятствует размещению Composed::composed сразу за Base::otherB. Если кому-то кажется, что эта разница не существенна, то я бы предложил вам посчитать: одна кэш линия(64 байта), может вместить 5 объектов типа Derived и 4 объекта типа Composed. И это может сказаться на производительности приложения, если подобные объекты используются в критичном для производительности месте. Разница будет тем существеннее, чем больше мы попусту тратим память под заполнение.

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

Множественное наследование

Теперь рассмотрим то, как могут быть расположены объекты базовых классов при множественном наследовании:

class BaseA
{
    int fieldA;
};

class BaseB
{
    int fieldB;
};

class Derived : public BaseA, public BaseB
{
    int fieldD;
};

Типичное представление(оно не гарантировано стандартом!) объекта класса Derived представлено на следующем рисунке:

Как видно из рисунка базовые классы располагаются в объекте-наследнике последовательно, в том порядке, в котором они указаны в списке базовых классов. Теперь рассмотрим следующим код:

Derived* pDer = new Derived;
BaseA* pBaseA = pDer;
BaseB* pBaseB = pDer;

Визуализируем наши указатели:

Каждый указатель указывает на свою часть объекта; таким образом, чтобы получить доступ ко всем частям объекта мы должны иметь указатель на самый последний класс в иерархии(в нашем случае Derived). Указатели pBaseA и pBaseB ничего не знают об окружающих их данных, которые принадлежат безымянному объекту, на который указывает pDer. Следовательно, если мы сохраним объект, на который указывает pBaseA или pBaseB, то вся остальная информация скопирована не будет! Эта ситуация называется срез(slicing) и приводится в любом мало-мальски грамотном учебники по C++.  И если вы раньше не понимали, почему такая ситуация возникает и что в неё плохого – теперь должны понимать.

Ещё один интересный вывод, который можно сделать из картинки выше - почему в С++ разрешено неявное преобразование из дочернего класса в базовый, но не наоборот. Действительно, как можно неявно преобразовать BaseA* к Derived*, когда у нас нет никакой гарантии, что BaseA* указывает на под-объект Derived, а не на “чистый” объект BaseA.

Также, часто, в учебниках по C++ встречается так называемое ромбовидное наследование:

class UltimateBase
{
    int fieldU;
};

class BaseA : public UltimateBase
{
    int fieldA;
};

class BaseB : public UltimateBase
{
    int fieldB;
};

class Derived : public BaseA, public BaseB
{
    int fieldD;
};

Графически:

При ромбовидном наследовании, мы получаем два(их может быть гораздо больше, это простейший случай) одинаковых объекта в наследнике, что не позволяет нам идентифицировать к какому из них идёт обращение, если таковое требуется. Именно поэтому программист должен явно указывать, к какому из двух объектов он хочет обратиться путём указания пути(через BaseA или BaseB) к нужному объекту. Другим решением данной проблемы выступает введение виртуального базового класса, но об этом мы поговорим в следующей статье.