std :: classe di tipo vettoriale ottimizzata per contenere un numero ridotto di elementi

In una parte del programma di importanza temporale c'è un membro della classe simile a questo: std :: vector m_vLinks; Durante la profilazione ho notato che circa il 99,98% delle esecuzioni in questo vettore contiene solo 0 o 1 elementi. Tuttavia in casi molto rari potrebbe trattenere di più. Questo vettore è sicuramente un collo di bottiglia secondo il profiler, così sto pensando di seguire ottimizzazione:std :: classe di tipo vettoriale ottimizzata per contenere un numero ridotto di elementi

Craft una classe fatta a mano con il vettore-come l'interfaccia
Questa classe terrà vera dimensione, un elemento e puntatore opzionale al vettore
In questo caso quando il vettore contiene 1 elemento non ci saranno allocazioni di memoria dinamica, e anche l'accesso a questo elemento sarà (un po ') più veloce a causa della rimozione di un punto di riferimento.
Quando occorre tenere vettore più dati viene allocata dinamicamente
Naturalmente questo vettore non fornirà un blocco di memoria in possesso di tutti gli elementi (non necessario qui), e anche alcune operazioni sarà più complesso

Prima di iniziare a prototipare questa cosa per vedere se aiuta, mi chiedo se qualcuno abbia incontrato contenitori personalizzati con funzionalità simili in alcune librerie di terze parti?

ho già pensato a boost :: array, ma non vogliono limite di dimensione che impone

fonte

2012-02-21 Alex Zakharenko

Quali operazioni eseguono esattamente la maggior parte del tempo nello scenario? – sharptooth

rappresenta un collo di bottiglia perché ne crei di nuovi di frequente? In tal caso dubito che la tua ottimizzazione possa aiutare molto ... –

Assegnare e liberare il buffer dinamico del vettore (Io uso il pool di oggetti per contenere oggetti che hanno questo membro, ma in ogni caso è necessario pulirli periodicamente scambiando il vettore di Links con il vettore vuoto, sebbene questa operazione non è frequente). –

LLVM ha una classe per quella denominata SmallVector.

fonte

2012-02-21 14:45:34

Ovviamente, l'unica domanda: è più veloce, davvero? C'è una gerarchia piuttosto pesante e mi chiedo se possa gestire la velocità di 'vector' o meno. –

In generale, le gerarchie non rallentano il codice. I compilatori lo vedono bene. In particolare, se vedi roba come "is_pod " in una gerarchia, sai che è un calcolo in fase di compilazione. – MSalters

@MSalters: scusa se non sembra corretto. Quello che volevo dire è che c'è troppo codice per me per guardare o no che sarà più veloce di 'vector'. –

Generalmente uso std::list per questi casi. Le operazioni O (N) in std::list non mi fanno male quando N == 1.

fonte

2012-02-21 14:58:41 MSalters

Suppongo che ci sia almeno 1 allocazione dinamica della memoria quando l'elemento viene aggiunto alla lista (anche se si tratta del primo elemento). Avevo bisogno della soluzione che potesse contenere 1 elemento senza allocazioni dinamiche –

Vero, ma quella allocazione dinamica è sempre della stessa dimensione (nodo singolo), diversamente da std :: vector, e il puntatore del nodo è sempre dereferenziato. In realtà non è così brutto come penseresti, su hardware moderno e con moderni allocatori. – MSalters

L'allocazione dinamica viene risolta dal pool che sta utilizzando. Tuttavia, ciò porta a una località povera. – phkahler

In una parte non critica del proprio codice, eseguire: m_vLinks.reserve(1);. In questo modo, nella parte temporale, di solito non ci sarà alcuna allocazione dinamica.

fonte

2012-02-21 15:00:10

Mi piace la tua proposta. Semplice. Mantienilo semplice. (+1) –

http://stackoverflow.com/a/36371057/1599699 – Andrew

Il mio primo tentativo sarebbe quello di ottimizzare l'allocatore di memoria. Le implementazioni di Naive malloc non sono troppo efficienti, potresti provare a provare tcmalloc o jemalloc.

Il mio secondo tentativo sarebbe quello di cambiare l'allocatore. Howard Hinnant ha dimostrato come utilizzare un allocatore di stato che ha una memoria preallata nello stack. Questo è solo conforme allo standard in C++ 11, ma potrebbe già essere supportato.

Il mio terzo tentativo sarebbe quello di modificare il codice e pre-allocare la memoria, se possibile. Invece di costruire di nuovo il vector ogni volta, è possibile tenerlo in giro: la sua capacità non diminuirà e quindi gli usi successivi non allocheranno la memoria.

Ci sono poche possibilità che un'implementazione homebrew corrisponda alla velocità delle classi std::vector<T>, poiché molti dei suoi metodi sono stati ottimizzati per le massime prestazioni.

fonte

2012-02-21 15:05:06

std :: classe di tipo vettoriale ottimizzata per contenere un numero ridotto di elementi

risposta

Problemi correlati