Qual è il tasso di crescita ideale per un array allocato dinamicamente?

https://stackoverflow.com/questions/1100311

11-09-2019
|

Domanda

C++ ha std::vettoriale e Java ha ArrayList e molti altri linguaggi hanno la propria forma di array allocato dinamicamente.Quando un array dinamico esaurisce lo spazio, viene riallocato in un'area più ampia e i vecchi valori vengono copiati nel nuovo array.Una questione fondamentale per le prestazioni di un array di questo tipo è la velocità con cui l'array aumenta di dimensioni.Se diventi sempre abbastanza grande da adattarsi alla spinta attuale, finirai per riallocare ogni volta.Quindi ha senso raddoppiare la dimensione dell'array o moltiplicarla, ad esempio, per 1,5x.

Esiste un fattore di crescita ideale?2x?1,5x?Per ideale intendo matematicamente giustificato, miglior bilanciamento tra prestazioni e memoria sprecata.Mi rendo conto che in teoria, dato che la tua applicazione potrebbe avere una potenziale distribuzione di push, questo dipende in qualche modo dall'applicazione.Ma sono curioso di sapere se esiste un valore che è "solitamente" migliore o è considerato migliore entro alcuni vincoli rigorosi.

Ho sentito che c'è un documento su questo argomento da qualche parte, ma non sono riuscito a trovarlo.

Soluzione

Si interamente dipenderà dal caso d'uso. Non vi preoccupate di più sul tempo sprecato copia dei dati in giro (e riallocando gli array) o la memoria aggiuntiva? Per quanto tempo l'array destinato a durare? Se non sarà in giro per molto tempo, utilizzando un buffer più grande potrebbe essere una buona idea - la sanzione è di breve durata. Se è intenzione di rimanere in giro (per esempio in Java, andando in generazioni più anziane e più anziani) che è ovviamente più di una sanzione.

Non c'è cosa come un "fattore di crescita ideale". Non è solo teoricamente dipende dall'applicazione, è sicuramente dipende dall'applicazione.

2 è un fattore di crescita abbastanza comune - Sono abbastanza sicuro che è quello che utilizza ArrayList e List<T> in .NET. ArrayList<T> in Java utilizza 1.5.

EDIT: Come Erich sottolinea, Dictionary<,> in .NET utilizza "il doppio della dimensione quindi aumentare per il prossimo numero primo" in modo che i valori di hash possono essere distribuiti ragionevolmente tra i secchi. (Sono sicuro che ho visto di recente documentazione suggerisce che i numeri primi non sono in realtà che l'ideale per la distribuzione secchi hash, ma questo è un argomento per un'altra risposta.)

Altri suggerimenti

Ricordo di aver letto molti anni fa perché 1.5 è preferito a due, almeno applicato al C++ (questo probabilmente non si applica ai linguaggi gestiti, dove il sistema runtime può riposizionare gli oggetti a piacimento).

Il ragionamento è questo:

Supponiamo che tu inizi con un'allocazione di 16 byte.
Quando ne hai bisogno di più, allochi 32 byte, quindi liberi 16 byte.Ciò lascia un buco di 16 byte in memoria.
Quando ne hai bisogno di più, allochi 64 byte, liberando i 32 byte.Ciò lascia un buco di 48 byte (se 16 e 32 fossero adiacenti).
Quando ne hai bisogno di più, allochi 128 byte, liberando 64 byte.Ciò lascia un buco di 112 byte (assumendo che tutte le allocazioni precedenti siano adiacenti).
E così e così via.

L'idea è che, con un'espansione 2x, non vi è alcun momento in cui il buco risultante sarà mai abbastanza grande da poter essere riutilizzato per l'allocazione successiva.Utilizzando un'allocazione 1,5x, abbiamo invece questo:

Inizia con 16 byte.
Quando ne hai bisogno di più, alloca 24 byte, quindi libera i 16, lasciando un buco di 16 byte.
Quando ne hai bisogno di più, alloca 36 byte, quindi libera i 24, lasciando un buco di 40 byte.
Quando ne hai bisogno di più, alloca 54 byte, quindi libera i 36, lasciando un buco di 76 byte.
Quando ne hai bisogno di più, alloca 81 byte, quindi libera i 54, lasciando un buco di 130 byte.
Quando ne hai bisogno di più, usa 122 byte (arrotondando per eccesso) dal buco di 130 byte.

Idealmente (nel limite come n → ∞), è il rapporto aureo : φ = 1,618 ...

In pratica, si vuole qualcosa di simile, come 1.5.

Il motivo è che si vuole essere in grado di riutilizzare blocchi di memoria più anziani, per approfittare di caching e di evitare costantemente rendendo il sistema operativo che si darà più pagine di memoria. L'equazione che ci si risolvere per garantire questo si riduce a x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ, la cui soluzione si avvicina x = φ per i grandi n .

Un approccio quando risponde alle domande come questo è solo "barare" e guardare a ciò che le biblioteche popolari fare, sotto l'ipotesi che una biblioteca ampiamente utilizzato è, per lo meno, non fare qualcosa di orribile.

Quindi, solo la verifica molto rapidamente, Ruby (1.9.1-P129) sembra usare 1,5x quando si aggiunge ad un array, e Python (2.6.2) utilizza 1.125x più una costante (in 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 sopra è il numero di elementi nella matrice. Nota bene si aggiunge che newsize a new_allocated, quindi l'espressione con le bitshifts e operatore ternario è in realtà solo calcolando l'eccessiva allocazione.

Diciamo che si cresce la dimensione della matrice da x. Quindi supporre che si avvia con la dimensione T. La prossima volta che crescere l'array la sua dimensione sarà T*x. Poi sarà T*x^2 e così via.

Se il vostro obiettivo è quello di essere in grado di riutilizzare la memoria che è stato creato prima, allora si vuole assicurarsi che la nuova memoria si alloca è inferiore alla somma della memoria precedente si deallocata. Pertanto, abbiamo questa disuguaglianza:

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

Possiamo rimuovere T da entrambi i lati. Così otteniamo questo:

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

In modo informale, quello che diciamo è che a ripartizione nth, vogliamo che il nostro tutta la memoria precedentemente deallocato sia maggiore o uguale alla necessità di memoria alla ripartizione n-esimo in modo da poter riutilizzare la memoria precedentemente deallocato.

Per esempio, se vogliamo essere in grado di fare questo al 3 ° gradino (vale a dire, n=3), allora abbiamo

x^3 <= 1 + x

Questa equazione è vero per ogni x tale che 0 < x <= 1.3 (approssimativamente)

Vedere che cosa x Noi otteniamo per diversi n di seguito:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Si noti che il fattore di crescita deve essere inferiore a 2 dal x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Dipende. Alcune persone analizzano i casi di utilizzo comuni per trovare il numero ottimale.

Ho visto 1.5x 2.0x phi x, e la potenza di 2 usato prima.

Se si dispone di una distribuzione su lunghezze degli array, e si dispone di una funzione di utilità che dice quanto ti piace sprecare spazio in funzione del tempo di sprecare, allora si può sicuramente scegliere un ridimensionamento ottimale (e iniziale dimensionamento) strategia.

La ragione semplice multiplo costante viene utilizzata, è ovviamente così che ogni accodamento è ammortizzato tempo costante. Ma questo non significa che non è possibile utilizzare una (più grande) diverso rapporto per piccoli formati.

In Scala, è possibile ignorare loadFactor per le tabelle standard hash biblioteca con una funzione che esamina le dimensioni attuali. Stranamente, le matrici ridimensionabili semplicemente doppio, che è ciò che la maggior parte delle persone lo fanno in pratica.

Non so di alcun raddoppio (o 1,5 * ing) array che in realtà catturano errori di memoria e crescono meno in questo caso. Sembra che se si ha un allineamento enorme singolo, che ci si vuole farlo.

Vorrei inoltre aggiungere che, se si sta tenendo le matrici ridimensionabili intorno abbastanza a lungo, e si favoriscono lo spazio nel tempo, potrebbe avere senso per drammaticamente overallocate (per la maggior parte dei casi), inizialmente e poi ridistribuire esattamente la giusta dimensione, quando il gioco è fatto.

Sono d'accordo con Jon Skeet, anche il mio amico theorycrafter insiste sul fatto che questo può essere dimostrato di essere O (1) quando si imposta il fattore a 2x.

Il rapporto tra tempo CPU e la memoria è diversa per ogni macchina, e quindi il fattore varierà altrettanto. Se si dispone di una macchina con gigabyte di RAM e una CPU lenta, copiando gli elementi per un nuovo array è molto più costoso che su una macchina veloce, che potrebbe a sua volta avere meno memoria. E 'una questione che può essere risolta in teoria, per un computer divisa, che in scenari reali non aiuta affatto.

So che è una vecchia domanda, ma ci sono molte cose che sembrano mancare a tutti.

Innanzitutto, questa è la moltiplicazione per 2:taglia << 1.Questa è la moltiplicazione per nulla tra 1 e 2:int(float(size) * x), dove x è il numero, * è la matematica in virgola mobile e il processore deve eseguire istruzioni aggiuntive per il casting tra float e int.In altre parole, a livello macchina, il raddoppio richiede un’unica istruzione molto veloce per trovare la nuova dimensione.Moltiplicare per qualcosa tra 1 e 2 richiede almeno un'istruzione per eseguire il cast di size su un float, un'istruzione per moltiplicare (che è una moltiplicazione float, quindi probabilmente richiede almeno il doppio dei cicli, se non 4 o addirittura 8 volte di più) e un'istruzione per eseguire il cast di nuovo su int, e ciò presuppone che la tua piattaforma possa eseguire calcoli float sui registri di uso generale, invece di richiedere l'uso di registri speciali.In breve, dovresti aspettarti che i calcoli per ciascuna allocazione richiedano almeno 10 volte il tempo di un semplice spostamento a sinistra.Tuttavia, se stai copiando molti dati durante la riallocazione, ciò potrebbe non fare molta differenza.

Secondo, e probabilmente il grande kicker:Tutti sembrano presupporre che la memoria che viene liberata sia contigua a se stessa, oltre che contigua alla memoria appena allocata.A meno che tu non stia preallocando tutta la memoria da solo e quindi utilizzandola come pool, quasi certamente non è così.Il sistema operativo potrebbe occasionalmente finisci per farlo, ma la maggior parte delle volte ci sarà abbastanza frammentazione dello spazio libero affinché qualsiasi sistema di gestione della memoria semidecente sarà in grado di trovare un piccolo buco in cui si adatterà la tua memoria.Una volta arrivati a pezzi davvero piccoli, è più probabile che vi ritroviate con pezzi contigui, ma a quel punto le vostre allocazioni sono abbastanza grandi da non eseguirle abbastanza frequentemente da avere più importanza.In breve, è divertente immaginare che l'utilizzo di un numero ideale consentirà l'uso più efficiente dello spazio di memoria libero, ma in realtà ciò non accadrà a meno che il programma non venga eseguito su bare metal (come in, non esiste un sistema operativo sotto prende tutte le decisioni).

La mia risposta alla domanda?No, non esiste un numero ideale.È così specifico per l'applicazione che nessuno ci prova nemmeno.Se il tuo obiettivo è l'utilizzo ideale della memoria, sei praticamente sfortunato.Per quanto riguarda le prestazioni, le allocazioni meno frequenti sono migliori, ma se seguissimo solo quella, potremmo moltiplicare per 4 o addirittura 8!Naturalmente, quando Firefox passa da 1 GB a 8 GB in un colpo solo, le persone si lamenteranno, quindi non ha nemmeno senso.Ecco alcune regole pratiche che seguirei però:

Se non puoi ottimizzare l'utilizzo della memoria, almeno non sprecare i cicli del processore.Moltiplicare per 2 è almeno un ordine di grandezza più veloce rispetto ai calcoli in virgola mobile.Potrebbe non fare una grande differenza, ma almeno farà una certa differenza (soprattutto nella fase iniziale, durante le allocazioni più frequenti e più piccole).

Non pensarci troppo.Se hai passato 4 ore cercando di capire come fare qualcosa che è già stato fatto, hai solo perso tempo.In tutta onestà, se ci fosse un'opzione migliore di *2, sarebbe stata fatta nella classe vettoriale C++ (e in molti altri posti) decenni fa.

Infine, se tu Veramente vuoi ottimizzare, non preoccuparti delle piccole cose.Al giorno d'oggi, a nessuno importa che 4KB di memoria vengano sprecati, a meno che non lavorino su sistemi embedded.Quando arrivi a 1 GB di oggetti di dimensioni comprese tra 1 MB e 10 MB ciascuno, il raddoppio è probabilmente eccessivo (voglio dire, ovvero tra 100 e 1.000 oggetti).Se riesci a stimare il tasso di espansione previsto, a un certo punto puoi livellarlo a un tasso di crescita lineare.Se prevedi circa 10 oggetti al minuto, probabilmente la crescita da 5 a 10 dimensioni di oggetti per passaggio (una volta ogni 30 secondi o un minuto) va bene.

Ciò che conta è non pensarci troppo, ottimizzare ciò che puoi e personalizzare la tua applicazione (e piattaforma) se necessario.

Altri due centesimi

Molti computer hanno la memoria virtuale! Nella memoria fisica si può avere pagine casuali ovunque che vengono visualizzati come un unico spazio contiguo in memoria virtuale del programma. La risoluzione della indirezione è ottenuta l'hardware. Virtuale esaurimento della memoria è stato un problema su sistemi a 32 bit, ma in realtà non è più un problema. In modo da riempire il foro di non è più una preoccupazione (ad eccezione di ambienti speciali). Dal momento che Windows 7, anche Microsoft supporta 64 bit, senza sforzo supplementare. @ 2011
O (1) viene raggiunto con qualsiasi r > 1 fattore. Stesso dimostrazione matematica non funziona solo per 2 come parametro.
r = 1,5 può essere calcolata con old*3/2 quindi non c'è necessità di operazioni in virgola mobile. (Dico /2 perché i compilatori lo sostituirà con il bit spostamento nel codice assembly generato qualora lo ritengano opportuno.)
MSVC è andato per r = 1.5, per cui v'è almeno un compilatore importante che non utilizza 2 come rapporto.

Come già detto da qualcuno 2 si sente meglio di 8. E anche 2 si sente meglio di 1.1.

La mia sensazione è che 1.5 è un buon valore predefinito. Diverso da quello che dipende dal caso specifico.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow