我们的应用程序使用了大量字典,这些字典具有不经常更改的多级查找.我们正在研究转换使用字典进行大量查找的一些关键代码,以使用替代结构 - 更快的查找,点亮内存/ gc.这让我们比较了各种可用的词典/库 -
Dictionary(System.Collections.Generics.Dictionary-SCGD) ,ImmutableDictionary,.C5.HashDictionaryFSharpMap
运行包含各种项目的以下程序 - 100,1000,10000,100000 - 表示词典在大多数范围内仍然是赢家.第一行表示集合中的项目.MS/Ticks将随机执行x查找所花费的时间(代码如下).
项目 - 100
SCGD - 0 MS - 50 Ticks
C5 - 1 MS - 1767 Ticks
Imm - 4 MS - 5951 Ticks
FS - 0 MS - 240 Ticks
项目 - 1000
SCGD - 0 MS - 230 Ticks
C5 - 0 MS - 496 Ticks
Imm - 0 MS - 1046 Ticks
FS - 1 MS - 1870 …
我知道之前已经问过这个问题(我将继续研究),但我需要知道如何以线程安全的方式创建特定的链表功能.我当前的问题是我有一个循环遍历链表中所有元素的线程,另一个可能会在此列表的末尾添加更多元素.有时会发生这样的情况:一个线程尝试将另一个元素添加到列表中,而第一个元素正忙于迭代它(这会导致异常).
我想只是添加一个变量(布尔标志)来表示列表当前正在忙于迭代,但是我如何检查它并等待第二个线程(如果它等待,则可以,因为第一个线程运行很快).我能想到的唯一方法是通过使用while循环不断检查这个忙碌的标志.我意识到这是一个非常愚蠢的想法,因为它会导致CPU在没有任何用处的情况下努力工作.现在我在这里要求更好的见解.我已经阅读了关于锁等等,但它似乎与我的情况无关,但也许我错了？
与此同时,如果我找到解决方案,我将继续搜索互联网并发回.
编辑:让我知道我是否应该发布一些代码来清理,但我会尝试更清楚地解释它.
所以我有一个带有链表的类,其中包含需要处理的元素.我有一个线程通过函数调用遍历此列表(让我们称之为"processElements").我有第二个线程,以非确定的方式添加元素进行处理.但是,有时它会在processElements运行时尝试调用此addElement函数.这意味着当一个元素被第一个线程迭代时,它被添加到链表中.这是不可能的,并导致异常.希望这清除它.
我需要添加新元素的线程,直到processElements方法执行完毕.
我一直在阅读无锁技术,比如比较和交换,并利用Interlocked和SpinWait类来实现线程同步而不需要锁定.
我已经运行了一些我自己的测试,我只是有很多线程尝试将字符附加到字符串.我尝试使用常规locks和比较和交换.令人惊讶的是(至少对我而言),锁比使用CAS显示出更好的结果.
这是我的代码的CAS版本(基于此).它遵循copy-> modify-> swap模式:
private string _str = "";
public void Append(char value)
{
var spin = new SpinWait();
while (true)
{
var original = Interlocked.CompareExchange(ref _str, null, null);
var newString = original + value;
if (Interlocked.CompareExchange(ref _str, newString, original) == original)
break;
spin.SpinOnce();
}
}
更简单(也更有效)的锁定版本:
private object lk = new object();
public void AppendLock(char value)
{
lock (lk)
{
_str += value;
}
}
如果我尝试添加50.000个字符,则CAS版本需要1.2秒,锁定版本需要700毫秒(平均值).对于100k字符,它们分别需要7秒和3.8秒.这是在四核(i5 2500k)上运行的.
我怀疑CAS显示这些结果的原因是因为它在最后一次"交换"步骤失败了.我是正确的.当我尝试添加50k字符(50k成功交换)时,我能够计算出70k(最佳情况)和近200k(最差情况)失败尝试之间的数量.最糟糕的情况是,每5次尝试中有4次失败.
所以我的问题是:
我的理解是,采用CAS的解决方案尽管难以编码,但随着争用的增加,其规模要好得多,并且比锁具更好.在我的例子中,操作非常小且频繁,这意味着高争用和高频率.那么为什么我的测试显示不然呢？
我认为较长的操作会使情况更糟 - …