O que é fragmentação de memória?

Eu ouvi o termo "fragmentação de memória" usado algumas vezes no contexto de alocação de memória dinâmica em C ++. Encontrei algumas perguntas sobre como lidar com a fragmentação da memória, mas não consigo encontrar uma pergunta direta que lide com ela mesma. Assim:

• O que é fragmentação de memória?
• Como posso saber se a fragmentação da memória é um problema para o meu aplicativo? Que tipo de programa tem maior probabilidade de sofrer?
• Quais são as boas maneiras comuns de lidar com a fragmentação da memória?

Além disso:

• Ouvi dizer que o uso de alocações dinâmicas pode aumentar a fragmentação da memória. Isso é verdade? No contexto do C ++, eu entendo que todos os contêineres padrão (std :: string, std :: vector, etc) usam alocação dinâmica de memória. Se eles são usados ​​em um programa (especialmente std :: string), a fragmentação da memória tem mais chances de ser um problema?
• Como a fragmentação da memória pode ser tratada em um aplicativo pesado para STL?

Imagine que você tem uma extensão "grande" (32 bytes) de memória livre:

----------------------------------
|                                |
----------------------------------

Agora, aloque parte dele (5 alocações):

----------------------------------
|aaaabbccccccddeeee              |
----------------------------------

Agora, liberte as quatro primeiras alocações, mas não a quinta:

----------------------------------
|              eeee              |
----------------------------------

Agora, tente alocar 16 bytes. Opa, eu não posso, mesmo que haja quase o dobro disso de graça.

Em sistemas com memória virtual, a fragmentação é um problema menor do que você imagina, porque grandes alocações precisam ser contíguas no espaço de endereço virtual , não no espaço de endereço físico . Portanto, no meu exemplo, se eu tivesse memória virtual com um tamanho de página de 2 bytes, poderia fazer minha alocação de 16 bytes sem nenhum problema. A memória física ficaria assim:

----------------------------------
|ffffffffffffffeeeeff            |
----------------------------------

Considerando que a memória virtual (sendo muito maior) poderia ser assim:

------------------------------------------------------...
|              eeeeffffffffffffffff                   
------------------------------------------------------...

O sintoma clássico da fragmentação da memória é que você tenta alocar um bloco grande e não pode, mesmo que pareça ter memória livre suficiente. Outra conseqüência possível é a incapacidade do processo de liberar memória de volta para o sistema operacional (porque ainda há algum objeto em uso em todos os blocos que foram alocados no sistema operacional, mesmo que esses blocos agora não sejam mais utilizados).

As táticas para impedir a fragmentação da memória no C ++ funcionam alocando objetos de diferentes áreas, de acordo com seu tamanho e / ou vida útil esperada. Portanto, se você criar muitos objetos e destruí-los juntos mais tarde, aloque-os a partir de um conjunto de memórias. Quaisquer outras alocações que você fizer entre eles não serão do pool, portanto, não serão localizadas entre eles na memória; portanto, a memória não será fragmentada como resultado.

Geralmente, você não precisa se preocupar muito, a menos que seu programa seja de longa duração e faça muita alocação e liberação. É quando você tem misturas de objetos de vida curta e longa que você corre mais risco, mas mesmo assim mallocfará o possível para ajudar. Basicamente, ignore-o até que seu programa tenha falhas de alocação ou inesperadamente faça com que o sistema fique com pouca memória (pegue isso nos testes, de preferência!).

As bibliotecas padrão não são piores do que qualquer outra coisa que aloca memória e todos os contêineres padrão possuem um Allocparâmetro de modelo que você pode usar para ajustar sua estratégia de alocação, se for absolutamente necessário.

O que é fragmentação de memória?

A fragmentação da memória ocorre quando a maior parte da memória é alocada em um grande número de blocos ou blocos não contíguos - deixando uma boa porcentagem da memória total não alocada, mas inutilizável para os cenários mais comuns. Isso resulta em exceções de falta de memória ou erros de alocação (ou seja, malloc retorna nulo).

