Otimização do Gradiente Circular da pixman

Durante a execução do projeto de otimização da pixman, encontramos alguns pontos que uma simples otimização do código C e um pouco de matemática podem alterar o desempenho do código. Os processos foram simples, como calcular valores constantes fora do loop ou simplificação de contas que geram resultados consistentes.

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;
}

Otimizando o código

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.

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));
//
// 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 semelhante 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.

Simplificando os cálculos

Percebam agora a evolução das variáveis pdx e pdy. Elas são definidas como pdx = rx - c1x e pdy = ry - c1y e a cada iteração é feito rx += cx e ry += cy. Com uma conta simples podermos alterar o pdx e pdy para o seguinte:

double pdx = rx - c1x;
double pdy = ry - c1y;
 
// e dentro do loop
 
pdx += cx; 
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.

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 pré calculado fora do loop, ficando:
 
Bstep = -2. * (cx*radial->cdx + cy*radial->cdy); // fora do loop 
B += Bstep; // dentro do loop

Assim trocamos um cálculo complexo dentro do loop, por um cálculo externo e uma soma simples dentro do loop.

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;
double pdy = ry - c1y;
double Bstep = -2. * (cx*radial->cdx + cy*radial->cdy);
double B = -2. * (pdx*radial->cdx + pdy*radial->cdy + r1*radial->dr);
 
while (buffer < end) 
{
  if (!mask || *mask++ & maskBits)
  {
    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);
  }
  pdx += cx;
  pdy += cy;
  B += Bstep;
  ++buffer;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License