Java オブジェクト割り当てのオーバーヘッド

Question

複数のスレッドからのアクセスを簡素化するために、Java で不変の DOM ツリーを作成しています。*

ただし、可能な限り高速な挿入と更新をサポートする必要があります。また、不変であるため、ツリーの N 番目のレベルのノードに変更を加えた場合、新しいツリーを返すために少なくとも N 個の新しいノードを割り当てる必要があります。

私の質問は、ツリーが変更されるたびに新しいノードを作成するよりも、事前にノードを割り当てた方が劇的に高速になるでしょうか?これは非常に簡単に実行できます。数百の未使用ノードのプールを保持し、変更操作で必要になるたびにノードを作成するのではなく、プールから 1 つを取り出します。他に何も起こっていないときは、ノード プールを補充できます。(明らかでない場合があるかもしれませんが、このアプリケーションではヒープ領域よりも実行時間の方がはるかに重要です)

これを行う価値はあるでしょうか?高速化に関するその他のヒントはありますか?

あるいは、不変の DOM ライブラリが既に存在するかどうかを知っている人はいますか?探しましたが何も見つかりませんでした。

*注記：不変性の概念に詳しくない方のために説明すると、不変性とは基本的に、オブジェクトを変更する操作において、メソッドは変更されたオブジェクトではなく、変更が反映されたオブジェクトのコピーを返すことを意味します。したがって、別のスレッドがまだオブジェクトを読み取っている場合、そのスレッドはひどくクラッシュすることなく、変更が行われたことに気づかずに「古い」バージョンで問題なく動作し続けます。見る http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

最近では、オブジェクトの作成が非常に速くなり、オブジェクト プーリングの概念は (少なくとも一般的には) 時代遅れになっています。接続プーリングはもちろん引き続き有効です)。

時期尚早な最適化を避けてください。コピーを実行するときに必要なときにノードを作成し、それが法外に遅くなるかどうかを確認します。その場合は、速度を上げるためのいくつかのテクニックを検討してください。ただし、自分のものが十分に高速ではないことがすでにわかっている場合を除き、プーリングを実行するために必要となるすべての複雑さを導入するつもりはありません。

Answer 2

答えにならないことは言いたくないのですが、このようなパフォーマンスに関する質問に答える唯一の決定的な方法は、両方のアプローチをコード化し、2 つのベンチマークを行い、結果を比較することだと思います。

Answer 3

すべてがスレッドセーフであることを確認するために、特定のメソッドの明示的な同期を回避できるかどうかはわかりません。

特定のケースでは、新しく作成したノードを他のスレッドで利用できるようにする際に、どちらか一方を同期する必要があります。そうしないと、VM/CPU が共有ノードへの参照の書き込みを超えてフィールドの書き込みの順序を変更し、データが公開される危険性があります。パーティが構築したオブジェクト。

より高いレベルで考えてみてください。IMMUTABLE ツリー (基本的にはその子を指すノードのセット) があります。そこにノードを挿入したいとします。そうなると、もう逃げ道はありません。新しいツリー全体を作成する必要があります。

子を指すノードのセットとしてツリーを実装することを選択した場合は、変更されたノードのルートへのパスに沿って新しいノードを作成する必要があります。他のものは以前と同じ値を持ち、通常は共有されます。したがって、部分的な新しいツリーを作成する必要があります。これは通常、(編集されたノードの深さ) 親ノードを意味します。

直接的ではない実装に対処できる場合は、「」で説明されているのと同様のテクニックを使用して、ノードの一部を作成するだけで済むはずです。 純粋に機能的なデータ構造 作成の平均コストを削減するか、半関数的なアプローチ (既存のイテレータをラップするイテレータの作成など、古いノードの代わりに新しいノードを修復するメカニズムとともに作成するなど) を使用してバイパスすることができます。時間の経過とともに構造内にそのようなパッチが発生します)。その場合、XPath スタイル API は DOM API よりも優れている可能性があります。ツリーからノードをもう少し切り離して、変異したツリーをよりインテリジェントに処理できるかもしれません。

Answer 4

そもそも何をしようとしているのか少し混乱しています。すべてのノードを不変にして、それらをプールしたいと考えていますか?これら 2 つのアイデアは相互に排他的ではありませんか?プールからオブジェクトを引き出すとき、子をリンクするためにセッターを呼び出す必要はありませんか?

おそらく、不変ノードを使用しても、そもそも必要なスレッドセーフ性は得られないと思います。1 つのスレッドがノードを反復処理 (検索など) しているときに、別のスレッドがノードの追加/削除を行っている場合はどうなるのでしょうか?検索結果が無効になることはありませんか?すべてがスレッドセーフであることを確認するために、特定のメソッドの明示的な同期を回避できるかどうかはわかりません。

Answer 5

@無法者プログラマー

プールからオブジェクトを引き出すとき、子供たちをリンクするためにセッターを呼び出す必要がありませんか？

各ノードはパッケージの内部で不変である必要はなく、外向きのインターフェイスに対してのみ不変である必要があります。 node.addChild() これはパブリック可視性を備えた不変関数であり、Document を返しますが、 node.addChildInternal() これは、パッケージの可視性を備えた通常の変更可能な関数になります。ただし、パッケージの内部にあるため、子孫としてのみ呼び出すことができます。 addChild() また、構造全体がスレッドセーフであることが保証されています (オブジェクト プールへのアクセスを同期している場合)。これに欠陥があることがわかりますか...?もしそうなら、教えてください！

おそらく、不変ノードを使用しても、そもそも必要なスレッドセーフ性は得られないと思います。1 つのスレッドがノードを反復処理 (検索など) しているときに、別のスレッドがノードの追加/削除を行っている場合はどうなるのでしょうか?

ツリー全体は不変になります。Thread1 と Thread2、そしてツリー dom1 があるとします。Thread1 は dom1 で読み取り操作を開始し、同時に Thread2 は dom1 で書き込み操作を開始します。ただし、Thread2 が行う変更はすべて、実際には新しいオブジェクト dom2 に対して行われ、dom1 は不変になります。Thread1 によって読み取られる値が (数マイクロ秒) 古くなっているのは事実ですが、IndexOutOfBounds 例外や NullPointer 例外、あるいは書き込み先の変更可能なオブジェクトを読み取っている場合と同様にクラッシュすることはありません。次に、Thread2 は、dom2 を含むイベントを Thread1 に発行して、必要に応じて読み取りを再度実行し、結果を更新できます。

編集：明確化された

Answer 6

@Outlaw の意見も一理あると思います。DOM ツリーの構造はノード自体に存在し、その子を指すノードを持ちます。ツリーの構造を変更するには、ノードを変更する必要があるため、ノードをプールすることはできず、新しいノードを作成する必要があります。

より高いレベルで考えてみてください。IMMUTABLE ツリー (基本的にはその子を指すノードのセット) があります。そこにノードを挿入したいとします。そうなると、もう逃げ道はありません。新しいツリー全体を作成する必要があります。

はい、不変ツリーはスレッドセーフですが、パフォーマンスに影響します。オブジェクトの作成は速いかもしれませんが、オブジェクトを作成しない場合よりも速くはありません。:)