(Estático) Seleção de contêineres ideais em programas C ++

Olá. Hoje eu gostaria de falar novamente sobre análise estática. E novamente sobre C ++. Somente, diferentemente do PVS-Studio, não procuraremos erros em nossos programas (embora eles procurem não apenas erros), mas também por locais que não foram escritos da maneira ideal. E um desses lugares é escolher um contêiner para os dados no programa. Se eu sou do seu interesse, bem-vindo ao gato!

O problema

No CoreHard 2018 Autumn (uma conferência muito boa, venha), falei sobre como os compiladores C ++ não otimizam bem no momento. E uma das minhas queixas foi que os compiladores não podem otimizar o uso de contêineres em nossos programas. Vejamos alguns exemplos de código.

void foo() { std::vector<int> v(42); } 

Parece que, em um caso tão simples, o compilador deve ser capaz de otimizar essa função e simplesmente lançar uma declaração variável do tipo std :: vector, já que a partir do C ++ 14, o compilador pode remover alocações dinâmicas de memória, mas o compilador não. A razão para isso é que, no momento, apenas um compilador C ++ implementa otimização para remover alocações dinâmicas - Clang. Todos os outros compiladores até agora não sabem como fazer isso. Mas mesmo Clang pode fazer isso em um número limitado de casos.

Nesse caso, poderíamos substituir std :: vector por std :: array, desde que o tamanho do vetor selecionado não seja muito grande, pois podemos não ter pilha suficiente para essa substituição. Essa substituição removerá uma alocação de memória bastante cara para o heap, e a vantagem é que, ao usar std :: array, o compilador já pode lançar std :: array completamente da função!

Se estamos falando sobre otimização de desempenho, propomos considerar o seguinte exemplo:

 void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } } 

Nesse caso, vemos o uso de uma operação extremamente ineficaz no caso da inserção std :: vector no início do contêiner. Todos os programadores de C ++ sabem que isso é extremamente ruim de fazer, pois faz com que todos os elementos sejam alterados todas as vezes, o que leva a grandes custos de cópia / movimentação. Seria muito melhor nesse caso substituí-lo por std :: list, que não importa onde a inserção ocorre, ou std :: deque (embora seja nesse caso que você possa ver claramente que não precisa apenas usar insert. Mas este é apenas um exemplo, não mais :)

Vejamos outro exemplo de código:

 void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } } 

Nesse caso, podemos notar que podemos substituir std :: list sem problemas (sim, eu sei que poucas pessoas o usam) por std :: forward_list. Nesse caso, nesse caso, não perderemos absolutamente nada, mas obteremos economia de memória. Naturalmente, o compilador não faz essa otimização agora.

Um truque semelhante pode ser feito no seguinte exemplo:

 void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } } 

Aqui podemos ver que o que realmente precisamos não é std :: deque, mas std :: stack. Isso não pode ser chamado de otimização, pois std :: stack é um adaptador e, por padrão, ele usa std :: deque dentro (a menos que o usuário especifique o contrário). Aqui, podemos falar mais sobre otimização semântica, ou seja, simplificando o código para entender. Do meu ponto de vista, isso também é importante. Se você perguntar: "Talvez essa substituição também traga um ganho de desempenho?", Responderei: "Talvez. Veja os detalhes da implementação em sua versão da biblioteca padrão. ”

Bem, acho que existem exemplos suficientes. Cada um de vocês também pode criar muitos deles.

Ferramentas usadas

Para implementar o analisador estático, usei o Clang Static Analzyer (CSA) e o Clang Tidy, que fazem parte do pacote LLVM. Escolhi essas ferramentas, pois as considero as mais promissoras entre as ferramentas abertas para análise estática. Além disso, o Clang fornece um dos analisadores de C ++ da mais alta qualidade dos quais outros analisadores estáticos não podem se gabar (a não ser, é claro, que eles usem libclang).

O CSA e o Clang Tidy são analisadores estáticos, ambos parte do LLVM. Qual a diferença? A diferença é que o Clang Tidy foi projetado para escrever verificações simples, que consistem basicamente em encontrar algum tipo de padrão na árvore de sintaxe abstrata, exibindo algum tipo de aviso e possivelmente substituindo-o automaticamente por outro. Você pode aprender mais sobre Clang Tidy aqui .

O CSA foi projetado para escrever verificações mais "sérias" e com uso intensivo de recursos (do ponto de vista da implementação e do ponto de vista do tempo de execução / memória gasta). Lá, por exemplo, um mecanismo de execução simbólico está disponível.

Decidi implementar a verificação no CSA, uma vez que não me parece comum, além disso, no futuro, será cada vez mais difícil. E foi decidido executar o Clang Tidy, pois esse analisador estático tem muitas integrações com vários IDEs.

