complexidade de tempo de alocação de memória

Question

O que é a complexidade de tempo de alocação dinâmica de memória usando nova, malloc, etc.? Eu sei muito pouco sobre como alocadores de memória são implementados, mas presumo que a resposta é que depende da implementação. Portanto, por favor, responder por alguns dos mais comuns casos / implementações.

Edit: Lembro-me vagamente de ouvir que alocação de pilha é ilimitado, no pior caso, mas eu estou realmente interessado no caso da média / típica.

Answer 1

Uma das coisas que você tem que perceber quando se lida com a notação O é que muitas vezes é muito importante entender o que n é. Se o n é algo relacionado com algo que você pode controlar (por exemplo: o número de elementos em uma lista que você quer classificadas). Então faz sentido olhar duro para isso

Na maioria das implementações de pilha, o seu n é o número de blocos contíguos de memória o gerente está a lidar. Este é decididamente não algo tipicamente sob controle cliente. A única n o cliente realmente tem o controle sobre o tamanho do bloco de memória que ela quer. Muitas vezes isso não tem relação com a quantidade de tempo que o alocador leva. Uma grande n pode ser o mais rápido alocado como uma pequena n , ou pode demorar muito mais tempo, ou pode até mesmo ser unservicable. Tudo isso poderia mudar para o mesmo n , dependendo de como alocações e deallocations de outros clientes anterior entrou. Então, realmente, a menos que você esteja implementando uma pilha, em seguida, a resposta adequada é que ele não é -deterministic .

É por isso que os programadores em tempo real rígidos tentar evitar a alocação dinâmica (após a inicialização).

Answer 2

A complexidade de tempo para um alocador de pilha pode ser diferente em sistemas diferentes, dependendo do que eles podem ser otimizando para.

Em sistemas desktop, o alocador de heap provavelmente usa uma mistura de diferentes estratégias, incluindo cache alocações recentes, listas Lookaside para tamanhos comuns de alocação, caixas de pedaços de memória com certas características de tamanho, etc, para tentar um tempo de alocação de manter baixo, mas também manter gerenciável fragmentação. Veja as notas para a implementação malloc Doug Lea para uma visão geral das várias técnicas que são utilizadas: http: //g.oswego.edu/dl/html/malloc.html

Para sistemas mais simples, uma estratégia de primeiro ajuste ou melhor ajuste pode ser utilizado, com os blocos livres armazenados em uma lista ligada (o que daria um tempo O (N) com N sendo o número de blocos livres). Mas um sistema de armazenamento mais sofisticada, como uma árvore AVL pode ser usado para ser capaz de localizar blocos livres em O (log N) tempo ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).

Um sistema em tempo real pode usar um alocador pilha como TLSF (dois níveis Segregate Fit), que tem um O (1) custo de alocação: http://www.gii.upv.es/tlsf/

Answer 3

Eu acho que geralmente seria O (n), onde n é o número de blocos de memória disponíveis (desde que você tem para digitalizar os blocos de memória disponíveis para encontrar um adequado).

Dito isto, eu vi otimizações que podem torná-lo mais rápido, especificamente a manutenção de várias listas de blocos disponíveis dependendo de suas faixas de tamanho (para blocos menos de 1k estão em uma lista, blocos de 1k a 10k estão em outra lista e assim por diante).

Isto ainda é O (n), no entanto, apenas com uma menor n.

Eu estaria interessado em ver sua fonte que há uma alocação de pilha que é ilimitada (se, por isso, quer dizer que pode demorar para sempre).

Answer 4

Basta verificar como típico alocadores de trabalho.

Um galo-da-ponteiro obras alocador em O (1) , e é um pequeno ' 1 ' para isso.

Para um alocador, alocação de k bytes meios de armazenamento de segregados "devolver o primeiro bloco da lista ( n )", onde List ( n ) é a lista de blocos de n bytes que n> = k . É pode descobrir que List ( n ) está vazio, de modo que um bloco da lista seguinte (List ( 2n )) teria que ser split com ambos os blocos resultantes de n bytes serem colocados List ( n ), e este efeito pode ondulação através de todos os tamanhos availlable, para fazer uma complexidade de o (ns) em que NS é o número de diferentes tamanhos availlable, e ns = log (N) onde N é o tamanho de o maior availlable tamanho do bloco, por isso mesmo que seria pequeno. Na maioria dos casos, especialmente depois de uma série de blocos foram alocados e desalocados, a complexidade é O (1) .

Answer 5

Apenas duas observações:

• TLSF é O (1) no sentido de que é não tem um Loop único; e gerencia até 2Gb. Embora seja muito difícil de acreditar, basta verificar o código.

• Não é verdade que a política de "melhor ajuste" (encontrar o bloco apertado) é o mais adequado para alcançar pequena fragmentação. Está longe de ser trivial para demonstrar esta afirmação, na verdade, não foi formalmente provada, mas há muitas evidências que vão nessa direção. (Tema de pesquisa agradável).