Ottimizzazione di diversi milioni di caratteri * per conversioni di stringhe

Question

Ho un'applicazione che deve contenere diversi milioni di caratteri * come parametro di input (in genere stringhe inferiori a 512 caratteri (in unicode)) e convertirli e memorizzarli come. stringhe nette.

Si sta rivelando un vero e proprio collo di bottiglia nelle prestazioni della mia applicazione. Mi chiedo se c'è qualche schema di progettazione o idee per renderlo più efficiente.

C'è una parte fondamentale che mi fa sentire come può essere migliorata: ci sono un sacco di duplicati. Dici che arrivano 1 milione di oggetti, potrebbero esserci solo 50 modelli char * unici.

Per la cronaca, ecco l'algoritmo che sto utilizzando per convertire char * a stringa (questo algoritmo è in C++, ma il resto del progetto è in C#)

String ^StringTools::MbCharToStr (const char *Source) 
{ 
    String ^str; 

    if((Source == NULL) || (Source[0] == '\0')) 
    { 
     str = gcnew String(""); 
    } 
    else 
    { 
     // Find the number of UTF-16 characters needed to hold the 
     // converted UTF-8 string, and allocate a buffer for them. 
     const size_t max_strsize = 2048; 

     int wstr_size = MultiByteToWideChar (CP_UTF8, 0L, Source, -1, NULL, 0); 
     if (wstr_size < max_strsize) 
     { 
     // Save the malloc/free overhead if it's a reasonable size. 
     // Plus, KJN was having fits with exceptions within exception logging due 
     // to a corrupted heap. 

     wchar_t wstr[max_strsize]; 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     } 
     else 
     { 
     wchar_t *wstr = (wchar_t *)calloc (wstr_size, sizeof(wchar_t)); 
     if (wstr == NULL) 
      throw gcnew PCSException (__FILE__, __LINE__, PCS_INSUF_MEMORY, MSG_SEVERE); 

     // Convert the UTF-8 string into the UTF-16 buffer, construct the 
     // result String from the UTF-16 buffer, and then free the buffer. 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     free (wstr); 
     } 
    } 
    return str; 
} 

Answer 1

È possibile utilizzare ciascun carattere dalla stringa di input per alimentare una struttura trie. Alle foglie, avere un singolo oggetto stringa .NET. Quindi, quando arriva uno char* che hai già visto, puoi trovare rapidamente la versione .NET esistente senza allocare memoria.

pseudo-codice:

• inizio con un trie vuoto,
• processo un char * cercando il trie finché non si può andare oltre
• aggiungere nodi fino a quando l'intero char * è stato codificato come nodi
• la foglia, collegare una stringa .NET reale

la risposta a questa domanda altri SO dovrebbe farti starte d: How to create a trie in c#

Answer 2

avrei probabilmente usare una cache basata su una struttura ad albero ternario o simile, e cerca la stringa di input per vedere se è già convertita prima di convertire anche un singolo carattere in rappresentazione .NET.

Answer 3

C'è una parte fondamentale che mi fa sentire come può essere migliorata: ci sono un sacco di duplicati. Dici che arrivano 1 milione di oggetti, potrebbero esserci solo 50 modelli char * unici.

Se questo è il caso, si può prendere in considerazione la memorizzazione dei modelli "trovate" all'interno di una mappa (ad esempio utilizzando un std::map<const char*, gcroot<String^>> [anche se avrete bisogno di un operatore di confronto per la const char*), e l'uso che per il ritorno il valore precedentemente convertito.

C'è un sovraccarico per memorizzare la mappa, fare il confronto, ecc. Tuttavia, questo può essere mitigato dal consumo di memoria drasticamente ridotto (è possibile riutilizzare le istanze di stringa gestite), nonché salvare le allocazioni di memoria (calloc /gratuito). Inoltre, l'utilizzo di malloc anziché di calloc potrebbe essere un miglioramento (molto piccolo), in quanto non è necessario azzerare la memoria prima di chiamare MultiByteToWideChar.

Answer 4

Penso che la prima ottimizzazione che potresti fare qui sarebbe di fare il tuo primo tentativo chiamando MultiByteToWideChar con un buffer invece di un puntatore nullo. Perché hai specificato CP_UTF8, MultiByteToWideChar deve percorrere l'intera stringa per determinare la lunghezza prevista.Se c'è una lunghezza che è più lunga della stragrande maggioranza delle stringhe, potresti prendere in considerazione l'allocazione ottimistica di un buffer di quella dimensione nello stack; e se ciò fallisce, allora andare all'assegnazione dinamica. Cioè, sposta il primo ramo se il tuo blocco if/else al di fuori dello if/else.

Si potrebbe anche risparmiare un po 'di tempo calcolando la lunghezza della stringa di origine una volta e passandola in modo esplicito - in questo modo MultiByteToWideChar non deve fare un strlen ogni volta che lo si chiama.

Detto questo, sembra che se il resto del progetto è C#, dovresti usare le librerie di classi .NET BCL progettate per fare questo piuttosto che avere un assembly side by side in C++/CLI al solo scopo di convertire stringhe. Questo è ciò che è System.Text.Encoding.

Dubito che qualsiasi tipo di struttura di dati di memorizzazione nella cache che è possibile utilizzare qui farà alcuna differenza significativa.

Oh, e non ignorare il risultato di MultiByteToWideChar - non solo non si dovrebbe trasmettere nulla a void, si ha un comportamento non definito nell'evento MultiByteToWideChar non riesce.