Como vamos (tentar) resolver problemas

Para começar, vale a pena introduzir algumas restrições bastante fortes, relacionadas principalmente ao fato de que este é apenas um protótipo:

• Análise apenas no nível de funções; Essa limitação significa que não haverá análise entre funções, bem como entre unidades de conversão. A restrição na análise entre funções foi imposta para simplificar a implementação dessa análise e, no futuro, pode ser corrigida com relativa facilidade, executando uma análise estática para toda a unidade de tradução, e não apenas para cada função. A restrição na análise entre unidades de tradução é imposta pelas restrições existentes no CSA, que serão corrigidas em breve (confirmações já estão sendo lançadas no upstream);
• Suporte apenas para um número limitado de contêineres. Isso é relativamente fácil de corrigir no futuro, adicionando novas regras para novos contêineres.
• Use para análise apenas uma árvore de sintaxe abstrata. Já que para a prototipagem, esse é o tipo mais simples de análise. Para resultados mais precisos, é claro, você pode tentar usar pelo menos a execução simbólica, mas esse método tem suas desvantagens. Você pode ler mais sobre métodos aqui .

Agora, o protótipo implementa o seguinte algoritmo simples:

• Primeiro, na árvore de sintaxe abstrata, encontramos os vértices responsáveis ​​por declarar as variáveis ​​de tipo de contêiner que suportamos.
• Em seguida, encontramos as operações relacionadas a esses contêineres, classificamos e salvamos essas informações em um cache temporário.
• Após chegar ao final da função, analisamos as estatísticas coletadas e, com base em regras predefinidas, emitimos uma recomendação sobre o uso de um contêiner.

A classificação das operações de contêineres no momento é a seguinte (será expandida no futuro):

• Adicione um item à parte superior do contêiner.
• Adicionando um item ao meio do contêiner.
• Adicionando um item ao final do contêiner.
• Removendo um item do início do contêiner.
• Removendo um item do meio do contêiner.
• Removendo um item do final do contêiner.

A classificação no momento está incompleta e mesmo nesta lista não funciona corretamente. Por exemplo, a operação de inserção, mesmo que seja realizada no início, o analisador classifica como inserção no meio, embora na verdade não seja.

Combate a falsos positivos

Em qualquer análise estática, os falsos positivos são a principal dor de cabeça. Se houver muitos deles, as mensagens úteis serão perdidas no lixo. Portanto, nesse caso, você deve agir de maneira muito conservadora e emitir avisos somente nos casos em que estivermos realmente confiantes em nossos diagnósticos e poderemos dizer que algo está realmente errado em algum lugar do código.

Se estamos falando sobre otimização de compilador, ainda é mais triste - a otimização adequada não pode alterar o comportamento do programa de acordo com o padrão C ++ (caso contrário, esse otimizador não vale nada). E a otimização também não deve introduzir pessimização :) Então, você deve ter muito mais cuidado com suas decisões.

Nesse analisador, essa luta resultou no fato de que, se o analisador perceber que alguma operação não suportada está sendo executada no momento, a análise desse contêiner será desativada.

Desvantagens e possíveis soluções

Existem vários problemas com este método.

O primeiro problema é que, para o analisador no momento, todas as ramificações do código são igualmente prováveis. Mais precisamente, ele nem conhece ramos diferentes da execução de código.
Isso se traduz em problemas com a análise para algo como este código:

 void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } } 

Muito provavelmente, em nossa aplicação, essas ramificações de código não têm probabilidades iguais de execução, pois no mundo real um ponteiro geralmente indica algo normal, e não nullptr. No mesmo LLVM existem heurísticas estáticas nesse escore. Por exemplo, ele leva em consideração o caso acima ao comparar ponteiros com nullptr e comparar entre si a igualdade de valores de duas variáveis ​​com um ponto flutuante e alguns outros casos interessantes. Mas isso é cada vez mais parecido com muletas e, do meu ponto de vista, a solução real para esse problema é adicionar análise ou instrumentação dinâmica.

O segundo problema é a falta de suporte para contêineres personalizados. Vivemos no mundo do C ++, eles gostam de andar aqui (vamos deixar a discussão dos motivos desse fenômeno nem sempre ruim fora do escopo deste artigo) de tudo, incluindo nossos contêineres. Exemplos incluem o mesmo LLVM, LibreOffice e muitos outros. Nesse sentido, surge a questão - como analisar contêineres que não são da biblioteca STL? Afinal, eu gostaria de incluir análises para o maior número possível de contêineres.

Existem diferentes maneiras de resolver o problema.

A primeira é que o usuário anota seus contêineres de alguma forma (um tipo especial de comentário, atributos C ++, outra coisa). O problema com esse método é que precisamos entender como anotar em geral, quais informações precisamos para uma análise qualitativa. Outro problema pode ser a modificação do código dos contêineres, o que nem sempre é possível.

