Игаль *    (yigal_s) wrote,
Игаль *   
yigal_s

меряем, наконец, производительность lock-free синхронизации

Несколько лет назад была у меня идея померять масштабируемость и другие параметры lock-free и сравнить его с обычным blocking кодом. Я не очень тогда хорошо понимал, как это делать, задал максимальную интенсивность доступа к "разделяемым данным", получил очень странные результаты, обсуждавшиеся здесь: http://ru-programming.livejournal.com/1240730.html, как-то не очень понял, что делать дальше, да и времени думать особо не было.

Теперь же, когда мне объяснили, что мерять производительность этих алгоритмов надо всё-таки не на самых экстремальных нагрузках, и раз уж вот тут http://ru-programming.livejournal.com/1357645.html# зашел об этом разговор, я написал заново (пользуясь почерпнутыми идеями) тест и даже кое-что померял. Идея теста достаточно проста - треды в цикле лезут и модифицируют одно и то же разделяемое данное (либо в стиле lock-free, либо под традиционной критической секцией) и между подобными доступами вставляют случайную задержку, что-то при этом вычисляя на своих локальных данных. Варьируя среднюю длину случайной задержки, можно моделировать изменение интенсивности доступа к разделяемому данному.

Текст теста (ужасно неряшливо написанный): http://yigal-c.livejournal.com/7344.html

Обсуждение результатов (намерянные графики и дискуссия): http://ru-programming.livejournal.com/1357645.html?thread=22036557

Возможно, я сюда перекопирую сами графики, но как-то не хочется повторяться с обсуждением. Основной вывод - на реалистичных нагрузках lock-free лучше, чем критическая секция. А на очень высоких нагрузках критическая секция , кажется, "вышибает" все треды и даёт возможность одному треду достаточно быстро сделать свою работу без всякой конкуренции, что и даёт блокирующему алгоритму возможность работать быстрее, чем lock-free (я ещё сделаю измерения, чтобы убедиться в верности этой гипотезы). Но, разумеется, эти измерения касались не настоящего алгоритма, а модельного, достаточно минималистского. Реальные lock-free, естественно, должны тестироваться в каждом отдельном случае.

Вопросы и предложения приветствуются.

График 1а и 1b.
Физическое время работы программы из 8 параллельных тредов. По горизонтали - средняя длина случайной задержки между доступами к разделяемому данному (в условных единицах), по вертикали - время работы программы в миллисекундах. Левая диаграмма и правая диаграмма отражают одни и те же данные, но на правой диаграмме по горизонтали - логарифмическая шкала. Синий график - lock free алгоритм, красный график - алгоритм с критической секцией.


График 2. Те же данные. Преимущество алгоритма lock-free по сравнению с critical section. По горизонтали - длина случайной задержки, по вертикали - разница времен работы алгоритмов в миллисекундах.



График 3. Зависимость времени работы программы от числа конкурирующих тредов. По горизонтали - количество тредов, по вертикали - время работы программы. Длина случайной задержки = 200.



График 4. То же, но длина случайной задержки = 1000.



График 5 и 6. Те же данные для задержки в 200 и в 1000 в зависимости от количества тредов, но теперь меряется "total throughput" - скорость модификации (всеми тредами разом) разделяемого данного в зависимости от количества конкурирующих тредов. Поскольку в каждом случае вводятся искусственные задержки, то данные на первой диаграмме бессмысленно напрямую сравнивать с данными второй диаграммы. Что замечательно, на второй диаграмме (задержка 1000) видно, что lock-free (синий график) наконец обеспечивает существенный рост производительности при росте числа тредов вплоть до 7, а алгоритм с критической секцией практически достигает насыщения производительности при всего двух тредах.

Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 1 comment