Оптимизация игр под iOS платформу. Векторизация кода

Давно назревало желание написать парочку статей, в которых я смогу выложить свой опыт и знания на тему оптимизации игр под ARMv7 архитектуру CPU и PowerVR SGX 5 серию GPU, читай iOS платформу. Но все, или почти все, советы в равной степени применимы под другие системы с тем же железом, читай Андроиды. Начну свою первую статью с наиболее важной, ИМХО, оптимизации – векторизации кода под NEON.

Что такое NEON? NEON – это SIMD движок общего назначения, используемый в ARM процессорах. На борту имеет 16 регистров по 128 бит каждый, которые можно рассматривать как 32 регистра по 64 бита. NEON делит свои регистры с VFP, хотя имеет свой отдельный пайплайн. Как и в случае с SSE данные должны быть выровнены на 16 байт. NEON так же умеет работать с невыровненными данными, но обычно это в 2 раза медленнее.

NEON умеет работать с:

• Знаковымибез знаковыми 8163264-битными целочисленными типами данных;
• Числами с плавающей запятой одинарной точности – 32-х битный float.

Он великолепно подходит для мультимедийных задач, в том числе и игр.

Начнем с основного – сердца каждой современной мобильной системы, системы на чипе или SoC (System on Chip). Известно, что в iOS девайсах используется Apple A серия систем на чипе – А4, А5, А5х, А6 и А6х. Наиболее важные спецификации этих чипов приведены в таблице:

*Внимание: каждое ядро процессора снабжено своим NEON юнитом, когда же VFP — один на процессор.
** Внимание: NEON работает на частоте CPU

Легко заметить, что NEON имеет 5-ти кратный прирост частоты по сравнению с GPU! Конечно, это не значит, что мы получим 5-ти кратное увеличение производительности по сравнению с GPU – IPC, пайплайн, т.д. имеют весомое значение. Но у NEON’а есть одна киллер фича – он может параллельно обрабатывать 4 32-х битных флоата, в то время как PowerVR SGX – только один. Кажется, у PowerVR SGX 5-й серии SIMD регистры имеют длину в 64 бита, так как GPU может параллельно обрабатывать 4 флоата половинной точности (16 бит). Рассмотрим пример:

highp vec4 v1, v2; 
highp float s1, s2; 

// Плохо 
v2 = (v1 * s1) * s2; //v1 * s1 будет выполнено на скалярном процессоре – 4 операции, результат этого умножения будет умножен на s2, опять на скалярном процессоре - еще 4 операции.
//8 операций в общем

// Хорошо 
v2 = v1 * (s1 * s2); //s1 * s2 – 1 операция на скалярном процессоре; результат * v1 – 4 операции на скалярном.
//5 операций в общем

Теперь рассмотрим другой пример, исполняемый на векторном движке GPU:

mediump vec4 v1, v2, v3; 
highp vec4 s1, s2, s3;

v3 = v1 * v2; //исполняется на векторном процессоре – 1 операция
s3 = s1 * s2; //исполняется на скалярном процессоре – 4 операции

Вам понадобится highp спецификатор для ваших данных, к примеру, позиции вершин. Профит от NEON’а здесь очевиден.

Теперь перейдем к другому преимуществу NEON’а. Известно, что PowerVR SGX 5-й серии обладают USSE, шейдерный процессор, которому без разницы какой тип шейдеров обрабатывать – вершинный или пиксельный. Это значит, что у программиста есть некий бюджет мощности и ему решать, на что его потратить – вершинный или пиксельный процессинг. Вот тут-то и приходит на помощь NEON – это ваш новый вершинный процессор. Вы можете подумать, что я забыл здесь вставить троллфейс, но все вполне серьёзно. Производительность почти каждой мобильной системы ограничена филлрейтом, особенно в 2D играх, особенно в наше время гонки за разрешением экранов. Перенеся весь вершинный процессинг на NEON у вас высвобождаются ресурсы для пиксельного процессинга. В дополнение к этому NEON поможет сократить количество вызовов на отрисовку – посчитайте позиции всех вершин одного батча в мировых координатах и нарисуйте N объектов за один вызов.

С теорией покончено! Теперь перейдем к хардкору! Есть несколько способов воспользоваться преимуществами NEON’a:

