Перед вами две структуры:
struct Test1 {
double double_1 = 0;
long long_1 = 0;
long long_2 = 0;
int int_1 = 0;
int int_2 = 0;
short short_1 = 0;
short short_2 = 0;
char char_1 = 0;
char char_2 = 0;
};
struct Test2 {
long long_1 = 0;
int int_1 = 0;
int int_2 = 0;
short short_1 = 0;
short short_2 = 0;
double double_1 = 0;
char char_1 = 0;
long long_2 = 0;
char char_2 = 0;
};
с одинаковыми свойствами, но размер этих двух структур отличается.
Размер Test1: 56 байт, Test2: 72 байта. Разница в 16 байт, хотя, по идее они должны иметь одинаковый размер. Почему так?
Дело в том что, компилятор выравнивает свойства структуры в соответствии с требованием к выравниванию типа на целевой платформе,
и т.к. ему запрещено менять порядок полей в структуре (в отличии, например, от локальных переменных), образуются пустоты.
У компилятора gcc, например, есть ключик Wpadded, который предписывает компилятору вывести предупредительное сообщение в случае добавления в структуру пустых полей-отступов.
Можно просто расположить свойства в структуре отсортировав в порядке убывания их размера.
Как это сделано в первой структуре, и тогда пустот будет меньше, свободной памяти больше!
Данные расположены ближе друг к другу.
Обычно так и делают... . Когда идей получше нет!
Можно, например, оптимизировать код алгоритма под конкретную архитектуру или процессор.
struct S {
char ch1, ch2;
};
Обе переменные могут быть размещены в одном и том же кеш-банке памяти, что в некоторых случаях, сделает невозможным их синхронную обработку.
Иногда по некоторым причинам может потребоваться специальный порядок следования полей структуры, например, специальное выравнивание переменных для оптимизации попадания в
кеш процессора.
Типовые алгоритмы обработки данных задействуют быстродействие ОЗУ едва ли на треть, а зачастую и менее того.
Удивительно, но большинство программистов даже не подозревают об этой проблеме.
На аппаратном уровне обмен данными между процессором и оперативной памятью, осуществляется не побайтово, а пакетами данных, размером, обычно, в кеш линию процессора.
По той же самой причине по которой вы ходите в магазин, закупившись по максимуму, когда он расположен далеко.
Т.е. выполняя команду чтения одного байта, процессор считает из ОЗУ пакет данных содержащий этот байт и положит их в свой кеш.
У процесссора уходит в сотни раз меньше времени на чтение данных из своего кеша, чем с оперативной памяти, так как физически кеш расположен внутри ядра процессора.
По этим причинам он стремится заранее заполнить свой кеш данными из оперативной памяти, применяя различные стратегии по оптимизации, большинство из которых общеизвестны.
Например, одна из них гласит:
Данные, которые недавно были нужны, с большой долей вероятности понадобятся вновь и поэтому они будут в кеше процессора.
Так же, процессор старается удерживать в кеше данные которые расположены рядом с теми данными, которые были не давно запрошены.
Так же, дополнительно, применяются различные стратегии по оптимизация, которые постоянно совершенствуются.
A Некоторые процессоры, вообще, наделены искуственным интелектом, который анализирует программу и кэширует данные с умом.
Это не сложно проверить!
Например.
#include <iostream>
#include <vector>
#include <sys/time.h>
#include <numeric>
#include <algorithm>
#include <random>
#include <chrono>
static auto gen_int()
{
static std::size_t idx = 0;
static int data[] = {1, 2, 3, 4, 5};
if (idx >= sizeof(data))
idx = 0;
return data[idx++];
}
int main()
{
const std::size_t buffer_size = 1024l*1024*1024*3; // 3GB
char* const buffer = (char*) std::malloc(buffer_size);
for (std::size_t i=0; i<buffer_size; i += 1024)
buffer[i] = gen_int();
std::vector<int> random_list, sequence_list;
sequence_list.resize(buffer_size);
std::iota(std::begin(sequence_list), std::end(sequence_list), 0);
random_list = sequence_list;
std::shuffle(std::begin(random_list), std::end(random_list),
std::default_random_engine(std::chrono::system_clock::now().time_since_epoch().count()));
const auto lambda = [buffer](const auto& v)
{
std::size_t result = 0;
timeval start_tm, end_tm, res_tm;
gettimeofday(&start_tm, 0);
for (auto l : v)
result += buffer[l];
gettimeofday(&end_tm, 0);
timersub(&end_tm, &start_tm, &res_tm);
long double res = res_tm.tv_sec;
res += res_tm.tv_usec/1000000.;
return std::pair{result, res};
};
{
auto [result2, res2] = lambda(sequence_list);
std::cout << "sequence_list: " << std::endl;
std::cout << "result: " << result2 << std::endl;
std::cout << "took time: " << res2 << std::endl;
}
std::cout << std::endl;
{
auto [result1, res1] = lambda(random_list);
std::cout << "random_list: " << std::endl;
std::cout << "result: " << result1 << std::endl;
std::cout << "took time: " << res1 << std::endl;
}
return 0;
}
Напишем программу которая вычисляет сумму элементов массива, двумя разными способами.
Первый, последовательно.
Второй, в случайном порядке.
Кол-во итераций одинаково.
Время выполнения алгоритма при случайном обращении к элементам массива, медленнее, больше чем в 10 раз.
Не плохая такая оптимизация работы процессора, за счет грамотной работы с его кеш памятью.
Как показывает данный код, одним только асимптотическим анализом, эффективность алгоритма не всегда можно оценить.
Почему так произошло, должно быть уже ясно.
Современный процессор наиболее эффективно выполняет чтение и запись в память, когда данные естественным образом выровнены,
что обычно означает, что адрес данных в памяти кратен размеру этого типа.
Выравненные естественным образом целочисленные данные гарантированно не пересекают границ кеш-линий и соответсвенно доступ к ним занимает меньше времени,
т.к. нет обращения к нескольким кеш линиям.
Как уже отмечалось, компилятор позаботился о выравнивании уже за вас.
- Выравнивание массива выполняется так же, как и выравнивание типа данных его первого элемента
(все остальные элементы будут корректно выровнены автоматически).
- Выравнивание объединения (union) соответствует выравниванию самого большого по размеру типа данных из тех,
которые включены в объединение.
Функция std::malloc().
Стандарты языков C и C++ гарантируют, что адрес возвращаемый функцией выровнен.
В большинстве систем, возвращаемый указатель выровнен на размер указателя умноженный на два.
На архитектуре amd64, это 16 байт.
Следует отметить тот факт, что физические страницы памяти на которые будут отображаться виртуальные, почти всегда не будут смежными.
Это связанно с тем что, в целях снижения фрагментации физических страниц памяти, алгоритм распределения памяти будет стремиться использовать уже фрагментированные страницы.
И, следует с осторожностью размещать данные на таких участках памяти. Т.к. обращение за данными, размещенных на разных, не смежных, страницах памяти,
потребует больше времени из-за трансляции виртуального адреса в физический. На разных системах, размер страниц разный, но он обычно кратен числу в степени двойки.
На счёт замедления трансляции адресов могу ошибаться, не помню. Напиши в комментария как оно есть на самом деле.
Функция std::calloc().
Вот так выглядит реализация этой функции.
Комментировать вообщем то особо и нечего. Функция наследует все свойства std::malloc.
Оператор new.
Стандарт так же гарантирует, что адрес возвращаемый функцией, выровнен.
Внутри оператора new происходит вызов всё той же функции std::malloc.
И соответственно оператор наследует все её свойства.
Начиная с 17 стандарта в плюсах появился оператор new который умеет выравнивать.
Вызывается так:
new (std::align_val_t(16)) char[1024];
число на которое нужно выровнять, должно быть кратным числам в степени двойки
т.е. 1, 2, 4, 8, 16 и т.д.
alignof
[слайд с стандартом]
В стандарте про этот оператор сказано совсем не много.
Из этого следует, что это Implementation-defined, т.е. поведение зависит от целевой платформы, по большей части.
static_assert(sizeof(char) == alignof(char), "sizeof != alignof");
static_assert(sizeof(bool) == alignof(bool), "sizeof != alignof");
static_assert(sizeof(short) == alignof(short), "sizeof != alignof");
static_assert(sizeof(int) == alignof(int), "sizeof != alignof");
static_assert(sizeof(wchar_t) == alignof(wchar_t), "sizeof != alignof");
static_assert(sizeof(long) == alignof(long), "sizeof != alignof");
static_assert(sizeof(long long) == alignof(long long), "sizeof != alignof");
static_assert(sizeof(float) == alignof(float), "sizeof != alignof");
static_assert(sizeof(double) == alignof(double), "sizeof != alignof");
static_assert(sizeof(long double) == alignof(long double), "sizeof != alignof");
static_assert(sizeof(char8_t) == alignof(char8_t), "sizeof != alignof");
static_assert(sizeof(char16_t) == alignof(char16_t), "sizeof != alignof");
static_assert(sizeof(char32_t) == alignof(char32_t), "sizeof != alignof");
По умолчанию, для встроенных типов, выравнивание равно размеру самого типа. т.е. (значение возвращаемое оператором alignof равно значению возвращаемым sizeof)
Для остальных, наибольшим требованием к выравниванию. За исключением структур объявленных со спецификатором alignas.
Всё сказанное актуально для архитектуры amd64.
Выравниванием можно управлять с помощью спецификатора alignas.
template<class T>
struct S5 {
alignas(alignof(T)) T v1; // 1
alignas(T) T v2; // 2, equal expression above
T v3;
};
S5<double> s5;
Вот еще две формы применения спецификатора:
// 1
template<const std::size_t N, class ...T>
struct S3 {
alignas(T...) double var3; // == alignas(T) alignas(U) T buffer[N];
};
S3<10, double, float> s3;
// 2
template<const std::size_t N, class T, class U>
struct S1 {
alignas(T) alignas(U) T buffer[N];
};
S1<10, double, float> s1;
Обе формы дают эквивалентный эффект.
первая, принимает пак параметров.
во втором случае, в выражении используется несколько спецификаторов выравнивания.
Чтобы гарантировать, что запрашиваемое выравнивание U не слабее,
чем собственное выравнивание у некоторого объекта типа T,
стандарт языка, требует, добавить к запрашиваемому выравниванию
ещё и выравнивание для самого типа T.
Еще вот такая форма применения спецификатора предусмотренна:
struct alignas(32) S {};
Которая задаёт выравнивание для структуры в целом.
Интересно то, что размещающий оператор new, проигнорирует подобное требование к выравниванию, как будто его и не было.
Функция std::align.
пример использования:
// функция возвращает выровненный адрес в соответствии с требованием к выравниванию на
// целевой платформе либо nullptr если памяти не хватает.
template<typename T> inline
auto m_align(void* ptr, std::size_t buf_size)
{
return std::align(alignof(T), sizeof(T), ptr, buf_size);
}
struct alignas(128) ST9 { char с; };
int main()
{
const auto mem_size = 1024;
auto ptr = new char [mem_size];
std::cout << (long) ptr << std::endl;
std::cout << (long) m_align<ST9>(ptr, mem_size) << std::endl;
return 0;
}