Какой из них наиболее удобен для кэша?

Question

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

А) Пример вектора объектов

struct A
{
    GLsizei mIndices;
    GLuint mVBO;
    GLuint mIndexBuffer;
    GLuint mVAO;

    size_t vertexDataSize;
    size_t normalDataSize;
};

std::vector<A> gMeshes;

for_each(gMeshes as mesh)
{
    glBindVertexArray(mesh.mVAO);
    glDrawElements(GL_TRIANGLES, mesh.mIndices, GL_UNSIGNED_INT, 0);
    glBindVertexArray(0);

    ....
}

Б) Векторы с атомными данными

std::vector<GLsizei> gIndices;
std::vector<GLuint> gVBOs;
std::vector<GLuint> gIndexBuffers;
std::vector<GLuint> gVAOs;
std::vector<size_t> gVertexDataSizes;
std::vector<size_t> gNormalDataSizes;

size_t numMeshes = ...;

for (index = 0; index++; index < numMeshes)
{
    glBindVertexArray(gVAOs[index]);
    glDrawElements(GL_TRIANGLES, gIndices[index], GL_UNSIGNED_INT, 0);
    glBindVertexArray(0);

    ....
}

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

Answer 1

В зависимости от уровня кеша, о котором вы говорите, кеш работает следующим образом:

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

Поэтому наивно задаваемые вопросы:

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

Итак, я бы ожидал, что B будет быстрее для этого кода. Тем не мение:

• если это единственный доступ к данным, то вы могли бы ускорить А, удалив большинство членов данных из struct, Так сделай это. Предположительно на самом деле это не единственный доступ к данным в вашей программе, и другие обращения могут повлиять на производительность двумя способами: время, которое они на самом деле занимают, и заполнение кеша данными, которые вам нужны.
• то, что я ожидаю, и то, что на самом деле происходит, часто разные вещи, и нет смысла полагаться на предположения, если у вас есть какая-либо возможность проверить это. В лучшем случае последовательный доступ означает, что ни в одном из кодов нет ошибок кэширования. Тестирование производительности не требует специального инструмента (хотя они могут сделать это проще), только часы с секундной стрелкой. В крайнем случае, создайте маятник из зарядного устройства телефона.
• Есть некоторые осложнения, которые я проигнорировал. В зависимости от оборудования, если вам не повезло с B, то на самом низком уровне кэша вы можете обнаружить, что доступы к одному вектору исключают доступы к другому вектору, потому что соответствующая память просто использует одно и то же место в кэше. Это приведет к двум ошибкам кэша на запись. Это произойдет только в том, что называется "кэш прямого отображения". "Двусторонний кеш" или лучше спас бы день, позволив сосуществовать частям обоих векторов, даже если их первое предпочтительное местоположение в кеше одинаково. Я не думаю, что аппаратное обеспечение ПК обычно использует кэш с прямым отображением, но я точно не знаю и не очень разбираюсь в графических процессорах.

Answer 2

Я рекомендую выполнять профилирование с использованием perf или oprofile и публиковать результаты здесь (при условии, что вы работаете в linux), включая количество элементов, с которыми вы перебирались, общее количество итераций и оборудование, на котором вы тестировали.

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

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

Не забывайте, что с векторами STL вы также зависите от распределителя... например, он может в любое время принять решение о перераспределении массива, что сделает ваш кеш недействительным. Еще один фактор, чтобы попытаться изолировать, если вы можете!

Answer 3

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

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

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

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

Answer 4

Зависит от ваших шаблонов доступа. Ваша первая версия - AoS (массив структур), вторая - SoA (структура массивов).

SoA имеет тенденцию использовать меньше памяти (если вы не храните так мало элементов, что накладные расходы массивов на самом деле нетривиальны), если есть какой-либо вид заполнения структуры, который вы обычно получаете в представлении AoS. Он также имеет гораздо большую PITA для кодирования, так как вы должны поддерживать / синхронизировать параллельные массивы.

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

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

Это также охватывает только шаблоны доступа к памяти. С представителями SoA вы также можете писать более эффективные и простые SIMD-инструкции. Но опять же он в основном подходит для последовательного доступа.

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