Многопоточность против общей памяти

Question

У меня есть проблема, которая по сути представляет собой серию поисков нескольких копий предметов (игл) в массивной, но в памяти базе данных (10 с Гб) - стоге сена.

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

(Это уже распределено по нескольким машинам, где каждая машина имеет свою собственную копию стога сена. )

Существует множество способов распараллеливания этого процесса на отдельных машинах.

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

3 возможных архитектуры:

1. Процесс загружает стог сена в общую память Posix.

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

2. Процесс загружает стог сена в память и затем разветвляется.

   Каждый процесс использует одну и ту же память из-за семантики копирования при записи.

3. Процесс загружает стог сена в память и порождает несколько потоков поиска

Вопрос в том, что один из методов может быть лучше иПочему? или, скорее, каковы компромиссы.

(ради аргумента предположим, что производительность превосходит сложность реализации).

Реализация двух или трех и измерение возможно, конечно, но тяжелая работа. Существуют ли причины, по которым кто-то может быть лучше?

• Данные в стоге сена неизменны.
• Процессы работают в Linux. Таким образом, процессы не намного дороже, чем потоки.
• Стог сена занимает много ГБ, поэтому кеши ЦП вряд ли помогут.
• Процесс поиска - это, по сути, бинарный поиск (фактически равный_диапазон с касанием). интерполяции).
• Поскольку задачи логически независимы, выигрыш от межпотоковой связи не выгоднее, чем межпроцессное взаимодействие (как, например, https://stackoverflow.com/a/18114475/1569204).

Iне могу придумать каких-либо очевидных компромиссов производительности между потоками и разделяемой памятью. Есть ли какие-нибудь? Может быть, компромиссы в обслуживании кода более актуальны?

---

Фоновое исследование

ЕдинственноеСоответствующий ответ SO, который я смог найти, относится к накладным расходам на синхронизацию потоков - Linux: процессы и потоки в многоядерном процессоре - что верно, но здесь менее применимо.

Связано и интересно, норазличные вопросы:

• Многопоточность: в чем смысл моПотоки, чем ядра?
• Разница в производительности между общей памятью IPC и памятью потоков
• производительность - многопоточные или многопроцессорные приложения

Интересная презентация: https://elinux.org/images/1/1c/Ben-Yossef-GoodBadUgly.pdf

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

Answer 1

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

Затем вы говорите, что операции выполняются исключительно в памяти, поэтому скорость не зависит от (сети или хранилища)Производительность IO. Два узких места, с которыми вы сталкиваетесь, - это пропускная способность процессора и оперативной памяти. Итак, чтобы поработать над правой частью, выясните, что является ограничивающим фактором. Обеспечение эффективности соответствующей части обеспечивает оптимальную производительность для ваших поисков.

Далее вы говорите, что выполняете двоичный поиск. В основном это означает, что вы делаете log(n) сравнений, где каждое сравнение требует загрузки определенного элемента из стога сена. Эта загрузка, вероятно, проходит через все кэши, поскольку размер данных делает попадания в кэш очень маловероятными. Однако вы можете хранить несколько игл для одновременного поиска в кеше. Если затем вам удастся сначала запустить загрузку кэша для игл, а затем выполнить сравнение, вы можете сократить время простоя ЦП или ОЗУ, поскольку они ожидают выполнения новых операций. Это, очевидно, (как и другие) параметр, который необходимо настроить для системы, в которой он работает.

Еще больше, пересмотрите бинарный поиск. Бинарный поиск работает надежно с хорошей верхней границей для случайных данных. Если у вас есть какие-либо закономерности (то есть что-то неслучайное) в ваших данных, попробуйте использовать эти знания. Если вы можете приблизительно оценить местоположение искомой иглы, вы можете уменьшить количество поисков. Это в основном переносит работу с шины ОЗУ на ЦП, так что это опять же зависит от того, что является фактическим узким местом. Обратите внимание, что вы также можете переключать алгоритмы, например переходить от обоснованного предположения к бинарному поиску, когда у вас осталось меньше определенного количества элементов для рассмотрения.

Наконец, вы говорите, что у каждого узла есть полная копияваша база данных. Если каждому из N узлов назначается одна N-я база данных, это может улучшить кэширование. Затем вы сделаете один первый шаг в поиске элемента, чтобы определить узел, а затем отправите поиск ответственному узлу. В случае сомнений каждый узел все еще может обработать поиск как запасной вариант.

Answer 2

Современный подход заключается в использовании потоков и одного процесса.

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

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

Также может быть немного проще добавлять процессы, чем добавлять потоки. Вам придется написать некоторый код, чтобы изменить количество потоков обработки в сети (или использовать фреймворк или сервер приложений).

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

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

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