A maneira mais fácil de pensar sobre isso é imaginar que você tem uma grande parede vazia e precisa colocar fotos de tamanhos variados . Cada foto ocupa um determinado tamanho e você obviamente não pode dividi-la em pedaços menores para ajustá-la. Você precisa de um espaço vazio na parede, do tamanho da imagem, ou não pode colocá-lo. Agora, se você começar a pendurar fotos na parede e não tomar cuidado com a forma de organizá-las, em breve você terminará com uma parede parcialmente coberta por fotos e mesmo que você tenha pontos vazios, a maioria das novas fotos não caberá porque são maiores que os pontos disponíveis. Você ainda pode pendurar fotos muito pequenas, mas a maioria não serve. Então você terá que reorganizar (compactar) os que já estão na parede para abrir espaço para mais ..

Agora, imagine que a parede é sua (pilha) de memória e as imagens são objetos. Isso é fragmentação da memória.

Como posso saber se a fragmentação da memória é um problema para o meu aplicativo? Que tipo de programa tem maior probabilidade de sofrer?

Um sinal revelador de que você pode estar lidando com a fragmentação da memória é se você receber muitos erros de alocação, especialmente quando a porcentagem de memória usada for alta - mas ainda não tiver esgotado toda a memória -, portanto, tecnicamente, você deve ter muito espaço para os objetos que você está tentando alocar.

Quando a memória está muito fragmentada, as alocações de memória provavelmente demoram mais, porque o alocador de memória precisa trabalhar mais para encontrar um espaço adequado para o novo objeto. Se, por sua vez, você tiver muitas alocações de memória (o que provavelmente ocorre desde que terminou com a fragmentação da memória), o tempo de alocação pode até causar atrasos visíveis.

Quais são as boas maneiras comuns de lidar com a fragmentação da memória?

Use um bom algoritmo para alocar memória. Em vez de alocar memória para muitos objetos pequenos, pré-aloque memória para uma matriz contígua desses objetos menores. Às vezes, desperdiçar um pouco na alocação de memória pode prejudicar o desempenho e poupar o trabalho de lidar com a fragmentação da memória.

Fragmentação de memória é o mesmo conceito que fragmentação de disco: refere-se ao desperdício de espaço, porque as áreas em uso não são compactadas o suficiente.

Suponha que, para um exemplo simples de brinquedo, você tenha dez bytes de memória:

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Agora vamos alocar três blocos de três bytes, nomes A, B e C:

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Agora desaloque o bloco B:

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Agora, o que acontece se tentarmos alocar um bloco de quatro bytes D? Bem, temos quatro bytes de memória livre, mas não temos quatro contíguos bytes de memória livre, portanto não podemos alocar D! Esse é um uso ineficiente da memória, porque deveríamos ter conseguido armazenar D, mas não conseguimos. E não podemos mover C para liberar espaço, porque muito provavelmente algumas variáveis ​​em nosso programa estão apontando para C e não podemos encontrar e alterar automaticamente todos esses valores.

Como você sabe que é um problema? Bem, o maior sinal é que o tamanho da memória virtual do seu programa é consideravelmente maior que a quantidade de memória que você está realmente usando. Em um exemplo do mundo real, você teria muito mais que dez bytes de memória; portanto, D seria alocado a partir de um byte 9 e os bytes 3-5 permaneceriam sem uso, a menos que você alocasse algo com três bytes de comprimento ou menos.

Neste exemplo, 3 bytes não são muito desperdiçados, mas considere um caso mais patológico em que duas alocações de um par de bytes estão, por exemplo, com dez megabytes de memória e você precisa alocar um bloco de tamanho 10 megabytes + 1 byte. Você precisa solicitar ao sistema operacional mais de dez megabytes de memória virtual para fazer isso, mesmo que você tenha apenas um byte de espaço suficiente.

Como você evita isso? Os piores casos tendem a surgir quando você cria e destrói objetos pequenos com freqüência, pois isso tende a produzir um efeito de "queijo suíço" com muitos objetos pequenos separados por muitos buracos pequenos, tornando impossível alocar objetos maiores nesses buracos. Quando você sabe que vai fazer isso, uma estratégia eficaz é pré-alocar um grande bloco de memória como um pool para seus pequenos objetos e, em seguida, gerenciar manualmente a criação dos pequenos objetos dentro desse bloco, em vez de permitir o alocador padrão lida com isso.

Em geral, quanto menos alocações você fizer, menos provável será a fragmentação da memória. No entanto, a STL lida com isso com bastante eficácia. Se você tem uma string que está usando a totalidade de sua alocação atual e acrescenta um caractere a ela, ela não é re-alocada para o comprimento atual mais um, mas dobra seu comprimento. Essa é uma variação da estratégia "pool para alocações pequenas e frequentes". A string está capturando um grande pedaço de memória para poder lidar eficientemente com pequenos aumentos de tamanho repetidos sem fazer realocações pequenas e repetidas. Na verdade, todos os contêineres STL fazem esse tipo de coisa; portanto, geralmente você não precisa se preocupar muito com a fragmentação causada pela realocação automática de contêineres STL.

Embora, é claro, os contêineres STL não agrupem memória entre si, por isso, se você criar muitos contêineres pequenos (em vez de alguns contêineres que são redimensionados com frequência), talvez seja necessário se preocupar em impedir a fragmentação da mesma maneira que você seria para qualquer objeto pequeno criado com freqüência, STL ou não.

• O que é fragmentação de memória?

A fragmentação da memória é o problema de a memória se tornar inutilizável, embora esteja teoricamente disponível. Existem dois tipos de fragmentação: fragmentação interna é a memória que é alocada, mas não pode ser usada (por exemplo, quando a memória é alocada em blocos de 8 bytes, mas o programa faz repetidamente alocações únicas quando precisa de apenas 4 bytes). fragmentação externa é o problema de a memória livre se dividir em muitos pequenos pedaços, para que grandes solicitações de alocação não possam ser atendidas, embora exista bastante memória livre geral.

• Como posso saber se a fragmentação da memória é um problema para o meu aplicativo? Que tipo de programa tem maior probabilidade de sofrer?

a fragmentação da memória é um problema se o seu programa usar muito mais memória do sistema do que os dados reais do paylod exigiriam (e você descartou vazamentos de memória).

• Quais são as boas maneiras comuns de lidar com a fragmentação da memória?

Use um bom alocador de memória. IIRC, aqueles que usam uma estratégia de "melhor ajuste" geralmente são muito superiores em evitar a fragmentação, se um pouco mais lenta. No entanto, também foi demonstrado que, para qualquer estratégia de alocação, existem piores casos patológicos. Felizmente, os padrões típicos de alocação da maioria dos aplicativos são realmente relativamente benignos para os alocadores. Existem vários papéis por aí, se você estiver interessado nos detalhes:

• Paul R. Wilson, Mark S. Johnstone, Michael Neely e David Boles. Alocação dinâmica de armazenamento: uma pesquisa e uma revisão crítica. Nos Anais do Workshop Internacional de 1995 sobre Gerenciamento de Memória, Springer Verlag LNCS, 1995
• Mark S.Johnstone, Paul R. Wilson. O problema da fragmentação de memória: resolvido? Em ACM SIG-PLAN Avisos, volume 34 No. 3, páginas 26-36, 1999
• MR Garey, RL Graham e JD Ullman. Análise de pior caso de algoritmos de alocação de memória. No Quarto Simpósio Anual da ACM sobre a Teoria da Computação, 1972

Atualização:
Google TCMalloc: Malloc de cache de threads
Verificou-se que é bastante bom em lidar com a fragmentação em um processo demorado.

Estou desenvolvendo um aplicativo para servidor que teve problemas com a fragmentação de memória no HP-UX 11.23 / 11.31 ia64.

Parecia assim. Houve um processo que fez alocações e desalocações de memória e foi executado por dias. E mesmo que não houvesse vazamentos de memória, o consumo de memória do processo continuava aumentando.

Sobre a minha experiência. No HP-UX, é muito fácil encontrar fragmentação de memória usando o HP-UX gdb. Você define um ponto de interrupção e, ao atingi-lo, executa este comando: info heape vê todas as alocações de memória para o processo e o tamanho total da pilha. Então você continua seu programa e, algum tempo depois, novamente atinge o ponto de interrupção. Você faz de novo info heap. Se o tamanho total do heap for maior, mas o número e o tamanho das alocações separadas forem iguais, é provável que você tenha problemas de alocação de memória. Se necessário, faça isso algumas vezes antes.

Minha maneira de melhorar a situação era essa. Depois de fazer algumas análises com o HP-UX gdb, vi que os problemas de memória eram causados ​​pelo fato de eu ter usado std::vectorpara armazenar alguns tipos de informações de um banco de dados. std::vectorrequer que seus dados sejam mantidos em um bloco. Eu tinha alguns contêineres baseados std::vector. Esses contêineres eram recriados regularmente. Muitas vezes, havia situações em que novos registros eram adicionados ao banco de dados e, depois disso, os contêineres eram recriados. E como os contêineres recriados eram maiores, eles não se encaixavam nos blocos de memória livre disponíveis e o tempo de execução solicitava um novo bloco maior do sistema operacional. Como resultado, mesmo que não houvesse vazamentos de memória, o consumo de memória do processo aumentou. Melhorei a situação quando troquei os contêineres. Em vez de std::vectorcomeçar a usarstd::deque que tem uma maneira diferente de alocar memória para dados.

Sei que uma das maneiras de evitar a fragmentação da memória no HP-UX é usar o Small Block Allocator ou o MallocNextGen. No RedHat Linux, o alocador padrão parece lidar muito bem com a alocação de muitos pequenos blocos. No Windows existe Low-fragmentation Heape soluciona o problema do grande número de pequenas alocações.

Meu entendimento é que, em um aplicativo pesado para STL, você precisa primeiro identificar problemas. Os alocadores de memória (como na libc) realmente lidam com o problema de muitas alocações pequenas, o que é típico para std::string(por exemplo, no meu aplicativo de servidor, existem muitas strings STL, mas como vejo na execução, info heapelas não estão causando problemas). Minha impressão é que você precisa evitar grandes alocações frequentes. Infelizmente, existem situações em que você não pode evitá-las e precisa alterar seu código. Como eu disse no meu caso, melhorei a situação quando mudei para std::deque. Se você identificar sua fragmentação da memória, poderá ser possível falar sobre isso com mais precisão.

É provável que a fragmentação da memória ocorra quando você aloca e desaloca muitos objetos de tamanhos variados. Suponha que você tenha o seguinte layout na memória:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

Agora, quando obj2lançado, você tem 120kb de memória não utilizada, mas não pode alocar um bloco completo de 120kb, porque a memória está fragmentada.

Técnicas comuns para evitar esse efeito incluem buffers de anel e conjuntos de objetos . No contexto da STL, métodos como std::vector::reserve()podem ajudar.

Uma resposta muito detalhada sobre fragmentação de memória pode ser encontrada aqui.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

Este é o culminar de 11 anos de respostas sobre fragmentação de memória que tenho fornecido às pessoas que me fazem perguntas sobre fragmentação de memória em softwareverify.com

O que é fragmentação de memória?

Quando seu aplicativo usa memória dinâmica, ele aloca e libera pedaços de memória. No começo, todo o espaço de memória do seu aplicativo é um bloco contíguo de memória livre. No entanto, quando você aloca e libera blocos de tamanhos diferentes, a memória começa a ficar fragmentada , ou seja, em vez de um grande bloco livre contíguo e vários blocos alocados contíguos, haverá um bloco alocado e livre misturado. Como os blocos livres têm tamanho limitado, é difícil reutilizá-los. Por exemplo, você pode ter 1000 bytes de memória livre, mas não pode alocar memória para um bloco de 100 bytes, porque todos os blocos livres têm no máximo 50 bytes de comprimento.

Outra fonte inevitável, mas menos problemática de fragmentação é que, na maioria das arquiteturas, os endereços de memória devem estar alinhados aos limites de 2, 4, 8 etc. bytes (isto é, os endereços devem ser múltiplos de 2, 4, 8 etc.). Isso significa que mesmo que você tenha, por exemplo, uma estrutura contendo 3 charcampos, sua estrutura pode ter um tamanho de 12 em vez de 3, devido ao fato de que cada campo está alinhado a um limite de 4 bytes.

Como posso saber se a fragmentação da memória é um problema para o meu aplicativo? Que tipo de programa tem maior probabilidade de sofrer?

A resposta óbvia é que você recebe uma exceção de falta de memória.

Aparentemente, não existe uma boa maneira portátil de detectar fragmentação de memória em aplicativos C ++. Veja esta resposta para mais detalhes.

Quais são as boas maneiras comuns de lidar com a fragmentação da memória?

É difícil no C ++, pois você usa endereços de memória direta em ponteiros e não tem controle sobre quem faz referência a um endereço de memória específico. Portanto, reorganizar os blocos de memória alocados (da maneira que o coletor de lixo Java faz) não é uma opção.

