Geração de código executável dinamicamente (on-the-fly) - Parte III

Por | Sem categoria | Sem Comentários

Motivação

No post anterior mostrei algumas alternativas de otimização para o algoritmo para aplicação de filtros em imagens digitais. Também examinei algumas alternativas de melhoria de performance pela utilização das funções de paralelismo do framework 4.

Esta série está me ajudando a reafirmar a convicção de que grandes melhorias podem ser obtidas em alto nível. A Microsoft está melhorando constantemente o framework e tem disponibilizado excelentes mecanismos de otimização. Exemplo disso, as excelentes extensões de paralelização do framework 4.

Como disse desde o início, há situações onde alguma geração IL apresente desempenho incomparável. Esta série de posts tem por objetivo evidenciar essa condição.

Sobre essa parte

Nessa parte apresento uma abordagem para geração de código executável on-the-fly (finalmente).

Mais rápido sim, mas por quê?

No post anterior (parte II) mostrei algumas implementações com performance melhor do que a do código do primeiro post. Mas por que esse código foi mais rápido?

Antes de mais nada, é importante observar que o algoritmo utilizado não foi modificado. O que ocorreu é que, diferente da abordagem genérica, na abordagem específica muitos dos parâmetros eram conhecidos. Então, muito do processamento envolvemendo estes parâmetros foi substuído por constantes. Interessante ainda observar que essa substuição ocorreu fundamentalmente dentro do loop principal. O que maximizou o impacto das alterações.

Observe, esse é o bloco de códgigo do loop mais interno na versão genérica:

    int yFilter = i / filterHeight;
    int xFilter = i % filterWidth;

    int iSrc = iDst + stride * (yFilter - filterHeight / 2) +
		bytesPerPixel * (xFilter - filterWidth / 2);

    if (iSrc >= 0 && iSrc < srcBytesCount)
    {
	pixelsAccum += filter[i] * src[iSrc];
       filterAccum += filter[i];
    }

E essa é uma parte do código para detecção de limites:

    int iSrc = iDst - stride - bytesPerPixel;
    if (iSrc >= 0 && iSrc < srcBytesCount)
    {
        pixelsAccum -= src[iSrc];
        filterAccum--;
    }

Repare que, de fato, é o mesmo código. A diferença está no fato dos parâmetros do filtro terem sido substuídas por constantes. Repare na implementação de EdgeDetectionFilter que o loop interno foi substuído por uma série de pequenos blocos com os parâmetros internos resolvidos. O código não ficou mais bonito mais com uma performance muito melhor.

Se é mais rápido, por que não escrever sempre código específico?

Há muitas respostas válidas para essa questão. Selecionemos algumas:

  1. Menor flexibilidade - Cada novo conjunto de parâmetros implica na escrita de um método inteiramente novo;
  2. Menor legibilidade - A resolução dos parâmetros, para tornar o código fixo, tornou o código, de certa forma, obscuro;
  3. Maior custo de manutenção – Caso uma melhoria no algoritmo possa ser implementada, isso demandará alterações de diversos trechos de código independentemente.

 

Então o caminho é aceitar uma implementação com performance mais pobre?

Nunca!! Bem, as vezes pode até ser Smiley piscando. A questão é verificar qual é a necessidade real de incremento na performance da sub-rotina que está sendo avaliada. Há casos onde a solução deva realmente ser partir para a implementação específica. Entretanto, uma alternativa viável é modificar o método principal para que este gere código executável específico on-the-fly. Ou seja, código específico gerado por código genérico. Code As Data!

Como implementar código on-the-fly em .net (afinal)

O .net Framework oferece uma alternativa para geração de código executável on-the-fly. Trata-se da namespace System.Reflection.Emit introduzida no Framework 2.0. As classes dessa namespace permitem que um programa gere métodos, classes e até montagens inteiras. O único ponto de atenção das classes desse namespace é que elas exigem um bom conhecimento relacionado a Intermediate Language (IL).

