Arquivo da categoria: Posts

Microsoft Dynamics AX 2012 – Qual usuário é responsável pela query em execução?

Não tão focado no desenvolvimento em si, este post tem um intuito bastante específico:

Em um banco de dados SQL Server onde o Microsoft Dynamics AX 2012 está rodando, todas as conexões tem como origem a AOS e, consequentemente, um usuário normalmente chamado de “svc.aos”. Assim, é difícil coletar de uma vez só todo o “contexto” relacionado ao banco de dados conjuntamente com o usuário responsável.

Como contexto, podemos entender coisas como: query, plano de execução e duração.

Existe uma stored procedure que, de forma sintética, é capaz de apresentar diversas informações com uma simples execução. Ela é a sp_WhoIsActive.

Porém, como ela é focada somente no SQL Server e não no Dynamics 2012 propriamente dito, construí uma alteração que pode ser conferida aqui no meu github que é responsável por adicionar uma coluna a mais que representa o usuário existente dentro da UserInfo que está vinculado à determinada sessão do banco de dados.

Exemplo de uso:

EXEC sp_WhoIsActive
        @find_block_leaders = 1,
        @get_plans = 1,
        @sort_order = '[blocked_session_count] DESC',
        @get_dax_user = 1,
        @get_dax_database = 'CONTOSO';

Resultado:

A coluna “dax” reflete o nome do usuário existente na UserInfor do database especificado no parâmetro “get_dax_database”.

Por limitação de espaço, a imagem não apresenta outras colunas importantes como o próprio plano de execução.

Mesmo assim, é possível conferir qual é o usuário que está causando, neste exemplo, um lock.

Análise da complexidade de algoritmos – Comportamento Assintótico

Como primeiro post para este blog resolvi escrever um pouco sobre o comportamento assintótico, um assunto que, na minha opinião, deveria ser de conhecimento básico para todo engenheiro de software.

Então, ao invés de estruturar este post sobre diversos livros, referências, ou até mesmo outros blogs, prefiro ir direto ao ponto e explicar de forma breve porém, esclarecedora.

Não é o objetivo tornar este post como referência máxima sobre o assunto (está anos luz longe disso) e sim, despertar o interesse para sua importância e como será encaixado em outros posts deste mesmo blog.

Big-O, e a complexidade de tempo

Comparação do número de operações em relação à entrada

A imagem acima foi extraída de um ótimo, porém também sintético, post escrito por Daniel Miessler e pode ser conferido aqui.

Em termos gerais, podemos olhar para o Big-O como um método para comparar a eficiência de um algoritmo dado o tamanho da sua entrada.

Porém, sempre que vamos trabalhar com um grande volume de informações, tomo gráficos como esse do post como um suporte ao pensamento. A dor de construir sistemas ineficientes é extremamente desproporcional à dor de, possivelmente, construí-los e arquitetá-los de forma melhor.

Como métrica experimental, formalizemos que a instrução de entrada do algoritmo (n) tem duração de 1 segundo.

Então…

Complexidade Constante -> O(1):
Coloco aqui coisas como operações matemáticas ou operações lógicas.
Exemplo:

int x = 10 * n;
//ou
if(x < 10)...

Ambos são exemplos de códigos que sempre terão “a mesma duração em tempo” para serem executados.
Que nesse caso podemos dizer que, não importa o valor que passarmos em “n”, sempre irá demorar 1 segundo para ser executado.

Complexidade Logarítmica -> O(log n):
Sendo o logaritmo uma espécie de “inverso” da potencialização / exponencial. Podemos imaginar (ou até validar na imagem acima) que, também, se trata de uma série que possui um tempo baixo em relação à entrada.
Exemplo:

public static int BinarySearch(int[] inputArray, int targetValue)
{
    int min = 0;
    int max = inputArray.Length - 1;
    int guess;

    while (min <= max)
    {
        guess = (min + max) / 2;

        if (targetValue == inputArray[guess])
        {
            return guess;
        }
        else if (targetValue < inputArray[guess])
        {
            max = guess - 1;
        }
        else
        {
            min = guess + 1;
        }
    }

    return -1;
}

Costumo pensar nesse tipo de problema como algo: “tudo o que é possível reduzir o problema pela metade a cada iteração”. A busca binária talvez seja o exemplo mais clássico disso. Porém, ela exige que o vetor (array) esteja ordenado para funcionar. Aqui já temos alguns indícios para o futuro, como:

É melhor eu manter meu dado ordenado para buscar depois, ou o custo de manter ordenado é mais alto do que uma busca em uma estrutura não ordenada?

Em relação ao tempo, ele pode ser calculado também pelo logaritmo, suponhamos então:

Vetor com 1 item: log(1) = 0 (menos de 1 segundo)

Vetor com 10 itens: log(10) = 1 (segundo)

Vetor com 100 itens: log(100) = 2 (segundos)

Vetor com 1000 itens: log(1000) = 3 (segundos)

Complexidade Linear -> O(n):
A complexidade linear é, talvez, a mais cotidiana no desenvolvimento comum. Isso porque esta complexidade aumenta no mesmo ritmo que o tamanho da entrada.

Exemplos disso não faltam pois, qualquer iteração que precise percorrer todos os registros dados como entrada, serão, no mínimo, de complexidade linear.
Exemplo:

public static int UnsortedSearch(int[] inputArray, int targetValue)
{
    for (int i = 0; i < inputArray.Length; i++)
    {
        if(inputArray[i] == targetValue)
        {
            return i;
        }
    }

    return -1;
}

Aproveitando-me do assunto “algoritmos de busca”, o exemplo acima vem a calhar. Pois demonstra que, funcionaria para qualquer lista ordenada ou não, ao custo de que o Big-O, seu pior caso, seja “em segundos” o mesmo do tamanho do vetor.
Temos então:

