Является ли мое понимание преимуществ и недостатков AoS vs SoA правильными?

Ответ 1

"Обход" означает просто циклический перебор данных.

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

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

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

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

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

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

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

Это для масок обнаружения столкновений (в двумерной космической игре (Бесконечное небо), где все коллизия происходит между отрезком линии и контуром корабля (отслеживается автоматически по спрайту), а не между двумя полигонами). Здесь оригинал, который зацикливался на векторе 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 для данной вершины будет переменной времени выполнения, а не константой времени компиляции.)

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

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

Конечно, ручная векторизация выиграет здесь, так как я делаю такие вещи, как XORing с плавающей запятой вместе, потому что меня интересует только их знаковый бит как значение истинности, а не сравнение, а затем XORing результата сравнения. (Мое тестирование до сих пор показало, что обработка отрицательного 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 внесла это изменение, необходимо провести дополнительное тестирование. Возможно, с Broadwell, когда инструкции с тремя входами за пределами FMA (такие как CMOV и ADC) декодируются в один моп, но это чистое предположение. Тестирование на Haswell и Broadwell необходимо.