Strategia di crescita del buffer

Question

Ho un buffer generico generato per accumulare pezzi di stringa "casuali" e quindi recuperare il risultato. Code per gestire tale buffer è scritto in pianura C.

Pseudocodice API:

void write(buffer_t * buf, const unsigned char * bytes, size_t len);/* appends */ 
const unsigned char * buffer(buffer_t * buf);/* returns accumulated data */ 

Sto pensando alla strategia di crescita dovrei scegliere per questo buffer.

Non so se i miei utenti preferirebbero la memoria o la velocità, o quale sarebbe la natura dei dati dell'utente.

Ho visto due strategie in natura: aumentare il buffer con incrementi di dimensione fissa (che è quello che ho attualmente implementato) o far crescere i dati in modo esponenziale. (C'è anche una strategia per allocare la quantità esatta di memoria necessaria - ma nel mio caso non è interessante.)

Forse dovrei lasciare che l'utente scelga la strategia ... Ma ciò renderebbe il codice un po 'più complesso ...

C'era una volta, Herb Sutter wrote (riferimento a Andrew Koenig) che la migliore strategia è, probabilmente, crescita esponenziale con fattore 1.5 (ricerca di "Strategia di crescita"). È ancora la scelta migliore?

Qualche consiglio? Cosa dice la tua esperienza?

Answer 1

A meno che non si abbia una buona ragione per fare altrimenti, la crescita esponenziale è probabilmente la scelta migliore. Usare 1.5 per l'esponente non è davvero magico, e in effetti non è quello che Andrew Koenig ha originariamente detto. Ciò che ha originariamente detto è che il fattore di crescita dovrebbe essere inferiore a (1 + sqrt (5))/2 (~ 1,6).

Pete Becker dice quando era a Dinkumware P.J. Plauger, proprietario di Dinkumware, dice di aver fatto alcuni test e ha scoperto che 1.5 funzionava bene. Quando si assegna un blocco di memoria, l'allocatore di solito alloca un blocco che è almeno leggermente più grande di quello richiesto per dare spazio a una piccola informazione di conservazione del libro. La mia ipotesi (anche se non confermata da alcun test) è che riducendo il fattore un po 'lasciamo che la dimensione reale del blocco si adatti ancora al limite.

Riferimenti: Credo Andrew originariamente pubblicato questo in una rivista (il Journal of Object Oriented Programming, IIRC) che non è stato pubblicato in anni ormai, in modo da ottenere una ri-stampa probabilmente sarebbe molto difficile.

Andrew Koenig's Usenet post e P.J. Plauger's Usenet post.

Answer 2

La strategia di crescita esponenziale viene utilizzata in tutto STL e sembra funzionare correttamente. Direi di continuare con questo almeno finché non trovi un caso preciso in cui non funzionerà.

Answer 3

La risposta, come sempre, è "dipende".

L'idea alla base della crescita esponenziale, ovvero l'allocazione di un nuovo buffer x volte la dimensione corrente, richiede più buffer e le probabilità sono che sarà necessario molto più buffer di un piccolo incremento fisso fornisce.

Quindi, se si dispone di un buffer da 8 byte e occorre allocare più 8 byte in più, è probabile che allocare ulteriori 16 byte sia una buona idea: non è probabile che qualcuno con un buffer da 16 byte richieda un 1 byte in più. E se lo fanno, tutto ciò che sta accadendo è che stai sprecando un po 'di memoria.

ho pensato che il miglior fattore di crescita è stata del 2 - vale a dire il doppio della tua buffer, ma se Koenig/Sutter dire 1,5 è ottimale, quindi sto d'accordo con loro. Potresti voler modificare il tuo tasso di crescita dopo aver ottenuto alcune statistiche di utilizzo.

crescita esponenziale Quindi è un buon compromesso tra prestazioni e mantenere la memoria basso utilizzo.

Answer 4

Il punto chiave è che la strategia di crescita esponenziale consente di evitare copie costose del contenuto del buffer quando si colpisce la dimensione corrente per il costo di po 'di memoria sprecata. L'articolo che colleghi ha i numeri per il trade-of.

Answer 5

Non c'è modo chiunque può dare buoni consigli senza conoscere qualcosa circa le assegnazioni, ambiente di runtime, caratteristiche di esecuzione, ecc, ecc

codice che funziona è il modo più importante di codice altamente ottimizzato, che è ... in fase di sviluppo. Scegli un algoritmo, qualsiasi algoritmo lavorabile, e provalo!Se si dimostra non ottimale, cambia la strategia. Mettendo questo nel controllo dell'utente della biblioteca spesso non li favorisce. Ma se hai già qualche schema opzionale, allora aggiungerlo potrebbe essere utile, a meno che tu non prenda un buon algoritmo (e n^1.5 sia piuttosto buono).

---

Inoltre, l'utilizzo di una funzione denominata write in C (non C++) in conflitto con < io.h> e < stdio.h>. Va bene se nulla li usa, ma sarebbe anche difficile aggiungerli in seguito. Meglio usare un nome più descrittivo.

Answer 6

• doppio delle dimensioni fino a una soglia (~ 100MB?) E quindi abbassare la crescita esponenziale verso 1,5, .., 1.3
• Un'altra opzione sarebbe quella di rendere la dimensione del buffer di default configurabile in fase di esecuzione.

Answer 7

Io di solito uso una combinazione di aggiunta di una piccola quantità fissa e moltiplicazione per 1,5 perché è efficace da implementare e porta a intervalli di passo ragionevoli che sono più grandi all'inizio e più sensibili alla memoria quando il buffer cresce. Come offset fisso solito uso la dimensione iniziale del buffer e iniziare con piuttosto piccole dimensioni iniziali:

new_size = old_size + (old_size >> 1) + initial_size; 

come initial_size uso 4 per i tipi di raccolta, 8, 12 o 16 per tipi di stringa e 128 4096 dal -/buffer di output a seconda del contesto.

Ecco un piccolo grafico che mostra che questo cresce molto più velocemente (giallo + rosso) nei primi passi rispetto alla moltiplicazione solo per 1.5 (rosso).

Quindi, se si è iniziato con 100 si avrebbe bisogno, per esempio 6 aumenta per accogliere 3000 elementi, mentre moltiplicando con il solo 1.5 avrebbe bisogno 9.

Al dimensioni maggiori l'influenza l'aggiunta diventa trascurabile , che rende entrambi gli approcci scalabili ugualmente bene di un fattore di 1,5 quindi.Questi sono i fattori di crescita efficaci se si utilizza la dimensione iniziale come importo fisso per l'aggiunta:

2.5 
1.9 
1.7 
1.62 
1.57 
1.54 
1.53 
1.52 
1.51 
1.5 
... 

Answer 8

Il punto di usare crescita esponenziale (se il fattore sia 1.5 o 2) è di evitare esemplari. Ogni volta che si rialloca l'array, è possibile attivare una copia implicita dell'articolo, che, ovviamente, diventa più costoso più grande diventa. Utilizzando una crescita esponenziale, si ottiene un numero costante di ricoperi ammortizzati, cioè raramente si finisce per copiare.

Finché si esegue un computer desktop di qualche tipo, ci si può aspettare una quantità di memoria sostanzialmente illimitata, quindi il tempo è probabilmente il lato giusto di tale compromesso. Per i sistemi hardware in tempo reale, probabilmente vorresti trovare un modo per evitare del tutto le copie: ti viene in mente una lista collegata.

Answer 9

Come idea originale, in questo caso specifico, è possibile modificare l'API per richiedere al chiamante di allocare la memoria per ogni blocco e quindi ricordare i blocchi anziché copiare i dati.

Quindi, quando è il momento di produrre effettivamente il risultato, si sa esattamente quanta memoria sarà necessaria e può allocare esattamente quello.

Questo ha il vantaggio che il chiamante dovrà allocare memoria per i blocchi in ogni caso, e quindi potrebbe anche farne uso. Ciò evita anche di copiare i dati più di una volta.

Ha lo svantaggio che il chiamante dovrà allocare dinamicamente ogni blocco. Per aggirare questo, è possibile allocare memoria per ogni blocco, e ricordarli, piuttosto che mantenere un buffer grande, che viene ridimensionato quando si riempie. In questo modo, copierai i dati due volte (una volta nel blocco che hai assegnato, un'altra volta nella stringa risultante), ma non di più. Se devi ridimensionare più volte, potresti finire con più di due copie.

Inoltre, aree molto grandi di memoria libera potrebbero essere difficili da trovare per l'allocatore di memoria. L'allocazione di pezzi più piccoli potrebbe essere più facile. Potrebbe non esserci spazio per un chunk di memoria da un gigabyte, ma potrebbe esserci spazio per migliaia di blocchi di megabyte.