[C++] Memory allocator

[giuseppe500]

Ciao.
Girando per internet e un po studiando in queste feste sono caduto su una cosa interessante:
i memory allocator:
http://en.wikipedia.org/wiki/Dynamic_memory_allocation.
Da quello che ho capito allocano un grande spazio il piu possibile contiguo e vasto per poi suddividerlo rapidamente e spedirlo a chi chiede della memoria
ho letto i vantaggi e gli svantaggi , e vorrei utilizzarli nel piccolo engine che sto costruendo in dx per lo scene manager(un grafo che descrive gli oggetti presenti nella scena per intenderci).
Ho la senzazione pero' che possa essere effettivamente complicato creare anche un semplice memory allocator , ma ce ne sono di open source.
soprattutto mi sono sembrate fatte al mio caso le freelist:
http://en.wikipedia.org/wiki/Free_list
che allocano zone tutte della stessa memoria e hanno un puntatore alla successiva zona.
La mia idea sarebbe quella di creare un albero binario bilanciato per partizionare velocemente le zone di memoria che sono di una determinata grandezza (le grandezze saranno 10/15 nel mio caso, perchè i modelli sono di quel numero , ma posso averne moltissimi).
In questo albero infatti un nodo tiene n kb e ripartiziono se la zona di memoria è piu piccola di n creo un nodo a sx o è piu grande di n creo un nuovo nodo a dx, se ho pochi pacchetti di memoria tipici ma diversi traa di loro potrei trovare un numero grossolano che sia il piu' vicino possibile ad un multiplo di tutti gli oggetti.
voi ne avete mai usati?
ciao.

[shodan]

che allocano zone tutte della stessa memoria e hanno un puntatore alla successiva zona.

Che è più o meno quello che fanno tutti gli allocatori.

Se ti serve un buon allocatore, ti consiglio di dare un'occhiata al Doug Lea Allocator.
http://g.oswego.edu/dl/html/malloc.html

Così puoi studiarne il sorgente e renderti conto di come sia complicata la cosa.
Io l'ho usato e adattato alle mie esigenze, estraendo le funzioni che m'interessavano ( la malloc e la free) e poi impacchettando il tutto in un'interfaccia compatibile con lo std::allocator.
In questo modo invece di scrivere:

vector<MyClass> vec;

posso scrivere:

vector< MyClass, CustomAllocator<MyClass> > vec;

[giuseppe500]

grazie shodan.
Ho letto i vari goal degli allocator nel tuo link?
Ma hai visto miglioramenti sostanziali delle prestazioni con questo allocator?
Penso che comunque dichiarare tutte le allocazioni con un custom allocator sia utile all' inizio della progettazione , in modo che se bisogna cambiare l'allocator per qualche motivo è basta cambiare le classi dell' allocator.
Ciao.

[shodan]

Originariamente inviato da giuseppe500
Ma hai visto miglioramenti sostanziali delle prestazioni con questo allocator?

Se cerchi un pò con google, troverai diverse tabelle di comparazione a riguardo. E' considerato un pò lo "stato dell'arte" per quanto riguarda gli allocatori. (Anche se ovviamente occorre sempre andarci piano quando si parla di "stato dell'arte").

Per quel che mi riguarda, ho notato notevoli incrementi con la std::list mentre un pò meno con il vector. Si parla comunque di grosse allocazioni di più elementi (1.000.000)
Per singolo elemento non ci si accorge nemmeno che c'è.

Penso che comunque dichiarare tutte le allocazioni con un custom allocator sia utile all' inizio della progettazione , in modo che se bisogna cambiare l'allocator per qualche motivo è basta cambiare le classi dell' allocator.

Infatti è per quello che ho messo il tutto in una classe allocator compatibile STL. Quando mi serve, cambio allocatore e ricompilo.

[giuseppe500]

Quello che ti chiedo shodan è se secondo te è un impresa ardua creare un piccolo allocator per un videogioco dove devo allocare piu' o meno sempre oggetti di una certa grandezza(i miei modelli) , conosciuta a compile time.
dato che i normali allocator devono essere generici per qualsiasi tipo di grandezza da allocare, e se per questo limitando la complessita e l'algoritmo di allocazione posso guadagnare in modo sensibile le prestazioni.
Non utilizzo le liste stl e non mi interessa l'stl , utilizzo come container una semplice lista implementata con i template , sempre per la leggerezza.
Mi sono appoggiato per le implementazioni e le idee ad un famoso libro sugli engine dei videogiochi.
ma ho sempre paura che su questi libri ci siano molte inesatezze , è per questo che te lo chiedo.
Ciao shodan, buon anno.

[MItaly]

[OT]Se ti serve una STL appositamente pensata per i videogiochi c'è la EASTL, che, guarda caso, tra le altre cose cambia diverse cose per quanto riguarda gli allocatori.[/OT]

[shodan]

Originariamente inviato da giuseppe500
Quello che ti chiedo shodan è se secondo te è un impresa ardua creare un piccolo allocator

Se dev'essere generico e valido per tutti i tuoi oggetti: SI è un delirio.
Se accetti che ogni oggetto abbia un proprio specifico pool di allocazione, la cosa diventa più semplice, ma occorre accettare dei compromessi (pochi a dire il vero).

In sostanza, l'idea di ogni FixedSize Allocator è di preallocare un'area di memoria grezza ( in un array di puntatori a classe base) e costruire o distruggere il nuovo oggetto senza allocare o deallocare ogni volta la memoria (che verrà liberata solo alla fine del programma).

Inserendo questo FixedSize Allocator in una classe container che ridefinisce operator new e operator delete ( che richiamano le funzioni dell'allocatore) e derivando la classe base dei tuoi oggetti da questa classe container, il tutto diventa trasparente all'utente. Quando si supera il numero massimo di oggetti allocabili, o si lancia un'eccezione (la classica std::bad_alloc() ) oppure si ritorna un puntatore nullo. (In questo caso penso che sia migliore il puntatore nullo che l'eccezione.)

Buon anno anche a te

[giuseppe500]

grazie mitaly , ma si puo' scaricare liberamente ? non ho trovato il link e dire che ho cercato.
Non credo che pero sia opensource.
Ciao.

[MItaly]

Originariamente inviato da giuseppe500
grazie mitaly , ma si puo' scaricare liberamente ? non ho trovato il link e dire che ho cercato.

Hmmm, hai ragione, probabilmente è solo per loro uso interno... mi spiace, credevo fosse scaricabile liberamente, mentre invece sembra che nemmeno la vendano.