ottimizzazione stringa piccola per il vettore?

So che diverse (tutte?) Implementazioni di STL implementano un'ottimizzazione "piccola stringa" dove invece di memorizzare i soliti 3 puntatori per inizio, fine e capacità una stringa memorizzerà i dati di carattere reali nella memoria utilizzata per i puntatori se sizeof (caratteri) < = sizeof (puntatori). Sono in una situazione in cui ho molti piccoli vettori con una dimensione di elemento < = sizeof (puntatore). Non posso usare matrici di dimensioni fisse, poiché i vettori devono essere in grado di ridimensionarsi dinamicamente e potenzialmente diventare abbastanza grandi. Tuttavia, la dimensione mediana (non significativa) dei vettori sarà di soli 4-12 byte. Quindi una ottimizzazione "piccola stringa" adattata ai vettori sarebbe abbastanza utile per me. Esiste una cosa del genere?ottimizzazione stringa piccola per il vettore?

Sto pensando di far ruotare il mio proprio mediante la forza bruta che converte un vettore in una stringa, cioè fornendo un'interfaccia vettoriale a una stringa. Buona idea?

fonte

2010-02-01 BuschnicK

La tua domanda non è molto chiara. Inoltre, cosa intendi con un'interfaccia 'vector' in una' stringa'? Stai parlando di una speciale classe 'svector' per contenere stringhe piccole? – dirkgently

No. Intendo una stringa che contiene valori arbitrari anziché tipi di caratteri, proprio come un vettore. Un'interfaccia vettoriale per una stringa significa avvolgere l'oggetto stringa ed esporre un'interfaccia vettoriale compatibile, aggiungendo le funzioni mancanti come push_back. – BuschnicK

Non sarebbe possibile fare qualcosa con l'allocatore? Non avresti nemmeno 3 punti di memoria, dal momento che il vettore ha bisogno anche di un modo per sapere se è nella modalità "piccola" o "grande". – UncleBens

È possibile prendere in prestito l'implementazione SmallVector da LLVM. (solo header, che si trova in LLVM \ include \ llvm \ ADT)

fonte

2010-02-01 17:29:49

Non è più solo intestazione. L'intestazione – rightfold

è qui: https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallVector.h – Nick

Era discussed anni fa (e alcuni nomi in quel thread potrebbero sembrare un po 'familiari :-)), ma non conosco un'implementazione esistente. Non penso che proverei ad adattare std :: string all'attività. I requisiti esatti per il tipo su cui std :: basic_string non sono ben definiti, ma lo standard è abbastanza chiaro che è destinato solo a qualcosa che agisce molto come char. Per tipi che sono sostanzialmente diversi, potrebbe comunque funzionare, ma è difficile dire cosa succederebbe - non è mai stato concepito e probabilmente non è stato testato con molti tipi diversi dai piccoli interi.

Quando ci si arriva a fondo, l'implementazione di std::vector da zero (compresa l'ottimizzazione di un piccolo vettore) non sarà molto difficile.

fonte

2010-02-01 16:47:49

+11

Implementare 'std :: vector' * correttamente * da zero è sorprendentemente difficile. Ovviamente, se si sceglie di ignorare la sicurezza delle eccezioni, diventa molto più semplice, ma non è più un'implementazione 'vettoriale' significativa (o utile). – jalf

Grazie per il puntatore - purtroppo la discussione non ha mai veramente raggiunto una conclusione. L'implementazione del mio vettore non sarebbe poi così difficile, sono d'accordo. Tuttavia, speravo di collegare solo alcune classi già pronte e vedere l'effetto sul consumo di memoria. Attualmente sto giocando con varie idee per ridurre il nostro impatto sulla memoria e questo è solo uno di questi. – BuschnicK

Quando ciò viene detto, penso che un'implementazione vettoriale personalizzata sarebbe il modo migliore per raggiungere questo obiettivo. Disporre la classe vettoriale esistente renderebbe difficile sfruttare in modo efficiente la dimensione dell'oggetto, e un vettore personalizzato non è una scienza missilistica, a patto che tu stia attento e sappia cosa stai facendo. – jalf

Se T è un tipo POD perché non basic_string invece di vettore ??

fonte

2010-03-14 18:21:11

Nota che dovresti scrivere una specializzazione 'std :: char_traits' (o una classe di tratti equivalente) per il tipo POD. I requisiti non sono così severi, se non la necessità di nominare un valore speciale "eof", ma mi aspetto che sia un po 'noioso. –

Inoltre, non vi è alcuna garanzia che 'basic_string ' utilizzi l'ottimizzazione delle stringhe di piccole dimensioni, e nessun modo portatile per specificare quanti elementi, anche se lo fa. –

Boost 1.58 è stato appena rilasciato ed è la libreria Container con classe small_vector basata su LLVM SmallVector.

C'è anche un static_vector che non può crescere oltre la dimensione data inizialmente. Entrambi i contenitori sono solo di intestazione.

La libreria di facebook folly ha anche alcuni fantastici contenitori.

Ha un small_vector che può essere configurato con un parametro di modello di agire come static o small vettori di boost. Può anche essere configurato per utilizzare i piccoli numeri interi per la sua dimensione interna che non è sorprendente :)

Sono in corso lavori per rendere la libreria multipiattaforma in modo che il supporto di Windows/MSVC debba atterrare un giorno ...

fonte

2015-04-17 10:47:24 onqtam

ottimizzazione stringa piccola per il vettore?

risposta

Problemi correlati