Utilizzando realloc in C ++

Question

std::realloc è pericoloso in c ++ se la memoria contiene malloc'd tipi non-pod. Sembra che il solo problema è che std::realloc wont chiamare i distruttori di tipo se non può crescere la memoria in situ.

Un lavoro in giro banale sarebbe una funzione try_realloc. Invece di malloc'ing nuova memoria, se non può essere coltivata in situ, sarebbe semplicemente restituire false. Nel qual caso nuova memoria può essere destinata, gli oggetti copiati (o spostati) per la nuova memoria, ed infine la vecchia memoria liberata.

Questo sembra estremamente utile. std::vector potrebbe fare grande uso di questo, possibilmente evitando tutte le copie / riassegnazioni.
preventiva ignifugo:. Tecnicamente, cioè a parità di prestazioni O-grande, ma se la crescita vettore è un collo di bottiglia nella vostra applicazione una velocità x2 up è bello anche se il Big-O rimane invariato

MA, non riesco a trovare alcuna API C che funziona come una try_realloc.

mi sto perdendo qualcosa? È try_realloc non così utile come immagino? C'è qualche bug nascosta che rende inutilizzabile try_realloc?

Meglio ancora, C'è qualche API meno documentato che funziona come try_realloc?

Nota: Sono ovviamente, in codice specifico biblioteca / piattaforma qui. Non sono preoccupato come try_realloc è intrinsecamente un'ottimizzazione.

---

Aggiornamento: A seguito di un commento Steve Jessops è se vector sarebbe più efficiente utilizzando realloc ho scritto un proof of concept di prova. Il realloc-vector simula modello di crescita di un vettore, ma ha la possibilità di realloc invece. Ho eseguito il programma fino a un milione di elementi nel vettore.

Per confronto un vector deve allocare 19 volte durante la crescita di un milione di elementi.

I risultati, se il realloc-vector è l'unica cosa con il cumulo dei risultati sono impressionanti, 3-4 allocazione durante la crescita delle dimensioni del milione di byte.

Se il realloc-vector viene utilizzato insieme un vector che cresce al 66% della velocità della realloc-vector I risultati sono meno promettenti, ripartizione 8-10 volte durante la crescita.

Infine, se il realloc-vector viene utilizzato insieme un vector che cresce alla stessa velocità, il realloc-vector alloca 17-18 volte. A mala pena salvare un'allocazione sul comportamento vettore standard.

Non metto in dubbio che un hacker potrebbe gioco dimensioni di allocazione per migliorare il risparmio, ma sono d'accordo con Steve che l'enorme sforzo per scrivere e mantenere un tale allocatore non è il lavoro il guadagno.

Answer 1

vector cresce generalmente in grandi incrementi. Non si può fare che ripetutamente senza trasferimento, a meno che ad organizzare le cose con attenzione in modo che ci sia una gran parte di indirizzi liberi appena sopra il buffer interno del vettore (che in effetti richiede l'assegnazione di pagine intere, perché ovviamente non si può avere altre destinazioni in seguito sulla stessa pagina).

Quindi penso che, al fine di ottenere una buona ottimizzazione qui, è necessario più di una "soluzione banale" che fa una riallocazione a buon mercato se possibile - quello che dovete fare in qualche modo una certa preparazione per make e 'possibile, e che i costi di preparazione si spazio indirizzo. Se solo lo si fa per alcuni vettori, quelli che indicano che stanno andando a diventare grande, quindi è abbastanza inutile, perché possono indicare con reserve() che hanno intenzione di diventare grande. Si può solo farlo automaticamente per tutti i vettori se si dispone di un vasto spazio di indirizzamento, in modo da poter "sprecare" una grossa fetta di esso su ogni vettore.

A quanto mi risulta, la ragione per cui il concetto Allocator non ha alcuna funzione di riallocazione è quello di mantenere le cose semplici. Se std::allocator aveva una funzione try_realloc, allora o ogni Allocatore avrebbe dovuto avere uno (che nella maggior parte dei casi non potrebbero essere attuate, e sarebbe solo dovuto tornare falso sempre), oppure ogni contenitore standard dovrebbe essere specializzato per std::allocator a approfittarne. Nessuna delle due opzioni è una grande interfaccia allocator, anche se suppongo che non sarebbe stato uno sforzo enorme per gli implementatori di quasi tutte le classi Allocator solo per aggiungere una funzione di do-nothing try_realloc.

Se vector è lento a causa di riallocazione, deque potrebbe essere una sostituzione buona.

Answer 2

Si potrebbe implementare qualcosa di simile alla try_realloc avete proposto, utilizzando mmap con MAP_ANONYMOUS e MAP_FIXED e mremap con MREMAP_FIXED.

Modifica : appena notato che la pagina man per mremap dice ancora:

  

mremap () utilizza la tabella delle pagine di Linux   schema. mremap () cambia il   mapping tra          indirizzi e pagine di memoria virtuale. Questo può essere utilizzato per implementare   un efficiente          realloc (3).

Answer 3

realloc in C è poco più di una funzione di convenienza; ha un piccolo vantaggio per le copie di prestazioni / riduzione. La principale eccezione che posso pensare è codice che alloca una matrice grande riduce quindi la dimensione una volta che la dimensione necessaria è noto - ma anche questo potrebbe richiedere lo spostamento di dati in alcune implementazioni malloc (quelli che blocca strettamente per dimensione segregano) così ritengo questo uso di realloc davvero cattiva pratica.

Fino a quando non si costantemente riallocare l'array ogni volta che si aggiunge un elemento, ma invece crescere in modo esponenziale la matrice (ad esempio del 25%, 50% o 100%) ogni volta che si esaurisce lo spazio, proprio l'assegnazione manualmente nuova memoria, copiando, e liberando il vecchio produrrà meno lo stesso (e identica, in caso di frammentazione della memoria) prestazioni usando realloc. Questo è sicuramente l'approccio che C ++ implementazioni STL utilizzano, quindi penso che tutta la vostra preoccupazione è infondata.

Modifica : Quello (raro ma non inaudita) caso in cui realloc è effettivamente utile è per i blocchi giganti su sistemi con memoria virtuale, dove i interagisce libreria C con il kernel a trasferirsi pagine intere ai nuovi indirizzi. La ragione per cui dico questo è raro perché è necessario avere a che fare con molto grandi blocchi (almeno diverse centinaia kB) prima della maggior parte delle implementazioni sarà nemmeno entrare nel regno di trattare con allocazione della pagina-granularità, e probabilmente molto più grande (diversi MB forse) prima di entrare e uscire kernelspace per riorganizzare la memoria virtuale è più conveniente che semplicemente facendo la copia. Naturalmente try_realloc non sarebbe utile qui, dal momento che tutto il vantaggio deriva dal fatto fare la mossa a buon mercato.