Отсутствие кэша и удобство использования в Entity Systems

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

Однако он поднял некоторые вопросы об общем поведении C ++, о языке, на котором я реализую систему управления сущностями, а также о некоторых проблемах с удобством использования.

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

Но когда мне нужно перебрать массивы компонентов, чтобы сделать что-то с ними из системы в реальной реализации игрового процесса, я замечаю, что почти всегда работаю с двумя или более типами компонентов одновременно. Например, система рендеринга использует компонент Transform и Model вместе для фактического вызова рендеринга. Мой вопрос заключается в том, что, поскольку в этих случаях я не выполняю линейную итерацию по одному непрерывному массиву за раз, немедленно ли я жертвую выигрышем в производительности от такого распределения компонентов? Это проблема, когда я итерирую в C ++ два разных смежных массива и использую данные обоих в каждом цикле?

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

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

• Каждая сущность содержит вектор дескрипторов родового компонента, который может представлять любой тип.
• Каждый дескриптор компонента может быть разыменован для получения необработанного указателя T *. *См. ниже.
• Каждый тип компонента имеет свой пул, непрерывный блок памяти (фиксированный размер в моем случае).

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

Тем не менее, есть случаи (как я обнаружил), где действительно вы можете буквально написать цикл for для определенного типа компонента и эффективно использовать строки кэша вашего процессора. Для тех, кто не знает или хочет узнать больше, загляните на https://en.wikipedia.org/wiki/Locality_of_reference . На той же ноте, когда это возможно, старайтесь, чтобы размер вашего компонента был меньше или равен размеру строки вашего кэша ЦП. Мой размер строки составлял 64 байта, что, я считаю, является обычным явлением.

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

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

Я тоже решил эту проблему лично. В итоге у меня была система, в которой:

• Каждый дескриптор компонента содержит ссылку на индекс пула
• Когда компонент «удален» или «удален» из пула, последний компонент в этом пуле перемещается (буквально с помощью std :: move) в свободное место, или ни одного, если вы только что удалили последний компонент.
• Когда происходит «своп», у меня есть обратный вызов, который уведомляет любых слушателей, чтобы они могли обновить любые конкретные указатели (например, T *).

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

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

Это помогает? Я постараюсь прояснить все, что неясно. Также приветствуются любые исправления.

Чтобы ответить только на это:

Мой вопрос заключается в том, что, поскольку в этих случаях я не выполняю линейную итерацию по одному непрерывному массиву за раз, немедленно ли я жертвую выигрышем в производительности от такого распределения компонентов? Это проблема, когда я итерирую в C ++ два разных смежных массива и использую данные обоих в каждом цикле?

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

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

Начиная с простой векторной структуры:

struct float3 { float x, y, z; };

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

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

Сроки (10 000 000 элементов)

линейный доступ

• отдельные массивы
• чередующийся источник
• чередующийся источник и результат 0,48 с

произвольный доступ (раскомментируйте random_shuffle)

• отдельные массивы 2.42 с
• чередующийся источник 4.43s
• чередующийся источник и результат 4.00s

Исходный код (скомпилировано с Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}

Краткий ответ: профиль затем оптимизировать.

Длинный ответ:

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

Это проблема, когда я итерирую в C ++ два разных смежных массива и использую данные обоих в каждом цикле?

C ++ не несет ответственности за ошибки в кэше, так как он применим для любого языка программирования. Это связано с тем, как работает современная архитектура процессора.

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

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

Agner's Fog рекомендует не оптимизировать, прежде чем профилировать приложение и / или точно знать, где находятся узкие места. (Все это упоминается в его превосходном руководстве. Ссылка ниже)

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

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

Обязательно посмотрите его превосходное руководство по оптимизации C ++ .

Еще одна вещь, о которой я хотел спросить, - как хранить ссылки на компоненты или объекты, поскольку сама природа компонентов лежит в памяти.

Лично я выделю наиболее используемые компоненты вместе в одном блоке памяти, чтобы у них были «близкие» адреса. Например, массив будет выглядеть так:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] а затем начните оптимизацию оттуда, если производительность не была «достаточно хорошей».

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

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

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

// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
    // 1 byte
    char a;

    // 1 byte
    char b;
};

struct Bar
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Допустим, мы хотим чередовать Fooи Barхранить их прямо рядом друг с другом в памяти:

// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'

    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Теперь вместо 18 байтов для хранения Foo и Bar в отдельных областях памяти требуется 24 байта для их объединения. Неважно, если вы поменяете порядок:

// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;

    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'
};

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

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

Где стрелки просто указывают, что объект «владеет» компонентом. Мы можем видеть, что, если бы мы попытались получить доступ ко всем компонентам движения и рендеринга сущностей, которые имеют и то и другое, мы в конечном итоге перепрыгнули через место в памяти. Такой тип спорадического шаблона доступа может привести к загрузке данных в строку кэша для доступа, скажем, к компоненту движения, а затем к большему количеству компонентов и удалению прежних данных, только чтобы снова загрузить ту же область памяти, которая уже была удалена для другого движения компонент. Так что это может быть очень расточительным, загружая одни и те же области памяти более одного раза в строку кэша, чтобы просто просмотреть и просмотреть список компонентов.

Давайте немного исправим этот беспорядок, чтобы лучше видеть:

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

Очень простой способ улучшить эту ситуацию - это просто отсортировать компоненты по идентификатору / индексу объекта, которому они принадлежат. В этот момент вы получите что-то вроде этого:

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

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

И это не требует какого-то чрезвычайно сложного дизайна, просто время прохода радикальной сортировки по линейному времени, может быть, после того, как вы вставили и удалили группу компонентов для определенного типа компонента, после чего вы можете пометить его как нужно быть отсортированным. Разумно реализованная радикальная сортировка (вы даже можете распараллелить ее, что я и делаю) может отсортировать миллион элементов за 6 мс на моем четырехъядерном i7, как показано здесь:

Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

Выше указано, что нужно отсортировать миллион элементов 32 раза (включая время до memcpyрезультатов до и после сортировки). И я предполагаю, что большую часть времени у вас фактически не будет более миллиона компонентов для сортировки, поэтому вы очень легко сможете уловить это время от времени, не вызывая заметного заикания частоты кадров.