Правильно ли я понимаю преимущества/недостатки AoS и SoA?

«обход» просто означает цикл по данным.

И да, вы правы насчет способов кэширования и коллизий. 64B (размер строки кэша) блоки памяти, которые смещены друг от друга на большую степень двойки, сопоставляются с одним и тем же набором и, таким образом, конкурируют друг с другом за пути в этом наборе, вместо того, чтобы кэшироваться в разных наборах. (например, кэши данных Intel L1 имеют размер 32 КБ, 8-канальную ассоциативность, 64-битные строки. 32kiB / 64 B/line = 512 lines сгруппированы в 512 lines / 8 ways/set = 64 sets.

Загрузка 9 элементов, смещенных друг от друга на 4 КБ (64B/line * 64 sets, не случайно размер страницы), вытеснит первый.

Кэши L2 и L3 более ассоциативны, например, 16- или 24-канальные, но все же подвержены подобному «алиасингу», подобно хеш-таблице, где есть большой спрос на одни наборы (сегменты) и нет спроса на другие наборы (сегменты). ). Для кэшей ЦП «хэш-функция» почти всегда заключается в использовании некоторых битов адреса в качестве индекса и игнорировании других битов. (Старшие биты адреса используются в качестве тега, чтобы определить, действительно ли какой-либо способ в наборе кэширует запрошенный блок, а младшие биты используются для выбора байтов в строке кэша.)

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

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

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

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

Это для масок обнаружения столкновений (в 2D-космической игре (Endless Sky), где все столкновение между сегментом линии и контуром корабля (автоматически трассируется из спрайта), а не между двумя полигонами). Вот оригинал, зацикленный на вектор из double пар x,y (и использовал некоторые (не встроенные!) функции для работы с ними как вектор SIMD 16B, часто с медленным SSE3, инструкции по горизонтальному добавлению и тому подобное :( ).

SSE2/SSE3 для пар XY, вероятно, лучше, чем ничего, если вы не можете изменить макет данных, но изменение макета устраняет всю перетасовку для параллельного выполнения 4 перекрестных произведений. См. слайды из этого Презентация SIMD (SSE) на Insomniac Games (GDC 2015). Он начинается с очень простых вещей для тех, кто раньше ничего не делал с SIMD, и объясняет, чем именно полезны структуры массивов. В конце он переходит к промежуточным/продвинутым методам SSE, поэтому его стоит пролистать, даже если вы уже знакомы с некоторыми вещами SIMD. См. также вики-страницу sse, где есть другие ссылки.

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

class Mask {
...

struct xy_interleave {
    static constexpr unsigned vecSize = 4;
    static constexpr unsigned alignMask = vecSize-1;
    alignas(64) float x[vecSize];
    float y[vecSize];
    // TODO: reduce cache footprint by calculating this on the fly, maybe with an unaligned load?
    float dx[vecSize]; // next - current;   next.x = x+dx
    float dy[vecSize];
};
std::vector<xy_interleave> outline_simd;

}

Затем я могу перебрать его с помощью таких вещей, как (здесь настоящий код: это мой незавершенный неочищенный код, который не готов к отправке вверх по течению)

__m128 minus_point_ps = _mm_cvtpd_ps(-point);    // + is commutative, which helps the compiler with AVX
const __m128 minus_px = _mm_set1_ps(minus_point_ps[0]);
const __m128 minus_py = _mm_set1_ps(minus_point_ps[1]);
const __m128 range2 = _mm_set1_ps(float(range*range));

for(const xy_interleave &curr : outline_simd)
{
    __m128 dx = _mm_load_ps(curr.x) + minus_px;
    __m128 dy = _mm_load_ps(curr.y) + minus_py;
    // this is using GNU Vector Extensions for + and *, instead of _mm_add_ps and _mm_mul_ps, since GNU C++ defines __m128 in terms of __v4sf
    __m128 cmp = _mm_cmplt_ps(dx*dx - range2, dy*dy);  // transform the inequality for more ILP
    // load the x and y fields from this group of 4 objects, all of which come from the same cache line.

    if(_mm_movemask_ps(cmp))
        return true;
}

Это компилируется в действительно красиво выглядящие циклы asm, в которых только один указатель зацикливается на std::vector, а вектор загружается из постоянных смещений относительно этого указателя цикла.

Однако скалярные резервные циклы для тех же данных менее красивы. (И на самом деле я использую такие циклы (с j+=4) и в частях, векторизованных вручную, поэтому я могу изменить чередование, не нарушая код. Он полностью компилируется или превращается в развертку).

// TODO: write an iterator or something to make this suck less
for(const xy_interleave &curr : outline_simd)
    for (unsigned j = 0; j < curr.vecSize; ++j)
    {
        float dx = curr.x[j] - px;
        float dy = curr.y[j] - py;
        if(dx*dx + dy*dy < range2)
            return true;
    }

К сожалению, мне не удалось заставить gcc или clang автоматически векторизовать это, даже для простых случаев без условных выражений (например, просто найти минимальный диапазон от запроса x, y до любой точки в маске коллизии, вместо проверки, если точка находится в пределах диапазона).

Я мог бы отказаться от этой идеи и использовать отдельные массивы x и y. (Возможно, упаковать голову в хвост в одном и том же std::vector<float> (с выровненным аллокатором), чтобы он оставался частью одного распределения, но это все равно будет означать, что циклам потребуются отдельные указатели x и y, потому что смещение между x и y для данной вершины будет переменной времени выполнения, а не константой времени компиляции.)

Наличие всех смежных xs было бы большим подспорьем, если я хочу перестать хранить x[i+1]-x[i] и вычислять его на лету. С моим макетом мне нужно было бы перетасовывать векторы, а не просто делать невыровненное смещение на 1 число с плавающей запятой.

Надеемся, что это также позволит компилятору автоматически векторизовать некоторые функции (например, для ARM или для AVX/AVX2 с более широкими векторами).

Конечно, ручная векторизация здесь выиграет, так как я делаю такие вещи, как XORing float вместе, потому что меня волнует только их знаковый бит как истинное значение, вместо того, чтобы выполнять сравнение, а затем XOR результат сравнения. (Мое тестирование до сих пор показало, что обработка отрицательного 0 как отрицательного по-прежнему дает правильные результаты для Mask::Intersect, но любой способ выразить это в C будет следовать правилам IEEE, где x >= 0 истинно для x=-0.).

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

У вас это ровно наоборот. Это была опечатка? Группировка всех foo[i].key полей в массив foo.key[i] означает, что все они упакованы вместе в кэше, поэтому доступ только к этому одному полю во многих объектах означает, что вы используете все 64 байта каждой строки кэша, к которой вы прикасаетесь.

Вы правильно поняли, когда писали

При работе только с некоторыми данными из многих записей «Лицо» только эти данные необходимо загрузить в память.

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

Режимы индексированной адресации:

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

С несколькими указателями вы захотите либо использовать режимы адресации, такие как [reg1 + 4*reg2] на x86, либо вам нужно будет отдельно увеличивать кучу разных указателей внутри вашего цикла. Режимы индексированной адресации потенциально немного медленнее в Intel SnB-семействе, потому что они не может оставаться микрослитым с моповами ALU в неупорядоченном ядре (только в декодерах и кэше мопов). Skylake может сохранить их микроплавкими, но необходимы дальнейшие испытания, чтобы выяснить, когда Intel внесла это изменение. Возможно, с Бродвеллом, когда инструкции с тремя входами за пределами FMA (например, CMOV и ADC) декодируются в один моп, но это чистое предположение. Необходимо тестирование на Haswell и Broadwell.