• Пусть компилятор векторизирует код вместо вас. Плохой способ. Компилятор может векторизировать… а может и не векторизировать. Даже если компилятор векторизирует код, то далеко не факт, что это будет оптимальный код. Но, с другой стороны, этот способ не требует никаких усилий с вашей стороны, а профит получить можно. Но все же не стоит слепо надеяться на компилятор, а вручную векторизировать хотя бы наиболее критичный код.
• NEON ассемблер. А вот и он, хардкор. Путь истинного джедая и все такое. Придется учить темную магию, проводить ночи за мануалами от ARM и т.д. Также стоит иметь в виду, что NEON код работает в обоих ARM и Thumb-2 режимах.
• NEON интринсики (такие же как SSE для x86). В отличии от ассемблера, где компилятор тупо вставит то, что ему дали, интринсики будут оптимизированны. С ними жить намного проще – нету необходимости изучать тайминги инструкций, перетасовывать их, чтобы избежать застоя пайплайна и т.д.
• Использовать либы с уже векторизированным кодом – GLKMath, math neon.

Пришло время обнаружить все преимущества и недостатки каждого из методов. Для этого я написал простенькое демо – каждый кадр 10000 спрайтов будут менять свою позицию на случайную в пределах экрана. Цель – получить максимально быстрый код с минимальной нагрузкой на CPU – ведь в играх надо много чего считать, помимо данных для рендера.

Все данные хранятся в одном VBO. Метод Update перемножает матрицу проекции на ModelView матрицу случайной позиции. Далее каждая вершина каждого спрайта будет перемножена на результирующую ModelViewProjection матрицу. Финальная позиция каждой вершины будет просто передана в gl_Position в вершинном шейдере. Все данные выравнены на границу в 16 байт.

Код Update метода:

void Update()
{
    GLKMatrix4 modelviewMat =
    {
	1, 0, 0, 0,
	0, 1, 0, 0,
	0, 0, 1, 0,
	0, 0, 0, 1,
    };
    const u32 QUADS_COUNT = 10000;
    const u32 VERTS_PER_QUAD = 4;
    const float Y_DELTA = 420.0f / QUADS_COUNT;	//равномерно распределить все спрайты по Y
    float vertDelta = Y_DELTA;
    
    for (int i = 0; i < QUADS_COUNT * VERTS_PER_QUAD; i += VERTS_PER_QUAD)
    {
        float randX = random() % 260;	//Матрица смещения на случайное число
        
        modelviewMat.m[12] = randX;
        modelviewMat.m[13] = vertDelta;
        
        float32x4x4_t mvp;
        Matrix4ByMatrix4((float32x4x4_t*)proj.m, (float32x4x4_t*)modelviewMat.m, &mvp);
        
        for (int j = 0; j < 4; ++j) {
            Matrix4ByVec4(&mvp, &squareVertices[j], &data[i + j].pos);
        }
        
        vertDelta += Y_DELTA;
    }
	
    glBindBuffer(GL_ARRAY_BUFFER, vertexBuffer);
    glBufferData(GL_ARRAY_BUFFER, sizeof(data), data, GL_STREAM_DRAW);
}

Что ж, теперь мы подошли к сути этой статьи – векторизации кода. Далее будет представлен код, используемый в трех сравниваемых подходах для наиболее часто используемых операций в геймдеве – перемножение матрицы на вектор и перемножение матрицы на матрицу.
 
Копипаста с GLKMath:

static __inline__ GLKVector4 GLKMatrix4MultiplyVector4(GLKMatrix4 matrixLeft, GLKVector4 vectorRight)
{
    float32x4x4_t iMatrix = *(float32x4x4_t *)&matrixLeft;
    float32x4_t v;
    
    iMatrix.val[0] = vmulq_n_f32(iMatrix.val[0], (float32_t)vectorRight.v[0]);
    iMatrix.val[1] = vmulq_n_f32(iMatrix.val[1], (float32_t)vectorRight.v[1]);
    iMatrix.val[2] = vmulq_n_f32(iMatrix.val[2], (float32_t)vectorRight.v[2]);
    iMatrix.val[3] = vmulq_n_f32(iMatrix.val[3], (float32_t)vectorRight.v[3]);
    
    iMatrix.val[0] = vaddq_f32(iMatrix.val[0], iMatrix.val[1]);
    iMatrix.val[2] = vaddq_f32(iMatrix.val[2], iMatrix.val[3]);
    
    v = vaddq_f32(iMatrix.val[0], iMatrix.val[2]);
    
    return *(GLKVector4 *)&v;
}

static __inline__ GLKMatrix4 GLKMatrix4Multiply(GLKMatrix4 matrixLeft, GLKMatrix4 matrixRight)
{
    float32x4x4_t iMatrixLeft = *(float32x4x4_t *)&matrixLeft;
    float32x4x4_t iMatrixRight = *(float32x4x4_t *)&matrixRight;
    float32x4x4_t m;

    m.val[0] = vmulq_n_f32(iMatrixLeft.val[0], vgetq_lane_f32(iMatrixRight.val[0], 0));
    m.val[1] = vmulq_n_f32(iMatrixLeft.val[0], vgetq_lane_f32(iMatrixRight.val[1], 0));
    m.val[2] = vmulq_n_f32(iMatrixLeft.val[0], vgetq_lane_f32(iMatrixRight.val[2], 0));
    m.val[3] = vmulq_n_f32(iMatrixLeft.val[0], vgetq_lane_f32(iMatrixRight.val[3], 0));

    m.val[0] = vmlaq_n_f32(m.val[0], iMatrixLeft.val[1], vgetq_lane_f32(iMatrixRight.val[0], 1));
    m.val[1] = vmlaq_n_f32(m.val[1], iMatrixLeft.val[1], vgetq_lane_f32(iMatrixRight.val[1], 1));
    m.val[2] = vmlaq_n_f32(m.val[2], iMatrixLeft.val[1], vgetq_lane_f32(iMatrixRight.val[2], 1));
    m.val[3] = vmlaq_n_f32(m.val[3], iMatrixLeft.val[1], vgetq_lane_f32(iMatrixRight.val[3], 1));

    m.val[0] = vmlaq_n_f32(m.val[0], iMatrixLeft.val[2], vgetq_lane_f32(iMatrixRight.val[0], 2));
    m.val[1] = vmlaq_n_f32(m.val[1], iMatrixLeft.val[2], vgetq_lane_f32(iMatrixRight.val[1], 2));
    m.val[2] = vmlaq_n_f32(m.val[2], iMatrixLeft.val[2], vgetq_lane_f32(iMatrixRight.val[2], 2));
    m.val[3] = vmlaq_n_f32(m.val[3], iMatrixLeft.val[2], vgetq_lane_f32(iMatrixRight.val[3], 2));

    m.val[0] = vmlaq_n_f32(m.val[0], iMatrixLeft.val[3], vgetq_lane_f32(iMatrixRight.val[0], 3));
    m.val[1] = vmlaq_n_f32(m.val[1], iMatrixLeft.val[3], vgetq_lane_f32(iMatrixRight.val[1], 3));
    m.val[2] = vmlaq_n_f32(m.val[2], iMatrixLeft.val[3], vgetq_lane_f32(iMatrixRight.val[2], 3));
    m.val[3] = vmlaq_n_f32(m.val[3], iMatrixLeft.val[3], vgetq_lane_f32(iMatrixRight.val[3], 3));

    return *(GLKMatrix4 *)&m;
}

Легко заметить, что реализация этих операций от Apple использует далеко не оптимальный подход – передача переменных по значению, копирование переменных. Выглядит довольно медленно, по крайней мере в дебаг сборке оно и будет являться таковым. Посмотрим, как этот код покажет себя при профиллировке.
 
Ассемблерный подход:

inline void Matrix4ByVec4(float32x4x4_t* __restrict__ mat, const float32x4_t* __restrict__ vec, float32x4_t* __restrict__ result)
{
    asm
    (
     "vldmia %0, { d24-d31 } nt"
     "vld1.32    {q1}, [%1]nt"
     
     "vmul.f32 q0, q12, d2[0]nt"
     
     "vmla.f32 q0, q13, d2[1]nt"
     "vmla.f32 q0, q14, d3[0]nt"
     "vmla.f32 q0, q15, d3[1]nt"
     
     "vstmia %2, { q0 }"
     
     :
     : "r" (mat), "r" (vec), "r" (result)
     : "memory", "q0", "q1", "q8", "q9", "q10", "q11"
     );
}

