1

私はrb-treeの実装を書きました。ノードはmallocを使用して割り当てられます。最初に大きなテーブルを割り当て、そのスペースを使用してノードを割り当て、テーブルがオーバーフローするたびにサイズを2倍にすることをお勧めします。割り当てる時間がかなり長いと仮定すると、挿入操作がいくらか速くなりますが、私にはわかりません。

4

1 に答える 1

1

たくさんの小さなアイテムを割り当てるのではなく、1つの大きなブロックを割り当てる（そしてそれを自分で分割する）方がよいかどうかという問題は、多くの状況に当てはまります。そして、それに対する万能の答えはありません。ただし、一般的には、大きなブロックを割り当てる方がおそらく少し速くなります。ただし、スピードアップ（ある場合）は大きくない場合があります。私の経験では、単一の大規模な割り当てを行うことは、通常、動的割り当てを多用する高度な並行システムでの努力と複雑さの価値があります。シングルスレッドのアプリケーションを使用している場合、各ノードの割り当てが挿入操作の非常に小さなコストを構成していると思います。

いくつかの一般的な考え/コメント：

  • 単一の大きなブロックを割り当てる（そして必要に応じてそれを大きくする）と、通常、全体として使用するメモリが少なくなります。一般的な汎用アロケータ（たとえば、Cのmalloc / free）には、割り当てごとにオーバーヘッドがあります。したがって、たとえば、100バイトの小さな割り当て要求では、128バイトが使用される可能性があります。
  • 多くのメモリの断片化が発生するメモリに制約のあるシステムでは、メモリの大きなブロックを割り当ててスライスすることはできない場合がありますが、複数の小さな割り当ては引き続き成功する可能性があります。
  • 大きなブロックを割り当てると、アロケータレベル（mallocなど）での同期の競合が減りますが、独自の管理対象リスト/ブロックからノードを取得する場合は、独自の同期を提供する必要があります（マルチスレッドシステムを想定）。ただし、ノード自体の挿入に関連する同期が必要になる可能性が高いため、同じ操作で処理できます。

最終的には、それをテストして違いを測定する必要があります。実行できる簡単なことの1つは、処理する予定のノードの数と、それにかかる時間（および場合によってはノードの解放時間）を割り当てる単純な「使い捨て」テストを作成することです。これにより、割り当てコストのある種の概算が得られる可能性があります。

于 2013-03-12T14:25:05.620 に答える