锁vs比较和交换

我一直在阅读有关无锁技术，比如比较和交换，并利用Interlocked和SpinWait类来实现线程同步而不锁定。锁vs比较和交换

我已经跑了一些我自己的测试，在那里我只是有很多线程试图追加一个字符到一个字符串。我尝试使用常规的lock和比较和交换。令人惊讶的是（至少对我来说），锁显示比使用CAS好得多的结果。

下面是我的代码的CAS版本（基于this）。它遵循一个禁止复制>修改 - >交换模式：

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秒和锁定版本700ms（平均）。对于100k字符，分别需要7秒和3.8秒。这是在一个四核（i5 2500k）上运行的。

我怀疑CAS之所以显示这些结果的原因是因为它最后一次“交换”步骤失败了很多。我是对的。当我尝试添加50k个字符（50k成功交换）时，我能够计算在70k（最好的情况下）和接近200k（最坏的情况）失败的尝试之间。最糟糕的情况是，每5次尝试中有4次失败。

所以我的问题是：

我缺少什么？ CAS不应该给出更好的结果吗？好处在哪里？
为什么究竟CAS何时是更好的选择？（我知道这已被问到，但我找不到任何令人满意的答案，这也解释了我的具体情况）。

我的理解是，使用CAS的解决方案尽管难于编码，但随着争用的增加，其规模会变得更好，并且执行得更好。在我的例子中，操作非常小且频繁，这意味着高争用和高频率。那么为什么我的测试显示其他情况？

我认为较长的操作会使情况更糟 - >“掉期”失败率会进一步增加。

PS：这是我用来运行测试的代码：

Stopwatch watch = Stopwatch.StartNew(); 
var cl = new Class1(); 
Parallel.For(0, 50000, i => cl.Append('a')); 

var time = watch.Elapsed; 
Debug.WriteLine(time.TotalMilliseconds);

来源

2013-10-18 dcastro

不，您不测量CAS的执行时间，但主要是字符串比较的执行时间。不幸的是，Interlocked类没有针对引用类型的原子读取 - 修改 - 写入操作（这就是您在“锁定”示例中基本上做的事情，而不依赖于字符串比较。） – elgonzo

您的无锁解决方案比锁更多的工作版。首先，读取现有值的最初'CompareExchange'是过度杀伤，执行一个易失性读（'Thread.VolatileRead'）将给你相同的结果，而没有较少的开销。其次，循环中的每个尝试更新都将复制字符串的“当前”值并追加新值。你无法做任何事情，但锁定版本不会遇到这个问题。这是最有可能导致大部分时间差异的字符串副本。 – William

对于我们凡人来说，坚持使用现有的锁，而不是试图推出自己的锁。多线程很难处理[ABA]（http://en.wikipedia.org/wiki/ABA_problem）问题。 – William

的问题是环路上的故障率，事实上，字符串是不可变的组合。我使用以下参数自己做了几项测试。

Ran 8个不同的线程（我有一个8核心机器）。
每个线程都叫做Append 10,000次。

我观察到的是字符串的最终长度是80,000（8 x 10,000），所以这是完美的。追加尝试次数平均为〜300,000。所以这是〜73％的失败率。只有27％的CPU时间导致有用的工作。现在因为字符串是不可变的，这意味着在堆上创建了一个新的字符串实例，原始内容加上一个额外的字符被复制到它中。顺便说一句，这个复制操作是O（n），所以随着字符串长度的增加它变得越来越长。由于复制操作，我的假设是失败率会随着字符串长度的增加而增加。原因在于随着复制操作花费越来越多的时间，碰撞的可能性越高，因为线程花费更多时间争夺完成ICX。我的测试证实了这点。你应该自己尝试这个相同的测试。

这里最大的问题是顺序字符串并置不适合并行。由于操作结果X _n取决于X _n-1采取完全锁定的速度会更快，尤其是如果它意味着您避免了所有故障并重试。在这种情况下，悲观策略赢得了对抗乐观的战斗。当你可以将问题分割成真正可以并行运行的独立卡盘时，低技术效果会更好。

作为便笺，使用Interlocked.CompareExchange来做_str的初始读取是不必要的。原因是在这种情况下读取不需要内存屏障。这是因为实际执行工作的调用（代码中的第二个调用）将创建完整的屏障。所以最糟糕的情况是，第一次读取是“陈旧”，ICX操作未能通过测试，并且循环回转再次尝试。然而，这一次，以前的ICX强制进行“新鲜”阅读。

下面的代码是我如何推广使用低锁定机制的复杂操作。事实上，下面介绍的代码允许您传递一个代表操作的委托，所以它是非常普遍的。你想在生产中使用它吗？可能不是因为调用委托很慢，但你至少可以得到这个想法。您始终可以对操作进行硬编码。

public static class InterlockedEx 
{ 
    public static T Change<T>(ref T destination, Func<T, T> operation) where T : class 
    { 
    T original, value; 
    do 
    { 
     original = destination; 
     value = operation(original); 
    } 
    while (Interlocked.CompareExchange(ref destination, value, original) != original); 
    return original; 
    } 
}

其实我不喜欢的条款“过时”和“新鲜”的讨论记忆障碍的时候，因为这不是他们对真正的东西。与实际担保相比，这更多是一种副作用。但是，在这种情况下，它更好地说明了我的观点。

来源

2013-10-20 02:48:40

这非常有启发性，特别是对不断增长的故障率的解释以及为什么这种方法不能扩展。谢谢。 – dcastro

锁vs比较和交换

回答

相关问题