inline void Matrix4ByMatrix4(const float32x4x4_t* __restrict__ m1, const float32x4x4_t* __restrict__ m2, float32x4x4_t* __restrict__ r)
{
    asm 
    (
     "vldmia %1, { q0-q3 } nt"
     "vldmia %2, { q8-q11 }nt"
     
     "vmul.f32 q12, q8, d0[0]nt"
     "vmul.f32 q13, q8, d2[0]nt"
     "vmul.f32 q14, q8, d4[0]nt"
     "vmul.f32 q15, q8, d6[0]nt"
     
     "vmla.f32 q12, q9, d0[1]nt"
     "vmla.f32 q13, q9, d2[1]nt"
     "vmla.f32 q14, q9, d4[1]nt"
     "vmla.f32 q15, q9, d6[1]nt"
     
     "vmla.f32 q12, q10, d1[0]nt"
     "vmla.f32 q13, q10, d3[0]nt"
     "vmla.f32 q14, q10, d5[0]nt"
     "vmla.f32 q15, q10, d7[0]nt"
     
     "vmla.f32 q12, q11, d1[1]nt"
     "vmla.f32 q13, q11, d3[1]nt"
     "vmla.f32 q14, q11, d5[1]nt"
     "vmla.f32 q15, q11, d7[1]nt"
     
     "vstmia %0, { q12-q15 }"
     :
     : "r" (result), "r" (m2), "r" (m1)
     : "memory", "q0", "q1", "q2", "q3", "q8", "q9", "q10", "q11", "q12", "q13", "q14", "q15"
     );
}

Для человека не знакомого с ассемблером все кажется довольно страшным – я сам такой, могу разбираться только в NEON ассемблере. Но на самом деле здесь все просто – q1-q15 это, собственно, NEON регистры. vldmiavld1.32 – инструкции загрузки; vstmia – сохранения в память; vmul.f32vmla.f32 — умножитьумножить и прибавить.

Метод интринсиков:

inline void Matrix4ByVec4(float32x4x4_t* __restrict__ mat, const float32x4_t* __restrict__ vec, float32x4_t* __restrict__ result)
{
    (*result) = vmulq_n_f32((*mat).val[0], (*vec)[0]);
    
    (*result) = vmlaq_n_f32((*result), (*mat).val[1], (*vec)[1]);
    (*result) = vmlaq_n_f32((*result), (*mat).val[2], (*vec)[2]);
    (*result) = vmlaq_n_f32((*result), (*mat).val[3], (*vec)[3]);
}

inline void Matrix4ByMatrix4(const float32x4x4_t* __restrict__ m1, const float32x4x4_t* __restrict__ m2, float32x4x4_t* __restrict__ r)
{
    (*r).val[0] = vmulq_n_f32((*m1).val[0], vgetq_lane_f32((*m2).val[0], 0));
    (*r).val[1] = vmulq_n_f32((*m1).val[0], vgetq_lane_f32((*m2).val[1], 0));
    (*r).val[2] = vmulq_n_f32((*m1).val[0], vgetq_lane_f32((*m2).val[2], 0));
    (*r).val[3] = vmulq_n_f32((*m1).val[0], vgetq_lane_f32((*m2).val[3], 0));
    
    (*r).val[0] = vmlaq_n_f32((*r).val[0], (*m1).val[1], vgetq_lane_f32((*m2).val[0], 1));
    (*r).val[1] = vmlaq_n_f32((*r).val[1], (*m1).val[1], vgetq_lane_f32((*m2).val[1], 1));
    (*r).val[2] = vmlaq_n_f32((*r).val[2], (*m1).val[1], vgetq_lane_f32((*m2).val[2], 1));
    (*r).val[3] = vmlaq_n_f32((*r).val[3], (*m1).val[1], vgetq_lane_f32((*m2).val[3], 1));
    
    (*r).val[0] = vmlaq_n_f32((*r).val[0], (*m1).val[2], vgetq_lane_f32((*m2).val[0], 2));
    (*r).val[1] = vmlaq_n_f32((*r).val[1], (*m1).val[2], vgetq_lane_f32((*m2).val[1], 2));
    (*r).val[2] = vmlaq_n_f32((*r).val[2], (*m1).val[2], vgetq_lane_f32((*m2).val[2], 2));
    (*r).val[3] = vmlaq_n_f32((*r).val[3], (*m1).val[2], vgetq_lane_f32((*m2).val[3], 2));
    
    (*r).val[0] = vmlaq_n_f32((*r).val[0], (*m1).val[3], vgetq_lane_f32((*m2).val[0], 3));
    (*r).val[1] = vmlaq_n_f32((*r).val[1], (*m1).val[3], vgetq_lane_f32((*m2).val[1], 3));
    (*r).val[2] = vmlaq_n_f32((*r).val[2], (*m1).val[3], vgetq_lane_f32((*m2).val[2], 3));
    (*r).val[3] = vmlaq_n_f32((*r).val[3], (*m1).val[3], vgetq_lane_f32((*m2).val[3], 3));
}