O segundo método oferece ao usuário um mecanismo para escrever suas próprias regras. No momento, as regras no analisador são costuradas no código-fonte do próprio analisador e, se o usuário quiser adicionar suas próprias regras, ele precisará fazer o download do código-fonte do analisador, montá-lo, descobrir como escrever verificações, escrever, reconstruir etc. Você pode fornecer ao usuário uma maneira de definir suas verificações em algumas DSL, nas quais o usuário grava apenas verificações de seus contêineres e o analisador está envolvido em toda a rotina. Considero esse método mais promissor que o anterior.

Além disso, a substituição automática de contêiner não é suportada, pois essa funcionalidade não está no CSA (mas está no Clang Tidy). Mas, em casos difíceis, executar a AutoCorreção nem sempre é uma tarefa trivial, e o analisador funciona mais provavelmente no modo semi-manual.

Possíveis aplicações

Vejo várias aplicações para esse tipo de análise:

1. Como um analisador estático. Tudo é simples aqui - outro teste de análise estática, que você executa como seu coração deseja (com as mãos, no IDE automaticamente durante o desenvolvimento, no IC, etc.), onde você provavelmente terá uma dica de que em algum lugar poderia pegar um recipiente e melhor.
2. Como otimização no compilador. Em alguns casos, podemos garantir que a substituição do contêiner definitivamente não afetará negativamente o desempenho. Por exemplo, substituindo std :: vector por tamanhos pequenos conhecidos em tempo de compilação por std :: array ou substituindo std :: list por std :: forward_list quando não precisamos de conexão dupla e não tiramos o tamanho da lista. O compilador pode substituir contêineres por outros mais ideais, sem o nosso conhecimento, como já acontece em um grande número de coisas.
3. Como um analisador dinâmico. Essa é a direção que me parece mais promissora para esse tipo de análise. De fato, com a ajuda do conhecimento sobre o perfil de execução do programa, podemos, por exemplo, obter informações tão importantes para nós quanto as probabilidades de cada execução de ramificação de código. E isso é necessário para uma avaliação mais precisa. E com essa análise, você já pode pensar na direção da integração com o PGO ...

Também é importante notar que esse método é aplicável, é claro, não apenas para programas em C ++. Eu realmente gostaria de ver esse tipo de análise / otimização estática no compilador e em outras linguagens de programação. Por exemplo, o analisador estático SAP para ABAP já sabe como realizar análises estáticas de otimização em um nível básico, o que é uma boa notícia. Se você conhece projetos similares para outras linguagens de programação - escreva nos comentários e adicionarei ao artigo!

Trabalhe em direções semelhantes

Para o mundo C ++, não encontrei esses analisadores em lugar algum. Para o mundo ABAP, mencionei o analisador acima, que pode encontrar operações ineficientes para uma parte dos contêineres padrão, mas até onde eu sei, uma análise estática muito simples é implementada lá.

Um trabalho muito mais interessante é o Chameleon - um analisador dinâmico para Java, que é muito inteligente. Eles ajustaram um pouco a JVM e, durante a operação, coletam várias estatísticas sobre o uso de contêineres e, dependendo do perfil de carga atual, selecionam determinados contêineres e os substituem automaticamente durante a operação. Infelizmente, as fontes estão fechadas e não há chance de obtê-las (tentei).

Eu também recomendo olhar para vários trabalhos (existem muitos) no SETL . Neles, os autores também costumavam levantar questões sobre a seleção automática do contêiner.

Referências

1. Implementação atual no github
2. C ++ Rússia 2017: Yuri Efimochev, clang-tidy: uma jornada dentro da árvore de sintaxe abstrata do C ++
3. Camaleão: Seleção Adaptativa de Coleções
4. Guia do analisador estático de clang
5. Bate-papo em russo sobre o desenvolvimento de compiladores no Telegram. Se você estiver interessado, entre, é muito interessante lá. Apenas tome cuidado com o dilúvio - eles o punirão imediatamente :)

Em vez de uma conclusão, eu gostaria de focar no fato de que ele é apenas um protótipo até agora e tem muitos "buracos" na implementação. Neste artigo, só quero compartilhar com você a ideia de uma análise e sua popularização. Bem, talvez alguém esteja interessado neste tópico e haverá um desejo de se conectar ao projeto - eu ficarei feliz apenas! Além disso, você sempre pode coletar este analisador em seu próprio local para experimentá-lo nos seus exemplos de teste.

Se você tem algo para complementar o material, encontrou um problema semelhante ou simplesmente possui algumas informações que podem ser úteis sobre esse tópico - não hesite em compartilhar essas informações nos comentários.

Obrigado pela atenção!