Блокировки работают не так уж медленно

http://preshing.com/20111118/locks-arent-slow-lock-contention-is/
  • Перевод
  • Tutorial
Блокировки в общем и мьютексы, как их частная реализация, имеют давнюю историю неправильной оценки скорости их работы. Ещё в 1986-ом году в одной из Usenet-конференций Matthew Dillon написал: «Большинство людей ошибочно уяснили себе, что блокировки работают медленно». Сегодня, спустя многие годы, можно констатировать, что ничего не изменилось.

Действительно, блокировки могут работать медленно на некоторых платформах, или в сверх-конкурентном коде. И, если вы разрабатываете многопоточное приложение, то вполне возможно, что рано или поздно натолкнётесь на ситуацию, когда какая-нибудь одна блокировка будет съедать очень много ресурсов (скорее всего из-за ошибки в коде, приводящей к слишком частому её вызову). Но всё это частные случаи, не имеющие в общем случае отношения к утверждению «блокировки работают медленно». Как мы увидим ниже, код с блокировками может работать весьма производительно.

Одна из причин заблуждений о скорости работы блокировок состоит в том, что многие программисты не отличают понятия «легковесный мьютекс» и «мьютекс, как объект ядра ОС». Всегда используйте легковесные мьютексы. К примеру, если вы программируете на С++ под Windows, то ваш выбор это критические секции.

imageВторой причиной заблуждений могут служить, как это ни парадоксально, бенчмарки. К примеру, далее в этой статье мы будем измерять производительность блокировок под высокой нагрузкой: каждый поток будет требовать блокировку для выполнения любого действия, а сами блокировки будут очень короткими (и, в результате, очень частыми). Это нормально для эксперимента, но такой способ написания кода — это не то, что вам нужно в реальном приложении.

Блокировки критикуются и по другим причинам. Есть целое семейство алгоритмов и технологий, называемых "lock-free" программированием. Это невероятно захватывающий и вызывающий способ разработки, который способен принести огромный прирост производительности в целый ряд приложений. Я знаю программистов, которые тратили недели на полировку своих «lock-free»-алгоритмов, писали на них миллион тестов — и всё лишь для того, чтобы поймать редкий баг, связанный с определённой комбинацией таймингов, несколькими месяцами позже. Эта комбинация опасности и награды за неё может быть очень привлекательной для некоторых программистов (в том числе и меня). С мощью «lock-free» классические блокировки начинают казаться скучными, устаревшими и тормозящими.

Но не спешите сбрасывать их со счетов. Одним из хороших примеров, где блокировки часто используются и показывают хорошую производительность, являются аллокаторы памяти. Популярная реализация malloc от Doug Lea часто используется в геймдеве. Но она однопоточна, так что нам необходимо защитить её блокировками. Во время активной игры у нас вполне может возникнуть ситуация, когда несколько потоков обращаются к аллокатору с частотой, скажем, 15 000 раз в секунду. Во время загрузки игры эта цифра может доходить и до 100 000 раз в секунду. Как вы увидите дальше, это совершенно не является проблемой для кода с блокировками.

Бенчмарк


В этом тесте мы запустим поток, который будет генерировать случайные числа с помощью алгоритма вихря Мерсенна. По ходу работы он будет регулярно захватывать и освобождать объект синхронизации. Время между захватом и освобождением будет случайно, но в среднем оно будет стремиться к заданной нами величине. К примеру, представим, что мы хотим использовать блокировку 15 000 раз в секунду и удерживать её 50% времени. Вот как в этом случае будет выглядеть таймлайн. Красный цвет означает время, когда блокировка захвачена, серый — когда свободна.

image

Это, по сути, процесс Пуасона. Если мы знаем среднее количество времени для генерации одного случайного числа (а это, например, 6.349 наносекунд на процессоре 2.66 GHz quad-core Xeon) — мы можем измерить количество выполненной работы в некоторый юнитах, а не в секундах. Мы можем использовать технику, описанную в другой моей статье, для определения количества юнитов работы между захватом и освобождением объекта синхронизации. Вот реализация на С++. Я опустил некоторые несущественные детали, но вы можете скачать полный исходный код здесь.

QueryPerformanceCounter(&start);
for (;;)
{
    // Выполняем некоторую работу без блокировки
    workunits = (int) (random.poissonInterval(averageUnlockedCount) + 0.5f);
    for (int i = 1; i < workunits; i++)
        random.integer();   // выполняем один юнит работы
    workDone += workunits;

    QueryPerformanceCounter(&end);
    elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
    if (elapsedTime >= timeLimit)
        break;

    // Выполняем некоторую работу с блокировкой
    EnterCriticalSection(&criticalSection);
    workunits = (int) (random.poissonInterval(averageLockedCount) + 0.5f);
    for (int i = 1; i < workunits; i++)
        random.integer();   // выполняем один юнит работы
    workDone += workunits;
    LeaveCriticalSection(&criticalSection);

    QueryPerformanceCounter(&end);
    elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
    if (elapsedTime >= timeLimit)
        break;
}

