petite optimisation de chaîne pour le vecteur?

Je sais que plusieurs implémentations STL implémentent une optimisation "small string" où au lieu de stocker les 3 pointeurs habituels pour begin, end et capacity une chaîne stockera les données de caractères dans la mémoire utilisée pour les pointeurs si sizeof (caractères) < = sizeof (pointeurs). Je suis dans une situation où j'ai beaucoup de petits vecteurs avec une taille d'élément < = sizeof (pointeur). Je ne peux pas utiliser des tableaux de taille fixe, car les vecteurs doivent être capables de redimensionner dynamiquement et peuvent potentiellement devenir assez volumineux. Cependant, la taille médiane (non moyenne) des vecteurs ne sera que de 4 à 12 octets. Donc une optimisation "petite chaîne" adaptée aux vecteurs me serait très utile. Est-ce qu'une telle chose existe?petite optimisation de chaîne pour le vecteur?

Je pense à lancer le mien par simple force brute en convertissant un vecteur en chaîne, c'est-à-dire en fournissant une interface vectorielle à une chaîne. Bonne idée?

Source

2010-02-01 BuschnicK

Votre question n'est pas très claire. De plus, que voulez-vous dire par une interface 'vector' à une' string'? Parlez-vous d'une classe 'svector' spéciale pour contenir de petites chaînes? – dirkgently

Non. Je veux dire une chaîne contenant des valeurs arbitraires au lieu de types de caractères - tout comme un vecteur. Une interface vectorielle à une chaîne signifie l'encapsulation de l'objet chaîne et l'exposition d'une interface compatible avec le vecteur, en ajoutant les fonctions manquantes comme push_back. – BuschnicK

Ne serait-il pas possible de faire quelque chose avec l'allocateur? Vous n'obtiendrez même pas 3 pointeurs de mémoire, car le vecteur a également besoin d'un moyen de savoir s'il est dans le mode "petit" ou "grand". – UncleBens

Vous pouvez emprunter l'implémentation SmallVector à partir de LLVM. (en-tête uniquement, situé dans LLVM \ include \ llvm \ ADT)

Source

2010-02-01 17:29:49

Ce n'est plus seulement en-tête. – rightfold

l'en-tête est ici: https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallVector.h – Nick

Il était discussed ans (et quelques-uns des noms dans ce fil peuvent sembler un peu familier :-)), mais je ne connais pas une implémentation existante. Je ne pense pas que j'essaierais d'adapter std :: string à la tâche. Les exigences exactes sur le type sur lequel std :: basic_string ne sont pas bien énoncées, mais la norme est assez claire que c'est seulement destiné à quelque chose qui agit beaucoup comme char. Pour les types qui sont sensiblement différents, cela peut encore fonctionner, mais il est difficile de dire ce qui se passerait - il n'a jamais été prévu, et n'a probablement pas été testé avec de nombreux types autres que les petits entiers. Quand vous y arriverez, l'implémentation de std::vector à partir de rien (même avec une optimisation de petit vecteur) ne sera pas très difficile.

Source

2010-02-01 16:47:49

+11

L'implémentation correcte de 'std :: vector' * correctement * est étonnamment difficile. Bien sûr, si vous choisissez d'ignorer la sécurité des exceptions, cela devient beaucoup plus facile, mais alors ce n'est plus une implémentation 'vecteur' significative (ou utile). – jalf

Merci pour le pointeur - malheureusement, la discussion n'a jamais vraiment abouti. Mettre en œuvre mon propre vecteur ne serait pas si difficile, je suis d'accord. Cependant, j'espérais juste brancher une classe déjà faite et voir l'effet sur la consommation de mémoire. Je suis actuellement en train de jouer avec différentes idées de réduction de notre empreinte mémoire et ce n'est qu'un d'entre eux. – BuschnicK

Quand cela est dit, je pense qu'une implémentation de vecteur personnalisé serait le meilleur moyen d'y parvenir. Envelopper la classe de vecteurs existante rendrait difficile l'exploitation efficace de la taille de l'objet, et un vecteur personnalisé n'est pas sorcier, à condition d'être prudent et de savoir ce que vous faites. – jalf

Si T est un type POD, pourquoi pas basic_string au lieu du vecteur ??

Source

2010-03-14 18:21:11

Notez que vous devriez écrire une spécialisation 'std :: char_traits' (ou une classe de traits équivalente) pour le type POD. Les exigences ne sont pas si sévères, si ce n'est la nécessité de nommer une valeur spéciale «eof», mais je pense que c'est un peu fastidieux. –

De plus, il n'y a aucune garantie que 'basic_string ' utilisera une optimisation de petite chaîne, et pas de façon portable de spécifier combien d'éléments, même si c'est le cas. –

Boost 1.58 vient de sortir et il est Container bibliothèque a une classe small_vector basée sur la LLVM SmallVector. Il existe également un static_vector qui ne peut pas dépasser la taille initiale donnée. Les deux conteneurs sont uniquement en-tête.

La bibliothèque de facebook a également quelques récipients impressionnants.

Il a une small_vector qui peut être configuré avec un paramètre de modèle pour agir comme static ou small vecteurs de boost. Il peut également être configuré pour utiliser de petits types entiers pour sa taille interne, ce qui n'est pas une surprise :)

Il y a des travaux en cours pour faire de la bibliothèque une plate-forme multiplateforme pour que le support Windows/MSVC se pose un jour ...

Source

2015-04-17 10:47:24 onqtam

petite optimisation de chaîne pour le vecteur?

Répondre

Questions connexes