文字列インターン

コンピュータサイエンスにおいて、文字列インターンは、各異なる文字列値のコピーを1つだけ保存する方法であり、このコピーは不変でなければなりません。^[1]文字列をインターンすると、文字列の作成時やインターン時に時間がかかる代わりに、一部の文字列処理タスクの時間効率やスペース効率が向上します。異なる値は文字列インターンプールに保存されます。

各文字列の単一のコピーはinternと呼ばれ、通常は文字列クラスのメソッド（JavaのString.intern() ^[2]など）によって検索されます。Javaのすべてのコンパイル時定数文字列は、このメソッドを使用して自動的にインターン化されます。^[3]

文字列のインターンは、Java、Python、PHP（5.4以降）、Lua ^[4]、. NET言語^[5] など、いくつかの最新のオブジェクト指向 プログラミング言語でサポートされています。Lisp 、Scheme、Julia、Ruby、Smalltalkは、基本的にインターンされた文字列であるシンボル型を持つ言語の一部です。Standard ML of New Jerseyのライブラリには、同じことを行う型が含まれています。主にメソッド名として使用されるObjective-Cのセレクタは、インターンされた文字列です。 atom

文字列以外のオブジェクトもインターン化できます。たとえば、Javaでは、プリミティブ値がラッパーオブジェクトにボックス化されると、特定の値（any 、any 、0から127までのany、および-128から127までのanyまたは）がインターン化され、これらの値の1つを2回ボックス化すると、同じオブジェクトになることが保証されます。^[6]booleanbytecharshortint

Lisp は、シンボルに対してインターンされた文字列の概念を導入しました。歴史的には、文字列インターンプールとして使用されるデータ構造は、oblist (リンク リストとして実装された場合) またはobarray (配列として実装された場合) と呼ばれていました。

現代の Lisp 方言では、通常、シンボルと文字列を区別します。特定の文字列をインターンすると、既存のシンボルが返されるか、その文字列と同じ名前の新しいシンボルが作成されます。シンボルには、文字列にはない追加のプロパティ (関連付けられた値のストレージや名前空間など) がしばしばあります。この区別は、インターンされた文字列を必ずしもインターンされていない文字列と誤って比較するのを防ぐのにも役立ちます。インターンされた文字列は、使用パターンによっては断続的な障害を引き起こす可能性があります。

文字列のインターンにより文字列の比較が高速化されます。文字列の比較は、オブジェクトの属性やメソッドを検索するために文字列キーを持つ連想配列に大きく依存するアプリケーション (コンパイラや動的プログラミング言語ランタイムなど) でパフォーマンスのボトルネックになることがあります。インターンを行わないと、2 つの異なる文字列を比較するには、両方のすべての文字を調べる必要があります。^{[注 1]} これは、いくつかの理由で低速になります。文字列の長さが本質的にO(n)であること、通常はメモリの複数の領域からの読み取りが必要で時間がかかること、読み取りによってプロセッサ キャッシュがいっぱいになり、他の用途に使用できるキャッシュが少なくなるという理由があります。インターンされた文字列では、元のインターン操作の後に単純なオブジェクト同一性テストで十分です。これは通常、ポインター等価性テストとして実装され、通常はメモリ参照をまったく行わない単一のマシン命令のみです。

文字列のインターン化は、同じ文字列値のインスタンスが多数ある場合、たとえばネットワークやストレージから読み取られる場合、メモリ使用量を削減します。このような文字列には、マジックナンバーやネットワークプロトコル情報が含まれる場合があります。たとえば、XMLパーサーは、メモリを節約するためにタグと属性の名前をインターン化する場合があります。Java RMIシリアル化オブジェクトストリームを介したオブジェクトのネットワーク転送では、シリアル化時に重複オブジェクトの代わりにStringオブジェクトのハンドルが使用されるため、インターン化された文字列をより効率的に転送できます。^[7]

インターンされた文字列が不変でない場合、欠点の 1 つは、マルチスレッドと混在すると文字列のインターンが問題になる可能性があることです。多くのシステムでは、文字列インターンはアドレス空間内のすべてのスレッド (またはポインタを共有する可能性のあるすべてのコンテキスト) にわたってグローバルである必要があります。したがって、インターンプールは安全な同時アクセスのために同期する必要があるグローバルリソースです。これは文字列の作成にのみ影響し (インターンプールは必要に応じてチェックおよび変更する必要があります)、二重チェックロックはこれが安全な最適化であるプラットフォームで使用できますが、インターンプールを変更するときに相互排他が必要になるため、コストがかかる可能性があります。^[8]

文字列スペースを複数のプールに分割し、それらを互いに独立して同期させることによっても競合を軽減できます。

インターンされた文字列の実装の多くは、使用されなくなった文字列を (手動またはその他の方法で) 再利用しようとしません。 インターンされた文字列の数が少ないか固定されているか、または短命なアプリケーションの場合、システム リソースの損失は許容できる可能性があります。 しかし、実行時に多数の文字列インターンが作成される長時間実行されるシステムの場合、未使用のインターンを再利用する必要が生じる可能性があります。 このタスクはガベージ コレクターによって処理できますが、これが正しく機能するには、文字列インターンへの弱い参照がインターン プールに格納されている必要があります。

• フライウェイトパターン

• Visual J# 文字列クラス
• .NET 文字列クラス
• Guava Java ライブラリ - Interner - 非 permgen String.intern および、弱参照および強参照実装によるその他の不変型をサポートします
• Java の文字列の intern() メソッドを理解する
• Internify ライブラリは、文字列 (またはハッシュ可能な任意の型) をインターンするために設計された軽量でスレッドセーフな C++17 ライブラリです。