выравнивание структур

[Алексей++]

В каком случае выравнивание структуры X по 1 байту может сказаться на скорости работы программы ?

[Basurman]

Это скорее Assembler, чем Windows - методы адресации памяти процессором (байт, слово ...).
Скорость выборки данных из памяти повышается при совпадении начала переменной с началом ячейки памяти (32 разряда - двойное слово, 64 - учетверённое слово).

[Алексей++]

Но просто если выровнять по 4, то не факт, что начало массива структур начнётся с адреса, кратного 4. Или он всё равно так разместиться?

[Basurman]

Если переменная (экземпляр массива структур) динамическая - в любом случае случае начнётся с адреса кратного 4 (для 32 разрядов), выделение памяти.
Если выравнивать на 4, переменные должны начинаться с адресов кратных 4 (теряется память, оттого программы теперь такие большие - но увеличиватся скорость).
А вообще, что зря дискутировать.
Проще скомпилировать простенькую программку, с включённой опцией полного листинга и посмотреть в нём размещение переменных.

[Алексей++]

Ок, запробую )
А размер программ, кстати, тут ни при чём - переменные же не в модуле расположены (только константы там). А вот озу жрут некоторые поделки - это даа.. Вот как раз за озу и борюсь
Сравню ещё, как выравнивание на скорость повлияет

[Basurman]

А инициализированные переменные (с изначально заданным значением, не обнулённые)?

[Алексей++]

А инициализированные переменные (с изначально заданным значением, не обнулённые)?

вопрос не понятен

[RXL]

Чтение невыровненных данных может потребовать больше времени на выборку данных.

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

Байтовое выравнивание внутри структуры при следующих случаях:
1. структура используется для считывания бинарных структур с диска - т.е., выравнивание нужно для точного позиционирования членов структуры;
2. при обработке используются все или почти все члены компактной структуры и потерь на невыровненные данные не будет;
3. структура настолько мала, что умещается в одной-двух строках кеша;
4. экономия памяти (в ущерб производительности).

Байтовое выравнивание структур относительно друг друга:
1. структуры располагаются в памяти последовательно друг за другом и в том же порядке обрабатываются;
2. экономия памяти.

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

Неинициализированные данные - тоже данные. Требования те же.

[lapulya]

Еще есть пара случаев, но они экзотические, например, передача структуры (при помещении ее в 32 бита) в чужие среды, имеется ввиду, например, функция в делфи и т.д.

[x77]

В каком случае выравнивание структуры X по 1 байту может сказаться на скорости работы программы ?

только в том случае, если программа часто выделяет память относительно малыми блоками. только не по 1 байту, а по границе блока, которым выделяет память менеджер памяти компилятора (который может не иметь ничего общего с менеджером памяти самой ОС).

[Антон (LogRus)]

x77, принято считать, что чтение/записи не выровненных данных дороже чем выравненных

[sss]

Блин, не приводит выравнивание к тормозам.... Операции типа mov r/m, r/m/i имеют одинаковое значение тактов выполнения вне зависимости от значения m... Толи дело, когда вызов сервиса ТРЕБУЕТ выравнивания. Но в этом случае тормозов не будет - будет просто отказ операции. Вот одно из мест, где я столкнулся с таким отказом -

Код:

::GetQueuedCompletionStatus( m_hIoPort, &dwNumBytes, &ulKey, (OVERLAPPED**) &pOverlapped, INFINITE);

Оказалось - система требует выравнивания pOverlapped на 4 байта...

Кстати - у компилятора нет менеджера памяти. Менеджер памяти в Windows всегда выделяет памяти не меньше 8 байт...

[Алексей++]

sss, вот я потому вопрос и задал - миф или реальность ? Я так понимаю, ноги растут из состава команды mov - множитель 4 есть , а +1, +2 и +3 - дополнительные опции. Если такты одинаковые, то на выравнивание надо смотреть лишь с точки зрения совместимости структур из разных программных модулей или реальных устройств

[Антон (LogRus)]

sss, я сказал следующее...

принято считать, что чтение/записи не выровненных данных дороже чем выравненных

[sss]

Алексей1153++, я думаю в словах о тормозах из-за выравнивания есть истина. Но она на уровне алгоритмов работы....

LogRus - сейчас вижу.  Твой пост появился сразу до моего. Браузер предупреждал - я не стал смотреть  .

[darkelf]

sss, вот я потому вопрос и задал - миф или реальность ?

Реальность, т.к. количество тактов будет разное, и может не работать на некоторых платформах (типа ARM/SPARC).
Связано это с тем, что на самом деле на шину адреса подаётся адрес слова (я говорю о ситуации для 386 процессора, когда в основном и начались эти игры с выравниванием), так вот, для невыраненного значение процессору по шине надо будет выдать два запроса чтения вместо одного, для одной половинки слова, и взять оттуда часть, и для другой половиники, тоже всять оттуда нужную часть, а затем соединить и отправить в регистр или куда эта ячейка запрашивалась. В своё время у нас была такая ситуация, что для невыравненных структур происходило падение производительности в 1.5 раза, на встраиваемом процессоре 586@133MHz, для более новых процессоров ситуация так-же имеет место быть, но там ещё свою роль начинает играть кэш - тут про это кто-то уже говорил.

[x77]

x77, принято считать, что чтение/записи не выровненных данных дороже чем выравненных

дык я не спорю. я просто говорю, что словить "тормоза" на невыровненных данных - надо постараться. в общем случае этого просто не видно. и заметить эти тормоза (вплоть до того, что какой-то процесс начнёт визуально тормозить) можно только тогда, когда этот процесс очень часто выделяет память из кучи, т.к. выделение памяти - сама по себе одна из наиболее дорогостоящих операций.

