Выравнивание битов для увеличения пространства и производительности

Question

В книге Game Coding Complete, 3-е издание, автор упоминает методику уменьшения размера структуры данных и для повышения производительности доступа. По сути, это зависит от того факта, что вы получаете производительность, когда переменные-члены выровнены по памяти. Это очевидная потенциальная оптимизация, которой могли бы воспользоваться компиляторы, но, убедившись, что каждая переменная выровнена, они в конечном итоге вздувают размер структуры данных.

Или, по крайней мере, это было его требование.

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

#pragma pack( push, 1 )

struct SlowStruct
{
    char c;
    __int64 a;
    int b;
    char d;
};

struct FastStruct
{
    __int64 a;
    int b;
    char c;
    char d;  
    char unused[ 2 ]; // fill to 8-byte boundary for array use
};

#pragma pack( pop )

Используя вышеупомянутые struct объекты в неопределенном тесте, он сообщает об увеличении производительности на 15.6% (222ms по сравнению с 192ms) и меньшем размере для FastStruct. Все это имеет смысл на бумаге для меня, но не выдерживает моего тестирования:

Результаты того же времени и (считая для char unused[ 2 ])!

Теперь, если #pragma pack( push, 1 ) выделен только на FastStruct (или полностью удален), мы видим разницу:

Итак, наконец, здесь лежит вопрос: оптимизируют ли современные компиляторы (в частности, VS2010) для выравнивания битов, отсюда и отсутствие повышения производительности (но увеличение размера структуры как побочный эффект, как заявил Майк Макшаффри)? Или мой тест недостаточно интенсивен / не дает результатов, чтобы дать какие-либо существенные результаты?

Для тестов я выполнил множество задач от математических операций, обхода / проверки многомерного массива по главному столбцу, матричных операций и т. Д. Для элемента без выравнивания __int64. Ни одна из них не дала разных результатов ни для одной из структур.

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

Answer 1

Это сильно зависит от аппаратного обеспечения.

Позвольте мне продемонстрировать:

#pragma pack( push, 1 )

struct SlowStruct
{
    char c;
    __int64 a;
    int b;
    char d;
};

struct FastStruct
{
    __int64 a;
    int b;
    char c;
    char d;  
    char unused[ 2 ]; // fill to 8-byte boundary for array use
};

#pragma pack( pop )

int main (void){

    int x = 1000;
    int iterations = 10000000;

    SlowStruct *slow = new SlowStruct[x];
    FastStruct *fast = new FastStruct[x];



    //  Warm the cache.
    memset(slow,0,x * sizeof(SlowStruct));
    clock_t time0 = clock();
    for (int c = 0; c < iterations; c++){
        for (int i = 0; i < x; i++){
            slow[i].a += c;
        }
    }
    clock_t time1 = clock();
    cout << "slow = " << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;

    //  Warm the cache.
    memset(fast,0,x * sizeof(FastStruct));
    time1 = clock();
    for (int c = 0; c < iterations; c++){
        for (int i = 0; i < x; i++){
            fast[i].a += c;
        }
    }
    clock_t time2 = clock();
    cout << "fast = " << (double)(time2 - time1) / CLOCKS_PER_SEC << endl;



    //  Print to avoid Dead Code Elimination
    __int64 sum = 0;
    for (int c = 0; c < x; c++){
        sum += slow[c].a;
        sum += fast[c].a;
    }
    cout << "sum = " << sum << endl;


    return 0;
}

---

Core i7 920 @ 3,5 ГГц

slow = 4.578
fast = 4.434
sum = 99999990000000000

Ладно, особой разницы нет.Но он все еще остается неизменным на нескольких запусках.
Таким образом, выравнивание имеет небольшое значение для Nehalem Core i7.

---

Intel Xeon X5482 Harpertown @ 3,2 ГГц (Core 2 - поколение Xeon)

slow = 22.803
fast = 3.669
sum = 99999990000000000

Теперь взгляните ...

в 6,2 раза быстрее !!!

---

Вывод:

Вы видите результаты.Вы сами решаете, стоит ли вам проводить эти оптимизации.

---

РЕДАКТИРОВАТЬ:

Те же тесты, но без #pragma pack:

Core i7 920 @ 3,5 ГГц

slow = 4.49
fast = 4.442
sum = 99999990000000000

Intel Xeon X5482 Harpertown @ 3,2 ГГц

slow = 3.684
fast = 3.717
sum = 99999990000000000

• Номера Core i7 не изменились.Очевидно, он может справиться с перекосами без проблем для этого теста.
• Core 2 Xeon теперь показывает одинаковое время для обеих версий.Это подтверждает, что смещение является проблемой в архитектуре Core 2.

Взято из моего комментария:

Если вы пропустите #pragma pack, компилятор сохранит все выравнивание, поэтому вы не увидите эту проблему.Так что это на самом деле пример того, что может произойти, если вы неправильно используете #pragma pack.

Answer 2

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

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

Вот в чем дело: могут быть псевдонимы и другие неприятности с доступом к подслову, и доступ к целому слову не медленнее, чем к подслову. Так что, в общем, со временем упаковывать более плотно, чем размер слова, не эффективнее, если у вас есть доступ, скажем, к одному члену.

Answer 3

Visual Studio - отличный компилятор, когда дело доходит до оптимизации. Однако имейте в виду, что нынешняя «Война оптимизации» в разработке игр не на арене ПК. Хотя такая оптимизация вполне может быть мертвой на ПК, на консольных платформах это совершенно другая пара обуви.

Тем не менее, вы можете захотеть опубликовать этот вопрос на специализированном стеке обмена играми gamedev , вы можете получить некоторые ответы прямо с «поля».

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

Answer 4

Современные компиляторы выравнивают элементы по разным границам байтов в зависимости от размера элемента. Смотрите в нижней части это .

Обычно вам действительно не нужно заботиться о заполнении структуры, но если у вас есть объект, который будет иметь 1000000 экземпляров или что-то в этом духе, эмпирическое правило просто упорядочивает членов от самых больших до самых маленьких. Я бы не рекомендовал возиться с заполнением директивами #pragma.

Answer 5

Стандарт C определяет, что поля в структуре должны быть расположены по возрастающим адресам. Структура, которая имеет восемь переменных типа int8 и семь переменных типа int64, хранящихся в этом порядке, займет 64 байта (в значительной степени независимо от требований выравнивания машины). Если бы поля были упорядочены «int8», «int64», «int8», ... «int64», «int8», структура заняла бы 120 байт на платформе, где поля «int64» выровнены по 8-байтовым границам. Изменение порядка полей позволит вам упаковать их более плотно. Однако компиляторы не будут переупорядочивать поля в структуре без явного разрешения на это, так как это может изменить семантику программы.

Answer 6

На некоторых платформах у компилятора нет опции: объекты типов больше, чем char часто предъявляют строгие требования к расположению по соответствующим образом выровненным адресам. Как правило, требования выравнивания идентичны размеру объекта до размера самого большого слова, поддерживаемого процессором изначально. То есть short обычно требуется по четному адресу, long обычно требуется по адресу, кратному 4, double по адресу, кратному 8, и, например, SIMD векторы по адресу, кратному 16.

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

Поскольку я увидел утверждение, что это не имеет значения: это имеет значение в большинстве (если не во всех) системах, которые я использую. Есть простые примеры показа разных размеров. Насколько это влияет на производительность, очевидно, зависит от того, как будут использоваться структуры.

#include <iostream>

struct A
{
    char a;
    double b;
    char c;
    double d;
};

struct B
{
    double b;
    double d;
    char a;
    char c;
};

int main()
{
    std::cout << "sizeof(A) = " << sizeof(A) << "\n";
    std::cout << "sizeof(B) = " << sizeof(B) << "\n";
}

./alignment.tsk 
sizeof(A) = 32
sizeof(B) = 24

Answer 7

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

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

Имея кэши, и, как и в случае современных компьютерных платформ, полагающихся на кэши для получения любой производительности, вы хотите быть выровненными и упакованными. Простое обучаемое правило дает вам обоим ... в общем. Это очень хороший совет. Добавление специфических прагм для компилятора не так хорошо, делает код непереносимым и не требует большого количества поиска по SO или поиску в Google, чтобы выяснить, как часто компилятор игнорирует прагму или не выполняет то, что вы действительно хотели.