Sim, gc é amortizado em tempo constante. Suponha que você tenha um algoritmo que é executado no tempo com um conjunto de trabalho de pico do tamanho . Agora, observe que você pode alocar no máximo palavras durante a execução do programa e que o custo de tempo para executar um coletor de lixo de cópia é (ou seja, o custo de um gc é proporcional ao total quantidade de dados ativos). Portanto, se você executar o gc no máximo em , o custo total de tempo de execução será limitado por , o que significa que o custo amortizado do gc é constante. Portanto, se você tiver um coletor no estilo Cheney, com cada semi-espaço com tamanho , é fácil ver que uma coleção completa não pode ser chamada mais de uma vez a cadak O ( n ) O ( k ) O ( n / k ) O ( n ) 2 k n / knkO ( n )O ( k )O ( n / k )O ( n )2 kn / k etapas, já que alocar palavras leva e o conjunto de trabalho nunca excede o tamanho , o que lhe dá o limite que você deseja. Isso justifica ignorar os problemas do GC.O ( k ) kkO(k)k
No entanto, um caso em que a presença ou ausência de gc não é ignorável é ao escrever estruturas de dados sem bloqueio. Muitas estruturas de dados modernas sem bloqueio deliberadamente vazam memória e dependem do gc para correção. Isso ocorre porque, em um nível alto, a maneira como eles funcionam é copiar alguns dados, fazer alterações e tentar atualizá-los atomicamente com uma instrução CAS e executá-los em loop até que o CAS seja bem-sucedido. Adicionar desalocação determinística a esses algoritmos os torna muito mais complexos e, portanto, as pessoas geralmente não se incomodam (especialmente porque são frequentemente direcionadas a ambientes semelhantes a Java).
EDIT: Se você quiser limites não amortizados, o coletor Cheney não fará isso - ele verifica todo o conjunto ao vivo toda vez que é chamado. A palavra-chave para o google é "coleta de lixo em tempo real" e Djikstra et al. e Steele deu os primeiros coletores de marcação e varredura em tempo real, e Baker deu o primeiro compacto em tempo real gc.
@article {dijkstra1978fly,
title = {{Coleta de lixo em tempo real: um exercício de cooperação}},
author = {Dijkstra, EW e Lamport, L. e Martin, AJ e Scholten, CS e Steffens, EFM},
journal = {Comunicações da ACM},
volume = {21},
number = {11},
pages = {966--975},
issn = {0001-0782},
ano = {1978},
editor = {ACM}
}
@article {steele1975multiprocessamento,
title = {{Multiprocessando a compactação de coleta de lixo}},
author = {Steele Jr, GL},
journal = {Comunicações da ACM},
volume = {18},
número = {9},
pages = {495--508},
issn = {0001-0782},
ano = {1975},
editor = {ACM}
}
@article {baker1978list,
title = {{Processamento da lista em tempo real em um computador serial}},
author = {Baker Jr, HG},
journal = {Comunicações da ACM},
volume = {21},
number = {4},
pages = {280--294},
issn = {0001-0782},
ano = {1978},
editor = {ACM}
}
List.map
no OCaml é na verdade complexidade quadrática, porque a profundidade da pilha é linear e a pilha é percorrida toda vez que o berçário é evacuado. O mesmo vale para as principais fatias que encontram grandes matrizes de ponteiros.A referência definitiva à coleta de lixo é:
Ben Zorn fez algum trabalho para medir os custos reais de diferentes algoritmos de coleta de lixo, embora o artigo a seguir seja mais recente apresente uma comparação muito mais abrangente:
Para mais informações, consulte:
fonte