CodeOptimization:pixman
De ccppbrasil.org
A pixman é uma biblioteca com rotinas de baixo nível em C para tratamento de imagens. Ela utilizada principalmente pela biblioteca de desenhos vetoriais cairo, que por sua vez é utilizada por muitos outros projetos conhecidos, como por exemplo o servidor X-Window X.org, a biblioteca GTK e o browser Firefox
A pixman provê uma série de funções para composição de imagens de 1, 4, 8, 16, 24 e 32 bits, permitindo, entre outras características, o tratamento de transparências (alpha blend).
Tabela de conteúdo |
[editar] Otimização da biblioteca pixman
A pixman foi escolhida para ser o primeiro projeto de otimização de código por sugestão do Rodrigo Kumpera que alegou que uma otimização desta biblioteca iria melhorar de forma substancial um grande número de usuários, por se tratar de uma biblioteca central de muitos softwares.
Com uma análise rápida, verificamos que a mesma tinha suporte apenas para intrinsics MMX, e que poderia ser atualizada facilmente para utilizar outras instruções. Decidimos então inicialmente utilizar intrinsics SSE2, que necessitam apenas de processadores Pentium 4, por que já traria um grande ganho e atenderia um número maior de usuários.
Posteriormente verificamos que existem muitos outros pontos de melhoria. Existem chances para uma simples otimização matemática, como para o uso de multi-processamento com a OpenMP.
[editar] Status atual
As alterações da biblioteca pixman já foram aceitas pelo projeto e provavelmente estarão na próxima versão do Firefox (3.1). Estamos terminando uns questionamentos feitos pela equipe da pixman e resolvendo uns problemas encontrados na compilação para Win32, mas no geral o código já é oficial da pixman.
Outra coisa interessante que ocorreu nesse meio tempo foi um contato com o pessoal da Mozilla Foundation elogiando o trabalho e pedindo para trabalharmos em conjunto evitando esforços duplicados na pixman. Eu estou com a idéia de mapear quais são as chamadas que o Firefox utiliza dentro da pixman e otimizá-las. É o meu modo de "pagar" pelo browser que uso.
[editar] Implementação do código SSE2
Seguindo a organização atual da pixman, criou-se uma nova infra-estrutura para suportar as instruções SSE2 e de forma paralela as funções existentes. Assim em tempo de execução a biblioteca verifica quais são as instruções que o processador suporta e aciona o código mais adequado.
As funções MMX se favorecem da facilidade de trabalhar os 3 componentes do pixel (R, G e B) com passos únicos, aumentando assim o desempenho de tratamento das mesmas em relação ao código C puro, no entanto estas instruções tratavam apenas um pixel por vez. A abordagem da implementação do SSE2 se baseou na adaptação do código MMX para utilizar SSE2 aproveitando a capacidade de ler e gravar 4 pixels (128 bits = 4 x pixels de 32bits) por vez na memória e de tratar dois pixel por instrução (cada pixel é tratado internamente com 64 bits).
Evitou-se o uso da linguagem assembly, pois dificultaria a leitura do código e a depuração de erros. Optou-se pelo uso de intrinsics que são padronizados, que possuem suporte nos principais compiladores atuais (GCC, Visual Studio e Intel Compiler) e permitem uma leitura mais familiar para a linguagem C.
[editar] O código
O código foi montado com base em funções inline para tratamento das operações básicas da pixman, por exemplo está função faz a multiplicação entre pixels.
static inline void
pixMultiply_2x128 (__m128i dataLo, __m128i dataHi,
__m128i alphaLo, __m128i alphaHi,
__m128i* retLo, __m128i* retHi)
{
__m128i lo, hi;
lo = _mm_mullo_epi16 (dataLo, alphaLo);
hi = _mm_mullo_epi16 (dataHi, alphaHi);
lo = _mm_adds_epu16 (lo, Mask0080);
hi = _mm_adds_epu16 (hi, Mask0080);
*retLo = _mm_mulhi_epu16 (lo, Mask0101);
*retHi = _mm_mulhi_epu16 (hi, Mask0101);
}
// Mask0080 = 0x0080 0080 0080 0080 0080 0080 0080 0080
// Mask0101 = 0x0101 0101 0101 0101 0101 0101 0101 0101
Anteriormente cada pixel de 32 bits (4 x 8 bits), foi transformado em 64 bits (4 x 16 bits) para a utilização desta função, resultando em duas variáveis de 128 bits. Neste código é feita a multiplicação de todos os componentes (_mm_mullo_epi16 = multiplicação entre 16 bits), posteriormente é feito um arredondamento inteiro (_mm_adds_epu16 = para cada 16 bits (valor + 128) e _mm_mulhi_epu16 = para cada 16 bits (valor*257) >> 16).
Observe que os comandos são chamados utilizando as variáveis de forma alternada, isto é feito para otimizar o tratamento das mesmas pelo processador. Com isso aproveitamos a capacidade dos processadores atuais de tratar mais de uma instrução ao mesmo tempo (mesmo os processadores com um núcleo único).
Outra coisa interessante a ser observada é o uso de ponteiros nessa função. Como se trata de uma função inline os ponteiros não são tratados da mesma forma como nas funções normais. Quando a otimização está ligada, o compilador não criar ponteiros e sim faz com que o código da função escreva diretamente sobre os dados das variáveis passadas com parâmetro. O código SSE2 da pixman faz uso dessa característica para conciliar performance com um código mais amigável.
[editar] Resultados conseguidos
Abaixo temos um trecho da análise feita pelo teste de performance do cairo comparando o código SSE2 com o original da pixman com MMX em um Mobile Pentium 4 3.2GHz:
image-rgb paint_solid_rgba_over-256 1.25 0.20% -> 0.15 0.60%: 8.66x speedup image-rgb paint-with-alpha_solid_rgb_over-256 1.25 0.09% -> 0.15 0.65%: 8.60x speedup image-rgb paint-with-alpha_solid_rgba_over-256 1.25 0.21% -> 0.15 0.27%: 8.47x speedup image-rgba paint-with-alpha_solid_rgba_over-256 1.25 0.19% -> 0.15 0.24%: 8.11x speedup image-rgba paint-with-alpha_solid_rgb_over-256 1.26 0.47% -> 0.15 0.11%: 8.09x speedup image-rgba paint_solid_rgba_over-256 2.15 0.07% -> 0.27 1.32%: 8.04x speedup image-rgba paint-with-alpha_similar_rgba_source-256 5.84 1.04% -> 1.05 0.26%: 5.55x speedup image-rgba paint-with-alpha_similar_rgb_source-256 5.86 0.24% -> 1.06 0.68%: 5.55x speedup image-rgba paint-with-alpha_image_rgba_source-256 5.82 0.19% -> 1.07 1.24%: 5.54x speedup image-rgba paint-with-alpha_image_rgb_source-256 5.85 0.34% -> 1.06 0.29%: 5.53x speedup image-rgb paint-with-alpha_similar_rgba_source-256 5.80 0.17% -> 1.07 0.31%: 5.41x speedup image-rgb paint-with-alpha_image_rgba_source-256 5.79 0.11% -> 1.07 0.16%: 5.39x speedup image-rgb paint-with-alpha_similar_rgb_source-256 5.82 0.12% -> 1.08 0.15%: 5.38x speedup image-rgb paint-with-alpha_image_rgb_source-256 5.81 0.03% -> 1.09 0.24%: 5.35x speedup image-rgb paint_solid_rgba_over-512 5.12 0.39% -> 1.15 3.80%: 4.85x speedup image-rgba paint-with-alpha_solid_rgb_over-512 5.24 0.69% -> 1.18 2.37%: 4.64x speedup image-rgba paint_solid_rgba_over-512 5.09 0.42% -> 1.21 2.40%: 4.41x speedup image-rgba paint-with-alpha_solid_rgba_over-512 5.11 0.31% -> 1.19 1.29%: 4.40x speedup image-rgb paint-with-alpha_solid_rgba_over-512 5.11 0.09% -> 1.20 1.95%: 4.29x speedup image-rgb paint-with-alpha_solid_rgb_over-512 5.10 0.05% -> 1.20 0.64%: 4.28x speedup image-rgba paint-with-alpha_image_rgba_source-512 25.36 0.13% -> 6.39 0.04%: 3.97x speedup image-rgba paint-with-alpha_image_rgb_source-512 25.38 0.32% -> 6.41 0.13%: 3.94x speedup image-rgba paint-with-alpha_similar_rgb_source-512 25.31 0.26% -> 6.42 0.21%: 3.93x speedup image-rgb paint-with-alpha_image_rgb_source-512 25.07 0.09% -> 6.40 0.18%: 3.92x speedup image-rgba paint-with-alpha_similar_rgba_source-512 25.36 0.94% -> 6.48 0.41%: 3.91x speedup image-rgba paint-with-alpha_solid_rgba_source-256 4.82 0.00% -> 1.24 0.10%: 3.90x speedup
Em um processador mais recente (um Core2 Quad Q6600) os resultado são um pouco mais modestos, mas ainda conseguimos uma melhora de 2.5x em alguns casos.
[editar] Otimização do código C
Encontramos também alguns pontos que uma simples otimização do código C pode alterar a performance do código. São processos simples, como calcular valores constantes fora do loop ou simplificação de contas que geram resultados consistentes.
[editar] O código
Como exemplo, observe o seguinte trecho de código:
radial_gradient_t *radial = (radial_gradient_t *)pict;
while (buffer < end)
{
if (!mask || *mask++ & maskBits)
{
double pdx, pdy;
double B, C;
double det;
double c1x = radial->c1.x / 65536.0;
double c1y = radial->c1.y / 65536.0;
double r1 = radial->c1.radius / 65536.0;
pixman_fixed_48_16_t t;
pdx = rx - c1x;
pdy = ry - c1y;
B = -2 * ( pdx * radial->cdx
+ pdy * radial->cdy
+ r1 * radial->dr);
C = (pdx * pdx + pdy * pdy - r1 * r1);
det = (B * B) - (4 * radial->A * C);
if (det < 0.0)
det = 0.0;
if (radial->A < 0)
{
t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536);
}
else
{
t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) / (2.0 * radial->A) * 65536);
}
*(buffer) = _gradient_walker_pixel (&walker, t);
}
++buffer;
rx += cx;
ry += cy;
}
Neste código todos os cálculos foram feitos dentro de um loop, porém muitos deles são valores ou expressões constantes que poderiam ser feitos somente uma vez.
[editar] Retirando as constantes
A primeira coisa a ser feita é retirar a definição e cálculo das variáveis de dentro do loop. Devemos tirar também alguns cálculos constantes, por exemplo:
// Verificamos que: t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536); // é equivalente à: // // t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) * 65536 / (2.0 * radial->A)); // // e como 65536 / (2.0 * radial->A) é constante poderemos calculá-lo previamente e // simplificar a conta dentro do loop, alterando o código para: double InvA2 = 65536. / (2.0 * radial->A); // fora do loop t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) * InvA2); // dentro do loop
Coisa semelhate podemos fazer também com:
C = (pdx * pdx + pdy * pdy - r1 * r1); det = (B * B) - (4 * radial->A * C);
Pois tanto r1 * r1 quanto 4 * radial->A são constantes.
[editar] Simplificando os cáculos
Percebam agora a evolução das variáveis pdx e pdy. Elas são definidas como pd* = r* - c1* e a cada iteração é feito r* += c*. Com uma conta simples podermos alterar o pdx e pdy para o seguinte:
double pdx = rx - c1x - cx; // para que na primeira iteração fique pdx = rx - c1x double pdy = ry - c1y - cy; // e dentro do loop pdx += cx; // antes dos outros códigos pdy += cy;
Esta otimização não gerou nenhum grande impacto, mas nos fez perceber que podemos fazer algo em relação à variável B.
[editar] Alterando um cálculo complexo
B é calculado dentro do loop como:
B = -2. * (pdx*radial->cdx + pdy*radial->cdy + r1*radial->dr); // Verificando como ficaria B na próxima iteração temos: // // B = -2. * ((pdx+cx)*radial->cdx + (pdy+cy)*radial->cdy + r1*radial->dr); // B = -2. * (pdx*radial->cdx + cx*radial->cdx + pdy*radial->cdy + cy*radial->cdy + r1*radial->dr); // B = -2. * (pdx*radial->cdx + pdy*radial->cdy + r1*radial->dr) + -2. * (cx*radial->cdx + cy*radial->cdy); // // B = B + -2. * (cx*radial->cdx + cy*radial->cdy); // // Note que -2. * (cx*radial->cdx + cy*radial->cdy) é constante, // logo pode ser precalculado fora do loop, ficando: Bstep = -2. * (cx*radial->cdx + cy*radial->cdy); // fora do loop B += Bstep; // dentro do loop
Assim trocamos um cáculo complexo dentro do loop, por um cálculo externo e uma soma simples dentro do loop.
[editar] Código final
Colocando todas as modificações no código temos a nova versão:
radial_gradient_t *radial = (radial_gradient_t *)pict;
double C;
double det;
double c1x = radial->c1.x / 65536.0;
double c1y = radial->c1.y / 65536.0;
double r1 = radial->c1.radius / 65536.0;
pixman_fixed_48_16_t t;
double r1pow2 = r1 * r1;
double A = radial->A;
double InvA2 = 65536. / (2. * A);
double A4 = (4. * A);
double pdx = rx - c1x - cx;
double pdy = ry - c1y - cy;
double Bstep = -2. * (cx*radial->cdx + cy*radial->cdy);
double B = -2. * ((pdx+cx)*radial->cdx + (pdy+cy)*radial->cdy + r1*radial->dr) - Bstep;
while (buffer < end)
{
pdx += cx;
pdy += cy;
if (!mask || *mask++ & maskBits)
{
B += Bstep;
C = (pdx * pdx + pdy * pdy - r1pow2);
det = (B * B) - (A4 * C);
if (det < 0.0)
{
t = (pixman_fixed_48_16_t) ((- B) * InvA2);
}
else if (A < 0)
{
t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) * InvA2);
}
else
{
t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) * InvA2);
}
*(buffer) = _gradient_walker_pixel (&walker, t);
}
++buffer;
}
