Слыш, Sincler, ты хотел примера, где у гармонично взаимодействующих процессов есть убедительный чистый выигрышь? Так вот, eao197 преподнес все ценителям данного подхода настоящий подарок. Он наконец дал пример, в котором отрыв у "сообщений" будет точным убедительным — а я, честно говоря, до последнего момента думал, что такое в принципе невозможно. Спасибо, дорогой друг eao197.

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

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

Таблица выполняется в виде функционально-чистого сбалансированного дерева. Когда изменяющий поток ее изменяет, он высылает потокам worker-ам новую ссылку на корень одним сообщением, multicast-рассылкой. Все.

Это будет работать быстрее, чем [мутабельная] "разделяемая память" [требующая явной синхронизации], по причине того, worker-ы при look-up-ах по таблице не будут пользоваться вообще никакими примитивами синхронизации, а функционально-чистое дерево обладает свойством транзакционности. Учитывая то, что look-up выполняется в сотни раз чаще, чем изменения.

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

Не я реально не пойму — ты, что, правда, всерьез думаешь, что ты в состоянии реалистично представить себе оптимальное решение на "актерах", не написав ни одной программы, и путая "гармонично взаимодействующие процессы" с полным отсутствием разделяемой памяти? Честно?

Здравствуйте, eao197, Вы писали:

AVK>>Прокомментируй:
AVK>>

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

E>3. Я воспринимаю эту фразу в том же смысле: "в некоторых случаях обмен сообщениями на любых очередях останется медленее на несколько порядков", но не в 100% случаев.

Анализ ДНК показал, что сперма на синем платье – это сперма Билла Клинтона. 17 августа президент дал показания суду. Его выступление можно считать шедевром юридической казуистики – недаром же Клинтон долго время работал адвокатом и прокурором. Вот, например, знаменитая цитата из его показаний:

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

http://www.lenta.ru/articles/2008/03/14/monicagate/

E>2. Лично я сомневаюсь в оценке "несколько порядков". Имхо, более вероятна разница в один порядок, максимум.

Ну прям чистый Comedy Club, прав Синклер. Тесты не показывают разницы даже на двоичный порядок, при этом, ты позволяешь себе "сомневаться" в том, что разница на два порядка, и тебе, недавно читавшем эти тесты, кажется "более вероятным" разница в один порядок. Еще пиши!

E>1. Я не могу отвечать за remark-a.

Ты уже взялся отвечать за remark-а. Теперь отвечай за себя. Знаешь ведь, как оно бывает .

Здравствуйте, AndrewVK, Вы писали:

E>>1. Я не могу отвечать за remark-a.

AVK>Ну так и не надо вообще за него тогда впрягаться.

Если мои сообщения здесь не желательны -- то какие проблемы, пусть модераторы меня забанят.

В противном случае хочу еще раз сказать, что я впрягся не за remark-а, а из-за статьи, которая, по словам Gaperton-а, доказывает, что OpenMP сливает MPI. Хотя даже разглядывание картинок в этой статье доказывает, что это не так.

Здравствуйте, Gaperton, Вы писали:

G>Таблица выполняется в виде функционально-чистого сбалансированного дерева. Когда изменяющий поток ее изменяет, он высылает потокам worker-ам новую ссылку на корень одним сообщением, multicast-рассылкой. Все.

Ссылку на корень можно подменить даже не рассылая ее worker-ам.
Более того, даже сбалансированное дерево не обязательно делать полностью иммутабельным -- отдельные его фрагменты могут подвергаться изменениям, но при этом не требовать синхронизации доступа.

G>Не я реально не пойму — ты, что, правда, всерьез думаешь, что ты в состоянии реалистично представить себе оптимальное решение на "актерах", не написав ни одной программы, и путая "гармонично взаимодействующие процессы" с полным отсутствием разделяемой памяти? Честно?

Ты правда думаешь, что можешь просить меня не переходить на личности утверждая, что я не написал ни одной программы?

E>Вторая статья:
E>

E>If you want your application to be portable on clusters and SMP machines, MPI might be the
E>best solution. If, however, you do not envision using more than eight or sixteen cores, then
E>OpenMP is probably one of your best choices if the benchmarks point in that direction. From a
E>conceptual standpoint, those with experience in both paradigms state that using OpenMP and
E>MPI provide a similar learning curve and nuance level. There are no shortcuts or free lunches
E>with OpenMP, or MPI for that matter.

E>Так что обе статьи говорят вполне ожидаемые вещи: получение преимуществ с помощью OpenMP вовсе не гарантировано (не очевидно, если тебе так больше нравится), но временами OpenMP будет наилучшим выбором.
E>Что полностью соответствует утверждению remark-а о том, что разделяемая память будет иметь преимущества в некоторых случаях.

Надо отметить, что эти времена уходят, поскольку мы движемся в сторону using more than eight or sixteen cores.

E>Соответственно, если такие случаи есть (а они есть, судя по результатам измерений), то в этих случаях механизм обмена сообщениями лишается преимуществ, которые имеет разделяемая память. О чем опять-таки remark и говорил, как о более честном, с его точки зрения, освящении достоинств обмена сообщениями.

Разделяемая память поддержана аппаратно (да-да! поддержана аппаратно), передача сообщений — нет. Посмотрим, что будет, если будет хотя бы поддержка обоих.

E>То, что это один компилятор ничего не решает. Решает качество OpenMP компилятора. Как тебе указал твой соратник, Сергей Зефиров, качество gcc не сильно выше плинтуса.

Не сильно выше плинтуса в случае неортогональных архитектур вроде DSP или старых микроконтроллеров.

На других архитектурах gcc показывает себя вполне достойно.

Здравствуйте, eao197, Вы писали:
E>Ссылку на корень можно подменить даже не рассылая ее worker-ам.
Это заблуждение.
Точнее, так можно сделать, но только в том случае, если эта ссылка наблюдаема из разных потоков.
Но тогда в них придется вставлять примитивы блокировки для обеспечения изоляции. На первый взгляд кажется, что можно обойтись атомарностью неблокирующего чтения, но это только в том случае, если транзакция маршрутизации требует только однократного прохода по дереву. В противном случае каждому worker придется перед началом каждой транзакции выполнять копирование ссылки на корень, что опять же дорого. Это эквивалентно постоянной рассылке сообщения "корень дерева теперь здесь".
Модель с рассылкой позволяет worker выполнять все чтения дерева без блокировок, при этом транзакционная целостность гарантирована архитектурой.

Здравствуйте, thesz, Вы писали:

T>Разделяемая память поддержана аппаратно (да-да! поддержана аппаратно), передача сообщений — нет. Посмотрим, что будет, если будет хотя бы поддержка обоих.

А есть примеры как поддержка сообщений может быть поддержана аппаратно?

Здравствуйте, Курилка, Вы писали:

К>А есть примеры как поддержка сообщений может быть поддержана аппаратно?
А на транспьютерах. Тамошние каналы как раз служат для передачи сообщений, а вот разделяемой памяти у них, насколько я понимаю, нет вовсе.
Между прочим, сейчас начинается некий ренессанс транспьютеров — видимо, вследствие того, что научились эффективно их использовать

Здравствуйте, Sinclair, Вы писали:

E>>Ссылку на корень можно подменить даже не рассылая ее worker-ам.
S>Это заблуждение.

Конечно

S>Точнее, так можно сделать, но только в том случае, если эта ссылка наблюдаема из разных потоков.

Именно. Разные потоки видят одно и то же дерево.

S>В противном случае каждому worker придется перед началом каждой транзакции выполнять копирование ссылки на корень, что опять же дорого. Это эквивалентно постоянной рассылке сообщения "корень дерева теперь здесь".

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

Здравствуйте, eao197, Вы писали:

E>Именно. Разные потоки видят одно и то же дерево.

S>>В противном случае каждому worker придется перед началом каждой транзакции выполнять копирование ссылки на корень, что опять же дорого. Это эквивалентно постоянной рассылке сообщения "корень дерева теперь здесь".

E>Т.е. ты утверждаешь, что один atomic_read будет эквивалентен мультикастовой рассылке сообщения?
Ну почему один. Мы говорим об N atomic_read по количеству workeroв.
E>С выбором получателей, блокировкой очередей, вставкой в N очередей экземпляра сообщения, разблокированием очередей, блокированием очередей на стороне приемника, сканирования очереди на предмет выбора подходящего сообщения (если используется отличная от FIFO политика обработки сообщений получателем).
E>Правильно я тебя понимаю?
Не совсем.

Здравствуйте, thesz, Вы писали:

T>Надо отметить, что эти времена уходят, поскольку мы движемся в сторону using more than eight or sixteen cores.

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

E>>То, что это один компилятор ничего не решает. Решает качество OpenMP компилятора. Как тебе указал твой соратник, Сергей Зефиров, качество gcc не сильно выше плинтуса.

T>Не сильно выше плинтуса в случае неортогональных архитектур вроде DSP или старых микроконтроллеров.

T>На других архитектурах gcc показывает себя вполне достойно.

Да, здесь я, похоже, погорячился. но для C++ компилятор от Intel-а часто обгоняет GNU на тех же самых программах: http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=icpp&lang2=gpp

А вопрос о качестве именно OpenMP части пока остается открытым.

Здравствуйте, Sinclair, Вы писали:

E>>Т.е. ты утверждаешь, что один atomic_read будет эквивалентен мультикастовой рассылке сообщения?
S>Ну почему один. Мы говорим об N atomic_read по количеству workeroв.

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

E>>С выбором получателей, блокировкой очередей, вставкой в N очередей экземпляра сообщения, разблокированием очередей, блокированием очередей на стороне приемника, сканирования очереди на предмет выбора подходящего сообщения (если используется отличная от FIFO политика обработки сообщений получателем).
E>>Правильно я тебя понимаю?
S>Не совсем.

Мог бы ты свою точку зрения раскрыть?

Здравствуйте, Sinclair, Вы писали:

S>Модель с рассылкой позволяет worker выполнять все чтения дерева без блокировок, при этом транзакционная целостность гарантирована архитектурой.

Я здесь вижу только одну проблему: если у нас есть 2 потока, модифицирующих дерево, и оба они "одновременно" получат сообщение, приводящее к необходимости это дерево модифицировать. Тогда каждый из них построит своё новое дерево, и после этого разошлёт новый корень, но в результате данные, изменённые одним из потоков будут потеряны.

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

Здравствуйте, DK3981, Вы писали:

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

Этот протокол нужен в любом случае.

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

E>Этот протокол нужен в любом случае.

Если модифицирующий поток один, то ему не с кем будет конкурировать.

Здравствуйте, DK3981, Вы писали:

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

E>>Этот протокол нужен в любом случае.

DK>Если модифицирующий поток один, то ему не с кем будет конкурировать.

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

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

Здравствуйте, eao197, Вы писали:
E>Если каждый worker будет получать уведомление о смене таблицы маршрутизации, то это означает, что он периодически будет проверять свою очередь сообщений.
Не то чтобы периодически. Он ее вообще проверяет непрерывно: собственно оттуда он и берет задания для работы.
Просто на 100 заданий, которые требуют чтения таблицы, приходится одно "вот тебе новая таблица".
E>Мог бы ты свою точку зрения раскрыть?
Я уже пояснил: ты сравниваешь один atomic_read с broadcast-ом. А нужно сравнивать 100 atomic_read с 99 local read и 1-м message_receive. Так понятнее?

Здравствуйте, Sinclair, Вы писали:

E>>Если каждый worker будет получать уведомление о смене таблицы маршрутизации, то это означает, что он периодически будет проверять свою очередь сообщений.
S>Не то чтобы периодически. Он ее вообще проверяет непрерывно: собственно оттуда он и берет задания для работы.
S>Просто на 100 заданий, которые требуют чтения таблицы, приходится одно "вот тебе новая таблица".

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

E>>Мог бы ты свою точку зрения раскрыть?
S>Я уже пояснил: ты сравниваешь один atomic_read с broadcast-ом. А нужно сравнивать 100 atomic_read с 99 local read и 1-м message_receive. Так понятнее?

Да, теперь я понял к чему именно относились твои слова "Не совсем."

Здравствуйте, eao197, Вы писали:

E>Это автоматически обязывает worker-а работать с очередями сообщений.
E>Тогда как это может быть совершенно избыточно, если worker обрабатывает большие пакеты данных с множеством сообщений внутри.
Не очень понятно, какие сообщения здесь имеются в виду. Если не те, которые в очереди — то неважно. В любом случае worker получает задание из очереди — ему просто неоткуда его больше получить. Ведь разделяемой памяти нет. Мы говорим о случае, когда модификаций дерева мало по сравнению с чтениями.
Хорошо, worker получил пакет, в котором 100 транзакций, каждая из которых читает дерево. Выполнил — полез в очередь — получил новое дерево — поехал дальше.
Никаких проблем.

Здравствуйте, Sinclair, Вы писали:

E>>Это автоматически обязывает worker-а работать с очередями сообщений.
E>>Тогда как это может быть совершенно избыточно, если worker обрабатывает большие пакеты данных с множеством сообщений внутри.
S>Не очень понятно, какие сообщения здесь имеются в виду.

Речь о заданиях (транзакциях). Например, worker может стартовать с пакетом из 100K sms, для каждой из которых нужно выбрать маршрут.

S>Хорошо, worker получил пакет, в котором 100 транзакций, каждая из которых читает дерево. Выполнил — полез в очередь — получил новое дерево — поехал дальше.
S>Никаких проблем.

Ну да, никаких. Чтение очереди ведь явно более дешевая операция, чем atomic_read.