Complexidade temporal de um compilador

54

Estou interessado na complexidade do tempo de um compilador. Claramente, essa é uma pergunta muito complicada, pois há muitos compiladores, opções e variáveis de compilador a serem consideradas. Especificamente, estou interessado em LLVM, mas estaria interessado em quaisquer pensamentos que as pessoas tivessem ou lugares para começar a pesquisar. Um bom google parece trazer pouco à luz.

Meu palpite seria que existem algumas etapas de otimização que são exponenciais, mas que têm pouco impacto no tempo real. Por exemplo, exponencial com base no número são argumentos de uma função.

Do alto da minha cabeça, eu diria que gerar a árvore AST seria linear. A geração de IR exigiria percorrer a árvore enquanto procurava valores em tabelas sempre crescentes, portanto ou . A geração e a vinculação de código seriam um tipo semelhante de operação. Portanto, meu palpite seria se removêssemos exponenciais de variáveis que não crescem realisticamente. $O(n^2)$ $O(n\log n)$ $O(n^2)$

Eu poderia estar completamente errado. Alguém tem alguma opinião sobre isso?

compilers superbriggs
fonte

7

Você deve ter cuidado ao afirmar que qualquer coisa é "exponencial", "linear", ou . Pelo menos para mim, não é de todo óbvio como você medir o seu input (exponencial no que o que faz? representa?)

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n \log n)$

n

$n$

Juho

2

Quando você diz LLVM, você quer dizer Clang? O LLVM é um grande projeto com vários subprojetos diferentes do compilador, por isso é um pouco ambíguo.

Nate CK

5

Para C #, é pelo menos exponencial para problemas de pior caso (você pode codificar o problema SAT completo do NP em C #). Isso não é apenas otimização, é necessário para escolher a sobrecarga correta de uma função. Para uma linguagem como C ++, será indecidível, pois os modelos estão completos.

CodesInChaos

2

@ Zane Eu não entendo o seu ponto. A instanciação do modelo acontece durante a compilação. Você pode codificar problemas difíceis em modelos de uma maneira que force o compilador a resolver esse problema para produzir uma saída correta. Você pode considerar o compilador um intérprete da linguagem de programação de modelos completa turing.

CodesInChaos

3

A resolução de sobrecarga em C # é bastante complicada quando você combina várias sobrecargas com expressões lambda. Você pode usar isso para codificar uma fórmula booleana de tal maneira que determinar se há uma sobrecarga aplicável requer o problema NS-complete 3SAT. Para realmente compilar o problema, o compilador precisa encontrar a solução para essa fórmula, que pode ser ainda mais difícil. Eric Lippert fala sobre isso em detalhes em seu blog expressões lambda vs. Métodos anônimos, Parte V

CodesInChaos

50

O melhor livro para responder sua pergunta provavelmente seria: Cooper e Torczon, "Engineering a Compiler", 2003. Se você tiver acesso a uma biblioteca universitária, poderá emprestar uma cópia.

Em um compilador de produção como llvm ou gcc, os designers fazem todos os esforços para manter todos os algoritmos abaixo de que é o tamanho da entrada. Para algumas análises para as fases de "otimização", isso significa que você precisa usar heurísticas em vez de produzir um código realmente ideal. $O(n^2)$ $n$

O lexer é uma máquina de estados finitos, portanto no tamanho da entrada (em caracteres) e produz um fluxo de tokens que são passados para o analisador. $O(n)$ $O(n)$

Para muitos compiladores para vários idiomas, o analisador é LALR (1) e, portanto, processa o fluxo de token no tempo no número de tokens de entrada. Durante a análise, você normalmente precisa acompanhar uma tabela de símbolos, mas, para muitos idiomas, isso pode ser tratado com uma pilha de tabelas de hash ("dicionários"). Cada acesso ao dicionário é , mas você pode ocasionalmente ter que percorrer a pilha para procurar um símbolo. A profundidade da pilha é onde é a profundidade de aninhamento dos escopos. (Então, em idiomas do tipo C, quantas camadas de chaves você possui.) $O(n)$ $O(1)$ $O(s)$ $s$

Em seguida, a árvore de análise é normalmente "achatada" em um gráfico de fluxo de controle. Os nós do gráfico de fluxo de controle podem ser instruções com três endereços (semelhante a uma linguagem de montagem RISC), e o tamanho do gráfico de fluxo de controle normalmente será linear no tamanho da árvore de análise.

Em seguida, uma série de etapas de eliminação de redundância é normalmente aplicada (eliminação de subexpressão comum, movimento invariante do código do loop, propagação constante, ...). (Isso geralmente é chamado de "otimização", embora raramente haja algo ideal sobre o resultado, o objetivo real é melhorar o código o máximo possível dentro das restrições de tempo e espaço que colocamos no compilador.) Cada etapa de eliminação de redundância será normalmente exigem provas de alguns fatos sobre o gráfico de fluxo de controle. Essas provas geralmente são feitas usando a análise de fluxo de dados . A maioria das análises de fluxo de dados é projetada para convergir em passa sobre o gráfico de fluxo, onde é (grosso modo) a profundidade de aninhamento do loop e uma passagem sobre o gráfico de fluxo leva tempo $O(d)$ $d$ $O(n)$ onde é o número de instruções com três endereços. $n$

Para otimizações mais sofisticadas, convém fazer análises mais sofisticadas. Nesse ponto, você começa a encontrar trocas. Você deseja que seus algoritmos de análise tomem muito menos que $O(n^2)$ tempo no tamanho do gráfico de fluxo do programa inteiro, mas isso significa que você precisa ficar sem informações (e com o programa melhorando as transformações) que podem ser caras de provar. Um exemplo clássico disso é a análise de alias, em que, para alguns pares de gravações de memória, você gostaria de provar que as duas gravações nunca podem atingir o mesmo local de memória. (Você pode fazer uma análise de alias para ver se é possível mover uma instrução acima da outra.) Mas, para obter informações precisas sobre alias, pode ser necessário analisar todos os caminhos de controle possíveis no programa, o que é exponencial no número de ramificações no programa (e, portanto, exponencial no número de nós no gráfico de fluxo de controle.)

Em seguida, você entra na alocação de registros. A alocação de registro pode ser formulada como um problema de coloração de gráfico, e sabe-se que a coloração de um gráfico com um número mínimo de cores é NP-Hard. Portanto, a maioria dos compiladores usa algum tipo de heurística gananciosa combinada com derramamento de registro, com o objetivo de reduzir o número de derramamentos de registro da melhor forma possível, dentro de um prazo razoável.

Finalmente, você entra na geração de código. A geração de código geralmente é realizada como um bloco básico máximo no momento em que um bloco básico é um conjunto de nós de gráfico de fluxo de controle conectados linearmente com uma única entrada e uma única saída. Isso pode ser reformulado como um problema de cobertura de gráfico, onde o gráfico que você está tentando cobrir é o gráfico de dependência do conjunto de instruções de 3 endereços no bloco básico e você está tentando cobrir com um conjunto de gráficos que representam a máquina disponível instruções. Esse problema é exponencial no tamanho do maior bloco básico (que poderia, em princípio, ser da mesma ordem que o tamanho de todo o programa); portanto, isso normalmente é feito com heurísticas, onde apenas um pequeno subconjunto das coberturas possíveis é examinado.

Lógica Errante
fonte

4

Thirded! Aliás, muitos dos problemas que os compiladores tentam resolver (por exemplo, alocação de registros) são difíceis de NP, mas outros são formalmente indecidíveis. Suponha, por exemplo, que você tenha uma chamada p () seguida por uma chamada q (). Se p for uma função pura, você poderá reordenar as chamadas com segurança, desde que p () não faça um loop infinito. Para provar isso, é necessário resolver o problema da parada. Assim como nos problemas difíceis de NP, um gravador de compilador poderia colocar tanto ou pouco esforço na aproximação de uma solução quanto possível.

Pseudônimo

4

Ah, mais uma coisa: existem alguns tipos de sistemas em uso hoje que são muito complexos em teoria. A inferência do tipo Hindley-Milner é conhecida pelo DEXPTIME-complete e as linguagens do tipo ML devem implementá-lo corretamente. No entanto, o tempo de execução é linear na prática porque a) casos patológicos nunca aparecem em programas do mundo real eb) programadores do mundo real tendem a inserir anotações de tipo, apenas para obter melhores mensagens de erro.

Pseudônimo

11

Ótima resposta, a única coisa que parece estar faltando é a parte simples da explicação, explicitada em termos simples: A compilação de um programa pode ser feita em O (n). Otimizar um programa antes da compilação, como faria qualquer compilador moderno, é uma tarefa praticamente ilimitada. O tempo que realmente leva não é governado por nenhum limite inerente da tarefa, mas pela necessidade prática de o compilador terminar em algum momento antes que as pessoas se cansem de esperar. É sempre um compromisso.

Aaaaaaaaaaaa

