Migliorare l'efficienza dei contenitori con oggetti allocati dinamicamente

Penso che potresti più o meno risolvere questo problema disponendo di un'API simile agli allocatori, in base alla quale un contenitore potrebbe specificare come allocare i suoi metadati e gli elementi in modo contiguo. Cioè, un contenitore fornirebbe una "modalità non in scatola" in cui sarebbe presumibilmente immutabile, o almeno di dimensione fissa. Non è possibile allocare contenitori non in scatola nello stack perché il loro sizeof non è una costante in fase di compilazione, ma è possibile utilizzare questa API durante la costruzione di un contenitore nidificato.

Questo sembrerebbe funzionare naturalmente per std::vector e std::array , ma per std::list e std::deque (che è tipicamente implementato come un elenco collegato di blocchi di dimensioni fisse) o strutture ad albero come std::map , non è necessariamente chiaro cosa significherebbe in realtà un tale "unboxing". State guadagnando dall'assegnare tutti i nodi dell'albero in modo contiguo, ma continuando ad attraversarli con un sacco di riferimenti indiretti al puntatore? Senza benchmarking è difficile da dire.

Now I feel as though that if there was some way to communicate to the container that M has a definite size m (as in M, which is not legal in C++), then from the type signature of Container > one can potentially deduce that a faster allocation scheme is possible. (It's a bit like dependent types, in a way.) That is, any Container1 > can be allocated more efficiently as a "flattened" container.

Questo non è affatto un problema concettualmente semplice, perché qui ci sono due aggregati concorrenti (la classe M e la vector ) che vogliono essere dimensionati in modo indipendente in modo dinamico.

Da un punto di vista del compilatore e del linguaggio con un focus sugli approcci standard ai sistemi di tipo, questo è un problema incredibilmente difficile e richiederebbe una fusione / fusione dei due concetti aggregati.

In C ++, se si desidera la soluzione più efficiente qui, in genere è necessario implementare questo aggregato fuso (il contenitore e M come una singola classe che unisce le due idee insieme). È una vera seccatura, ma se hai davvero bisogno del guadagno extra, questa è in genere la strada da percorrere. Il percorso alternativo è quello di raggiungere un allocatore personalizzato sotto il cofano (ma è quasi come implementare una struttura dati separata ancora, e comunque espone il sovraccarico dei puntatori nel vector che degrada la località di riferimento, anche se non tanto quanto la mancanza del allocatore personalizzato).

Un linguaggio in grado di affrontare questo potrebbe essere l'ideale per il giorno e l'età di oggi di ottimizzazione della memoria predominante nei campi critici per le prestazioni, ma assumerebbe una natura molto insolita con il suo sistema di tipi. Molto probabilmente il sistema tipo sarebbe stato progettato per interagire con i contenitori con una mentalità non scalare.

Potresti essere in grado di progettare anche qualcosa di simile in C ++, ma tenderà a richiedere un nuovo set di contenitori che raddoppieranno sia come allocatore sia come struttura dati dove possiamo richiedere di istanziare cinque elementi di T , ma in un modo che produce un nuovo aggregato, M , ad es. con metadati associati che ti permettono di accedere a quel piccolo blocco contiguo come se fosse un aggregato separato di T's da solo.

Lascia anche una domanda sui requisiti di omogeneità e allineamento dei dati, perché M != m T's , ad es. Avrebbe associato i metadati che memorizza cose come la dimensione potenzialmente e probabilmente altri dati associati a m T's , quindi lascia la domanda su dove archiviare e allineare quello all'interno del contenitore (o possibilmente all'esterno in parallelo, ma all'esterno potrebbe ostacolare il rendimento e implicherebbe un puntatore / indice in alto nel contenuto del contenitore una volta di più piuttosto che un indirizzamento relativo), insieme a problemi di costruzione / distruzione per M che sono separati da m T's .

Un'altra cosa è che se M è autorizzato a ridimensionare m mentre risiede nel contenitore, ora c'è una dinamica nuova e persino più complessa in corso e soluzioni come vector non sarebbero adatte al problema poiché richiederebbero la complessità in tempo lineare per ridimensionare un singolo M al suo interno. M come aggregato dovrebbe anche evitare di memorizzare puntatori al vector in un modo o nell'altro, poiché tali puntatori verrebbero invalidati ogni volta che viene modificata la capacità vector's , ogni volta che un elemento viene rimosso da un luogo diverso dal retro, ecc. Fondamentalmente questo design, per essere ottimale, ha bisogno dell'idea di contenitore e sottocontenitore strettamente accoppiati tra loro in modi che sarebbero incredibilmente difficili da fare in modo generalizzato attraverso un nuovo tipo di sistema di tipi.