Concaténation de chaînes en C # avec des chaînes internes

Question

Je connais cette question a été done , mais j'ai une tournure légèrement différente. Plusieurs ont fait remarquer qu'il s'agissait d'une optimisation prématurée, ce qui est tout à fait vrai si je demandais le principe de la praticité et le seul principe de la fonctionnalité. Mon problème est enraciné dans un problème pratique mais je suis quand même curieux.

Je crée un tas d'instructions SQL pour créer un script (car il sera sauvegardé sur le disque) pour recréer un schéma de base de données (facilement plusieurs centaines de tables, vues, etc.). Cela signifie que ma concaténation de chaînes est uniquement ajoutée. Selon MSDN, StringBuilder fonctionne en conservant un tampon interne (sûrement un caractère []), en y copiant les caractères de chaîne et en réallouant le tableau, si nécessaire.

Cependant, mon code comporte beaucoup de chaînes de répétition (& "CREATE TABLE [&"; & "GO \ n &" ;, etc.), ce qui signifie que je peux prendre leur avantage en cours d'internement , mais pas si j'utilise StringBuilder car ils seraient copiés chaque fois. Les seules variables sont essentiellement des noms de tables et sont déjà existantes en tant que chaînes dans d'autres objets déjà en mémoire.

Donc, autant que je sache, une fois mes données lues et mes objets contenant les informations de schéma créés, toutes mes informations de chaîne peuvent être réutilisées en effectuant un interning, oui?

En supposant cela, une liste ou une liste LinkedList de chaînes ne seraient-elles pas plus rapides car elles conserveraient les pointeurs sur les chaînes internées? Ensuite, il n'y a qu'un seul appel à String.Concat () pour une seule allocation de mémoire de la chaîne entière qui a exactement la longueur correcte.

Une liste devrait réaffecter la chaîne [] de pointeurs internés et une liste chaînée devrait créer des noeuds et modifier des pointeurs, de sorte qu'ils ne soient pas & "libres &"; mais si je concaténisais plusieurs milliers de chaînes internées , ils sembleraient alors être plus efficaces.

Maintenant, je suppose que je pourrais créer une heuristique sur le nombre de caractères pour chaque instruction SQL & amp; comptez chaque type et obtenez une idée approximative et prédéfinissez ma capacité de StringBuilder pour éviter de réaffecter son caractère [], mais il me faudrait un dépassement important pour réduire la probabilité de réaffectation.

Donc, dans ce cas, le plus rapide serait d'obtenir une seule chaîne concaténée:

 
• StringBuilder
 
• Liste < chaîne > des chaînes internées
 
• LinkedList < chaîne > des chaînes internées
 
• StringBuilder avec une heuristique de capacité
 
• Autre chose?

En tant que question distincte (il est possible que je ne passe pas toujours sur le disque), un seul StreamWriter vers un fichier de sortie serait-il encore plus rapide? Vous pouvez également utiliser List ou LinkedList puis les écrire dans un fichier de la liste au lieu de les concaténer en mémoire.

EDIT: Comme demandé, la référence (.NET 3.5) à MSDN. Il indique: & "; De nouvelles données sont ajoutées à la fin de la mémoire tampon si de la place est disponible; sinon, un nouveau tampon plus grand est alloué, les données du tampon d'origine sont copiées dans le nouveau tampon, puis les nouvelles données sont ajoutées au nouveau tampon. " Cela signifie pour moi un caractère []. qui est réalloué pour le rendre plus grand (ce qui nécessite de copier les anciennes données dans le tableau redimensionné) puis de l'ajouter.

Answer 1

Pour votre question distincte , Win32 a un WriteFileGather , qui permet d'écrire efficacement une liste de chaînes (internées) sur le disque - mais cela ne ferait une différence notable que lors de l'appel asynchrone, car l'écriture sur le disque occultera toutes les concaténations, mais extrêmement grandes.

Pour votre question principale : sauf si vous atteignez des mégaoctets de script ou des dizaines de milliers de scripts, ne vous inquiétez pas.

Vous pouvez vous attendre à ce que StringBuilder double la taille d'allocation à chaque réallocation. Cela signifierait qu’une augmentation de la mémoire tampon de 256 octets à 1 Mo ne représente que 12 réaffectations, ce qui est plutôt bon, étant donné que votre estimation initiale était de 3 ordres de grandeur par rapport à la cible.

À titre purement exercice, quelques estimations: la construction d’une mémoire tampon de 1 Mo balayera environ 3 Mo de mémoire (source de 1 Mo, cible de 1 Mo, 1 Mo en raison de copie pendant la realloation).

Une implémentation de liste chaînée balayera environ 2 Mo (et ceci ignore la surcharge de 8 octets / objet par référence de chaîne). Vous économisez ainsi 1 Mo de lecture / écriture en mémoire, par rapport à une bande passante mémoire typique de 10 Gbit / s et à 1 Mo de cache L2.)

Oui, une implémentation de liste est potentiellement plus rapide et la différence aurait de l'importance si vos tampons étaient d'un ordre de grandeur supérieur.

Dans le cas beaucoup plus courant de petites chaînes, le gain algorithmique est négligeable et facilement compensé par d'autres facteurs: le code StringBuilder est probablement déjà dans le cache de code et constitue une cible viable pour les microoptimisations. De plus, utiliser une chaîne en interne signifie ne pas copier du tout si la chaîne finale correspond au tampon initial.

L'utilisation d'une liste chaînée ramènera également le problème de réallocation de O (nombre de caractères) à O (nombre de segments) - votre liste de références de chaîne fait face au même problème qu'une chaîne de caractères!