@ Pseudônimo, o fato de que muitas vezes o compilador precisaria resolver o problema de parada (ou problemas difíceis de NP muito desagradáveis) é uma das razões pelas quais os padrões dão ao escritor do compilador uma margem de manobra ao assumir que comportamento indefinido não acontece (como loops infinitos e outras coisas). )

vonbrand

15

Na verdade, algumas linguagens (como C ++, Lisp e D) são completas em Turing em tempo de compilação, portanto, compilá-las é indecidível em geral. Para C ++, isso ocorre devido à instanciação recursiva do modelo. Para Lisp e D, você pode executar praticamente qualquer código em tempo de compilação, para poder lançar o compilador em um loop infinito, se desejar.

Demi
fonte

3

Os sistemas de tipo Haskell (com extensões) e Scala também são completos em Turing, o que significa que a verificação de tipo pode levar uma quantidade infinita de tempo. O Scala agora também possui macros completas de Turing.

Jörg W Mittag

5

Da minha experiência real com o compilador C #, posso dizer que, para certos programas, o tamanho do binário de saída cresce exponencialmente em relação ao tamanho da fonte de entrada (isso é realmente exigido pela especificação C # e não pode ser reduzido), portanto, a complexidade do tempo deve ser pelo menos exponencial também.

A tarefa geral de resolução de sobrecarga em C # é conhecida como NP-hard (e a complexidade real da implementação é pelo menos exponencial).

Um processamento de comentários de documentação XML em fontes C # também requer a avaliação de expressões XPath 1.0 arbitrárias em tempo de compilação, que também é exponencial, AFAIK.

Vladimir Reshetnikov
fonte

O que faz os binários C # explodirem dessa maneira? Soa como um bug de linguagem para mim ...

vonbrand 10/03

11

É a maneira como os tipos genéricos são codificados nos metadados. class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } }

Vladimir Reshetnikov

-2

Avalie-o com bases de código realistas, como um conjunto de projetos de código aberto. Se você plotar os resultados como (codeSize, finishTime), poderá plotar esses gráficos. Se seus dados f (x) = y são O (n), a plotagem de g = f (x) / x deve fornecer uma linha reta depois que os dados começam a ficar grandes.

Plote f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x) etc. O gráfico mergulhará para zero, aumente sem limite ou achatar. Essa idéia é útil para situações como medir o tempo de inserção a partir de um banco de dados vazio (ou seja, procurar um 'vazamento de desempenho' por um longo período).

Roubar
fonte

11

A medição empírica dos tempos de execução não estabelece complexidade computacional. Primeiro, a complexidade computacional é mais comumente expressa em termos de pior caso de tempo de execução. Segundo, mesmo se você quiser medir algum tipo de caso médio, precisará estabelecer que suas entradas são "médias" nesse sentido.

David Richerby

Bem, com certeza é apenas uma estimativa. Mas testes empíricos simples com muitos dados reais (todos os commit para vários repositórios git) podem muito bem superar um modelo cuidadoso. De qualquer forma, se uma função realmente é O (n ^ 3) e você plota f (n) / (n n n), deve obter uma linha barulhenta com uma inclinação de aproximadamente zero. Se você plotasse O (n ^ 3) / (n * n) somente, veria o aumento linear. É realmente óbvio se você superestimar e assistir a linha mergulhar rapidamente em zero.

Rob

11

Não. Por exemplo, o quicksort é executado no tempo na maioria dos dados de entrada, mas algumas implementações possuem no pior dos casos (normalmente, na entrada que já está classificada). No entanto, se você apenas plotar o tempo de execução, é muito mais provável que você encontre os casos que os casos .

Θ (n \log n)

$\Theta(n\log n)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n \log n)

$\Theta(n\log n)$

Θ (n^{2})

$\Theta(n^2)$

David Richerby

Concordo que é o que você precisa saber se estiver preocupado em receber uma negação de serviço de um invasor, fornecendo informações incorretas e realizando análises críticas em tempo real. A função real que mede os tempos de compilação será muito barulhenta, e o caso com o qual nos preocupamos será em repositórios de códigos reais.

Rob

11

Não. A pergunta é sobre a complexidade temporal do problema. Normalmente, isso é interpretado como o pior tempo de execução, o que não é enfaticamente o tempo de execução no código nos repositórios. Os testes que você propõe fornecem um controle razoável de quanto tempo você espera que o compilador execute em um determinado trecho de código, o que é uma coisa boa e útil de se saber. Mas eles não dizem quase nada sobre a complexidade computacional do problema.

David Richerby

Complexidade temporal de um compilador

Respostas: