Qual é a taxa de crescimento ideal para uma matriz alocada dinamicamente?

https://stackoverflow.com/questions/1100311

11-09-2019
|

Pergunta

C ++ tem std :: vector e Java tem ArrayList, e muitas outras línguas têm sua própria forma de matriz alocada dinamicamente. Quando uma matriz dinâmica ficar sem espaço, ele é realocado para uma área maior e os valores antigos são copiados para a nova matriz. A questão central para o desempenho do conjunto de tais é o quão rápido a matriz cresce em tamanho. Se você sempre só crescem grande o suficiente para caber o impulso atual, você vai acabar realocação de cada vez. Portanto, faz sentido para dobrar o tamanho da matriz, ou multiplicá-lo por 1.5x digamos.

Existe um fator de crescimento ideal? 2x? 1.5x? Pelo ideal Quero dizer matematicamente justificado, melhor desempenho de equilíbrio e memória desperdiçado. Eu percebo que, teoricamente, dado que a sua aplicação poderia ter qualquer distribuição potencial de empurrões que este é um pouco dependente da aplicação. Mas estou curioso para saber se há um valor que é "geralmente" melhor, ou é considerado o melhor dentro de algum rigorosa restrição.

Eu ouvi há um artigo sobre isso em algum lugar, mas eu fui incapaz de encontrá-lo.

Solução

Ele irá depender inteiramente o caso de uso. Você se preocupam mais com o tempo desperdiçado a cópia de dados em torno (e realocação de matrizes) ou a memória extra? Quanto tempo é a matriz vai durar? Se não vai ser por muito tempo, usando um buffer maior pode muito bem ser uma boa idéia - a pena é de curta duração. Se ele vai para pendurar ao redor (por exemplo, em Java, indo para as gerações mais velhas e mais velhos) que é, obviamente, mais de uma penalidade.

Não há tal coisa como um "fator de crescimento ideal." Não é só teoricamente aplicativo dependente, é definitivamente dependente da aplicação.

2 é um fator de crescimento bastante comum - eu tenho certeza que é o que ArrayList e List<T> em usos .NET. ArrayList<T> em Java usa 1.5.

EDIT: Como Erich aponta, Dictionary<,> em .NET usa "o dobro do tamanho, em seguida, aumentar para o próximo número primo" de modo que os valores de hash podem ser distribuídos razoavelmente entre baldes. (Eu tenho certeza que eu vi recentemente documentação sugerindo que primos não são realmente tão grande para distribuir baldes de hash, mas isso é um argumento para outra resposta.)

Outras dicas

Eu lembro de ter lido há muitos anos por 1,5 é preferível a dois, pelo menos, tão aplicado a C ++ (isso provavelmente não se aplica a línguas geridos, onde o sistema de tempo de execução pode realocar objetos à vontade).

O raciocínio é o seguinte:

Say você começa com uma dotação de 16 bytes.
Quando você precisar de mais, você alocar 32 bytes, em seguida, liberar 16 bytes. Isso deixa um buraco de 16 bytes na memória.
Quando você precisar de mais, você alocar 64 bytes, liberando os 32 bytes. Isto deixa um orifício de 48 bytes (se a 16 e 32 estavam adjacentes).
Quando você precisar de mais, você aloca 128 bytes, liberando os 64 bytes. Isto deixa um orifício de 112 bytes (assumindo que todas as alocações anteriores são adjacentes).
E assim e e assim por diante.

A idéia é que, com uma expansão de 2x, não há nenhum ponto no tempo que o buraco resultante é nunca vai ser grande o suficiente para reutilização para a próxima alocação. Usando uma alocação de 1,5x, temos este em vez disso:

Comece com 16 bytes.
Quando você precisar de mais, alocar 24 bytes, em seguida, liberar a 16, deixando um buraco de 16 bytes.
Quando você precisar de mais, alocar 36 bytes, em seguida, liberar a 24, deixando um buraco de 40 bytes.
Quando você precisar de mais, alocar 54 bytes, em seguida, liberar a 36, ??deixando um buraco 76-byte.
Quando você precisar de mais, alocar 81 bytes, em seguida, liberar a 54, deixando um buraco de 130 bytes.
Quando precisar de mais, use 122 bytes (arredondamento) do orifício 130 bytes.

O ideal (no limite como n ? 8), a relação É de ouro : f = 1,618 ...

Na prática, você quer algo próximo, como 1.5.

A razão é que você quer ser capaz de reutilizar blocos de memória mais velhos, para tirar vantagem de caching e evitar constantemente fazendo as OS dar-lhe mais páginas de memória. A equação que você resolver para garantir que esta reduz a x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ, cuja solução se aproxima x = f para grandes n .