O método CreateFilterMethodIL gera método para aplicação de filtro conforme parâmetro recebido. Por ser um pouco mais longo, vejamos o código aos poucos:

	static DynamicMethod CreateFilterMethodIL(byte[] src, byte[] dst,
            int stride, int bytesPerPixel, double[] filter, int filterWidth, int bias)
        {
            int filterHeight = filter.Length / filterWidth;

            DynamicMethod result = new DynamicMethod(
                "DoFilter",
                typeof(void),
                new Type[] { typeof(byte[]), typeof(byte[]) },
                typeof(FilterExtensionMethods));

A classe DynamicMethod representa uma construção de método em memória. O primeiro argumento é o nome do método. O segundo, o tipo de retorno. O terceiro, os tipos dos parâmetros recebidos. E, por fim, o quarto, referece a classe em que o método deverá ser "vinculado".

	    bool allwaysFilterNeg = true;
            bool neverFilterNeg = true;
            double negs = 0;
            for (int i = 0; i < filter.Length; i++)
            {
                if (filter[i] > 0) allwaysFilterNeg = false;
                if (filter[i] < 0)
                {
                    neverFilterNeg = false;
                    negs += filter[i];
                }
            }
            if (filter[filter.Length / 2] >= Math.Abs(negs)) neverFilterNeg = true;

Pequeno código auxiliar que serve para determinar se o filtro passado por parâmetro pode resultar em soma negativa. (Se você não entende isso, estude filtros digitais)

	    var ilgen = result.GetILGenerator();

            // criando as três variáveis usadas no corpo do método
            ilgen.DeclareLocal(typeof(int));        // iDst
            ilgen.DeclareLocal(typeof(double));     // pixelsAccum
            ilgen.DeclareLocal(typeof(double));     // filterAccum

            ilgen.Emit(OpCodes.Ldc_I4_0);           // iDst = 0;
            ilgen.Emit(OpCodes.Stloc_0);

O método GetILGenerator da classe DynamicMethod provê todo o necessário para emissão de código IL que irá compor o corpo do método. O método DeclareLocal serve para criar áreas de armazenamento (variáveis) com escopo limitado ao método. Por fim, a instução Emit registra códigos de Operação no IL relacionado.

Não tenho por objetivo, nesse post, ensinar IL. Caso você não saiba o significado das instruções, consulte o msdn.

	    // define um ponto de retorno .. goto ..
            var top = ilgen.DefineLabel();
            ilgen.MarkLabel(top);

            ilgen.Emit(OpCodes.Ldc_R8, 0.0);
            ilgen.Emit(OpCodes.Dup);
            ilgen.Emit(OpCodes.Stloc_1);            // pixelsAccum = 0
            ilgen.Emit(OpCodes.Stloc_2);            // filterAccum = 0

Quase todas as linguagens de programação definem comandos para instruções goto. Em alto nível, considero o uso dessa abordagem questionável. Entretanto, em linguagens de montagem, como a IL, geralmente essa abordagem é a única alternativa para controle de fluxo de execução

	    for (int i = 0; i < filter.Length; i++)
            {
                if (filter[i] == 0) continue;

                int yFilter = i / filterHeight;
                int xFilter = i % filterWidth;

                int offset = stride * (yFilter - filterHeight / 2) +
                        bytesPerPixel * (xFilter - filterWidth / 2);

                var lessThanZero = ilgen.DefineLabel();
                var greaterThan = ilgen.DefineLabel();
                var loopBottom = ilgen.DefineLabel();

                // primeiro vetor na pilha
                ilgen.Emit(OpCodes.Ldarg_0);

                ilgen.Emit(OpCodes.Ldloc_0);
		if (offset > 0)
		{
                	ilgen.Emit(OpCodes.Ldc_I4, offset);
                	ilgen.Emit(OpCodes.Add);            // iDst + offset
		}

                ilgen.Emit(OpCodes.Dup);
                ilgen.Emit(OpCodes.Dup);

                ilgen.Emit(OpCodes.Ldc_I4_0);
                ilgen.Emit(OpCodes.Blt_S, lessThanZero); // if (iDst < 0)

                ilgen.Emit(OpCodes.Ldc_I4, src.Length);
                ilgen.Emit(OpCodes.Bge_S, greaterThan); // if (iDst > src.Length)

                ilgen.Emit(OpCodes.Ldelem_U1);
                ilgen.Emit(OpCodes.Conv_R8); // obtém o elemento de cor ne vetor

                if (filter[i] != 1) // se filtro for 1, não altera valor de referência
                {
                    if (filter[i] == -1)
                    {
                        ilgen.Emit(OpCodes.Neg); // inverte o valor
                    }
                    else
                    {
                        // produto
                        ilgen.Emit(OpCodes.Ldc_R8, filter[i]);
                        ilgen.Emit(OpCodes.Mul);
                    }
                }

                ilgen.Emit(OpCodes.Ldloc_1);
                ilgen.Emit(OpCodes.Add);
                ilgen.Emit(OpCodes.Stloc_1); // atualizando pixelsAccum

                ilgen.Emit(OpCodes.Ldc_R8, filter[i]);
                ilgen.Emit(OpCodes.Ldloc_2);
                ilgen.Emit(OpCodes.Add);
                ilgen.Emit(OpCodes.Stloc_2); // filterAccum

                ilgen.Emit(OpCodes.Br, loopBottom);

                // organizando a pilha para o próximo elemento do filtro
                ilgen.MarkLabel(lessThanZero);
                ilgen.Emit(OpCodes.Pop);
                ilgen.MarkLabel(greaterThan);
                ilgen.Emit(OpCodes.Pop);
                ilgen.Emit(OpCodes.Pop);

                ilgen.MarkLabel(loopBottom);
            }

Bloco de código mais importante. Escreve o código IL personalizado para cada componente do filtro.

Observe que elementos do filtro de peso 0 são ignorados. Só essa modificação faz com que, por exemplo, as duas chamadas para inversão de cores com dimensão 1 e 3, que na abordagem genérica apresentam resultados diferentes, agora apresentem a mesma performance.

            ilgen.Emit(OpCodes.Ldarg_1);        // dst
            ilgen.Emit(OpCodes.Ldloc_0);        // iDst

            var shouldSkipDivide = ilgen.DefineLabel();
            var copyQuotient = ilgen.DefineLabel();
            var pixelIsBlack = ilgen.DefineLabel();
            var pixelIsWhite = ilgen.DefineLabel();
            var done = ilgen.DefineLabel();

            ilgen.Emit(OpCodes.Ldloc_1);
            ilgen.Emit(OpCodes.Ldloc_2);

            ilgen.Emit(OpCodes.Dup);
            ilgen.Emit(OpCodes.Ldc_R8, 0.0);
            ilgen.Emit(OpCodes.Beq_S, shouldSkipDivide); // if (filterAccum != 0)

            if (!neverFilterNeg)
            {
                if (allwaysFilterNeg)
                {
                    ilgen.Emit(OpCodes.Neg);
                }
                else
                {
                    var absFilterAccum = ilgen.DefineLabel();
                    ilgen.Emit(OpCodes.Dup);
                    ilgen.Emit(OpCodes.Ldc_R8, 0.0);
                    ilgen.Emit(OpCodes.Bge_S, absFilterAccum);
                    ilgen.Emit(OpCodes.Neg);
                    ilgen.MarkLabel(absFilterAccum);
                }
            }

            ilgen.Emit(OpCodes.Div); // pixelAccum / filterAccum
            ilgen.Emit(OpCodes.Br_S, copyQuotient);

            ilgen.MarkLabel(shouldSkipDivide);
            ilgen.Emit(OpCodes.Pop);

            ilgen.MarkLabel(copyQuotient);

Esse bloco de código é responsável por determinar como deverá ser feita a divisão dos pixels acumulados pelos pesos acumulados.

	    if (bias > 0)
            {
                ilgen.Emit(OpCodes.Ldc_R8, (double)bias);
                ilgen.Emit(OpCodes.Add);
            }

Se um bias foi informado...

	    ilgen.Emit(OpCodes.Dup);
            ilgen.Emit(OpCodes.Dup);

            ilgen.Emit(OpCodes.Ldc_R8, 0.0);
            ilgen.Emit(OpCodes.Blt_S, pixelIsBlack); // if (pixelsAccum < 0)

            ilgen.Emit(OpCodes.Ldc_R8, 255.0);
            ilgen.Emit(OpCodes.Bgt_S, pixelIsWhite); // if (pixelsAccum > 255)

            ilgen.Emit(OpCodes.Conv_U1); // cast para byte
            ilgen.Emit(OpCodes.Br_S, done);

            ilgen.MarkLabel(pixelIsBlack);
            ilgen.Emit(OpCodes.Pop);
            ilgen.Emit(OpCodes.Pop);
            ilgen.Emit(OpCodes.Ldc_I4_S, 0);
            ilgen.Emit(OpCodes.Br_S, done); // setando para 0

            ilgen.MarkLabel(pixelIsWhite);
            ilgen.Emit(OpCodes.Pop);
            ilgen.Emit(OpCodes.Ldc_I4_S, 255); // setando 255

O valor produzido está no intervalo aceito para um byte (0-255)? Em caso negativo, faça os ajustes Smiley de boca aberta

	     ilgen.MarkLabel(done);
            ilgen.Emit(OpCodes.Stelem_I1); // dst[iDst] = value;

            ilgen.Emit(OpCodes.Ldloc_0);
            ilgen.Emit(OpCodes.Ldc_I4_1);
            ilgen.Emit(OpCodes.Add);
            ilgen.Emit(OpCodes.Dup);
            ilgen.Emit(OpCodes.Stloc_0);    // iDst ++

            ilgen.Emit(OpCodes.Ldc_I4, src.Length);
            ilgen.Emit(OpCodes.Blt, top);

            ilgen.Emit(OpCodes.Ret);
	    return result;
        }

