Какой из них наиболее удобен для кэша
Я пытаюсь получить хорошее представление о дизайне, ориентированном на данные, и о том, как лучше всего программировать с учетом кеша. В принципе, есть два сценария, которые я не могу точно решить, какой из них лучше и почему — лучше ли иметь вектор объектов или несколько векторов с атомарными данными объектов?
А) Пример вектора объектов
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);
....
}
Какой из них более эффективен при использовании памяти и кэш-памяти, что приводит к уменьшению количества кеш-памяти и повышению производительности, и почему?
Решение
В зависимости от уровня кеша, о котором вы говорите, кеш работает следующим образом:
- если данные уже находятся в кеше, доступ к ним быстрый
- если данные не находятся в кеше, то вы несете расходы, но вся строка кеша (или страница, если мы говорим, что ОЗУ вместо файла подкачки, а не ОЗУ или ОЗУ) заносится в кеш, поэтому доступ к пропущенному адресу будет не скучай.
- если вам повезет, подсистема памяти обнаружит последовательный доступ и предварительно извлечет данные, которые, по ее мнению, вам понадобятся.
Поэтому наивно задаваемые вопросы:
- сколько пропусков кэша происходит? — B выигрывает, потому что в A вы выбираете неиспользуемые данные для каждой записи, тогда как в B вы получаете не что иное, как небольшую ошибку округления в конце итерации. Таким образом, чтобы просмотреть все необходимые данные, B извлекает меньше строк кэша, предполагая значительное количество записей. Если количество записей незначительно, то производительность кеша может быть мало или вообще не связана с производительностью вашего кода, потому что программа, которая использует достаточно маленький объем данных, обнаружит, что она все время находится в кеше.
- последовательный доступ? — да, в обоих случаях, хотя это может быть сложнее обнаружить в случае B, потому что есть две чередующиеся последовательности, а не только одна.
Итак, я бы ожидал, что B будет быстрее для этого кода. Тем не мение:
- если это единственный доступ к данным, то вы могли бы ускорить А, удалив большинство членов данных из
struct, Так сделай это. Предположительно на самом деле это не единственный доступ к данным в вашей программе, и другие обращения могут повлиять на производительность двумя способами: время, которое они на самом деле занимают, и заполнение кеша данными, которые вам нужны. - то, что я ожидаю, и то, что на самом деле происходит, часто разные вещи, и нет смысла полагаться на предположения, если у вас есть какая-либо возможность проверить это. В лучшем случае последовательный доступ означает, что ни в одном из кодов нет ошибок кэширования. Тестирование производительности требует никаких специальных инструментов (хотя они могут сделать это легче), только часы с секундной стрелкой. В крайнем случае, создайте маятник из зарядного устройства телефона.
- Есть некоторые осложнения, которые я проигнорировал. В зависимости от оборудования, если вам не повезло с B, то на самом низком уровне кэша вы можете обнаружить, что доступы к одному вектору исключают доступы к другому вектору, потому что соответствующая память просто использует одно и то же место в кеше. Это приведет к двум ошибкам кэша за запись. Это произойдет только в том, что называется «кэш прямого отображения». «Двусторонний кеш» или лучше спас бы день, позволив сосуществовать частям обоих векторов, даже если их первое предпочтительное расположение в кеше одинаково. Я не думаю, что аппаратное обеспечение ПК обычно использует кэш с прямым отображением, но я точно не знаю и не очень разбираюсь в графических процессорах.
Другие решения
Я понимаю, что это частично основано на мнении, а также на том, что это может быть причиной преждевременной оптимизации, но ваш первый вариант определенно имеет лучшую эстетику. Это один вектор против шести — в моих глазах нет соревнований.
Для производительности кеша это должно быть лучше. Это потому, что альтернатива требует доступа к двум различным векторам, что разделяет доступ к памяти каждый раз, когда вы визуализируете сетку.
При структурном подходе сетка по сути является автономным объектом и правильно не подразумевает никакого отношения к другим сеткам. При рисовании вы получаете доступ только к тот сетка, а при рендеринге все меш, вы делаете по одному в кеш-дружественной манере. Да, вы будете кушать кеш быстрее, потому что ваши векторные элементы больше, но вы не будете оспаривать это.
Вы также можете позже найти другие преимущества от использования этого представления. т.е. если вы хотите хранить дополнительные данные о сетке. Добавление дополнительных данных в большее количество векторов быстро загромождает ваш код и увеличивает риск ошибочных ошибок, а вносить изменения в структуру — тривиально.
Я рекомендую профилирование с любым перфорация или же OProfile и опубликовать свои результаты здесь (при условии, что вы работаете в linux), включая количество элементов, с которыми вы перебирались, общее количество итераций и оборудование, на котором вы тестировали.
Если бы мне пришлось угадывать (а это только предположение), я бы подозревал, что первый подход мог бы быть быстрее из-за локальности данных в каждой структуре, и, надеюсь, ОС / аппаратное обеспечение может предварительно выбрать для вас дополнительные элементы. Но опять же, это будет зависеть от размера кеша, размера строки кеша и других аспектов.
Определение «лучше» тоже интересно. Вы ищете общее время для обработки N элементов, низкую дисперсию в каждом образце, минимальное количество кеш-пропусков (на которое будут влиять другие процессы, работающие в вашей системе) и т. Д.
Не забывайте, что с векторами STL вы также зависите от распределителя … например он может в любое время принять решение о перераспределении массива, что сделает ваш кеш недействительным. Еще один фактор, чтобы попытаться изолировать, если вы можете!
Зависит от ваших шаблонов доступа. Ваша первая версия AoS (массив структур), второй SoA (структура массивов).
SoA имеет тенденцию использовать меньше памяти (если вы не храните так мало элементы, что накладные расходы массивов на самом деле нетривиальны), если есть какие-либо дополнения структуры, которые вы обычно получаете в представлении AoS. Он также имеет гораздо большую PITA для кодирования, так как вы должны поддерживать / синхронизировать параллельные массивы.
AoS имеет тенденцию превосходить произвольный доступ. В качестве примера, для простоты, скажем, каждый элемент помещается в строку кэша и правильно выравнивается (например, размер и выравнивание 64 байта). В этом случае, если вы случайно получаете доступ к nth элемент, вы получите все соответствующие данные для элемента в одной строке кэша. Если вы использовали SoA и распределяли эти поля по отдельным массивам, вам пришлось бы загружать память в несколько строк кэша, чтобы загрузить данные для этого одного элемента. И поскольку мы обращаемся к данным в случайном порядке, мы вообще не получаем большой пользы от пространственной локализации, поскольку следующий элемент, к которому мы собираемся получить доступ, может быть где-то в памяти.
Тем не менее, SoA имеет тенденцию превосходить последовательный доступ главным образом потому, что зачастую меньше данных для загрузки в кэш ЦП, во-первых, для всего последовательного цикла, потому что это исключает заполнение структуры и холодные поля. Под холодными полями я подразумеваю поля, к которым вам не нужно обращаться в определенном последовательном цикле. Например, физическая система может не заботиться о полях частиц, связанных с тем, как частица выглядит для пользователя, таких как цвет и дескриптор спрайта. Это неактуальные данные. Это касается только положения частиц. SoA позволяет избежать загрузки этих не относящихся к делу данных в строки кэша. Это позволяет вам загружать как можно больше релевантных данных за раз в строку кэша, поэтому вы получаете меньше обязательных пропусков кэша (а также сбоев страниц при достаточно больших данных) с помощью SoA.
Это также охватывает только шаблоны доступа к памяти. С представителями SoA вы также можете писать более эффективные и простые SIMD-инструкции. Но опять же это в основном подходит для последовательный доступ.
Вы также можете смешать две концепции. Вы можете использовать AoS для горячих полей, к которым часто обращаются вместе в произвольном порядке, затем поднимать холодные поля и хранить их параллельно.
detector