Теперь давайте представим, что мы запустили два таких потока, каждый на своём ядре процессора. Каждый поток будет удерживать блокировку 50% времени своей работы, но если один поток попытается получить доступ к критической секции в то время, когда она удерживается другим потоком, то он будет вынужден ждать. Классический случай борьбы за разделяемый ресурс.

image

Я думаю, что это достаточно приближенный к реальности пример того, как блокировки используются в реальных приложениях. Когда мы запустим вышеуказанный код в двух потоках, то обнаружим, что каждый поток проводит около 25% времени в ожидании и лишь 75% времени выполняя реальную работу. Вместе два потока увеличивают производительность в 1.5 раза по сравнению с однопоточным решением.

Я запускал этот тест с разными вариациями на процессоре 2.66 GHz quad-core Xeon — в 1 поток, в 2 потока, в 4 потока, каждый на своём ядре. Я также вариировал длительность захвата блокировки от вырожденного случая, где блокировка освобождалась незамедлительно, до противоположной грани, когда блокировка занимала 100% времени работы потока. Во всех случаях частота захвата оставалась константной — 15 000 раз в секунду.

image

Результаты были достаточно интересными. Для короткой длительности захвата (я бы сказал до 10% времени), система показывала крайне высокую степень параллелизма. Не идеально, но близко к этому. Блокировки работают быстро!

Для оценки результатов в плане практического применения я проанализировал работу аллокатора памяти в многопоточной игре с помощью профайлера. По ходу игры происходило около 15 000 вызовов аллокатора из трёх потоков, блокировки занимали около 2% общей производительности приложения. Эта величина находится в «зоне комфорта» в левой части графика.

Данные результаты показывают также, что как только длительность работы кода внутри блокировки переходит грацину в 90% общего времени — больше нет смысла писать многопоточный код. Однопоточное приложение в данном случае будет работать быстрее. Что ещё более удивительно — это резкий скачок вниз производительности 4-ех потоков в районе 60%. Это было похоже на аномалию, так что я повторил тест несколько раз, пробовал запускать тесты в другом порядке. Но каждый раз получалось одно и то же. Моя лучшая догадка состоит в том, что данная комбинация числа потоков, длительности блокировок и нагрузки на процессор вывели планировщик Windows в некоторый экстремальный режим работы, но я не исследовал это глубже.

Бенчмарк частоты захвата блокировки


Даже легковесный мьютекс несёт с собой некоторые накладные расходы. Пара операций lock/unlock для критической секции в Windows работает около 23.5 наносекунд (на вышеуказанном процессоре). Таким образом, даже 15 000 блокировок за секунду не несут какой-то существенной нагрузки, влияющей на производительность. Но что будет, если мы повысим частоту?

Вышеуказанный алгоритм предлагает очень удобные средства контроля количества работы, выполняемой между захватами блокировки. Я провёл ещё одну серию тестов: от 10 наносекунд до 31 микросекунды между блокировками, что соответствует примерно 32 000 блокировкам за секунду. В каждом тесте использовались два потока.

image

Как вы могли предположить, при очень высокой частоте накладные расходы на блокировки начинают влиять на общую производительность. На таких частотах внутри блокировки выполняется всего несколько инструкций, что сравнимо по времени с самим захватом\освобождением объекта синхронизации. Хорошие новости состоят в том, что для таких коротких (а значит, простых) операций вполне вероятно можно разработать и использовать некоторый lock-free алгоритм.

В то же время результаты показали, что вызов блокировок до 320 000 раз в секунду (3.1 микросекунд между блокировками) может быть вполне эффективным. В геймдеве аллокатор памяти может нормально работать на подобных частотах во время загрузки игры. Вы всё ещё получаете до 1.5х прироста от многопоточности в данном случае (но только если длительность самой блокировки будет небольшой).

Мы рассмотрели широкий спектр различных случаев использования блокировок: от очень высокой их производительности, до случаев, когда сама идея многопоточности теряет смысл. Пример с аллокатором памяти в игровом движке показал, что в реальных приложениях высокая частота использования блокировок вполне допустима при выполнении некоторых условий. С такими аргументами никто уже не сможет просто голословно сказать, что «блокировки работают медленно». Да, блокировки можно использовать неэффективным образом, но жить с этим страхом не стоит — к счастью у нас есть профайлеры, которые легко определяют подобные проблемы. Каждый раз, когда вы захотите броситься с головой в омут захватывающего и опасного lock-free программирования — вспомните данную статью и тот факт, что и блокировки могут работать достаточно быстро.