Armazena o valor no vetor de saida. Incrementa contador, e checa se a função foi concluída. E isso é tudo!

Exemplo de código IL produzido pelo método CreateFilterMethodIL

Para o filtro de inversão de cores da imagem:

	.method public hidebysig static void  DoFilter(uint8[] src, uint8[] dst)
	{
		.locals init
			(
			[0] int32,
			[1] float64,
			[2] float64
			)

		ldc.i4.0
		stloc.0

		top:
		ldc.r8 0.0
		dup
		stloc.1
		stloc.2

		ldarg.0
		ldloc.0

		dup
		dup

		ldc.i4.0
		blt.s lessThanZero

		ldc.i4
		bge.s greaterThan

		ldelemem.u1
		conv.r8

		neg

		ldloc.1
		add
		stloc.1

		ldc.r8 -1.0
		ldloc.2
		add
		stloc.2

		br loopBottom
		lessThanZero:
		pop
		greaterThan:
		pop
		pop

		loopbBottom:
		ldarg.1
		ldloc.2

		dup
		ldc.r8 0.0
		beq.s shouldSkipDivide

		neg
		div
		br.s copyQuotient

		shouldSkipDivide:
		pop

		copyQuotient:
		ldc.r8 255.0
		add

		dup
		dup

		ldc.r8 0.0
		blt.s pixelIsBlack

		ldc.r8 255.0
		blt.s pixelIsWhite

		conv.u1
		br.s done

		pixelIsBlack:
		pop
		pop
		ldc.i4.0
		br.s done

		pixelIsWhite:
		pop
		ldc.i4.s 255

		done:
		stelem.i1
		ldloc.0
		ldc.i4.1
		add
		dup
		stloc.0

		ldc.i4
		blt top

		ret
	}

