0

私のプロジェクトでは、グローバル ハッシュ テーブルにアクセスする N 個のスレッドがあり、これは避けられません。したがって、ロックフリーのハッシュ テーブルなどを使用する必要があると思います。結局のところ、lockfree ハッシュは通常特別な目的のためのものであり、あまり使いやすいものではないため、lockfree ハッシュ テーブルではなく、別のものを試すことにしました。

私の考えは：

グローバル ハッシュ テーブルにアクセスするN 個のスレッドがあるため、ハッシュ テーブルをM個のサブハッシュ テーブル ( M >= N ) にスピルしました。いつでも、M 個のサブハッシュテーブルから N 個のサブハッシュテーブルを選択するすべてのスレッドの合計は pow(M, N) であり、一意の M 個のサブハッシュテーブルから選択した N 個のサブハッシュテーブルの合計は P(M, N) です。 N) であるため、競合状態がない場合の率は P(M, N)/pow(M, N) であり、競合状態がある場合の率は1-P(M,N)/pow(M,N) です。 )、つまり 1-M!/(MN)!/pow(M,N) です。

私の計算では、rは競合状態の割合を意味します。

スレッド数=2

n=2, m=2 r=0.5
n=2, m=3 r=0.333333
n=2, m=4 r=0.25
n=2, m=5 r=0.2
n=2, m=6 r=0.166667
n=2, m=7 r=0.142857
n=2, m=8 r=0.125
n=2, m=9 r=0.111111
n=2, m=10 r=0.1
n=2, m=11 r=0.0909091
...
n=2, m=100 r=0.01
...

スレッド数=3

n=3, m=3 r=0.777778
n=3, m=4 r=0.625
n=3, m=5 r=0.52
n=3, m=6 r=0.444444
n=3, m=7 r=0.387755
...
n=3, m=29 r=0.10107
...

スレッド数=5

n=5, m=5 r=0.9616
n=5, m=6 r=0.907407
n=5, m=7 r=0.850062
n=5, m=8 r=0.794922
n=5, m=9 r=0.743941
...
n=5, m=96 r=0.100425

スレッド数=8

n=8, m=8 r=0.997597
n=8, m=9 r=0.99157
n=8, m=10 r=0.981856
n=8, m=11 r=0.968964
n=8, m=12 r=0.953583
...
n=8, m=268 r=0.100095

利点は、適切な m を選択することです。90% の時間でロックフリーになることができます。

欠点は、多くのリソースを浪費することです。

私の考えは正しいですか？より良い解決策はありますか？

4

1 に答える 1

0

あなたのアルゴリズムの複雑さは、その利点に値しないと思います。実際には、もっと単純な解決策がたくさんあります。開始する前に、使用パターンを決定することをお勧めします。それらを次のように要約できます。

  • HashTable readonly - 一度初期化すると、読み取りは安全です。
  • 追加のみまたは読み取り/書き込み比率が高い - 書き込みごとにハッシュテーブルを再作成し、Interlocked.CompareExchange を使用して置き換えます。
  • 読み取り/書き込み比率が低い - スピンウェイト ベースのリーダー/ライター ロックを使用してください。

そして覚えておいてください - 問題の最善の解決策を決定する唯一の方法は、慎重なテストと測定です!

于 2013-09-05T07:25:57.687 に答える