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

R>>Вот реализация "семафора" (или мьютекса), которая для доступа "на чтение" требует только 2 обычных сохранения в память, несколько загрузок из памяти и одно предсказываемое ветвление. При этом алгоритм распределенный, т.е. при доступе "на чтение" потоки работают с локальной памятью. За счёт этого такой мьютекс оказывается быстрее очереди с одним CAS в 300(!) раз уже на четырёх-ядерном процессоре Q6600 на тесте с высокой нагрузкой:
R>>http://groups.google.com/group/lock-free/browse_frm/thread/1efdc652571c6137

G>Ну вот, в аккурат после пропущенного Comedy Club ты опять поднимаешь мне настроение. Ну неужели такой крупный специалист по параллелизму как ты не заметил, что у тебя внутри каждого чтения стоит МЕМОРИ БАРЬЕР (20-90 накладных тактов в зависимости от ситуации на x86 сам по себе, плюс эффект от отключения переупорядочивания). На код свой посмотри!

G>Объясни мне, каким именно образом такой барьер будет быстрее чем CAS в 300 раз (откуда ты вообще эту цифру взял, интересно), при том, что CAS занимает на x86 те же 30-90 тактов? Ась?

Ну что?
"Абыдно, Да?" (с) Gaperton
"Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton

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

G>2) По причине переупорядочивания записи в память в архитектуре Power для корректного поведения твоего atomic read в данной программе тебе надо будет воспользоваться инструкцией lwsync, то есть барьер выставить, что занимает в районе 30-50 тактов. Это на многоядерном кристалле с общим кэшом L2, таком, какой стоит в XBox360. Это во-вторых.

G>И здесь ты неправ. В x86 у тебя сохранение порядка гарантируется только для одного адреса.
G>

G>Intel 64 memory ordering allows load instructions to be reordered with prior stores to a
G>different location.

G>Будет прикольно, если ты считаешь адрес нового корня, а записи для самого нового корня еще не дошли . Крэшдамп получишь красивый вместо результата. Абыдно, да? На, почитай первоисточник.

"Абыдно, Да?" (с) Gaperton
"Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton
"Ась?" (с) Gaperton

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

G>>2) По причине переупорядочивания записи в память в архитектуре Power для корректного поведения твоего atomic read в данной программе тебе надо будет воспользоваться инструкцией lwsync, то есть барьер выставить, что занимает в районе 30-50 тактов. Это на многоядерном кристалле с общим кэшом L2, таком, какой стоит в XBox360. Это во-вторых.

R>Ну и чем ты можешь это аргументировать?

Ниже пример почитай.

R>>>И точно так же, atomic_read с упорядочиванием consume является обычной инструкцией загрузки на архитектурах x86, IA-64, SPARC RMO/PSO/TSO, ARM, и на всех остальных современных архитектурах.

G>>Что, до такой степени "обычная", что в определении этой переменной, которую вы собрались читать обычными read даже не надо писать volatile, и компилятор ее спокойно применяет к ней регистровую оптимизацию, как в моем случае? .

R>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

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

G>>И здесь ты неправ. В x86 у тебя сохранение порядка гарантируется только для одного адреса.
G>>

G>>Intel 64 memory ordering allows load instructions to be reordered with prior stores to a
G>>different location.

G>>Будет прикольно, если ты считаешь адрес нового корня, а записи для самого нового корня еще не дошли . Крэшдамп получишь красивый вместо результата. Абыдно, да? На, почитай первоисточник.

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

Язык попридержи. Достал. Я дал тебе человеческое объяснение, и ссылку на документ. Мозгов не хватает понять, что я имею в виду, или как? У меня нет никакого желания тебе что-то втолковывать помимо твоей воли — считай как хочешь. Можешь мнить мебя мегаэкспертом в параллелизме — я не против.

R>Нет, не Абыдно. Где ты в паттерне публикации увидел store-load последовательность, которую надо упорядочивать? Поток потребителя её исполняет? Ну и что же он сохраняет и куда?

Я рассматриваю решение задачи в целом, а не бессвязные отдельные фрагменты, которые ты хочешь мне навязать, лишив разговор смысла. В целом же ты вроде как собираешься передавать потребителю новый указатель на корень новой структуры, при том, что ты только что модифицировал этот корень в источнике. В данном случае, чтобы переупорядочивание записи в память не испортило тебе все, ты должен выставить memory barrier, поскольку сам разделяемый указатель, и то, на что он указывает, должно меняться скоординировано, а таких гарантий тебе ни интеловская, ни (тем более) power-овская memory model сами по себе не дают.

Поэтому, "по причине переупорядочивания записи в память в архитектуре Power для корректного поведения твоего atomic read в данной программе тебе надо будет воспользоваться инструкцией lwsync". Потому, что именно lwsync наиболее дешевым образом в POWER дает тебе локальный TSO, на который ты так рассчитываешь, говоря про atomic_read в данной задаче.

Я достаточно доступно объясняю тебе про архитектуру POWER? Или ты опять дурачка включишь? Ты странно себя ведешь, вроде слова правильные знаешь, однако как до дела доходит, то включаешь феерического дурака. Либо ты это бросаешь, либо я прекращаю с тобой говорить. Надоело.

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

R> _ReadWriteBarrier() — это барьер КОМПИЛЯТОРА. Подавляет переупорядочивания компилятором. Всё. 0 тактов оверхеда в ран-тайм.

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

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

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

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

Пытаешься спасти свою репутацию? Угу, искушенные люди конечно сразу тебе поверили про ускорение в 300 раз . Которого в данной задаче, естественно, не будет, особенно если построить очередь на технике, подобной твоему mutex. Ты вообще плохо отдаешь себе отчет, с чем споришь.

R> "Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton

Как тебе однако хочется, чтобы я обкакался. Вот это называется обкакался.

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

А то, что я не знаю, какой там нахрен барьер _ReadWriteBarrier(), что послужило поводом твоей бурной радости — так всего знать невозможно (ты, к примеру, не знаешь про lwsync), да и в контексте общего спора, в котором глупые тезисы выдвигаешь ты, а не я, это совершенно не принципиально. Касательно того, что atomic_read, на котором eao собирался решать эту задачу, медленнее обычного — это правда и остается правдой, в данном случае нужен честный барьер в получателе чтобы все работало.

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

G>Во-вторых, пока ты меняешь структуру, все читатели стоят на блокировке.

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

G>Касательно того, что atomic_read, на котором eao

eao197, eao -- это такое же некорректное сокращение, как и Gaper.

G>собирался решать эту задачу, медленнее обычного — это правда и остается правдой, в данном случае нужен честный барьер в получателе чтобы все работало.

Зачем барьер в получателе?

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


R>>>>И точно так же, atomic_read с упорядочиванием consume является обычной инструкцией загрузки на архитектурах x86, IA-64, SPARC RMO/PSO/TSO, ARM, и на всех остальных современных архитектурах.

G>>>Что, до такой степени "обычная", что в определении этой переменной, которую вы собрались читать обычными read даже не надо писать volatile, и компилятор ее спокойно применяет к ней регистровую оптимизацию, как в моем случае? .

R>>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

G>В сторону уводишь ты, ты вообще по хожу не держишь контекста дискуссии. Не буду считать, что это "вообще на асме", поскольку сравнивается очередь и разделяемая мутабельная память в контексте задачи. И работа компилятора здесь важна.


Ну, ладно, как хочешь — в исходном коде на С там стоит volatile. Ну и в чём тут твоя мысль? Что ты хочешь этим сказать? Кроме того, что создаёшь у неискушённых читателей впечатление, что ты типа тоже что-то умное отвечаешь с какими-то терминами?



G>>>И здесь ты неправ. В x86 у тебя сохранение порядка гарантируется только для одного адреса.
G>>>

G>>>Intel 64 memory ordering allows load instructions to be reordered with prior stores to a
G>>>different location.

G>>>Будет прикольно, если ты считаешь адрес нового корня, а записи для самого нового корня еще не дошли . Крэшдамп получишь красивый вместо результата. Абыдно, да? На, почитай первоисточник.

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

G>Язык попридержи. Достал. Я дал тебе человеческое объяснение, и ссылку на документ. Мозгов не хватает понять, что я имею в виду, или как? У меня нет никакого желания тебе что-то втолковывать помимо твоей воли — считай как хочешь. Можешь мнить мебя мегаэкспертом в параллелизме — я не против.


Ну докажи, что это не ахинея. В ссылке надо документ ничего нет про то, где в паттерне публикации store-load последовательность на стороне читателя.


R>>Нет, не Абыдно. Где ты в паттерне публикации увидел store-load последовательность, которую надо упорядочивать? Поток потребителя её исполняет? Ну и что же он сохраняет и куда?

G>Я рассматриваю решение задачи в целом, а не бессвязные отдельные фрагменты, которые ты хочешь мне навязать, лишив разговор смысла. В целом же ты вроде как собираешься передавать потребителю новый указатель на корень новой структуры, при том, что ты только что модифицировал этот корень в источнике. В данном случае, чтобы переупорядочивание записи в память не испортило тебе все, ты должен выставить memory barrier, поскольку сам разделяемый указатель, и то, на что он указывает, должно меняться скоординировано, а таких гарантий тебе ни интеловская, ни (тем более) power-овская memory model сами по себе не дают.


Аааа! Я понял твою линию — теперь ты хочешь незаметно перейти со стороны потребителя на сторону производителя. Да, где производитель делает сохранение в объект и потом сохранения указателя на объект действительно будет барьер памяти (кстати, не на x86 — тут ты вообще в пролёте). С этим никто не спорит, поэтому переходим дальше.
Покажи на стороне потребителя (который делает только чтения, при этом data-dependent чтения) имеется store-load последовательность.



G>Поэтому, "по причине переупорядочивания записи в память в архитектуре Power для корректного поведения твоего atomic read в данной программе тебе надо будет воспользоваться инструкцией lwsync". Потому, что именно lwsync наиболее дешевым образом в POWER дает тебе локальный TSO, на который ты так рассчитываешь, говоря про atomic_read в данной задаче.

Где записи-то на стороне потребителя?

"Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton


G>Я достаточно доступно объясняю тебе про архитектуру POWER? Или ты опять дурачка включишь? Ты странно себя ведешь, вроде слова правильные знаешь, однако как до дела доходит, то включаешь феерического дурака. Либо ты это бросаешь, либо я прекращаю с тобой говорить. Надоело.


Ну хорошо, повторил свои слова ещё раз. Ничего плохого в этом нет, но это и совершенно не обязательно. Давай же перейдём дальше. Конкретный вопрос: на стороне потребителя не достаточно load-consume (data-dependent load)? или load-consume на POWER содержит барьер памяти?
Не надо опять уводить в какую-то прострацию, называть какие-то общие слова типа TSO.

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

R>"Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton

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

G>>Что, до такой степени "обычная", что в определении этой переменной, которую вы собрались читать обычными read даже не надо писать volatile, и компилятор ее спокойно применяет к ней регистровую оптимизацию, как в моем случае? .
R>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

Если нужен volatile, то на чём ни пиши, всё равно в регистры не уложишь.

Поэтому реплику про ассемблер считаю неорганизованной и отметаю.

Про передачу сообщений.

Её можно сделать сколь угодно мало требовательной путём группировки сообщений.

Типа, пишется в одну очередь, читается из другой. По переполнению/опустошению очереди сливаются, перед этим создаётся новый объект для изменяемой очереди.

Чтение из текущей рабочей очереди не имеет проблем с разделением ресурсов. Запись в текущую рабочую тоже таких проблем не имеет большую часть времени.

Это программная реализация. Про аппаратную вообще молчу.

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

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

G>>Во-вторых, пока ты меняешь структуру, все читатели стоят на блокировке.

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


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


G>>Касательно того, что atomic_read, на котором eao

E>eao197, eao -- это такое же некорректное сокращение, как и Gaper.

Ещё одна из его фишек, типа называть собесебника на "Вы", но при этом "вы" писать с маленькой буквы, или вставлять в середину абзаца вспомогательное предложение что типа собеседник не написал ни одной программы, или что собеседнику никогда не додуматься до таких первоклассных решений как Gaperton'у. А потом ещё как ни в чём не бывало говорить, что он типа выше таких низких вещей, и что его интересует только техническая дискуссия.
Я ещё могу понять, когда человек высказывает такое прямо и открыто. Но когда вот так, изподтяжка...



G>>собирался решать эту задачу, медленнее обычного — это правда и остается правдой, в данном случае нужен честный барьер в получателе чтобы все работало.

E>Зачем барьер в получателе?

Вот видишь, Gaperton, люди-то тут следят за ходом дискуссии. И твои левые попытки оправдать свою техническую неграмотность приплетанием левых фактов типа, что получателю надо упорядочивать какие-то store, или пуще того какие-то store-load последовательности — не остаются не замеченными. Тебя уже все раскусили.

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