Um alocador personalizado pode ajudar gerenciando a alocação de objetos pequenos em um pedaço maior de memória e reutilizando os slots livres desse pedaço.

Esta é uma versão super simplificada para manequins.

À medida que os objetos são criados na memória, eles são adicionados ao final da parte usada na memória.

Se um objeto que não esteja no final da parte usada da memória for excluído, o que significa que esse objeto estava entre outros dois objetos, ele criará um "buraco".

Isso é chamado de fragmentação.

Quando você deseja adicionar um item ao heap, o que acontece é que o computador precisa pesquisar um espaço para caber nesse item. É por isso que alocações dinâmicas quando não são executadas em um conjunto de memórias ou com um alocador em conjunto podem "atrasar" as coisas. Para um aplicativo STL pesado, se você estiver executando multi-threading, há o alocador Hoard ou a versão TBB Intel .

Agora, quando a memória está fragmentada, duas coisas podem ocorrer:

1. Terá de haver mais pesquisas para encontrar um bom espaço para colar objetos "grandes". Ou seja, com muitos objetos pequenos espalhados sobre a localização de um bom pedaço de memória contíguo, sob certas condições, pode ser difícil (isso é extremo).
2. A memória não é uma entidade de fácil leitura. Os processadores são limitados a quanto eles podem conter e onde. Eles fazem isso trocando as páginas se um item necessário for um local, mas os endereços atuais forem outro. Se você precisar trocar constantemente de páginas, o processamento poderá ficar mais lento (novamente, cenários extremos onde isso afeta o desempenho.) Veja esta postagem na memória virtual .

A fragmentação da memória ocorre porque são solicitados blocos de memória de tamanhos diferentes. Considere um buffer de 100 bytes. Você solicita dois caracteres, depois um número inteiro. Agora você libera os dois caracteres e solicita um novo número inteiro - mas esse número inteiro não cabe no espaço dos dois caracteres. Essa memória não pode ser reutilizada porque não está em um bloco contíguo grande o suficiente para realocar. Além disso, você invocou muitas despesas gerais do alocador para seus caracteres.

Essencialmente, a memória só vem em blocos de um determinado tamanho na maioria dos sistemas. Depois de dividir esses blocos, eles não poderão ser reunidos até que todo o bloco seja liberado. Isso pode levar ao uso de blocos inteiros quando, na verdade, apenas uma pequena parte do bloco está em uso.

A principal maneira de reduzir a fragmentação de heap é fazer alocações maiores e menos frequentes. No extremo, você pode usar um heap gerenciado capaz de mover objetos, pelo menos, dentro do seu próprio código. Isso elimina completamente o problema - de uma perspectiva da memória, de qualquer maneira. Obviamente objetos em movimento e tal têm um custo. Na realidade, você só tem realmente um problema se estiver alocando quantidades muito pequenas do heap com frequência. Usar contêineres contíguos (vetor, string, etc.) e alocar na pilha o máximo humanamente possível (sempre uma boa idéia para desempenho) é a melhor maneira de reduzi-lo. Isso também aumenta a coerência do cache, o que torna seu aplicativo mais rápido.

O que você deve se lembrar é que em um sistema desktop de 32 bits x86, você tem 2 GB de memória inteira, divididos em "páginas" de 4KB (com certeza o tamanho da página é o mesmo em todos os sistemas x86). Você precisará chamar alguma fragmentação omgwtfbbq para ter um problema. A fragmentação é realmente uma questão do passado, uma vez que os heaps modernos são excessivamente grandes para a grande maioria dos aplicativos, e há uma prevalência de sistemas capazes de resistir a isso, como heaps gerenciados.

Que tipo de programa tem maior probabilidade de sofrer?

Um bom exemplo (= horripilante) para os problemas associados à fragmentação da memória foi o desenvolvimento e o lançamento de "Elemental: War of Magic" , um jogo de computador da Stardock .

O jogo foi desenvolvido para 32 bits / 2 GB de memória e teve que fazer muita otimização no gerenciamento de memória para fazer o jogo funcionar dentro desses 2 GB de memória. Como a "otimização" levava à constante alocação e desalocação, com o tempo a fragmentação da memória heap ocorreu e fez o jogo travar todas as vezes .

Há uma entrevista sobre "história de guerra" no YouTube.