Vetor com 1 item: 1 segundo

Vetor com 10 itens: 10 segundos

Vetor com 100 itens: 100 segundos

Vetor com 1000 itens: 1000 segundos

Complexidade Linearítmica -> O(n log n):
Aqui a explicação pode ser composta das duas últimas complexidades apresentadas, é como se a cada iteração de um algoritmo linear O(n), tivéssemos um passo a mais de complexidade O(log n).
Acredito que, um exemplo mais próximo da realidade ainda seja o Heapsort, que possui um algoritmo em Java e uma explicação muito mais detalhada que a minha aqui.

class HeapSort
{
    public static void Sort(int[] elements)
    {
        BuildHeap(elements);

        for (int swapToPos = elements.Length - 1; swapToPos > 0; swapToPos--)
        {
            ArraySwap(elements, 0, swapToPos);

            Heapify(elements, swapToPos, 0);
        }
    }

    private static void BuildHeap(int[] elements)
    {
        int lastParentNode = elements.Length / 2 - 1;

        for (int i = lastParentNode; i >= 0; i--)
        {
            Heapify(elements, elements.Length, i);
        }
    }

    private static void Heapify(int[] heap, int length, int parentPos)
    {
        while (true)
        {
            int leftChildPos = parentPos * 2 + 1;
            int rightChildPos = parentPos * 2 + 2;

            int largestPos = parentPos;

            if (leftChildPos < length && heap[leftChildPos] > heap[largestPos])
            {
                largestPos = leftChildPos;
            }

            if (rightChildPos < length && heap[rightChildPos] > heap[largestPos])
            {
                largestPos = rightChildPos;
            }

            if (largestPos == parentPos)
            {
                break;
            }

            ArraySwap(heap, parentPos, largestPos);

            parentPos = largestPos;
        }
    }

    private static void ArraySwap(int[] vet, int offset1, int offset2)
    {
        int tmp = vet[offset1];
        vet[offset1] = vet[offset2];
        vet[offset2] = tmp;
    }
}

Algoritmos dessa categoria costumam aparecer como “nem tão eficientes como os lineares, nem tão lentos como os exponenciais”.

O tempo aqui é, também, a soma dos dois tempos anteriores.

Complexidade Quadrática -> O(N2):
Esta complexidade é facilmente sintetizável, pois a analogia é muito clara: quando possuímos uma repetição dentro da outra (for dentro de for). Uma vez que adicionarmos uma repetição dentro do bloco de repetições existentes, também aumentamos o expoente da complexidade, exemplo: for dentro de for dentro de for: O(n3).

Costumo avaliar soluções que entram nessa grandeza como as que, inicialmente, possuem um risco maior de serem ineficientes já na sua concepção.

Algoritmos que se enquadram neste grupo são todos os que possuem qualquer semelhança com a construção abaixo:

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        //processamento
    }
}

Aqui a exemplificação de tempos volta a ser útil:

Entrada de tamanho 1 = 1 segundo

Entrada de tamanho 10 = 100 segundos

Entrada de tamanho 100 = 10.000 segundos

Entrada de tamanho 1000 = 1.000.000 segundos

Complexidade Exponencial -> O(2n):
Algoritmos desse grupo normalmente se encaixam em pensamentos como: “quais são os possíveis valores [de uma lista], que juntos, dariam determinado resultado?”, esse pensamento diverge da força bruta por não conter permutações (3+5 é o mesmo que 5+3). Na faculdade os exemplos clássicos são a implementação recursiva da série de Fibonacci ou a Torre de Hanoi. Talvez no dia a dia, o exemplo mais próximo seja algo como “preciso encontrar uma um valor de X, este é dado pela soma de alguns dos itens dessa relação, que não sabemos quais”. Ou coisas como “se posso escolher 3 sabores de pizza, quantas possíveis combinações posso fazer?”. Em resumo, a busca por todos os “subgrupos de um grupo“.

class Subsets
{
    public static List<decimal[]> Create(decimal[] values)
    {
        var result = new List<decimal[]>();
        var subset = new Stack<decimal>();
        int idx = 0;

        Seek(values, result, subset, idx);

        return result;
    }

    private static void Seek(decimal[] values, List<decimal[]> result, Stack<decimal> subset, int index)
    {
        if(subset.Count > 0) result.Add(subset.ToArray());

        for (int i = index; i < values.Length; i++)
        {
            subset.Push(values[i]);

            Seek(values, result, subset, i + 1);

            subset.Pop();
        }
    }
}

Esse algoritmo, inclusive, já foi utilizado por mim, por diversas vezes, para auxiliar alguns setores que trabalhei a encontrar quais valores estavam dando determinada soma, a fim de ajudá-los a encontrar eventuais diferenças financeiras ou contábeis.

Porém, também está no grupo de algoritmos que teremos execuções sempre péssimas de tempos, como podemos ver abaixo:

Entrada de tamanho 1 = 2 segundo

Entrada de tamanho 10 = 1024 segundos

Entrada de tamanho 100 = 1267650600228229401496703205376 segundos

Entrada de tamanho 1000 = ? segundos

Complexidade Fatorial -> O(n!):
Esta linha de problemas é digna de conhecimento, mas não de aprofundamento aqui no blog.
Problemas fatoriais são, em uma exemplificação, os que necessitamos buscar todas as combinações (permutações) possíveis para descobrir o melhor resultado.

Conclusão

O blog não tem a intenção de manter esse viés teórico e sim, tentar trazer problemas tecnológicos enfrentados de forma real.

Porém, é inevitável que ter ideia da complexidade de um algoritmo é passo indispensável para tentar abordar uma nova modalidade de implementação e de ganho de performance.