Concatenazione di stringhe in C # con stringhe internate

StackOverflow https://stackoverflow.com/questions/812503

Domanda

Conosco questa domanda è stata fatto ma ho una svolta leggermente diversa. Molti hanno sottolineato che si tratta di un'ottimizzazione prematura, il che è del tutto vero se chiedessi il bene della praticità e il solo interesse della praticità. Il mio problema è radicato in un problema pratico, ma sono comunque curioso.

Sto creando un mucchio di istruzioni SQL per creare uno script (in quanto verrà salvato su disco) per ricreare uno schema di database (facilmente molte centinaia di tabelle, viste, ecc.). Ciò significa che la mia concatenazione di stringhe è di sola aggiunta. StringBuilder, secondo MSDN, funziona mantenendo un buffer interno (sicuramente un char []) e copiando i caratteri stringa e riallocando l'array come necessario.

Tuttavia, il mio codice ha molte stringhe ripetute (" CREATE TABLE [" ;, " GO \ n " ;, ecc.) che significa che posso prendere vantaggio del fatto che vengano internati ma non se uso StringBuilder poiché verrebbero copiati ogni volta. Le uniche variabili sono essenzialmente nomi di tabelle e tali che esistono già come stringhe in altri oggetti che sono già in memoria.

Per quanto posso dire che dopo aver letto i miei dati e creato i miei oggetti che contengono le informazioni dello schema, tutte le mie informazioni sulla stringa possono essere riutilizzate internando, sì?

Supponendo che, quindi, un elenco o una lista di stringhe non siano più veloci perché mantengono i puntatori alle stringhe internate? Quindi è solo una chiamata a String.Concat () per una singola allocazione di memoria dell'intera stringa che è esattamente la lunghezza corretta.

Una lista dovrebbe riallocare la stringa [] di puntatori internati e una lista collegata dovrebbe creare nodi e modificare puntatori, quindi non sono " free " da fare ma se sto concatenando molte migliaia di stringhe internate , sembrerebbero più efficienti.

Ora suppongo che potrei trovare qualche euristica sul conteggio dei caratteri per ogni istruzione SQL & amp; contare ogni tipo e avere un'idea approssimativa e preimpostare la mia capacità di StringBuilder per evitare di riallocare il suo carattere [] ma avrei dovuto superare un margine equo per ridurre la probabilità di riallocare.

Quindi, in questo caso, sarebbe più veloce ottenere una singola stringa concatenata:

     
  • StringBuilder
    •  &
  • Lista lt; & Stringa gt; di stringhe internate
    •  &
  • LinkedList lt; stringa gt &; di stringhe internate
    •  
  • StringBuilder con una capacità euristica
    •  
  • Qualcos'altro?

Come domanda separata (potrei non andare sempre su disco) a quanto sopra: un singolo StreamWriter su un file di output sarebbe ancora più veloce? In alternativa, utilizzare un Elenco o LinkedList, quindi scriverli in un file dall'elenco anziché prima concatenarli in memoria.

EDIT: Come richiesto, il riferimento (.NET 3.5) a MSDN. Dice: & Quot; I nuovi dati vengono aggiunti alla fine del buffer se è disponibile spazio; in caso contrario, viene allocato un nuovo buffer più grande, i dati dal buffer originale vengono copiati nel nuovo buffer, quindi i nuovi dati vengono aggiunti al nuovo buffer. " Questo per me significa un carattere [] che viene riallineato per renderlo più grande (che richiede la copia di vecchi dati nell'array ridimensionato) quindi l'aggiunta.

È stato utile?

Soluzione

Per la tua domanda separata , Win32 ha un WriteFileGather , che potrebbe scrivere in modo efficiente un elenco di stringhe (internate) su disco - ma farebbe una differenza notevole solo quando viene chiamato in modo asincrono, mentre la scrittura su disco metterà in ombra tutte le concatenazioni tranne quelle estremamente grandi.

Per la tua domanda principale : a meno che tu non stia raggiungendo megabyte di script o decine di migliaia di script, non preoccuparti.

Puoi aspettarti che StringBuilder raddoppi la dimensione di allocazione su ogni riallocazione. Ciò significherebbe far crescere un buffer da 256 byte a 1 MB sono solo 12 riallocazioni - abbastanza buono, dato che la tua stima iniziale era di 3 ordini di grandezza rispetto al target.

Solo come un esercizio, alcune stime: la costruzione di un buffer di 1 MB spazzerà circa 3 MB di memoria (sorgente 1 MB, destinazione 1 MB, 1 MB a causa di copia durante la riallocazione).

Un'implementazione dell'elenco collegato spazzerà circa 2 MB (e questo ignora l'overhead di 8 byte / oggetto per riferimento di stringa). Quindi stai salvando letture / scritture da 1 MB di memoria, rispetto a una larghezza di banda di memoria tipica di 10 Gbit / se cache L2 da 1 MB.)

Sì, un'implementazione dell'elenco è potenzialmente più veloce e la differenza sarebbe importante se i buffer fossero di un ordine di grandezza più grande.

Nel caso molto più comune di stringhe di piccole dimensioni, il guadagno algoritmico è trascurabile e facilmente compensato da altri fattori: il codice StringBuilder è probabilmente già nella cache del codice e un obiettivo praticabile per le microottimizzazioni. Inoltre, l'utilizzo di una stringa internamente significa nessuna copia se la stringa finale si adatta al buffer iniziale.

L'uso di un elenco collegato comporta anche la riduzione del problema di riallocazione da O (numero di caratteri) a O (numero di segmenti): l'elenco dei riferimenti alle stringhe presenta lo stesso problema di una stringa di caratteri!

Quindi, IMO l'implementazione di StringBuilder è la scelta giusta, ottimizzata per il caso comune e peggiora principalmente per buffer di destinazione inaspettatamente grandi. Mi aspetto che l'implementazione di un elenco degrada prima per molti piccoli segmenti, che in realtà è il tipo estremo di scenario per cui StringBuilder sta cercando di ottimizzare.

Tuttavia, sarebbe interessante vedere un confronto tra le due idee e quando l'elenco inizia ad essere più veloce.

Altri suggerimenti

Se avessi implementato qualcosa del genere, non avrei mai creato StringBuilder (o nessun altro nel buffer di memoria del tuo script). Invece, lo trasmetterei semplicemente al tuo file e renderei tutte le stringhe in linea.

Ecco un pseudo codice di esempio (non sintatticamente corretto o altro): 

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

Quindi, non avrai mai bisogno di una rappresentazione in memoria del tuo script, con tutta la copia delle stringhe.

Opinioni?

Nella mia esperienza, l'allocazione corretta di StringBuilder supera di gran lunga tutto il resto per grandi quantità di dati di stringa. Vale la pena sprecare un po 'di memoria, anche, superando la stima del 20% o 30% al fine di prevenire la riallocazione. Al momento non ho numeri concreti per il backup utilizzando i miei dati, ma dai un'occhiata a questa pagina per ulteriori informazioni .

Tuttavia, come Jeff ama sottolineare, non ottimizzare prematuramente!

EDIT: Come sottolineato da @Colin Burnett, i test che Jeff ha condotto non sono d'accordo con i test di Brian, ma lo scopo di collegare il post di Jeff era sull'ottimizzazione prematura in generale. Diversi commentatori sulla pagina di Jeff hanno notato problemi con i suoi test.

In realtà StringBuilder utilizza un'istanza di String internamente. System è infatti mutabile all'interno dell'assemblea "SOMESTRINGA", motivo per cui "SOMESTRINGB" può essere costruito sopra di esso. Puoi rendere <=> un pochino più efficace assegnando una lunghezza ragionevole quando crei l'istanza. In questo modo eliminerai / ridurrai il numero di operazioni di ridimensionamento.

Il string interning funziona per le stringhe che possono essere identificate in fase di compilazione. Pertanto, se si generano molte stringhe durante l'esecuzione, queste non verranno internate a meno che non lo si faccia da sé chiamando il metodo di interning su stringa.

Il tirocinio ti gioverà solo se le tue stringhe sono identiche. Le stringhe quasi identiche non beneficiano del interning, quindi <=> e <=> saranno due stringhe diverse anche se sono internate.

Se tutte (o la maggior parte) delle stringhe da concatenare sono internate, il tuo schema POTREBBE darti un potenziamento delle prestazioni, dal momento che potrebbe potenzialmente usare meno memoria e salvare alcune copie di stringhe di grandi dimensioni.

Tuttavia, se migliora effettivamente il perf dipende dal volume di dati che stai elaborando, perché il miglioramento è in fattori costanti, non nell'ordine di grandezza dell'algoritmo.

L'unico modo per dirlo realmente è eseguire l'app in entrambi i modi e misurare i risultati. Tuttavia, a meno che tu non abbia una significativa pressione della memoria e non abbia bisogno di un modo per salvare i byte, non mi preoccuperei e userei solo il generatore di stringhe.

Un StringBuilder non usa un char[] per archiviare i dati, usa una stringa mutabile interna. Ciò significa che non è necessario alcun passaggio aggiuntivo per creare la stringa finale come quando si concatena un elenco di stringhe, <=> restituisce semplicemente il buffer di stringa interno come stringa normale.

Le riallocazioni che <=> esegue per aumentare la capacità significa che i dati vengono copiati in media 1,33 volte in più. Se riesci a fornire una buona stima delle dimensioni quando crei <=> puoi ridurlo ulteriormente.

Tuttavia, per ottenere un po 'di prospettiva, dovresti guardare a ciò che stai cercando di ottimizzare. Ciò che impiegherà la maggior parte del tempo nel tuo programma è in realtà scrivere i dati su disco, quindi anche se puoi ottimizzare la gestione delle stringhe per essere due volte più veloce rispetto all'uso di un <=> (che è molto improbabile), la differenza complessiva sarà ancora solo un po 'per cento.

Hai considerato C ++ per questo? Esiste una classe di libreria che crea già espressioni T / SQL, preferibilmente scritte in C ++.

La cosa più lenta delle stringhe è malloc. Richiede 4KB per stringa su piattaforme a 32 bit. Prendi in considerazione l'ottimizzazione del numero di oggetti stringa creati.

Se devi usare C #, consiglierei qualcosa del genere: 

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();

Vorrei persino fare in modo che il computer valutasse il percorso migliore per la creazione di istanze di oggetti con framework di iniezione di dipendenza, se perf è COSÌ importante.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top