Uma abordagem ao responder a perguntas como esta é apenas para "enganar" e olhar para o que as bibliotecas populares fazem, sob a suposição de que uma biblioteca utilizada é, pelo menos, não fazer algo horrível.

Então, basta verificar muito rapidamente, Ruby (1.9.1-P129) parece usar 1,5x ao anexar a uma matriz, e Python (2.6.2) utiliza 1.125x mais uma constante (em Objects/listobject.c ):

/* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* check for integer overflow */ if (new_allocated > PY_SIZE_MAX - newsize) { PyErr_NoMemory(); return -1; } else { new_allocated += newsize; }

newsize acima é o número de elementos na matriz. Note bem que newsize é adicionado ao new_allocated, então a expressão com as bitshifts e operador ternário é realmente apenas o cálculo do-alocação mais.

Digamos que você crescer o tamanho da matriz por x. Portanto, vamos supor que você comece com o tamanho T. A próxima vez que você cresce a matriz seu tamanho será T*x. Então será T*x^2 e assim por diante.

Se o seu objetivo é ser capaz de reutilizar a memória que tenha sido criado antes, então você quer ter certeza da nova memória que você alocar é menor do que a soma de memória anterior, você desalocada. Portanto, temos essa desigualdade:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Podemos remover T de ambos os lados. Então, ficamos com este:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Informalmente, o que dizemos é que a alocação nth, queremos que a nossa memória todos os anteriormente deallocated ser maior ou igual à necessidade de memória na alocação enésimo para que possamos reutilizar a memória previamente desalocada.

Por exemplo, se queremos ser capazes de fazer isso na 3ª etapa (ou seja, n=3), então temos

x^3 <= 1 + x

Esta equação é verdadeira para todo x tal que 0 < x <= 1.3 (aproximadamente)

Veja o que x temos para n diferentes de abaixo:

n maximum-x (roughly) 3 1.3 4 1.4 5 1.53 6 1.57 7 1.59 22 1.61

Note que o fator de crescimento tem de ser inferior a 2 desde x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Ela realmente depende. Algumas pessoas analisar casos de uso comum para encontrar o número ideal.

Eu vi 1,5x 2,0x phi x, e potência de 2 usado antes.

Se você tem uma distribuição mais comprimentos de matriz, e você tem uma função de utilidade que diga o quanto você gosta de perder tempo desperdiçando espaço vs., então você definitivamente pode escolher uma boa estratégia de redimensionamento (e dimensionamento inicial).

A razão simples múltiplo constante é utilizada, é, obviamente, de modo que cada acréscimo amortizou tempo constante. Mas isso não significa que você não pode usar uma relação diferente (maior) para tamanhos pequenos.

Em Scala, você pode substituir loadFactor para as tabelas de hash da biblioteca padrão com uma função que olha para o tamanho atual. Estranhamente, as matrizes redimensionáveis ??apenas dobrar, que é o que a maioria das pessoas fazem na prática.

Eu não sei de nenhuma duplicação (ou 1.5 * ing) matrizes que realmente pegar erros de memória e crescer menos neste caso. Parece que se você tivesse uma enorme variedade única, que você iria querer fazer isso.

Eu tinha ainda acrescentar que, se você está mantendo as matrizes redimensionáveis ??em torno de tempo suficiente, e você é a favor do espaço ao longo do tempo, pode fazer sentido para dramaticamente overallocate (para a maioria dos casos) inicialmente e depois realocar a exatamente o tamanho certo quando você está feito.

Eu concordo com Jon Skeet, mesmo meu amigo theorycrafter insiste em que isso pode ser provado ser O (1) ao definir o fator de 2x.

A relação entre o tempo de CPU e memória é diferente em cada máquina, e assim o fator irá variar tanto. Se você tem uma máquina com gigabytes de RAM e uma CPU lenta, copiar os elementos para uma nova matriz é muito mais caro do que em uma máquina rápida, o que poderia, por sua vez têm menos memória. É uma pergunta que pode ser respondida em teoria, para um computador uniforme, que em cenários reais não ajuda você em tudo.

Eu sei que é uma questão antiga, mas há várias coisas que todo mundo parece estar faltando.

Em primeiro lugar, esta é a multiplicação por 2: tamanho << 1. Esta é a multiplicação por qualquer entre 1 e 2: int (float (tamanho) * x), onde x é o número, * é matemática de ponto flutuante, e o processador tem de executar instruções adicionais para a conversão entre bóia e int. Em outras palavras, no nível da máquina, duplicação leva uma única instrução, muito rápido para encontrar o novo tamanho. Multiplicando por algo entre 1 e 2 requer , pelo menos uma instrução ao tamanho elenco para uma bóia, uma instrução para multiplicar (que é flutuador multiplicação, por isso, provavelmente, leva pelo menos duas vezes mais ciclos, se não 4 ou até 8 vezes mais), e uma instrução para elenco de volta para int, e que assume que sua plataforma pode executar matemática flutuar na registos de uso geral, em vez de exigir o uso de registros especiais. Em suma, você deve esperar a matemática para cada alocação de tomar pelo menos 10 vezes, desde que uma simples mudança esquerda. Se você está copiando um monte de dados durante a realocação no entanto, isso pode não fazer muita diferença.

