問題タブ [string-interning]

2 つの質問。

1. リテラル文字列を宣言すると、ヒープの文字列プールに同じ文字列が存在するかどうかを検索します。これもインターン（クラスのメソッドインターンString）ですか？

2. 私の考えでは、各リテラル文字列宣言にはバイナリ検索などが必要なので、 nがプール内の既存の文字列の数である場合、少なくともlog(n)のコストがかかります。また、プールに多くの文字列がある場合、コストが高くなる可能性があります。(検索コストとメモリのトレードオフでしょうか?) この観点からすると、mant リテラル文字列を宣言するのは危険かもしれません。 この検索コストの重要性と、Java がこのように設計されている理由 (リテラル文字列が宣言されている場合のプールの検索)。

以下は、背景を理解するために参照したものです。

クラスのJavaDoc にはjava.lang.String次のように記載 されています。

文字列は定数です。作成後に値を変更することはできません。文字列バッファーは可変文字列をサポートします。String オブジェクトは不変であるため、共有できます。

http://www.janeg.ca/scjp/lang/strLiteral.htmlコメント:

つまり、コンパイラは文字列の元の値が一度作成されると変更できないことを認識しているため、既存のデータを安全に使用し、重複によるメモリの混乱を避けることができます。

V8やWebKitのJavaScriptCoreなどの一般的なJavaScriptエンジンは、 JavaScript文字列に文字列インターンを使用しますか？それとも、実際には同じ文字列の複数のインスタンスをメモリに保持していますか？

文字列のインターンを完全に無効にすることはできますか? あまり参考にならないかもしれませんが、ただの感想です。たとえば、jvm のチューニング中に、perm gen のサイズを制御するときに役立つポイントが少なくとも 1 つあります。

たとえば、私が OSGI フレームワークを配布し、誰でも独自のバンドルをいくつでも追加でき、各バンドルの文字列インターンがチューニング パラメーターを完全に台無しにする可能性がある場合などです。(もちろん、特定の固定ディストリビューションでチューニングを行う必要があることはわかっていますが、それでも...)

何かご意見は！！

特定のオブジェクトと等しい SortedDictionary からキーを取得する方法はありますか? 説明のために、メモリを大量に消費する不変のキー タイプを持つ辞書を作成するとします。

その後、次のようなことを行います。

明らかに、SortedDictionary には「GetKeyEqualTo」メソッドがありません。しかし、同様の効果を達成できる方法はありますか？これは基本的に、重いキー オブジェクトをインターンする効果があり、同一のインスタンスを破棄できます。キーのインデックスとそれに一致するオブジェクト インスタンスを取得することにより、SortedList クラスを使用してこれを実行できることはわかっていますが、SortedDictionary の一貫した挿入パフォーマンスは、私の用途には適しています。

すべての辞書のキーを反復して一致を検索するか、独自の BST クラスを作成する以外に、.NET の組み込みコレクションでこの目的を達成する方法はありますか?

内部化された文字列を一覧表示できるデバッグ ツールを探していますか? 理想的には、マークを付けて、そのマークの後に追加された文字列のリストを取得したいと考えています。

前もって感謝します。

私の質問は、インターンが文字列と SPC (文字列プール定数) を持つ文字列で動作しており、インターンの概念も整数で動作している場合、整数プール定数はありますか?そうでない場合、どのように機能しますか?

これは非常に Delphi 固有の質問です (おそらく Delphi 2007 固有の質問です)。現在、文字列をインターンするための単純な StringPool クラスを作成しています。優秀なコーダーとして、単体テストも追加しましたが、困惑するものを見つけました。

これはインターンのコードです:

FList はソートされた TStringList であるため、コードはリスト内の文字列を検索し、リスト内の文字列が既に存在する場合は既存の文字列を返します。まだリストにない場合は、最初に UniqueString を呼び出して参照カウントが 1 であることを確認してから、リストに追加します。(結果の参照カウントを確認したところ、予想どおり 'hallo' が 2 回追加された後で 3 になっています。)

テストコードに移りましょう:

これにより、文字列 'hallo' が文字列プールに 2 回追加され、文字列の参照カウントがチェックされ、s1 と s2 が実際に同じ文字列記述子を指していることも確認されます。

すべての CheckEquals は期待どおりに機能しますが、最後です。「expected: <3> but was: <4>」というエラーで失敗します。

では、なぜここで参照カウントが 4 なのですか? 私は3を期待していたでしょう：

• s1
• s2
• および StringList 内の別の 1 つ

これは Delphi 2007 であるため、文字列は AnsiStrings です。

そうそう、関数 StringReferenceCount は次のように実装されています。

デバッガーでは、同じものを次のように評価できます。

Sergからの回答に追加するだけです（これは100％正しいようです）：

交換したら

と

次に、s3（およびs1）の参照カウントを確認すると、予想どおり3です。この現象を引き起こすのは、FPool.Intern(s2) の結果を s2 に再度代入したためです (s2 は、パラメーターと関数結果の宛先の両方です)。Delphi では、結果を代入する隠し文字列変数が導入されています。

また、関数をプロシージャに変更すると、次のようになります。

隠し変数が必要ないため、参照カウントは予想どおり 3 です。

