Производительность кэша векторов, матриц и кватернионов

ProgramBox

Производительность кэша векторов, матриц и кватернионов

Post author:admin
Запись опубликована:14 апреля, 2023
Post category:Вопросы по программированию

#c #c #arrays #optimization #data-structures

#c #c #массивы #оптимизация #структуры данных

Вопрос:

В прошлом я неоднократно замечал, что код на C и C использует следующий формат для этих структур:

 class Vector3
{
    float components[3];
    //etc.
}

class Matrix4x4
{
    float components[16];
    //etc.
}

class Quaternion
{
    float components[4];
    //etc.
}

Мой вопрос в том, приведет ли это к повышению производительности кэша, чем, скажем, это:

 class Quaternion
{
    float x;
    float y;
    float z;
    //etc.
}

… Поскольку я бы предположил, что члены класса и функции в любом случае находятся в непрерывном пространстве памяти? В настоящее время я использую последнюю форму, потому что нахожу ее более удобной (однако я также вижу практический смысл в форме массива, поскольку она позволяет обрабатывать оси как произвольные, зависящие от выполняемой операции).

После того, как я воспользовался некоторыми советами респондентов, я протестировал разницу, и на самом деле с массивом это происходит медленнее — я получаю разницу в частоте кадров примерно на 3%. Я реализовал operator[] для переноса доступа к массиву внутри Vector3. Не уверен, имеет ли это какое-либо отношение к этому, но я сомневаюсь в этом, поскольку это все равно должно быть встроено. Единственным фактором, который я мог видеть, было то, что я больше не мог использовать список инициализаторов конструктора на Vector3(x, y, z) . Однако, когда я взял исходную версию и изменил ее, чтобы больше не использовать списки инициализатора конструктора, она работала очень незначительно медленнее, чем раньше (менее 0,05%). Понятия не имею, но, по крайней мере, теперь я знаю, что первоначальный подход был быстрее.

Ответ №1:

Эти объявления не эквивалентны в отношении расположения памяти.

 class Quaternion
{
    float components[4];
    //etc.
}

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

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

1. Компилятор может свободно добавлять дополнения также в C или только в C ?

2. Не могли бы вы привести конкретный практический пример, где в последнем случае было бы вставлено дополнение, но не в первом? Или это чисто теоретический аргумент?

3. @aix: Я думаю, с float этого, вероятно, никогда бы не было. В общем, на некоторых платформах доступ к памяти намного быстрее, если адреса выровнены определенным образом (например, начинаются с кратного 4).

4. @amit: Я не знаю, но я думаю, что да, потому что приведенное выше объявление также является модулем, а модули гарантированно будут иметь такое же расположение памяти, какое они имели бы в C.

5. Хотя спецификация позволяет компилятору добавлять отступы по своему усмотрению, ни один компилятор не добавляет отступы между объектами одного и того же типа иначе, чем между элементами массива, потому что это бессмысленно делать. Таким образом, несколько полей одного и того же типа практически всегда будут располагаться точно так же, как массив этого типа.

Ответ №2:

Я полагаю, что разница в производительности от подобной оптимизации минимальна. Я бы сказал, что нечто подобное приводит к преждевременной оптимизации для большей части кода. Однако, если вы планируете выполнять векторную обработку поверх своих структур, скажем, с помощью CUDA, композиция структуры имеет важное значение. Посмотрите на стр. 23, если это интересно:http://www.eecis.udel.edu /~mpellegr/eleg662-09s/li.pdf

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

2. @NickWiggill Я бы сказал, что самый простой способ — это проверить это, написать два простых тестовых примера и опробовать его. Не хочу говорить, что вы неправы, вы, безусловно, можете быть правы, но опять же, для меня это звучит как преждевременная оптимизация. Предположение о том, как код может повлиять на производительность кэша, различается в разных архитектурах, и даже с одной архитектурой это трудно понять без эмпирического тестирования.

3. @NickWiggill Поздравляет с ускорением. 3% — это не так уж много, но каждая мелочь имеет значение, когда производительность имеет решающее значение. Однако я бы рекомендовал отнестись к этому с недоверием. Подобные микрооптимизации часто не стоят того, чтобы их выполнять — т. Е. вы можете не получить одинаковую производительность на разных платформах или компилятор может фактически выполнить эту оптимизацию с включенными разными флагами. Кэш — сложная вещь в освоении. Я слышал много историй о людях, утверждающих, что их производительность выше, когда они делают один микроопт, чтобы фактически снизить производительность на другой платформе, вот почему микроопты часто выполняются динамически.

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

5. @NickWigill Это может быть большим. Но, как я уже сказал, производительность кэша на таком маленьком уровне трудно точно предсказать, и практически невозможно предсказать кроссплатформенность. Вот почему сейчас проводится множество передовых исследований по оптимизации компилятора, посвященных динамическому выполнению микроопт методом проб и ошибок для каждой машины.

Ответ №3:

Я не уверен, что компилятору удается лучше оптимизировать код при использовании массива в этом контексте (подумайте, например, о объединениях), но при использовании API, таких как OpenGL, это может быть оптимизацией при вызове таких функций, как

 void glVertex3fv(const GLfloat* v);

вместо вызова

 void glVertex3f(GLfloat x, GLfloat y, GLfloat z);

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

1. Вы все равно не будете вызывать эти функции, если вас действительно волнует производительность (копирование 3-х значений с плавающей запятой — ваша наименьшая проблема). И даже тогда, возможно, неопределенный, но практически без проблем, вы все равно можете использовать glVertex3fv(amp;v.x) .