например, у вас саксовский парсер, который пробегает 200-мегабайтовый xml и по селектору вычитывает в буфер некие данные. вот в этом случае выравнивание по границе блока, которыми менеджер памяти будет клянчить heap у ОСи - критично. а в большинстве случаев - да вы просто не увидите никакой разницы.

чтобы говорить предметно, надо запытать Лёшу, чего и нафига он собрался выравнивать

[Алексей++]

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

[x77]

Алексей1153++, тебе лениво написать два убогих теста? я ставлю полбанки на то, что имеет.

[Антон (LogRus)]

Раз пошла такая пьянка, вот мои 5 копеек.
давайте дружно представим:
1. объект попавший на границу кэш линии
2. многоядерный проц
3. многопоточноное ПО

1. обновление 2 кэш линий (с вытеснением 2-х других)
2 и 3. потенциальное пинальти для синхронизации 2-х кэш линий в двух и более ядрах

НО, всё это редкость

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

имеет смысл давать компилятору делать дело, а не пытаться экономить на спичках

[Алексей++]

тест обязательно будет, только вся эта тряхомундия дома лежит, на работу не брал. Поэтому пока только в теории ) Вечером, вечером

[x77]

LogRus, многопоточное ПО идеально работающее на одном проце, само по себе может начать жётско тормозить на двух и более процах. это не лучшие условия для "чистого" теста.

[x77]

Кстати - у компилятора нет менеджера памяти. Менеджер памяти в Windows всегда выделяет памяти не меньше 8 байт...

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

[RXL]

LogRus, еще добавим к п1. отсутствие данных в кеше - чтение двух блоков в две кеш-строки. Чтение из памяти занимает очень много времени, а два чтения - вдвое больше.

Команда, выполняющаяся по даташиту за 1 такт, будет выполняться за один такт только в "тепличных" условиях, когда данные в кеше L1 и выровнены согласно требованиям CPU:

Данные - Выравнивание
1 - 1
2 - 2
4 - 4
8 - 8
>8 - 16

Во всех остальных случаях идет пенальти: невыровненные данные в L1, промах L1 и попадание в L2 при чтении, невыровненное чтение L2, промах L2 и чтение из памяти (в зависимости частоты CPU, от шины, памяти и их нагруженности может измеряться десятками тактов).
По этому оптимизация дает существенный прирост производительности. Существенный прирост (в N раз) можно получить только на небольших объемах данных, которые поместятся в L1 или L2. В остальных случаях прирост будет примерно от ничтожного до 2-х кратного.

Выравнивание по ширине кеш-строки данных меньшего размера дает преимущество в том, что данные становятся доступны сразу после их поступления в кеш, но до полного считывания строки из памяти. По этому для отдельных мелких объектов правильнее выравнивание на 16, а для массива мелких объектов - на 4 (чтобы не было пенальти на невыровненный кеш).

Как не развивались процессоры за последние 15 лет, основные принципы оптимизации остаются те же.

[Антон (LogRus)]

возможно уже рекомендовал, но по рекомендую еще раз
"Хамелеоны быстрые и очень быстрые", автор известный дядька http://www.rsdn.ru/forum/cpp/3539197.flat.aspx#3539197

[sss]

Связано это с тем, что на самом деле на шину адреса подаётся адрес слова

Интересно, а как это будет выглядеть для 1 байта ? Два запроса чтения для 1 байта? Я в принципе понял о чем ты говоришь, - но мне постоянно кажется, что вы путаете выравнивание с попаданием чтения через границу страницы... И причем - что про кэш, что про чтение из памяти нескольких байт, располагающихся в разных страницах. При этом не важно - выравненные или не выравненные данные проходят границу страницы... Тоже дело при чтении секторов с диска...

[RXL]

sss, мы не путаем выравнивание ни с чем другим: если уж десять раз сказали "выравнивание", то это именно выравнивание, а не подравнивание и не уравнивание.
Не гадай - почитай первоисточники.

Границы страниц - еще один тормозящий фактор. Но речь не о страницах (не будем же мы выравнивать членов объекта по 4 кБ...).

[darkelf]

Связано это с тем, что на самом деле на шину адреса подаётся адрес слова

Интересно, а как это будет выглядеть для 1 байта ? Два запроса чтения для 1 байта? Я в принципе понял о чем ты говоришь, - но мне постоянно кажется, что вы путаете выравнивание с попаданием чтения через границу страницы... И причем - что про кэш, что про чтение из памяти нескольких байт, располагающихся в разных страницах. При этом не важно - выравненные или не выравненные данные проходят границу страницы... Тоже дело при чтении секторов с диска...

Для 386-го при считывании байта будет прочитано двойное слов (32-бита), и из этих прочитанных 32-х бит будут взяты соответствующие 8-мь. Именно по этому выравнивания для байта делать не надо - больше одного чтения памяти никак не получится, а вот уже для 16-ти битного слова - вполне надо, т.к. там его байты могут попасть в разные адресуемые двойные слова, например, у слова по адресу 3, на самом деле, один байт будет храниться в двойном слове по адресу 0, а второй - в двойном слове по адресу 4, соответственно надо будет выполнять два чтения, и выделить из этих двух двойных слов необходимые байты и скомпоновать их в слово, которое потом уже заслать в регистр или куда ещё.

[sss]

Понятно - выставить на шине адреса можно только биты A[31:3](A[35:3]). Поэтому используется адрес, кратный 8... И выделяется менеджером памяти так поэтому наверное.. 

[darkelf]

Да, начиная с Pentium шина данных 64-х битная, соответствено и шина адреса адресует уже не двойные слова, а четверные.