Importante verificar que o código gerado ainda poderia ser otimizado. Entretanto, observe que quase nenhuma operação matemática para cálculo de deslocamento foi executada. Observe também que apenas um filtro está presente.

Aplicando filtros utilizando geração dinâmica de código

Para aplicar um filtro utilizando código gerado dinamicamente, basta chamar o método ApplyFilterIL:

1: public  static  bool  ApplyFilterIL(this  Bitmap  bmp, double [] filter, int  filterWidth, int  bias = 0)
2: {
3:     Action <byte [], byte []> action = (bytesSource, bytesDest) =>
4:     {
5:         var  stride = bmp.GetStride();
6:         var  method = CreateFilterMethodIL(bytesSource,
7:             bytesDest, stride,
8:             stride / bmp.Width,
9:             filter, filterWidth, bias);
10:
11:         method.Invoke(null , new  object [] { bytesSource, bytesDest });
12:     };
13:
14:     return  RunBitmapAction(bmp, action);
15: }
16:

Observe que o método tem a mesma lista de parâmetros que o acionador do método convencional ApplyFilter

Considerações sobre performance

A performance das funções geradas dinamicamente é comparável as funções específicas somando o overhead necessário para geração dinâmica (cerca de 0,2s). Interessante destacar que o método gerado pode ser armazenado em cache para ser reutilizado, o que diminui o impacto do overhead.

Conclusões

No final desse post chega-se as seguintes conclusões (devem ser adicionadas as conclusões da parte II):

  1. A geração de código executável sob demanda é vantajosa em cenários onde o código possua grande repetição e onde os parâmetros influeciem de forma considerável o fluxo de execução;
  2. O overhead da geração de código dinâmico é facilmente contornada mediante desenvolvimento de cache;
  3. De fato, código é apenas um tipo “esperto” de dados.

Até a próxima Smiley piscando!