c# - 锁与比较和交换

Question

我一直在阅读无锁技术，例如比较和交换以及利用 Interlocked 和 SpinWait 类来实现线程同步而无需锁定。

我已经运行了一些自己的测试，其中我只是有很多线程试图将一个字符附加到一个字符串。我尝试使用常规 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 秒，锁定版本需要 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 核机器)。
• 每个线程调用 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 是不必要的。原因是在这种情况下读取不需要内存屏障。这是因为实际执行工作的 Interlocked.CompareExchange 调用(代码中的第二个调用)将创建一个完整的屏障。所以最坏的情况是第一次读取是“陈旧的”，ICX 操作未通过测试，并且循环旋转回来重试。然而，这一次，之前的 ICX 强制执行“全新”读取。¹

以下代码是我如何使用低锁机制概括复杂操作。事实上，下面给出的代码允许您传递代表操作的委托(delegate)，因此它非常通用。你想在生产中使用它吗？可能不是因为调用委托(delegate)很慢，但你至少明白了。您始终可以对操作进行硬编码。

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;
  }
}

---

¹在讨论内存障碍时，我实际上不喜欢“陈旧”和“新鲜”这两个词，因为这不是它们真正的意思。与实际保证相比，它更像是一种副作用。但是，在这种情况下，它更好地说明了我的观点。