Em segundo lugar, e provavelmente o grande kicker: Todo mundo parece supor que a memória que está sendo liberada é tanto contígua com ela mesma, bem como contígua com a memória recém-alocado. A menos que você está pré-alocando toda a memória a si mesmo e, em seguida, usá-lo como uma piscina, este é quase certamente não é o caso. O OS pode ocasionalmente acabar fazendo isso, mas na maioria das vezes, não vai ser o suficiente fragmentação do espaço livre que qualquer sistema de gerenciamento de memória decente metade será capaz de encontrar um pequeno buraco onde sua memória apenas se encaixam. Uma vez que você começa a realmente mordeu pedaços, que são mais propensos a acabar com peças contíguas, mas até então, suas atribuições são grandes o suficiente para que você não está fazendo-los com freqüência suficiente para que importa mais. Em suma, é divertido imaginar que o uso de algum número ideal permitirá o uso mais eficiente do espaço de memória livre, mas, na realidade, não vai acontecer a menos que seu programa está sendo executado em bare metal (como em, não há OS debaixo dela fazendo todas as decisões).

A minha resposta para a pergunta? Não, não existe um número ideal. É tão específico do aplicativo que ninguém realmente tenta mesmo. Se seu objetivo é o uso de memória ideal, você está praticamente fora de sorte. Para o desempenho, as alocações menos frequentes são melhores, mas se fomos apenas com isso, poderíamos multiplicar por 4 ou mesmo 8! Claro que, quando Firefox salta de usar 1GB até 8GB em um tiro, as pessoas estão indo para reclamar, de modo que não faz muito sentido. Aqui estão algumas regras de ouro que eu iria por que:

Se você não pode uso de memória otimizar, pelo menos não desperdiçar ciclos de processador. Multiplicando por 2 é pelo menos uma ordem de magnitude mais rápido do que fazer matemática ponto flutuante. Pode não fazer uma diferença enorme, mas ele vai fazer alguma diferença, pelo menos (especialmente no início, durante as alocações mais frequentes e menores).

Do not overthink. Se você apenas passado 4 horas tentando descobrir como fazer algo que já foi feito, você apenas perdeu seu tempo. Totalmente honestamente, se houve uma opção melhor do que * 2, que teria sido feito na classe C ++ vector (e muitos outros lugares) décadas atrás.

Por fim, se você realmente deseja otimizar, não suar as pequenas coisas. Agora dias, ninguém se preocupa com 4KB de memória que está sendo desperdiçado, a menos que eles estão trabalhando em sistemas embarcados. Quando você chegar a 1 GB de objetos que estão entre 1 MB e 10 MB cada, dobrando é provavelmente a maneira demasiado (Quer dizer, isso é entre 100 e 1.000 objetos). Se você pode estimar a taxa de expansão esperada, você pode nivelar-lo para uma taxa de crescimento linear em um determinado ponto. Se você espera que cerca de 10 objetos por minuto, em seguida, crescendo a 5 a 10 tamanhos de objeto por etapa (uma vez a cada 30 segundos a um minuto) é probably bem.

O que isso tudo vem para baixo é, não pense sobre isso, otimizar o que você pode, e personalizar a sua aplicação (e plataforma), se necessário.

Outros dois centavos

A maioria dos computadores têm memória virtual! Na memória física você pode ter páginas aleatórias em todos os lugares que são exibidos como um único espaço contíguo na memória virtual do seu programa. A resolução do engano é feita pelo hardware. esgotamento da memória virtual foi um problema em sistemas de 32 bits, mas não é realmente um problema. Portanto, enchendo o buraco não é mais uma preocupação (exceto ambientes especiais). Desde o Windows 7 até mesmo a Microsoft suporta 64 bits sem esforço extra. @ 2011

O (1) é alcançado com qualquer r > 1 fator. prova matemática mesma funciona não só para 2 como parâmetro.

r = 1,5 pode ser calculado com old*3/2 por isso não há necessidade de operações de ponto flutuante. (Digo /2 porque compiladores irá substituí-lo com pouco deslocamento no código assembly gerado se entenderem.)

MSVC fui para o r = 1,5, para que haja pelo menos um compilador importante que não use 2 como ratio.

Como mencionado por alguém 2 sente melhor do que 8. E também 2 sente melhor do que 1.1.

Meu sentimento é que 1,5 é um bom padrão. Outros, que depende do caso específico.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow