Обработка SVG без cairographics

Хочу поделиться идеями, почему на линуксах с Cairographics так медленно открываются окошки.
У меня есть своя библиотека обработки SVG, в которую я пытаюсь встроить SVG анимацию. В процессе работы обнаружил возможность оптимизации по скорости.


Иерархия библиотек такова: GTK3 использует Cairo в качестве базы. Я использую SVG и рисую с помощью cairo в окошке Gtk. В связи с анимацией я озаботился производительностью библиотеки. В идеале надо держать готовые кривые cairo_path_t и готовые матрицы трансформации cairo_matrix_t в бинарном виде, чтобы накладывать на них анимацию SVG и не тратить каждый раз время на разбор текстового формата и на преобразование кривых.

Рылся в исходниках Cairo, нашел там базовую операцию cairo_matrix_multiply, на которой строится все остальные примитивы, в том числе cairo_matrix_transform, cairo_matrix_translate, cairo_matrix_scale. Матрица имеет шесть элементов, четыре отвечают за поворот, два отвечают за трансляцию (смещение). На практике умножение матриц используется редко, только для отражений, тогда все коэффициенты либо нулевые, либо единичные. В основном используются примитивы _translate, _rotate и _scale

Тезис 1. Cairo не оптимизирована для векторизации. Компилятор GCC не использует векторные операции, если не описать векторный тип или выравнивание структуры явным образом. Операции умножения матриц разделены на группы, всегда можно выделить пару точек (x,y) или строчку в матрице (xx,yx) (xy,yy) (x0,y0), над которыми можно выполнить две операции в параллель.
Пример векторного описания матрицы 2x3:
typedef double v2df __attribute__((__vector_size__(16)));
typedef struct _cairo_matrix {
    v2df x;//double xx; double yx;
    v2df y;//double xy; double yy;
    v2df z;//double x0; double y0;
} svg_matrix_t;

Было 12 умножений 8 сложений, 64 инструкции:
void cairo_matrix_multiply (cairo_matrix_t *r,
            const cairo_matrix_t *a,
            const cairo_matrix_t *b)
{
    cairo_matrix_t r;

    r.xx = a->xx * b->xx + a->yx * b->xy;
    r.yx = a->xx * b->yx + a->yx * b->yy;

    r.xy = a->xy * b->xx + a->yy * b->xy;
    r.yy = a->xy * b->yx + a->yy * b->yy;

    r.x0 = a->x0 * b->xx + a->y0 * b->xy + b->x0;
    r.y0 = a->x0 * b->yx + a->y0 * b->yy + b->y0;

    *result = r;
}

Стало 6 умножений 4 сложения, 21 инструкция SSE/AVX:
static inline void svg_matrix_transform (svg_matrix_t *r,
            const svg_matrix_t *a)
{
    v2df x = r->x;
    v2df y = r->y;
    r->x = x*a->x[0] + y*a->x[1];
    r->y = x*a->y[0] + y*a->y[1];
    r->z = r->z + x*a->z[0] + y*a->z[1];
}
Ниже привожу ассемблерный код после компиляции с ключом -O3 -march=corei7-avx
    vmovddup        96(%esp), %xmm0
    vmovddup        32(%esp), %xmm4
    vmovddup        %xmm1, %xmm1
    vmovapd 144(%esp), %xmm3
    vmovapd 160(%esp), %xmm2
    vmulpd  %xmm3, %xmm0, %xmm0
    vmulpd  %xmm2, %xmm4, %xmm4
    vaddpd  %xmm4, %xmm0, %xmm0
    vmovddup        24(%esp), %xmm4
    vmulpd  %xmm2, %xmm4, %xmm4
    vmulpd  %xmm2, %xmm1, %xmm2
    vmovaps %xmm0, 144(%esp)
    vmovddup        56(%esp), %xmm0
    vmulpd  %xmm3, %xmm0, %xmm0
    vaddpd  %xmm4, %xmm0, %xmm0
    vmovaps %xmm0, 160(%esp)
    vmovddup        48(%esp), %xmm0
    vmulpd  %xmm3, %xmm0, %xmm0
    vaddpd  176(%esp), %xmm0, %xmm0
    vaddpd  %xmm2, %xmm0, %xmm0
    vmovaps %xmm0, 176(%esp)

Хочется отметить тот факт, что компилятор по моему описанию смог создать "чистый" код содержащий только инсрукции SSE/AVX.

Тезис 2. Cairo выполняет множество "лишних" операций, потому что операции *_scale, *_translate основаны на более сложной, более общей операции перемножения матриц 2х3. В тех случаях, когда компоненты матрицы равны нулю или единице, компилятор не имеет возможности оптимизировать код.
Решение: чтобы дать возможность оптимизации компилятору, надо использовать inline функции или макросы для базовых операций.

Было: оптимизации нет, будет выполнено заполнение матрицы и 12 умножений:

void cairo_matrix_scale (cairo_matrix_t *matrix, double sx, double sy)
{
    cairo_matrix_t tmp;
    cairo_matrix_init_scale (&tmp, sx, sy);
    cairo_matrix_multiply (matrix, &tmp, matrix);
}
После оптимизации -O3 в функции cairo_matrix_scale осталось 8 умножений и 40 команд процессора.
void cairo_matrix_translate (cairo_matrix_t *matrix, double tx, double ty)
{
    cairo_matrix_t tmp;
    cairo_matrix_init_translate (&tmp, tx, ty);
    cairo_matrix_multiply (matrix, &tmp, matrix);
}
После оптимизации -O3 в функции cairo_matrix_translate осталось 8 умножений и 43 команды процессора.
void cairo_matrix_rotate (cairo_matrix_t *matrix, double radians)
{
    cairo_matrix_t tmp;
    cairo_matrix_init_rotate (&tmp, radians);
    cairo_matrix_multiply (matrix, &tmp, matrix);
}

После оптимизации -O3 и -march=corei7-avx в функции cairo_matrix_rotate осталось 10 умножений и 53 команды процессора.

Далее результаты полученные с использованием векторизации.
Стало: максимум 2 операции умножения, 7 инструкций SSE/AVX, при использовании констант компилятор упростит выражение:
static inline void svg_matrix_scale (svg_matrix_t *r, v2df s)
{
    r->x *= s[0];
    r->y *= s[1];
}

Вот так выглядит ассемблерный код после использования inline функции svg_matrix_scale:     vmovapd 64(%esp), %xmm7
    vpermilpd       $0, %xmm7, %xmm0
    vmulpd  144(%esp), %xmm0, %xmm0
    vmovaps %xmm0, 144(%esp)
    vpermilpd       $3, %xmm7, %xmm0
    vmulpd  160(%esp), %xmm0, %xmm0
    vmovaps %xmm0, 160(%esp)


Операция сдвига, 2 операции умножения, 8 инструкций SSE/AVX, параметр - дистанция сдвига
static inline void svg_matrix_translate (svg_matrix_t *r, v2df d)
{
    r->z = r->z + r->x*d[0] + r->y*d[1];
}

Операция вращения матрицы, 4 операции умножения, 11 инструкций SSE/AVX,  косинус и синус упакованы в один вектор:
static inline void svg_matrix_rotate (svg_matrix_t *r, v2df cs)
{
    v2df x = r->x;
    v2df y = r->y;
    r->x = x*cs[0] + y*cs[1];
    r->y = y*cs[0] - x*cs[1];
}
Кроме того, использование inline функций позволяет компилятору уйти от операций на стеке и выполнять операции на регистрах SSE или AVX. В этом случае в каждой функции на две инструкции в меньше, обращений к памяти меньше. Данные оптимизации работают с архитектурами:-march=prescott, -march=nocona, -march=atom, -march=core2, -march=corei7... .

Надо упомянуть еще одну функцию:
static inline v2df svg_matrix_transform_point (const svg_matrix_t *m, v2df d)
{
    return m->x*d[0] + m->y*d[1] + m->z;
}
Операция состоит из 2-х умножений и 7 инструкций SSE/AVX. Эта функция используется в цикле при пересчете координат точек кривой, для каждой точки.

Тезис 3. Рисование дуг окружностей выполняется кубическими сплайнами. Это не я придумал, cairo так и делает. Точность аппроксимации дуги окружности кубическим сплайном по утверждению математиков вполне приемлемая, чтобы глазом было не отличить. После этого открытия я переписал свою библиотеку, чтобы не использовать операции рисования дуг вовсе, заменил их явным образом на сплайны. После замены операции вычисления углов уходят, синусы, косинусы и арктангенсы из программы уходят. Этот тезис упрощает мир: все многообразие фигур сводится к понятию "кривая". Кривая состоит из линий и кубических сплайнов. Таким образом, оптимизированное бинарное представление SVG может содержать кривые (cairo_path_t), матрицы преобразования (cairo_matrix_t) и стили (включают описание способа заливки цвет и толщину линий). При построении изображения, матрицы преобразования используются подряд несколько раз на уровне группы и на уровне элемента, группы могут быть вложенные. Таким образом подготовка матрицы преобразования для каждого элемента - это процесс перемножения матриц на каждом вложенном элементе SVG.

Вывод. Кривые можно генерировать без помощи cairo в формате cairo_path_t. Матрицы преобразования быстрее рассчитывать без cairo. Небольшие оптимизации в cairo позволили бы существенно ускорить обработку векторных изображений.