É possível prever estaticamente quando desalocar memória --- apenas do código-fonte?

27

Memória (e bloqueios de recursos) são retornados ao sistema operacional em pontos determinísticos durante a execução de um programa. O fluxo de controle de um programa por si só é suficiente para saber onde, com certeza, um determinado recurso pode ser desalocado. Assim como um programador humano sabe onde escrever fclose(file)quando o programa termina.

Os GCs resolvem isso descobrindo isso diretamente durante o tempo de execução quando o fluxo de controle é executado. Mas a verdadeira fonte de verdade sobre o fluxo de controle é a fonte. Então, teoricamente, deve ser possível determinar onde inserir as free()chamadas antes da compilação analisando a fonte (ou AST).

A contagem de referências é uma maneira óbvia de implementar isso, mas é fácil encontrar situações em que os ponteiros ainda são referenciados (ainda no escopo) e ainda não são mais necessários. Isso apenas converte a responsabilidade de desalocar manualmente os ponteiros em uma responsabilidade de gerenciar manualmente o escopo / referências a esses ponteiros.

Parece que é possível escrever um programa que possa ler a fonte de um programa e:

  1. prever todas as permutações do fluxo de controle do programa - com precisão semelhante à da execução ao vivo do programa
  2. acompanhar todas as referências aos recursos alocados
  3. para cada referência, percorra todo o fluxo de controle subsequente para encontrar o ponto mais antigo em que a referência é garantida como nunca desreferenciada
  4. nesse ponto, insira uma declaração de desalocação nessa linha de código-fonte

Existe alguma coisa lá fora que já faz isso? Não acho que Rust ou C ++ ponteiros inteligentes / RAII sejam a mesma coisa.

zelcon
fonte
57
procure o problema da parada. É o avô do motivo pelo qual a pergunta "Um compilador não consegue descobrir se um programa faz X?" sempre é respondido com "Não no caso geral".
catraca aberração
18
Memória (e bloqueios de recursos) são retornados ao sistema operacional em pontos determinísticos durante a execução de um programa. No.
Eufórico 07/03
9
@ratchetfreak Obrigado, nem sempre é possível saber coisas como esse problema de interrupção que me faz desejar obter meu diploma em ciência da computação em vez de química.
Zelcon
15
@ zelcon5, você já sabe sobre a química e o problema da parada ... :)
David Arno
7
@Euphoric a menos que você estruturar seu programa para os limites de quando é utilizado um recurso é muito claro como com RAII ou tente-com-recursos
catraca aberração

Respostas:

23

Veja este exemplo (artificial):

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

Quando o free deve ser chamado? antes malloc e atribuir a resource1nós não podemos, porque pode ser copiado pararesource2 , antes de atribuir a resource2nós não podemos porque podemos ter obtido 2 do usuário duas vezes sem um 1 interveniente.

A única maneira de ter certeza é testar o recurso1 e o recurso2 para ver se eles não são iguais nos casos 1 e 2 e liberar o valor antigo, caso não o sejam. Esta é essencialmente a contagem de referências, onde você sabe que existem apenas 2 referências possíveis.

catraca arrepiante
fonte
Na verdade, esse não é o único caminho; a outra maneira é permitir que apenas uma cópia exista. Isso, é claro, vem com seus próprios problemas.
precisa saber é o seguinte
27

RAII não é automaticamente a mesma coisa, mas tem o mesmo efeito. Ele fornece uma resposta fácil para a pergunta "como você sabe quando isso não pode mais ser acessado?" usando o escopo para cobrir a área quando um recurso específico está sendo usado.

Você pode considerar o problema semelhante "como posso saber que meu programa não sofrerá um erro de tipo em tempo de execução?". A solução para isso não é prever todos os caminhos de execução no programa, mas usar um sistema de anotação e inferência de tipo para provar que não pode haver esse erro. Ferrugem é uma tentativa de estender essa propriedade de prova à alocação de memória.

É possível escrever provas sobre o comportamento do programa sem precisar resolver o problema de interrupção, mas apenas se você usar anotações de algum tipo para restringir o programa. Veja também provas de segurança (sel4 etc.)

pjc50
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Maple_shaft
13

Sim, isso existe na natureza. O ML Kit é um compilador de qualidade de produção que possui a estratégia descrita (mais ou menos) como uma de suas opções de gerenciamento de memória disponíveis. Ele também permite o uso de um GC convencional ou a hibridação com contagem de referência (você pode usar um criador de perfil de heap para ver qual estratégia realmente produzirá os melhores resultados para o seu programa).

Uma retrospectiva sobre gerenciamento de memória com base na região é um artigo dos autores originais do ML Kit que aborda seus sucessos e falhas. A conclusão final é que a estratégia é prática ao escrever com a ajuda de um criador de perfil de heap.

(Esta é uma boa ilustração de por que você normalmente não deve procurar no Problema da Parada uma resposta a questões práticas de engenharia: não queremos ou precisamos resolver o caso geral dos programas mais realistas.)

Leushenko
fonte
5
Penso que este é um excelente exemplo de aplicação adequada do Problema da Parada. O problema de interrupção nos diz que o problema é insolúvel no caso geral, portanto, procure cenários limitados nos quais o problema é solucionável.
Taemyr
Note-se que o problema se torna muito mais solucionável quando falamos, não-secundários efetuando línguas puro ou quase puro funcionais como ML padrão e Haskell
cat
10

prever todas as permutações do fluxo de controle do programa

É aqui que está o problema. A quantidade de permutações é tão grande (na prática é infinita) para qualquer programa não trivial que o tempo e a memória necessários tornariam isso completamente impraticável.

Eufórico
fonte
bom ponto. Eu acho processadores quânticos são a única esperança, se há algum em tudo
Zelcon
4
@ zelcon5 Haha, não. A computação quântica torna isso pior , não melhor. Ele adiciona variáveis ​​adicionais ("ocultas") ao programa e muito mais incerteza. O código QC mais prático que eu já vi depende do "quantum para computação rápida, clássico para confirmação". Eu mal arranhei a superfície na computação quântica, mas parece-me que os computadores quânticos podem não ser muito úteis sem os computadores clássicos para fazer backup deles e verificar seus resultados.
Luaan 8/03/16
8

O problema de parada prova que isso não é possível em todos os casos. No entanto, ainda é possível em muitos casos e, de fato, é feito por quase todos os compiladores para provavelmente a maioria das variáveis. É assim que um compilador pode dizer que é seguro apenas alocar uma variável na pilha ou mesmo em um registro, em vez de em um armazenamento heap de longo prazo.

Se você possui funções puras ou semântica de propriedade realmente boa, pode estender ainda mais essa análise estática, embora se torne proibitivamente mais caro fazê-lo, quanto mais ramificações o código tiver.

Karl Bielefeldt
fonte
Bem, o compilador pensa que pode liberar a memória; mas pode não ser assim. Pense no erro comum do iniciante para retornar um ponteiro ou uma referência a uma variável local. Os casos triviais são capturados pelo compilador, true; os menos triviais não são.
Peter - Restabelece Monica
Esse erro é cometido por programadores em linguagens em que os programadores devem gerenciar manualmente a alocação de memória @Peter. Quando o compilador gerencia a alocação de memória, esses tipos de erros não acontecem.
Karl Bielefeldt
Bem, você fez uma declaração muito geral, incluindo a frase "quase todos os compiladores", que deve incluir compiladores C.
Peter - Restabelece Monica
2
Os compiladores C o utilizam para determinar quais variáveis ​​temporárias podem ser alocadas aos registradores.
Karl Bielefeldt
4

Se um único programador ou equipe escrever o programa inteiro, é razoável que os pontos de design possam ser identificados onde a memória (e outros recursos) deve ser liberada. Assim, sim, a análise estática do design pode ser suficiente em contextos mais limitados.

No entanto, quando você considera DLLs, APIs, estruturas (e também lança threads) de terceiros, pode ser muito difícil (ou seja, impossível em todos os casos) para os programadores em uso raciocinar corretamente sobre qual entidade possui qual memória e quando é o último uso dele. Nosso suspeito usual de linguagens não documenta suficientemente a transferência da propriedade da memória de objetos e matrizes, superficial e profunda. Se um programador não pode argumentar sobre isso (estaticamente ou dinamicamente!), Então um compilador provavelmente também não pode. Novamente, isso se deve ao fato de que as transferências de propriedade da memória não são capturadas em chamadas de método ou interfaces, etc., portanto, não é possível prever estaticamente quando ou onde no código para liberar memória.

Como esse é um problema tão sério, muitos idiomas modernos escolhem a coleta de lixo, que recupera automaticamente a memória algum tempo após a última referência ao vivo. O GC tem um custo de desempenho significativo (especialmente para aplicativos em tempo real), portanto, isso não é uma cura universal para todos. Além disso, você ainda pode ter vazamentos de memória usando o GC (por exemplo, uma coleção que cresce apenas). Ainda assim, esta é uma boa solução para a maioria dos exercícios de programação.

Existem algumas alternativas (algumas emergentes).

A linguagem Rust leva o RAII ao extremo. Ele fornece construções linguísticas que definem a transferência de propriedade em métodos de classes e interfaces com mais detalhes, por exemplo, objetos sendo transferidos para emprestados entre emprestadores e usuários, ou em objetos de vida útil mais longa. Ele fornece um alto nível de segurança no tempo de compilação para o gerenciamento de memória. No entanto, não é uma linguagem trivial, e também não deixa de ter problemas (por exemplo, não acho que o design seja totalmente estável, algumas coisas ainda estão sendo experimentadas e, portanto, estão sendo alteradas).

Swift e Objective-C seguem outra rota, que é a contagem de referência principalmente automática. A contagem de referências entra em problemas com os ciclos e, há desafios significativos para programadores, por exemplo, especialmente com fechamentos.

Erik Eidt
fonte
3
Claro, o GC tem custos, mas também possui benefícios de desempenho. Por exemplo, no .NET, a alocação a partir da pilha é quase gratuita, porque ela usa o padrão de "alocação de pilha" - basta incrementar um ponteiro, e é isso. Vi aplicativos que são executados mais rapidamente reescritos em torno do .NET GC do que eles usavam alocação manual de memória; na verdade, isso não é claro. Da mesma forma, a contagem de referência é realmente muito cara (apenas em locais diferentes de um GC) e algo que você não deseja pagar se puder evitá-lo. Se você deseja desempenho em tempo real, a alocação estática geralmente ainda é a única maneira.
Luaan 8/03/16
2

Se um programa não depende de nenhuma entrada desconhecida, sim, deve ser possível (com a ressalva de que pode ser uma tarefa complexa e pode levar muito tempo; mas isso também se aplica ao programa). Esses programas seriam completamente solucionáveis ​​em tempo de compilação; em termos de C ++, eles poderiam ser (quase) completamente compostos de constexprs. Exemplos simples seriam calcular os 100 primeiros dígitos de pi ou classificar um dicionário conhecido.

Peter - Restabelecer Monica
fonte
2

Liberar memória, em geral, é equivalente ao problema de interrupção - se você não pode dizer estaticamente se um programa será interrompido (estaticamente), também não é possível dizer se ele liberará memória (estaticamente).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Dito isto, Rust é muito legal ... https://doc.rust-lang.org/book/ownership.html

fadedbee
fonte