Целью этой статьи было вернуть блокировкам немного того уважения, которое они справедливо заслуживают. Я понимаю, что при всём богатстве вариантов использования блокировок в промышленном ПО, программистов сопровождали как успехи, так и болезненные неудачи в процессе поиска баланса производительности. Если у вас есть пример того или другого — расскажите об этом в комментариях.
Инфопульс Украина
97,00
Creating Value, Delivering Excellence
Поделиться публикацией

Похожие публикации

Комментарии 15

    +12
    Пара операций lock/unlock для критической секции в Windows работает около 23.5 наносекунд (на вышеуказанном процессоре).

    Это сферический тайминг в вакууме. В реальных условиях, когда пара ядер дергает одну блокировку, при каждом дергании происходит ещё сброс соответствующих кэш-линий у «соседнего» ядра, что очень больно по времени. Даже по графикам видно, что как только частота обращений к блокировкам превышает пару МГц, всё — сушите вёсла, безотносительно длительности собственно критической секции. Тупо подсистема памяти больше не вытягивает, не смотря на все гигагерцы.
      0
      >когда пара ядер дергает одну блокировку, при каждом дергании происходит ещё сброс соответствующих кэш-линий у «соседнего» ядра

      что это значит? если под понятием «дергании» имеется ввиду операция попытки захвата, то это несколько не так: сброс кеш-линии будет происходить только при операции записи значения «счетчика», а попытка захвата — лишь чтение изначально.
      Да, при успешной записи L1-кеш у каждого ядра обновится и общий L2 — тоже. Однако это справедливо для любой операции записи.

      И вот здесь самое интересное: мгновенный сброс кеш-линий (или эмуляция оного для юзера) для каждой записи возможен, но только если существует total-store-order между потоками. эта очень вещь затратная и все стараются такие операции записи обходить. здесь уже появляется lock-free код.

      критическая секция в Win32 устроена внутри как CAS-цикл, т.е. захват может не всегда быть удачным при первой и последующих попытках, но цикл будет продолжаться. Таким образом, попытка захвата — лишь чтение изначально, но не запись.

      графики показывают очень важную вещь (что есть правда) — чем больше кол-во конкурирующих между собой потоков — тем больше проседает система.

      здесь необходимо сделать ремарку: lock-free является вещью опасной, т.к. оно еще плохо сочетается с планировщиком ОС. Если система должна быть высококонкурентной, то нужно пользоваться SwitchToThread и т.п. (использовать что-то наподобие spin-wait), иначе
      >накладные расходы на блокировки начинают влиять на общую производительность

        0
        Давайте с начала.
        Даже если процессор в компе физически один, всё равно вокруг него куча микросхем, которые умеют лазить в память напрямую. Это GPU, это чипсет, это всякие втыкаемые контроллеры с DMA и т.д. и т.п.
        Даже если в этих микросхемах нет собственного кэша (что вряд ли), они всё равно обязаны соблюдать протоколы когерентности кэшей CPU.
        Ну и сам процессор должен соблюдать свои же протоколы, что логично.
        Дальше вот что: при любых примитивах синхронизации ближайшим общим хранилищем, через которую эту синхронизацию можно делать, является оперативная память, она же DRAM.
        Соответственно, все «атомарные» инструкции типа CAS/XCHG/wtf это просто «синтаксический сахар» для старых добрых наборов микроопераций с префиксом LOCK, которые были доступны ещё на 8086. Смысл в том, что процессор захватывает доступ к DRAM на время выполнения нескольких операций. И потом начинает своё «читать — проверить — модифицировать», не пуская на шину памяти никого другого.
        Если захват не удался — да, действительно, «ничего не происходит». Но если удался — то все кэши всех микросхем, подключенных к данной DRAM, инвалидируются по указанной строке.
        Проблема с DRAM в том, что она слишком медленная просто из-за архитектуры. Вы не можете взять и прочитать 1 байт памяти, как во времена Z80. Современные процессоры хапают сразу как минимум пакет из 64 байт. И это не потому, что проектировщики дебилы, просто слишком долго распространяется и обрабатывается сигнал запроса. По сути, процессор делает запрос, потом долго-долго ждёт, пока память его переварит, и только потом память буквально «выплёвывает» ответ.
        При росте частот инженеры как могли спасали пропускную способность памяти. Но задержки (латенси) так и остались на уровнях 30-летней давности. А для коротких блокировок критичны как раз задержки.
          0
          про RMW и блокировку шины я подразумевал
          >мгновенный сброс кеш-линий (или эмуляция оного для юзера)

          То, что вы написали — правильно, но никак не отвечает на мой вопрос. Кеш-линии и так будут инвалидироваться при операциях записи. Мой поинт в том, что не каждая попытка захвата будет сбрасывать кеш-линию.

          False sharing на уровне кешей L1 и L2 будет все равно.
          Причем же тут «вина» блокировок? Обычно реализации и так используют выровненный доступ по размеру кеш-линии, чтобы случайно не аффектить приложение.
            0
            Все верно, ну а как вы предлагаете жить без блокировок если они нужны? LockFree не панацея. Более того, на моей практике он всегда оказывался либо такой же, по скорости, как и код с блокировками (например легкими, типа Spin), либо медленнее, так как LockFree банально тяжелее и сложнее. LockFree используется в специфических задачах, в основном в ядре, там, где любой поток может быть снят без уведомления и нельзя использовать блокировку (как абстракцию) вообще.
              0
              Да я не против блокировок, я к таймингам прицепился. Уж слишком они похожи на обычную латентность драм. В многоядерном окружении всё будет сильно хуже.
          +2
          А причем тут кеш-линии, вы думаете что при атомарной изменении одной ячейки они не будут сбрасываться?
          +2
          Данный синтетически тест работает с очень маленьким набором данных — сброс L1 кэшей в нем не проявляет себя. Если же у вас нормальное приложение, которое действительно делает что-то (активно обращается к разным данным в памяти), то там картина может быть совсем другая.

          PS: Если честно, то для меня название стаитьи звучит зак злая ирония — последние несколько недель работаю с hi-concurrency — там лишняя блокировка это сразу сильные потери скорости. С другой стороны там и условия весьма специфические — требуется «прокачивать» через очередь >10M messages/sec.
            +1
            то там картина может быть совсем другая.

            Может. Если у нас код, работающий при захваченной блокировке, обращается к данным, расположенным в разных участках памяти, он сбрасывает/вымывает кеши и так и так, что с блокировкой, что без нее, верно? Обращение к еще одному адресу, стоящему особняком(блокировке), не должно привести к сильному проседанию. Тем более, что spin-lock блокировки может быть настроен на определенное количество обращений.
              0
              Если он обращается к разным участкам памяти. Но ведь наиболее частый сценарий — относительно небольшая область используемой памяти, либо обращение к памяти более-менее последовательно. Именно под эти сценарии в первую очередь оптимизируются современные процессоры. И как раз вот эта оптимизация и страдает, если у вас блокировки происходят часто. А вот на сколько страдает — нужно мерить для конкретного приложения реальный сценарий использования. Это как раз та область, где сами по себе синтетические тесты дают лишь пищу для размышлений, но никак не однозначный ответ что лучше, а что хуже. Тест из статьи — пример плохого, вредного теста. Но плохой он не из-за конструкции теста, а из-за интерпретации результатов и совершаемых выводов.
                0
                Но ведь наиболее частый сценарий — относительно небольшая область используемой памяти, либо обращение к памяти более-менее последовательно.

                Это, право слово, очень вольное допущение.

                Именно под эти сценарии в первую очередь оптимизируются современные процессоры.

                Не совсем. Этот сценарий в принципе, в отличие от произвольного доступа, возможно оптимизировать, и он оптимизируется. Что в свою очередь заставляет программистов располагать данные и обращаться к ним определенным образом. Здесь нельзя однозначно сказать, где причина, где следствие.

                И как раз вот эта оптимизация и страдает, если у вас блокировки происходят часто.

                Простите, а вы блокировкой защищаете единичную переменную или массив, который проходите последовательно?
                Я к тому, что надо говорить про каждый конретный случай отдельно. В вашем случае — да, страдает. Но lock-free тоже требуют накладных расходов, в зависимости от реализации может быть копирование с опять же выбивание кеша и т.д.
                Типичный случай для меня сейчас в текущей работе, например, защита линейного отсортированного массива(пара строка-объект), поиск в котором производится методом дихотомии. При большом размере коллекции скачки поначалу происходят по очень разным адресам, там не то что кеш ЦП будет играть свою скрипку, а банально подкачка страниц.

                Тест из статьи — пример плохого, вредного теста. Но плохой он не из-за конструкции теста, а из-за интерпретации результатов и совершаемых выводов.

                Скажем так — это средний вывод для среднего теста. Который — да — не учитывает другие факторы, которые могут влиять в другой ситуации.
            0
            Зашёл прочитать про торжество РосКомНадзора. Приятно удивился, поставил плюс.
              +5
              Чуть не пропустил статью из-за заголовка — можно решить, что снова о блокировках в Интернете.
                +1
                В статье не хватает зависимости throughput'а от настроек spinlock'а. А разница бывает значительной.
                  +1
                  Суть статьи в том, что это не блокировки медленные, а программисты неправильно их используют.
                  А все примеры говорят о том, что если много потоков требуют блокировок одних и тех же данных, то стоит проверить вариант пре- и постпроцессингом данных, для уменьшения количества и времени захвата блокировок.
                  PS. Почему на 60% подает производительность 4 потоков?

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое