Замки против сравнения и обмена

Я читал о методах без блокировки, таких как Compare-and-swap и использование классов Interlocked и SpinWait для достижения синхронизации потоков без блокировки.

Я провел несколько собственных тестов, где у меня просто есть множество потоков, пытающихся добавить символ в строку. Я пытался использовать обычные lockи сравнить и обменять. Удивительно (по крайней мере для меня), блокировки показали гораздо лучшие результаты, чем при использовании CAS.

Вот CAS-версия моего кода (основанная на этом). Следует шаблон копирования-> изменения-> обмена:

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

Если я пытаюсь добавить 50000 символов, версия CAS занимает 1,2 секунды, а версия блокировки - 700 мс (в среднем). Для персонажей 100k они занимают 7 секунд и 3,8 секунды соответственно. Это было запущено на четырехъядерном процессоре (i5 2500k).

Я подозревал, что причина, по которой CAS отображал эти результаты, заключалась в том, что он часто не выполнял последний шаг "обмена". Я был прав. Когда я пытался добавить 50 тыс. Символов (50 тыс. Успешных свопов), я мог рассчитывать между 70 тыс. (Наилучший сценарий) и почти 200 тыс. (Худший сценарий) неудачных попыток. В худшем случае, 4 из каждых 5 попыток потерпели неудачу.

Итак, мои вопросы:

  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);
Источник

1 ответ

Решение

Проблема заключается в сочетании частоты отказов в цикле и того факта, что строки являются неизменяемыми. Я сделал пару тестов самостоятельно, используя следующие параметры.

  • Пробежал 8 разных потоков (у меня 8 ядро ​​машины).
  • Каждый поток называется Append 10000 раз.

Что я заметил, так это то, что конечная длина струны составляла 80 000 (8 х 10 000), так что это было идеально. Число попыток добавления в среднем составило ~300 000 для меня. Так что это процент отказов ~73%. Только 27% процессорного времени привело к полезной работе. Теперь, поскольку строки являются неизменяемыми, это означает, что новый экземпляр строки создается в куче, и в нее копируется оригинальное содержимое плюс один дополнительный символ. Кстати, эта операция копирования - O(n), поэтому она увеличивается по мере увеличения длины строки. Из-за операции копирования моя гипотеза состояла в том, что частота отказов будет увеличиваться с увеличением длины строки. Причина в том, что, поскольку операция копирования занимает все больше и больше времени, вероятность столкновения возрастает, поскольку потоки тратят больше времени на финализацию ICX. Мои тесты подтвердили это. Вы должны попробовать этот же тест самостоятельно.

Самая большая проблема здесь заключается в том, что последовательные конкатенации строк не очень хорошо подходят для параллелизма. Поскольку результаты операции X n зависят от X n-1, будет быстрее взять полную блокировку, особенно если это означает, что вы избежите всех сбоев и повторных попыток. В этом случае пессимистическая стратегия выигрывает битву против оптимистической. Низкие методы работают лучше, когда вы можете разбить проблему на независимые блоки, которые действительно могут работать беспрепятственно параллельно.

В качестве примечания отметим использование Interlocked.CompareExchange сделать первоначальное чтение _str не нужно Причина в том, что в этом случае для чтения не требуется барьер памяти. Это потому что Interlocked.CompareExchange вызов, который фактически выполняет работу (второй в вашем коде), создаст полный барьер. Таким образом, наихудший сценарий состоит в том, что первое чтение "устарело", операция ICX не проходит тест, и цикл повторяется, чтобы повторить попытку. На этот раз, однако, предыдущий ICX вызвал "свежее" чтение. 1

Следующий код показывает, как я обобщаю сложную операцию, используя механизмы низкой блокировки. Фактически, код, представленный ниже, позволяет передавать делегат, представляющий операцию, поэтому она очень обобщенная. Хотите использовать его в производстве? Вероятно, не потому, что вызов делегата идет медленно, но вы, по крайней мере, поняли идею. Вы всегда можете жестко запрограммировать операцию.

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

Мне действительно не нравятся термины "устаревшие" и "свежие" при обсуждении барьеров памяти, потому что это не то, о чем они на самом деле. Это скорее побочный эффект, чем действительная гарантия. Но в данном случае это лучше иллюстрирует мою точку зрения.

Источник
Другие вопросы по тегам