R>Ещё одна из его фишек, типа называть собесебника на "Вы", но при этом "вы" писать с маленькой буквы...

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

R>Я ещё могу понять, когда человек высказывает такое прямо и открыто. Но когда вот так, изподтяжка...

Вполне нормальный полемический прием. И не он один здесь (в этой теме) этот прием применяет, и не всегда удачно

Предлагаю прислушаться к просьбе AVM и прекратить личные оскорбления, а то вся тема в СВ уедет.

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

G>>>Что, до такой степени "обычная", что в определении этой переменной, которую вы собрались читать обычными read даже не надо писать volatile, и компилятор ее спокойно применяет к ней регистровую оптимизацию, как в моем случае? .
R>>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

T>Если нужен volatile, то на чём ни пиши, всё равно в регистры не уложишь.
T>Поэтому реплику про ассемблер считаю неорганизованной и отметаю.


Стоп-стоп-стоп. Что Вы имеете в виду с Gaperton'ом? В чём тезис и при чём тут всплыл volatile и регистровые оптимизации? Вы хотите сказать, что это вносит какие-то серьёзные издержки в работу алгоритма? Т.е. я правильно понимаю, что Вы хотите, что бы примитив синхронизации работал только с регистрами? Или что?

Я имею в виду, что суть в том, что там, на машинном уровне, стоит обычная инструкция загрузки. Как она там появилась — абсолютно не важно в данном контектсе — хоть volatile в С, хоть напрямую на асме её написали (на асме написали инструкцию загрузки! а НЕ заставили примитив синхронизации работать только с регистрами!).
Для любого примитива синхрониазации абсолютно важно подавить оптимизации/переупорядочивания компилятора. Очередь это тоже делает. К счастью, это НЕ вносит НИКАКОГО существенного оверхеда в ран-тайм.



T>Про передачу сообщений.

T>Её можно сделать сколь угодно мало требовательной путём группировки сообщений.

T>Типа, пишется в одну очередь, читается из другой. По переполнению/опустошению очереди сливаются, перед этим создаётся новый объект для изменяемой очереди.

T>Чтение из текущей рабочей очереди не имеет проблем с разделением ресурсов. Запись в текущую рабочую тоже таких проблем не имеет большую часть времени.


Теоретически — да. На практике это не работает.
Группировка будет работать только в вырожденном случае, когда агнет посылает сообщения только одному другому агенту, и всё это, понятно, в одном потоке. Когда произвольное множество агентов посылает сообщения произвольному множеству агентов + это происходит во множестве потоков + надо гарантировать ФИФО (это тут очень важно — это рушит всю идею группирования) — ничего не получится, придётся честно каждое сообщение посылать. Если не согласен — обрисуй схему, которая будет работать для множества отправителей, множества получаетелей, множества потоков.
Получается кэшировать только в очень частных случаях, например если агент посылает несколько сообщений другому агенту и не посылает между этим сообщений другим агентам. Но это не особо интересно для практики — допустим агнет начинает чередовать рассылку — отсылает то одному, то другому — всё, финита ля комедиа, оптимизация порушилась, система легла.
Плюс кэш сообщений уже надо хранить не один на рабочий поток, а один на каждого агента (которых могут быть сотни тысяч), а потом как-то эти кэши опрашивать, мы ж не можем кэшировать вечно. Плюс необходима поддержка языка, типа как для GC — должны иметь возможность гарантированно периодически дергать функцию сброса кэша из рабочего потока (или мы будет дергать сброс кэша из другого потока, и защищать каждое обращение к этой очереди мьютексом?).
Вобщем, на практике это сыпется как карточный домик, вопросов больше, чем ответов.


Про очередь вообще не понял, чего мы с такой схемой добились. У нас была multi-producer/single-consumer очередь. Потребитель тут и так работает без конфликтов, т.к. он один — взять хотя бы ту же two-lock queue. Производители гарантированно сталкиваются, и то, что разбили на 2 очереди ни как не повлияет на сталкновения — всё производители всё равно будут работать с одной очередью.

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

AVM>Коллеги, давайте перестанем друг друга подкалывать и не будем выяснять кто первый начал, просто перестанем.
AVM>Понимаю, что некоторый высказывания коллег провоцируют, но давай просто будем немного взрослее.
AVM>А то взрослые мужики, обсуждаете интересную тему, но ведете себя как малые дети в песочнице.

А еще лучше, если кто нибудь возьмет обсуждаемую задачу и напишет совсем совсем простой тест с очередью и разделяемой памяти и просто померяет.

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

R>>>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

G>>В сторону уводишь ты, ты вообще по хожу не держишь контекста дискуссии. Не буду считать, что это "вообще на асме", поскольку сравнивается очередь и разделяемая мутабельная память в контексте задачи. И работа компилятора здесь важна.

R>Ну, ладно, как хочешь — в исходном коде на С там стоит volatile. Ну и в чём тут твоя мысль? Что ты хочешь этим сказать? Кроме того, что создаёшь у неискушённых читателей впечатление, что ты типа тоже что-то умное отвечаешь с какими-то терминами?

Во-первых, прекрати называть тех людей, кто со мной согласен — идиотами. Во-вторых, к примеру, на Itanium volatile не просто отключает регистровые оптимизации, но и добавляет барьер. Поэтому доступ к volatile-переменной на Itanium очень дорогой. Почитай здесь

http://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-for-multi-threaded-programming/

Кстати, твой мегабыстрый мутекс, который ты привел тут рядом, будет тормозить на Itanium (там обращения к volatile компилятся с барьерами), и не будет работать на Power (там требуется явный барьер).

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

G>>>>И здесь ты неправ. В x86 у тебя сохранение порядка гарантируется только для одного адреса.
G>>>>

G>>>>Intel 64 memory ordering allows load instructions to be reordered with prior stores to a
G>>>>different location.

G>>>>Будет прикольно, если ты считаешь адрес нового корня, а записи для самого нового корня еще не дошли . Крэшдамп получишь красивый вместо результата. Абыдно, да? На, почитай первоисточник.

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

G>>Язык попридержи. Достал. Я дал тебе человеческое объяснение, и ссылку на документ. Мозгов не хватает понять, что я имею в виду, или как? У меня нет никакого желания тебе что-то втолковывать помимо твоей воли — считай как хочешь. Можешь мнить мебя мегаэкспертом в параллелизме — я не против.

R>Ну докажи, что это не ахинея. В ссылке надо документ ничего нет про то, где в паттерне публикации store-load последовательность на стороне читателя.

Я тебе уже дал объяснение. Его достаточно. Мозгов не хватает понять, зачем здесь нужен lwsync, зато хватает ума кривляться — извини.

R>"Обкакался, так будь мужиком, блин, и имей смелость это признать" (с) Gaperton

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

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

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

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

AVM>>Коллеги, давайте перестанем друг друга подкалывать и не будем выяснять кто первый начал, просто перестанем.
AVM>>Понимаю, что некоторый высказывания коллег провоцируют, но давай просто будем немного взрослее.
AVM>>А то взрослые мужики, обсуждаете интересную тему, но ведете себя как малые дети в песочнице.

AVK>А еще лучше, если кто нибудь возьмет обсуждаемую задачу и напишет совсем совсем простой тест с очередью и разделяемой памяти и просто померяет.

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

Затем они попробуют закрыть ее своим "быстрым" непортабельным мутексом, который адекватно работает только на IA32/64. Это решение засчитано не будет, разумеется. Ну хорошо, даже на обычной критической секции (в районе 200-300 сотен тактов накладных) уже не так очевидно, что будет быстрее — в бинарном дереве будет до 10 обращений к памяти все-таки (предполагая там 100 записей). Ладно, пусть даже у низ этот волшебный бесплатный хакерский mutex есть, неважно. Вот так бы они поступили, если бы немного отвлеклись от желания доказать, что Гапертон дурак, и подумали наконец о задаче.

Это бы они сделали в надежде, что чисто функциональных хэш-таблиц вроде как не бывает. В ответ я бы применил простой массив в качестве индекса, и стал бы его тупо копировать при изменениях, полагаясь на то, что размер у него всего порядка 4х килобайт, и операция это крайне редка. И получил бы кроссплатформенное решение, которое работает без блокировок, более того — воркеры не ждут, пока я патчу массив, и спокойно продолжают работать.

В результате, версии с хакерским мутексом и эта работали бы на IA32/64 примерно одинаково, с разницей в доли процента. На Power (то есть, на XBox360) версия на сообщениях была бы несколько быстрее, думаю, не более чем на десятки процентов (реальная разница зависит от того, сколько тратится на обработку сообщения, и, я думаю, будет незначительна).