誰かがこの TStringPool 実装に興味を持っている場合: これは MPL の下でオープン ソースであり、dzchart の一部である dzlib の一部として利用できます。

https://sourceforge.net/p/dzlib/code/HEAD/tree/dzlib/trunk/src/u_dzStringPool.pas

しかし、上で述べたように、それは厳密にはロケット科学ではありません。;-)

以下はMSDNからの抜粋です。

共通言語ランタイムは、インターン プールと呼ばれるテーブルを維持することで、文字列ストレージを節約します。このテーブルには、プログラムでプログラムによって宣言または作成された一意の各リテラル文字列への単一の参照が含まれています。したがって、特定の値を持つリテラル文字列のインスタンスは、システム内に 1 回だけ存在します。

たとえば、同じリテラル文字列を複数の変数に割り当てると、ランタイムはインターン プールからリテラル文字列への同じ参照を取得し、それを各変数に割り当てます。

Intern メソッドは、インターン プールを使用して、str の値に等しい文字列を検索します。そのような文字列が存在する場合は、インターン プール内のその参照が返されます。文字列が存在しない場合は、str への参照がインターン プールに追加され、その参照が返されます。.... アプリケーションが割り当てるメモリの総量を削減しようとしている場合は、文字列のインターンには 2 つの望ましくない副作用があることに注意してください。まず、インターンされた String オブジェクトに割り当てられたメモリは、共通言語ランタイム (CLR) が終了するまで解放されない可能性があります。

これは、CLR が実行中のすべての .net アプリに対して 1 つのインターン プールを保持するということですか? 例: プログラム A が文字列リテラル "Test" を作成し、別のプログラムが別の文字列リテラル "Test" を作成しようとした場合、同じコピーが使用されますか? 同じ質問が JVM にも当てはまります。

少し前にストリングスとさまざまな言語について話し合っていたときに、ストリングスのインターンの話題が持ち上がりました。Java と .NET フレームワークは、すべての文字列といくつかのスクリプト言語でこれを自動的に行うようです。理論的には、同じ文字列の複数のコピーが作成されないため、メモリを節約できます。また、文字列の等価比較は、文字列の各文字を O(N) で実行するのではなく単純なポインター比較であるため、時間を節約できます。

しかし、考えれば考えるほど、そのコンセプトのメリットについて懐疑的になります。利点はほとんど理論的なものであるように私には思えます：

• まず、自動文字列インターニングを使用するには、すべての文字列が不変である必要があります。これにより、多くの文字列処理タスクが必要以上に難しくなります。(そして、はい、一般的に不変性に関するすべての議論を聞いてきました。それは重要ではありません。)
• 新しい文字列が作成されるたびに、少なくとも O(N) 操作である文字列インターニング テーブルに対してチェックする必要があります。(編集:ここで、N は文字列のサイズであり、テーブルのサイズではありません。これは人々を混乱させるためです。)したがって、新しい文字列の作成に対する文字列の等価性の比較の比率がかなり高くない限り、節約される正味の時間はそうではありません。正の値。
• 文字列等価テーブルが強い参照を使用している場合、不要になった文字列はガベージ コレクションされないため、メモリが浪費されます。一方、テーブルが弱い参照を使用している場合、文字列クラスはテーブルから文字列を削除するために何らかのファイナライザーを必要とするため、GC プロセスが遅くなります。(文字列インターン テーブルの実装方法によっては、これは非常に重要な場合があります。最悪の場合、ハッシュ テーブルから項目を削除すると、特定の状況下でテーブル全体の O(N) 再構築が必要になる場合があります。)

これは、実装の詳細について考えた結果です。見逃したものはありますか？文字列のインターンは実際に一般的なケースで大きなメリットをもたらしますか?

編集 2: わかりました、どうやら私は間違った前提から操作していたようです。私が話していた人は、ストリングインターンが新しく作成されたストリングのオプションであることを指摘したことはなく、実際には逆であるという印象が強かった. 問題を解決してくれたジョンに感謝します。彼のために別の受け入れられた答え。

かなり大きな（200 MB）XMLファイルを解析しているところ、それぞれが一連のパラメーター（key = value）を定義するオブジェクトのツリーになります。このデータ構造はTomcatWebアプリケーションで実行されており、これらのパラメーターを検索するために使用されます。

数か月前、このサーバーでヒープメモリの問題を発見しました。パラメータのキーと値（ほとんどは非常に冗長です）をインターンすることで解決でき、メモリフットプリントが150MB以上からわずか20MBに削減されました。

人々が起動時間について不平を言っているので、今日私はサーバーを再訪しています。サーバーのプロファイリングを行っていますが、XPP3を使用したXMLの解析には40秒かかりますが、String.intern（）には30秒以上かかります。

これはトレードオフであることを私は知っています。そして、私は自分でインターンをすることができることを知っています。XMLの解析はシングルスレッドであるため、単純なHashMapでも同様に機能する可能性があります。しかし、あなたが知っている、これはちょっと奇妙に感じます。

別の解決策を支持してString.internを削除する価値があるかどうかを確認するために、誰かが数値を計算しましたか？

だから問題は？このような問題について、どうすれば競合をできるだけ少なくすることができますか？

ありがとう、ステファン