---

Ainsi, la mise en œuvre de StringBuilder par OMI est le bon choix, elle est optimisée pour les cas courants et se dégrade principalement pour les mémoires tampons cibles de taille inattendue. Je m'attendrais à ce qu'une implémentation de liste se dégrade d'abord pour de très petits segments, ce qui est en fait le type de scénario extrême que StringBuilder tente d'optimiser.

Néanmoins, il serait intéressant de voir une comparaison des deux idées, et lorsque la liste commencera à être plus rapide.

Answer 2

Si je mettais en œuvre quelque chose comme ceci, je ne construirais jamais un StringBuilder (ni aucun autre dans la mémoire tampon de votre script). Je voudrais simplement le diffuser dans votre fichier à la place et rendre toutes les chaînes en ligne.

Voici un exemple de pseudo-code (pas syntaxiquement correct ou quoi que ce soit):

FileStream f = new FileStream("yourscript.sql");
foreach (Table t in myTables)
{
    f.write("CREATE TABLE [");
    f.write(t.ToString());
    f.write("]");
    ....
}

Ensuite, vous n'aurez plus jamais besoin d'une représentation en mémoire de votre script, avec toutes les copies de chaînes.

Des opinions?

Answer 3

D'après mon expérience, j'ai correctement attribué à StringBuilder une performance supérieure à celle de tous les autres pour de grandes quantités de données de chaîne. Vous pouvez même perdre un peu de mémoire en dépassant votre estimation de 20% ou 30% afin d'éviter toute réallocation. Je n'ai pas actuellement de chiffres précis pour sauvegarder mes données avec mes propres données, mais jetez un oeil à cette page pour plus .

Toutefois, comme Jeff tient à le souligner, n'optimisez pas prématurément!

EDIT: Comme l'a souligné @Colin Burnett, les tests effectués par Jeff ne concordent pas avec ceux de Brian, mais le lien entre le message de Jeff concernait l'optimisation prématurée en général. Plusieurs commentateurs sur la page de Jeff ont signalé des problèmes avec ses tests.

Answer 4

En réalité, StringBuilder utilise une instance de String en interne. System est en fait modifiable dans l’ensemble "SOMESTRINGA", raison pour laquelle "SOMESTRINGB" peut être construit par-dessus. Vous pouvez rendre <=> un peu plus efficace en affectant une longueur raisonnable lors de la création de l'instance. De cette façon, vous éliminerez / réduirez le nombre d'opérations de redimensionnement.

L'internement de chaînes fonctionne pour les chaînes identifiables au moment de la compilation. Ainsi, si vous générez beaucoup de chaînes lors de l'exécution, elles ne seront pas internées sauf si vous le faites vous-même en appelant la méthode interning on string.

L'internat ne vous profitera que si vos chaînes sont identiques. Les chaînes presque identiques ne tirent pas profit de l'internat. Par conséquent, <=> et <=> seront deux chaînes différentes, même si elles sont internées.

Answer 5

Si toutes les chaînes (ou la plupart) concaténées sont internées, votre schéma PEUT alors vous donner un gain de performances car il pourrait potentiellement utiliser moins de mémoire et économiser quelques grandes copies de chaînes.

Toutefois, l’amélioration de la performance dépend du volume de données que vous traitez, car l’amélioration est exprimée en facteurs constants et non en ordre de grandeur de l’algorithme.

La seule façon de vraiment savoir est de lancer votre application en utilisant les deux méthodes et de mesurer les résultats. Cependant, à moins que vous ne soyez soumis à une pression mémoire importante et que vous ayez besoin d'un moyen de sauvegarder des octets, cela ne me dérangerait pas et utiliserais simplement le constructeur de chaînes.

Answer 6

Un StringBuilder n'utilise pas de char[] pour stocker les données, il utilise une chaîne interne mutable. Cela signifie qu’il n’ya pas d’étape supplémentaire pour créer la chaîne finale, comme lors de la concaténation d’une liste de chaînes. Le <=> retourne simplement le tampon de chaîne interne sous forme de chaîne normale.

Les réaffectations effectuées par <=> pour augmenter la capacité signifient que les données sont en moyenne copiées 1,33 fois supplémentaires. Si vous pouvez fournir une bonne estimation de la taille lors de la création de la <=>, vous pouvez réduire encore davantage cette taille.

Cependant, pour avoir un peu de recul, vous devriez regarder ce que vous essayez d'optimiser. La plupart du temps, dans votre programme, c’est d’écrire les données sur le disque. Ainsi, même si vous pouvez optimiser le traitement de votre chaîne de caractères deux fois plus rapidement que l’utilisation de <=> (ce qui est très peu probable), la différence globale encore être que quelques pour cent.

Answer 7

Avez-vous envisagé le C ++ pour cela? Existe-t-il une classe de bibliothèque qui construit déjà des expressions T / SQL, de préférence écrite en C ++?

La chose la plus lente sur les chaînes est malloc. Il faut 4 Ko par chaîne sur les plates-formes 32 bits. Envisagez d’optimiser le nombre d’objets chaîne créés.

Si vous devez utiliser C #, je vous conseillerais quelque chose comme ceci:

string varString1 = tableName;
string varString2 = tableName;

StringBuilder sb1 = new StringBuilder("const expression");
sb1.Append(varString1);

StringBuilder sb2 = new StringBuilder("const expression");
sb2.Append(varString2);

string resultingString = sb1.ToString() + sb2.ToString();

J'irais même jusqu'à laisser l'ordinateur évaluer le meilleur chemin pour l'instanciation d'objet avec des infrastructures d'injection de dépendances, si perf est SI important.