Потом, они попробовали бы раздуть размер лукап-таблицы, и участив его модификации (последнее увеличит им оверхэд, на самом деле), выйдя за рамки исходной задачи, чтобы я просел на копировании данных. Нормальное желание, человеческое. Это и есть слабое место. На это бы я изобразил чисто-функциональный транзакционный массив в стиле B-Tree без ключей. Это надо, чтобы не перезаписывать при изменении весь индекс целиком — что на больших таблицах вышло бы боком. И опять обошелся кроссплатформенным решением без блокировок, наиграв всего одно-два лишних обращений в память, которое на Power и Itanium будет несколько быстрее, и примерно одинаково на Core 2 Dou.

После чего, я бы предложил посмотреть, как масштабируется производительность в финальной задаче от количества аппаратных потоков и кристаллов в SMP, и, по всей видимости, довольно убедительно уложил бы их на Нехалеме и Ниагаре. За счет того, что у меня никто никого не блокирует, и все взаимодействие асинхронно.

Примерно так бы все и было. С незначительными нюансами туда-сюда. Тока мне лень этим заниматься. Зачем? Мне и так все понятно, а у парней, я подозреваю, истерика в середине случится. Ну и кроме того, они ведь не додумались до хэш-таблицы. Да и задача слишком хороша для сообщений — могли бы и похуже что-нибудь придумать. Вроде поиска выхода из лабиринта, например . Правда, и в этой задаче их ждал бы небольшой сюрприз — сообщения как всегда наносят ответный удар с неожиданной стороны .

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

G>После чего, я бы предложил посмотреть, как масштабируется производительность в финальной задаче от количества аппаратных потоков и кристаллов в SMP, и, по всей видимости, довольно убедительно уложил бы их на Нехалеме и Ниагаре. За счет того, что у меня никто никого не блокирует, и все взаимодействие асинхронно.

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

Вот это решение уже побить иммутабельными структурами будет достаточно тяжело, и оно, в принципе, кроссплатформенно.

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

Мультикастная очередь не обязана иметь один слот, кстати. Если построить ее на однонаправленном списке, то это может быть вполне честная очередь. Позволяющая множеству читателей спокойно из нее читать, не пользуясь блокировками, потому что она также транзакционна. Делается она так.

В очереди всегда лежит, пнимаете-ли, как минимум один элемент, даже в пустой. Этот элемент — по сути своей фьючер. Однако, когда песатель кладет в очередь новый элемент, он будет указывать на фьючер. Короче, эта фигня ведет себя точь в точь как ленивый список. Без сборки мусора будет тяжело, это дизайн для Java/.NET.

Вот. Теперь, очередной парадокс. Иммутабельная структура данных, состоящая из таких очередей, также функционально чиста и транзакционна, однако. И позволяет делать довольно необычные вещи, несколько уже выходящие за рамки обычных представлений о дизайне на асинхронных сообщениях. Причина крышесрывания состоит в том, что очередь сообщений здесь рассматривается как first class object, которая сама может быть составным элементом структур данных. Занятно, не так ли? Кстати, это вроде как уже не совсем actors model. Это довольно интересное обобщение.

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

G>Вот. Теперь, очередной парадокс. Иммутабельная структура данных, состоящая из таких очередей, также функционально чиста и транзакционна, однако. И позволяет делать довольно необычные вещи, несколько уже выходящие за рамки обычных представлений о дизайне на асинхронных сообщениях. Причина крышесрывания состоит в том, что очередь сообщений здесь рассматривается как first class object, которая сама может быть составным элементом структур данных. Занятно, не так ли? Кстати, это вроде как уже не совсем actors model. Это довольно интересное обобщение.

Хм. Интересно, это новая парадигма, или это уже кто-то придумал? Надо бы статью написать, штоли, в любом случае. Чрезвычайно интересно.

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

AVK>А еще лучше, если кто нибудь возьмет обсуждаемую задачу и напишет совсем совсем простой тест с очередью и разделяемой памяти и просто померяет.

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

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

G>Примерно так бы все и было. С незначительными нюансами туда-сюда.

Феерический рассказ о том, как Gaperton поспорил сам с собой и блестяще выиграл спор у самого себя.

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

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

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

G> Кстати, это вроде как уже не совсем actors model. Это довольно интересное обобщение.

Ну, remark в соседнем топике утверждал, что фьючерсы сотоварищи совсем уже не actors model, это совершенно отдельный task parallelism. Но это все спор о терминах.