Почти такой же код, как и в GLKMath, но есть небольшие отличия. Пояснения: vmulq_n_f32 – умножение вектора на скаляр; vgetq_lane_f32 – макрос, выбирающий скаляр из вектора; vmlaq_n_f32 – умножить на скаляр и прибавить. Этот код – просто отражение ассемблера на интринсики. Посмотрим, как он покажет себя в сравнении с ним.

Я делал тест на iPod Touch 4. Таблица содержит результаты профиллирования Update функции:

*На скриншоте из Instruments можно заметить, что функция Matrix4ByMatrix4 не заинлайнилась.

Вот и еще один совет – агрессивно инлайнте ваш критический к производительности код. Предпочитайте __attribute__((always_inline)) перед обычным inline в таких случаях.

Обновленная таблица результатов:

Принудительный инлайн дал очень хороший прирост производительности! Посмотрим, как покажет себя автовекторизация кода. Все, что нам необходимо – это добавить –mllvm –vectorize –mllvm –bb-vectorize-aligned-only в Other C Flags в настройках проекта.

Финальная таблица результатов:

Довольно странные результаты можно наблюдать в случае с ассемблером и интринсиками – по сути код один и тот же, но результат отличается кардинально – почти в 2 раза! Ответ на этот вопрос кроется в ассемблерном листинге (желающие заглянут сами). В случае с ассемблером мы видим в листинге именно то, что мы и написали. В случае с интринсиками компилятор оптимизировал код. Медленный, на первый взгляд, код GLKMath компилятор прекрасно оптимизировал что дало такое же время исполнения кода, как и у вручную написанных интринсиков.

Настало время подводить итоги. Можно сделать несколько выводов:

• Инженеры из команды LLVM проделали великолепную работу. В итоге компилятор генерирует хорошо оптимизированный код для интринсиков. Я делал похожий тест более года назад, когда единственным компилятором в XCode был GCC 4.2 и он выдавал очень плохой результат – всего 10-15% прироста производительности по сравнению с FPU кодом. Это прекрасные новости – нет необходимости изучать ассемблер и я этому несказанно рад!
• Clang компилятор умеет автовекторизировать код. Для программиста это бонус в производительности написав лишь 4 слова. Что тут еще можно сказать кроме того, что это крутая штука?!
• NEON код дает очень хороший буст производительности по сравнению с обычным C кодом – 2.22 раз! По итогам проделанной оптимизации вершинный процессинг стал быстрее, чем копирование этих самых вершин на сторону GPU! Если заглянуть в ассемблер memcpy то можно увидеть, что там так же используется NEON код. К сожалению, я не нашел в нем прифетча, что, видимо, и является причиной более медленного кода.
• Изучение всех этих лоу левел вещей стоит потраченного времени, особенно, если ваша цель — стать профессионалом.

Ссылки

www.arm.com/products/processors/technologies/neon.php
blogs.arm.com/software-enablement/161-coding-for-neon-part-1-load-and-stores/
code.google.com/p/math-neon/
llvm.org/devmtg/2012-04-12/Slides/Hal_Finkel.pdf
Демо проект

Автор: akaStiX

Источник