锁定与比较和交换

Question

我一直在阅读无锁技术,比如比较和交换,并利用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次失败.

所以我的问题是:

1. 我错过了什么？CAS不应该给出更好的结果吗？好处在哪里？
2. 究竟为什么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);

Answer 1

问题是循环上的失败率和字符串是不可变的这一事实的组合.我使用以下参数自己做了几个测试.

• 跑8个不同的线程(我有一个8核机器).
• 每个线程调用Append10,000次.

我观察到的是,弦的最终长度是80,000(8 x 10,000),所以这是完美的.对我来说,追加尝试的次数平均约为300,000.这就是失败率~73%.只有27%的CPU时间带来了有用的工作.现在因为字符串是不可变的,这意味着在堆上创建了字符串的新实例,并且原始内容加上一个额外字符被复制到其中.顺便说一句,这个复制操作是O(n),因此随着字符串的长度增加它变得越来越长.由于复制操作,我的假设是失败率会随着字符串长度的增加而增加.原因在于,由于线程花费更多时间竞争完成ICX,因此复制操作花费的时间越来越多,冲突的可能性就越高.我的测试证实了这一点

这里最大的问题是顺序字符串连接不能很好地适应并行性.由于操作X _n的结果取决于X _n-1,因此完全锁定会更快,特别是如果它意味着您避免所有故障和重试.在这种情况下,悲观的策略赢得了与乐观的战斗.当你可以将问题分成独立的卡盘时,低技术可以更好地工作,这些卡盘真的可以无阻碍地并行运行.

作为旁注,使用Interlocked.CompareExchange初始读取_str是不必要的.原因是在这种情况下读取不需要存储器屏障.这是因为Interlocked.CompareExchange实际执行工作的调用(代码中的第二个调用)将创建一个完整的屏障.因此最糟糕的情况是第一次读取是"陈旧的",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;
  }
}

¹ 在讨论记忆障碍时,我实际上不喜欢"陈旧"和"新鲜"这两个词,因为这不是真正的内容.与实际保证相比,它更具有副作用.但是,在这种情况下,它更好地说明了我的观点.