Как я могу оценить производительность очереди без блокировки?

Question

Я реализовал очередь без блокировки, используя методологию указателя опасности, описанную в http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf, используя инструкции GCC CAS для реализации и локальное хранилище pthread для локальных структур потоков.Сейчас я пытаюсь оценить производительность написанного мной кода, в частности я пытаюсь провести сравнение между этой реализацией и той, которая использует блокировки (мьютексы pthread) для защиты очереди.
Язадавая этот вопрос здесь, потому что я попытался сравнить его с «заблокированной» очередью и обнаружил, что это имеет лучшие показатели по сравнению с реализацией без блокировки.Единственный тест, который я попробовал, - это создание 4-х потоков на 4-ядерном компьютере x86_64, выполняющем 10 000 000 случайных операций в очереди, и это значительно быстрее, чем в версии без блокировки.

Я хочу знать, можете ли вы предложить мне подход, которым я должен следовать, то есть, какую операцию я должен проверить в очереди и какой инструмент я могу использовать, чтобы увидеть, где мой код без блокировки тратит свое время,

Я также хочу понять, возможно ли, что производительность для очереди без блокировки только из-за того, что четырех потоков недостаточно, чтобы увидеть значительное улучшение ...

Спасибо

Answer 1

Первая точка: программирование без блокировки не обязательно повышает скорость. Программирование без блокировки (если все сделано правильно) гарантирует продвижение вперед. Когда вы используете блокировки, возможно, что один поток потерпит крах (например, перейдет в бесконечный цикл), удерживая мьютекс. Когда / если это произойдет, никакой другой поток, ожидающий этого мьютекса, не сможет больше продвинуться. Если этот мьютекс занимает центральное место в нормальной работе, вам, возможно, придется перезапустить весь процесс, прежде чем вообще можно будет выполнить какую-либо работу. При программировании без блокировки таких обстоятельств возникнуть не может. Другие потоки могут продвигаться вперед, независимо от того, что происходит в одном потоке ¹ .

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

Итог: больше потоков (по крайней мере, пара десятков) увеличат шансы очереди без блокировок, показывающей выигрыш в производительности, но с только четырьмя ядрами, это не будет ужасно удивительно, если очередь на основе блокировки все еще идет в ногу. Если вы добавите достаточное количество потоков и ядер, практически неизбежно победит версия без блокировки. Точное количество необходимых потоков и ядер сложно предсказать, но вы должны думать как минимум о десятках.

---

¹ По крайней мере, что-то вроде мьютекса. Нечто похожее на бомбу-вилку, которая просто съела все системные ресурсы, может лишить другие потоки достаточного количества ресурсов, чтобы что-то сделать, но некоторые заботы о таких вещах, как квоты, обычно тоже могут это предотвратить.

Answer 2

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

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

При сильных блокировках потоки блокируются и планируются один раз Получаются замки, что в основном означает, что они размещены в конце пробега очередь (для определенного уровня prio). По неосторожности это связывает приложение с системой состояние и время ответа для приложения теперь зависят от длины очереди выполнения.

Только мои 2 цента.

Answer 3

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

Наша собственная реализация может выиграть только в значительной степени для перегруженной части.Просто случайные операции с очередью (вы не слишком точны в своем вопросе), вероятно, не сделают этого, если средняя длина очереди намного больше, чем количество потоков, которые ее взламывают параллельно.Таким образом, вы должны убедиться, что очередь короткая, возможно, введя смещение в отношении случайной операции, которая выбирается, если очередь слишком длинная или слишком короткая.Тогда я бы также зарядил систему как минимум вдвое большим количеством потоков, чем ядер.Это гарантирует, что время ожидания (для памяти) не будет играть в пользу версии блокировки.