Stage di stringa - String interning
In informatica, l'internamento delle stringhe è un metodo per memorizzare solo una copia di ciascun valore di stringa distinto , che deve essere immutabile . Le stringhe interne rendono alcune attività di elaborazione delle stringhe più efficienti in termini di tempo o spazio al costo di richiedere più tempo quando la stringa viene creata o internata. I valori distinti vengono archiviati in un pool interno di stringhe .
La singola copia di ogni stringa è chiamata il suo interno ed è tipicamente cercata da un metodo della classe string, ad esempio String.intern() in Java . Tutte le stringhe costanti in fase di compilazione in Java vengono automaticamente internate utilizzando questo metodo.
L'internamento delle stringhe è supportato da alcuni moderni linguaggi di programmazione orientati agli oggetti , tra cui Java, Python , PHP (dalla 5.4), Lua , Ruby (con i suoi simboli), Julia e i linguaggi .NET . Lisp , Scheme e Smalltalk sono tra i linguaggi con un tipo di simbolo che sono fondamentalmente stringhe interne. La libreria dello Standard ML del New Jersey contiene un tipo di atomo che fa la stessa cosa. I selettori di Objective-C , utilizzati principalmente come nomi di metodi, sono stringhe interne.
Oggetti diversi dalle stringhe possono essere internati. Ad esempio, in Java, quando i valori primitivi sono racchiusi in un oggetto wrapper , alcuni valori (any boolean, any byte, any charda 0 a 127 e any shorto inttra -128 e 127) sono internati e due conversioni di boxing di uno di questi i valori sono garantiti per risultare nello stesso oggetto.
Storia
Lisp ha introdotto la nozione di stringhe interne per i suoi simboli . Storicamente, la struttura dati utilizzata come pool interno di stringhe era chiamata oblist (quando era implementata come lista collegata) o obarray (quando era implementata come array).
I moderni dialetti Lisp distinguono tipicamente i simboli dalle stringhe; l'internamento di una data stringa restituisce un simbolo esistente o ne crea uno nuovo, il cui nome è quella stringa. I simboli hanno spesso proprietà aggiuntive che le stringhe non hanno (come l'archiviazione per i valori associati o lo spazio dei nomi): la distinzione è utile anche per evitare il confronto accidentale di una stringa interna con una stringa non necessariamente interna, che potrebbe portare a errori intermittenti a seconda modelli di utilizzo.
Motivazione
L'internamento delle stringhe accelera i confronti delle stringhe, che a volte rappresentano un collo di bottiglia delle prestazioni nelle applicazioni (come compilatori e runtime del linguaggio di programmazione dinamico ) che si basano molto su array associativi con chiavi di stringa per cercare gli attributi e i metodi di un oggetto. Senza l'internamento, il confronto di due stringhe distinte può comportare l'esame di ogni carattere di entrambe. Questo è lento per diversi motivi: è intrinsecamente O(n) nella lunghezza delle stringhe; richiede tipicamente letture da diverse regioni di memoria , che richiedono tempo; e le letture riempiono la cache del processore, il che significa che c'è meno cache disponibile per altre esigenze. Con le stringhe interne, è sufficiente un semplice test di identità dell'oggetto dopo l'operazione interna originale; questo è tipicamente implementato come test di uguaglianza del puntatore, normalmente solo una singola istruzione macchina senza alcun riferimento di memoria.
L'internamento delle stringhe riduce anche l'utilizzo della memoria se sono presenti molte istanze dello stesso valore di stringa; ad esempio, viene letto da una rete o da un archivio . Tali stringhe possono includere numeri magici o informazioni sul protocollo di rete . Ad esempio, i parser XML possono inserire nomi di tag e attributi per risparmiare memoria. Il trasferimento in rete di oggetti su flussi di oggetti di serializzazione Java RMI può trasferire stringhe che sono internate in modo più efficiente, poiché l'handle dell'oggetto String viene utilizzato al posto degli oggetti duplicati durante la serializzazione.
Problemi
Multithreading
Una fonte di svantaggi è che l'internamento delle stringhe può essere problematico se combinato con il multithreading . In molti sistemi, gli stagisti di stringa devono essere globali su tutti i thread all'interno di uno spazio di indirizzi (o su qualsiasi contesto che può condividere puntatori), quindi i pool di stagisti sono risorse globali che dovrebbero essere sincronizzate per un accesso simultaneo sicuro. Sebbene ciò influisca solo sulla creazione di stringhe (dove il pool di stagisti deve essere controllato e modificato se necessario) e il blocco a doppio controllo può essere utilizzato su piattaforme in cui questa è un'ottimizzazione sicura, la necessità di mutua esclusione quando si modifica il pool di stagisti può essere costosa .
La contesa può anche essere ridotta partizionando lo spazio della stringa in più pool, che possono essere sincronizzati indipendentemente l'uno dall'altro.
Recupero di stringhe interne inutilizzate
Molte implementazioni di stringhe interne non tentano di recuperare (manualmente o in altro modo) le stringhe non più utilizzate. Per le applicazioni in cui il numero di stringhe interne è ridotto o fisso o di breve durata, la perdita di risorse di sistema può essere tollerabile. Ma per i sistemi di lunga durata in cui vengono creati un gran numero di stagisti di stringa in fase di esecuzione, potrebbe sorgere la necessità di recuperare gli stagisti inutilizzati. Questa attività può essere gestita da un Garbage Collector , anche se per farlo funzionare correttamente i riferimenti deboli a stagisti di stringa devono essere archiviati nel pool degli interni.
