Кеш инструкций и условные операторы

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

У меня вопрос: избавляет ли условное выражение от функции draw из кэша инструкций и, следовательно, разрушает мой план? или то, что я делаю, просто безумно?

struct position
{
    position(int x_, int y_):x(x_), y(Y_)
    int x,y;
};

vector<position> thePositions;
vector<sprite> theSprites;
vector<int> theNoOfEntities; //eg 3 things, 4 thingies, 36 dodahs
int noOfEntitesTotal;

//invoking the draw function
draw(&thePositions[0], &theSprites[0], &theNoOfEntities[0], noOfEntitesTotal)

void draw(position* thepos, sprite* thesp, int* theints, int totalsize)
{
    for(int j=0;int i=0;i<totalsize;i++)
    {
        j+=i%size[j]?1:0;
        thesp[j].draw(thepos[i]);
    }
}
Источник

2 ответа

Решение

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

В вашем случае вы условно сведены на x86 к плоской последовательности (и AFAIK, это также будет происходить на большинстве не x86-платформ, поскольку это математическая оптимизация, а не машинная):

IDIV DWORD PTR SS:[ARG.1]
MOV EAX,EDX
NEG EAX                                  ; Converts EAX to boolean
SBB EAX,EAX
NEG EAX

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

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

Если вы действительно обеспокоены неправильным предсказанием ветвлений и наложенными штрафами, используйте ресурсы, предоставленные вашим производителем целевой архитектуры (разные архитектуры ведут себя по-разному для неправильного предсказания ветвей), такие как эта и эта от Intel. CodeAnalyst от AMD - отличный инструмент для проверки неправильного предсказания ветвлений и возможных штрафов.

Источник

Вау, приятель! Без обид, но похоже, что вы читали о DOD, не понимая, как и почему. Теперь вы просто следуете рекомендациям, изложенным в статьях о DOD, как будто они важны. Это не так, в DOD важно понимать данные, понимать архитектуру компьютера и понимать, как ваш код может максимально эффективно манипулировать этими данными, используя ваши знания архитектуры. Рекомендации, изложенные в статьях DOD, служат лишь напоминанием о том, о чем стоит подумать.

Хотите знать, когда и как вам нужно использовать DOD? Узнайте об архитектуре, с которой вы работаете. Вы знаете стоимость одного промаха кэша? Это действительно очень, очень низкий. Делай математику. Я серьезно, делай математику самостоятельно, я мог бы дать тебе несколько цифр, но тогда ты многому не научишься. Так что узнайте, что вы можете об архитектуре, как работает процессор, как работают память и кэши, как работает язык ассемблера, как выглядит сборка, сгенерированная вашим компилятором. Когда вы знаете и понимаете все это, DOD становится не чем иным, как изложением некоторых почти очевидных рекомендаций по написанию действительно эффективного кода.

Источник
Другие вопросы по тегам