Re[10]: Lock-based & STM - Философия программирования

Здравствуйте, Константин Л., Вы писали:

R>>lock-free алгоритмы — это не о производительности и масштабируемости, это исключительно о гарантиях системного прогресса. lock-free алгоритмы зачастую бывают медленнее lock-based алгоритмов. Это как best-effort против QoS, или не real-time против real-time. QoS и real-time всегда медленнее, зато дают дополнительные гарантии.

КЛ>почему медленнее и о каких гарантиях идет речь

Вначале формальные определения:

wait-free

Каждый поток продвигается вперед не зависимо от внешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, т.к. с ним обычно связан цикл вида "выполнять atomic_compare_exchange, пока он не будет выполнен успешно".
Пример wait-free алгоритма:

void increment_reference_counter(rc_base* obj)
{
  atomic_increment(obj->rc);
}

void decrement_reference_counter(rc_base* obj)
{
  if (0 == atomic_decrement(obj->rc))
    delete obj;
}

Как видно, любой поток может выполнить эти функции за конечное число шагов, не зависимо ни от чего.

lock-free

Система в целом продвигается вперед. При этом каждый отдельный поток может не совершать продвижения вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).
Пример lock-free алгоритма:

void stack_push(stack* s, node* n)
{
  node* head;
  do
  {
    head = s->head;
    n->next = head;
  }
  while (!atomic_compare_exchange(s->head, head, n));
}

Как видно, любой поток может "крутиться" в этом цикле теоретически бесконечно. НО любой повтор этого цикла означает, что какой-то другой поток *успешно* выполнил свою операцию. И никакой заблокированный/прерванный поток *не* может препятствовать продвижению других потоков. Отсюда следует, что система в целом продвигается вперед не зависимо ни от чего.

obstruction-free

Поток продвигается вперед, только если не встречает конкуренции со стороны других потоков. В частности это означает, что при сильной конкуренции возможно *никакой* поток не будет совершать продвижения. Т.е. система будет находиться в т.н. live-lock. Это самая слабая гарантия. Этот класс алгоритмов может показаться немного странным, поэтому тут стоит заметить, что (1) заблокированные/прерванные потоки не могут препятствовать прогрессу других потоков, и (2) obstruction-free алгоритмы могут быть более быстрые, чем lock-free.
Простого примера тут не привести, поэтому отсылаю интересующихся к оригиналу:
Obstruction-Free Synchronization: Double-Ended Queues as an Example

lock-based

Ну и собственно все эти алгоритмы противопоставляются lock-based алгоритмам:
Система в целом может *не* продвигаться вперед. Например, поток прерван внутри критической секции, этот поток может заблокировать общесистемный прогресс, т.е. никакой выполняющийся поток не может выполнить никаких полезных действий. Или например, при использовании lock-based алгоритмов возможен т.н. dead-lock, очевидно, что при возникновении dead-lock система не совершает прогресса.

Производительность/масштабируемость

Самое интересное — до этого момента я не сказал ни слова ни о производительности, ни о масштабируемости. Всё правильно — все эти слова ни об этом. Они о гарантиях, которые я описал выше. Так как же lock-free (wait-free, obstruction-free) соотносится с производительностью? Это зависит от конкретного алгоритма — они могут быть как быстрее/лучше масштабироваться, так и медленнее/хуже масштабироваться.
Функции increment_reference_counter()/decrement_reference_counter() скорее всего будут быстрее аналогичного lock-based алгоритма, т.к. хотя бы одну тяжелую атомарную операцию вход/выход из критической секции содержать тоже будет, но там ещё будет собственно полезная работа + возможность заблокироваться/спин-ожидание.
Зато большинство lock-free алгоритмов для сложных структур данных (двусвязные списки) будут медленнее аналогичных lock-based алгоритмов, т.к. будут содержать больше тяжелых атомарных операций (2-5). Но хотя тут сложный вопрос, т.к. lock-based алгоритм будет вызывать много блокирования под нагрузкой, но с другой стороны мьютексы можно партицировать — т.е. имеем не один "большой" мьютекс, а много "маленьких", но с другой стороны, если у нас много "маленьких" мьютексов, то и операций захвата/освобождения будет больше. Т.е. тут каждый случай надо рассматривать в отдельности.
И тут я имею в виду только операции модификации, т.к. существует такая замечательная вещь как lock-free reader pattern, которая, кстати, может сочетаться и с lock-based writer частью. Но это уже отдельная история.

atomic-free

Т.о. lock-free это не о производительности. Есть класс алгоритмов синхронизации, которые именно о производительности. Они разрабатываются именно с мыслью не обеспечения каких-то гарантий, а с мыслью обеспечения максимальной производительности и линейной масштабируемости на многопроцессорных/многоядерных системах. Как следствие такие алгоритмы вполне могут содержать и lock-based части. К сожалению общепринятого слова для них, насколько я знаю, нет. Поэтому их часто и называют lock-free, в смысле "не lock-based". Я обычно называю такие алгоритмы atomic-free, с целью подчеркнуть факт минимизации тяжелых операций. Насколько я помню, термин почерпнут в какой-то работе David Dice.
Почему я всегда вместе со словом "производительность" употребляю слово "масштабируемость". Масштабируемость — это очень важный аспект алгоритмов синхронизации в контексте многопроцессорных/многоядерных систем, но он полностью отсутствует на однопроцессорных машинах. Зачастую у примитивов синхронизации следующий паттерн поведения. На однопроцессорной машине он выполняется Х времени, на двухпроцессорной — 2*Х времени, на четырех-процессорной — 10*Х времени и т.д. Поэтому в контексте многопроцессорности очень важно, что бы алгоритм не деградировал таким образом.

Для факультативного чтения могу предложить:
Practical lock-freedom
или более свежий:
Concurrent Programming Without Locks
Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

Обещаю что последний раз пристаю

Больше не буду, честно.

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

SH>Ну.. может переводами займёшься?

Да и вообще, материала на развёрнутую обзорную статью может хватить.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Константин Л., Вы писали:

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

КЛ>[]

КЛ>>>боюсь просить, почему медленнее и о каких гарантиях идет речь

R>>http://www.rsdn.ru/Forum/message/2930849.1.aspx

КЛ>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.

А откуда это очевидно?
Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?

R>>

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

R>Здравствуйте, Константин Л., Вы писали:

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

КЛ>>[]

КЛ>>>>боюсь просить, почему медленнее и о каких гарантиях идет речь

R>>>http://www.rsdn.ru/Forum/message/2930849.1.aspx

КЛ>>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.

R>А откуда это очевидно?
R>Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?

ты заставил меня задуматься...

интуитивно очевидно, но ты здесь, чтобы интуицию заменить фактами, так что давай!

пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?

R>>>

Здравствуйте, Константин Л., Вы писали:

КЛ>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

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

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

Версия для многопроцессорных/многоядерных машин, может вести себя еще немного сложнее — если первоначально cas-ом не удалось захватить блокировку, делается еще несколько попыток в цикле в user mode, ожидая что поток с другого ядра отпустит блокировку, и только потом поток блокируется в ядре

Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

КЛ>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?

Еще лочить желательно так, чтобы отношение времени когда поток НЕ держит блокировку, ко времени когда он ее дердит было большим. Ну это в общем то очевидно, просто у нас был интересный случай

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

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

Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить

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

RRM>Мьютексы могут быть реализованы с привлечением cas. Идея заключается в том, чтобы использовать cas для попытки захвата блокировки и только если захват не удался (мьютекс уже захвачен) переходить в ядро для блокировки потока.

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

RRM>Версия для многопроцессорных/многоядерных машин, может вести себя еще немного сложнее — если первоначально cas-ом не удалось захватить блокировку, делается еще несколько попыток в цикле в user mode, ожидая что поток с другого ядра отпустит блокировку, и только потом поток блокируется в ядре

RRM>Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

Именно так реализовано ожидание критических секций в Windows. Так что достаточно распространено

Здравствуйте, Константин Л., Вы писали:

КЛ>>>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.

R>>А откуда это очевидно?
R>>Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?

КЛ>ты заставил меня задуматься...

КЛ>интуитивно очевидно, но ты здесь, чтобы интуицию заменить фактами, так что давай!

В пределе, что я получал по переключению контекста — это 700 тактов. На Windows XP. 2 потока в цикле вызывали SwitchToThread() и передавали друг другу управление.

Захват reader-writer мьютекса в случае только с читателями, т.е. блокировок нет, у меня получается 500 тактов. И это же можно считать стоимостью lock-free алгоритма с двумя атомарными модификациями.

Цифры, в принципе, сравнимые.
Но в жизни, конечно, всё сложнее. Т.к. переключение контекста будет наверное дороже в общем случае. А блокировка в ядре происходит не всегда, а только иногда. А в lock-free алгоритмах, основанных на CAS могут "повторы", т.е. они под сильной нагрузкой могут деградировать ещё и за счёт этого. И т.д. и т.п.

К тому же мьютекс можно реализовать только с одним CAS — на входе, а на выходе обычное сохранение в память. И делать не блокирование на семафоре, а пассивное спин ожидание с помощью SwitchToThread(). Пока не начинаются очень частые вызовы SwitchToThread(), такой мьютекс получается достаточно быстрым.

В общем случае нельзя сказать, что быстрее. Для мьютекса цена всегда одинаковая, и не зависит от того, что мы им защищаем. А в lock-free алгоритме цена очень сильно зависит от того, что конкретно мы делаем.
Ну наверное можно сделать только такой вывод — если lock-free алгоритм использует только один CAS, то он будет не хуже, чем lock-based решение. Я по крайней мере не вижу, за счёт чего он может быть медленнее, т.к. мьютекс — это тот же lock-free алгоритм, с как минимум одним CAS.

КЛ>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

На месте, по крайней мере, я стоять не люблю

Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь

Тут либо ты меня не так понял, либо я не так сказал. Я не призываю использовать lock-based алгоритмы, я хочу сказать, что и тот и другой подход по сути своей очень схожи и дороги. Схожесть у них в том, что они оба основаны на постоянной модификации одних и тех же разделяемых переменных. И это у них основной источних их стоимости и немасштабируемости.

КЛ>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?

Если у тебя операция под мьютексом короткая, например, добавление элемента в очередь (фактически пара манипуляций с указателями), то получается, что у тебя полезной работы 1 такт, и 500 тактов пенальти за синхронизацию. Т.е. 0.2% полезной работы и 99.8% оверхед. Это, конечно, через чур утрированно, но суть такая. И reader-writer мьютексы никак не спасают, они делают только хуже.

Смотри презентацию "Abstraction, Reality Checks, and RCU":
http://www.rdrop.com/users/paulmck/RCU/RCUintro.2005.07.26bt.pdf

Она очень хорошо вводит в курс дела по вопросам производительности, масштабиремости, мьютексов, lock-free алгоритмов и т.д.

В частности страницы 5-6: эффективность мьютекса.
Страница 7: стоимости примитивных операций.
Страница 18: почему reader-writer мьютексы на самом деле не дают выполняться читателям параллельно, и только ухудшают ситуацию.
Страница 38: производительность/масштабируемость мьютексов и того, что я назвал atomic-free подход (самый нижний график — это reader-writer мьютекс).

R>>>>

R>>

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

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

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

Это называется starvation (голодание). Это известный момент касательно блокировок.

RRM>Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить

Windows тоже лазеет в ядро. Просто он не решал перепланироват на выполнение другой поток. Если бы приоритет второго потока был выше, то я думаю, что он мог бы сразу запускался на выполнение. Тогда бы это называлось уже не starvation, а priority inversion

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

RRM>>Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

_>Именно так реализовано ожидание критических секций в Windows. Так что достаточно распространено

Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

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

RRM>>Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить

R>Windows тоже лазеет в ядро. Просто он не решал перепланироват на выполнение другой поток. Если бы приоритет второго потока был выше, то я думаю, что он мог бы сразу запускался на выполнение. Тогда бы это называлось уже не starvation, а priority inversion

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

R>

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

R>Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

Могу ошибаться, но мне казалось, что там есть значение для счётчика по умолчанию. А InitializeCriticalSectionAndSpinCount просто позволяет им управлять. Но не помню, откуда я это взял, в msdn на эту тему ничего не нашёл.

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

R>На месте, по крайней мере, я стоять не люблю

R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь

Можно ли ознакомиться где-то с результатами этих изыскания?

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

R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь

Нифига не пустой труд. Я по работе на многопоточность не завязан и поэтому нету соответствующих знаний и возможности проверить/поэксперементировать. Сиплюснотые твои изыски тоже не получается применить.

Но я за твоими сообщениями внимательно слежу и когда припрет, я знаю где и главное какую инфу искать. То что некому вступить в дисскусию, это не означает что все улетает в трубу. Думаю за твоими сообщения ни я один слежу, просто нам по "скудоумею" возразить, обсудить нечего

Но как тока, мы так сразу

Предлагаю твои изыскания маркеровать тегом "remark"

PS Обязуюсь в дальнешем побороть лень и все интересные сообщения оценивать, дабы хоть какой то отклик был

... << RSDN@Home 1.2.0 alpha 4 rev. 1052>>

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

[]

КЛ>>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

R>На месте, по крайней мере, я стоять не люблю

R>Тут либо ты меня не так понял, либо я не так сказал. Я не призываю использовать lock-based алгоритмы, я хочу сказать, что и тот и другой подход по сути своей очень схожи и дороги. Схожесть у них в том, что они оба основаны на постоянной модификации одних и тех же разделяемых переменных. И это у них основной источних их стоимости и немасштабируемости.

просто когды ты впервые публиковал что-то по lock-free, ты ничего не упоминал об очень дорогих atomic операциях.

КЛ>>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?

R>Если у тебя операция под мьютексом короткая, например, добавление элемента в очередь (фактически пара манипуляций с указателями), то получается, что у тебя полезной работы 1 такт, и 500 тактов пенальти за синхронизацию. Т.е. 0.2% полезной работы и 99.8% оверхед. Это, конечно, через чур утрированно, но суть такая. И reader-writer мьютексы никак не спасают, они делают только хуже.

я о том же.

R>Смотри презентацию "Abstraction, Reality Checks, and RCU":

постараюсь глянуть, спасибо.

[]

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

Здравствуйте, Константин Л., Вы писали:

КЛ>По поводу того, что дискуссии не получается ты зря, мы читаем и наматываем на ус. так что это все очень полезно.

Возможно, проблема в том, что наматывание RSDN-овцами себе на ус никак не отражается на материальном благосостоянии самого remark-а.

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

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

R>>Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

SH>Могу ошибаться, но мне казалось, что там есть значение для счётчика по умолчанию. А InitializeCriticalSectionAndSpinCount просто позволяет им управлять. Но не помню, откуда я это взял, в msdn на эту тему ничего не нашёл.
Именно так написано у Рихтера... Сначала Spin Wait затем собственно ожидание.

PS Сорри, что медленно... праздники

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

R>На месте, по крайней мере, я стоять не люблю :)
R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь ;)

Ты пишешь преимущественно в ФП, а это опасный для здоровья форум, пиши в C++ :-)

Лично мне твои сообщения весьма интересны, но пока только теоретически, вот не являются сверхскоростные сервера моей нынешней сферой деятельности. Хотя я и хотел бы.

Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать ;-)

Кстати, а что именно разрабатываешь ты? Можно ли посмотреть на высокие технологии в действии?

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

RO>пиши в C++

+1

RO>Лично мне твои сообщения весьма интересны,
Присоединяюсь.

RO>Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать

+1

У меня тоже есть интерес к lock-, wait-, obstruction-, atomic-free алгоритмам. Пока наращиваю "мускульную массу", читаю вумных людей, пробую что то реализовывать и с ним играться.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

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

R>Для факультативного чтения могу предложить:
R>Practical lock-freedom
R>или более свежий:
R>Concurrent Programming Without Locks
R>Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

Я понял, что основа lock-free адгоритмов — CAS, multiple-CAS и STM?

Сейчас перечитываю вторую работу, кроме того примерно 1.5 года назад прочитал пару статей по STM.
Свои мысли на этот счет я изложил здесь

Больше всего сомнений/вопросов возникает по поводу достаточно длинных транзакций в связи
1) Возможно livelock — параллельные транзакции, ктр не дают закоммитить друг другу изменения

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

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

Есть ли какой-то опыт появления таких проблем в реальных приложениях или это в большей степени теоретические проблемы?

Столько внимания к моей персоне, я прям весь засмущался и покраснел

Место, где сейчас можно следить за моими изысканиями, это наверное здесь:
http://groups.google.com/group/lock-free/topics

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

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

Так же со всеми этими алгоритмами связана большая проблема. Алгоритмы синхронизации, основанные на мьютексах, очень... как сказать... прямолинейны в своей семантике, побочных эффектах и т.д. С "нетрадиционными" алгоритмами синхронизации обычно всё не так просто. Например, какой-то алгоритм рассчитан на применение в окружении с фиксированным количеством потоков. Или например, есть несколько алгоритмов освобождения памяти для lock-free алгоритмов, но все они обладают слабыми сторонами, т.е. например для ситуации, когда много чтений, но мало записей лучше подходит один алгоритм, а когда наоборот, то другой. Или например, большинство lock-free алгоритмов (в не garbage-collected environment) требуют наличия упомянутого механизма освобождения памяти, а эти алгоритмы зачастую "первазивны", т.е. требуют чтобы, например, все потоки приложения периодически вызывали определенную функцию, если этого не будет, то остановится всё освобождение памяти. И т.д.
Как следствие такие алгоритмы иногда сложно выразить в "библиотечной" форме, т.е. готовой для простого использования в любом приложении. Из-за описанных "побочных эффектов", существенную роль приобретает вопрос — как, где, когда и почему их *применить*. А не просто сам алгоритм.
Если бы не это, то самым естественным способом для выражения таких алгоритмов было бы просто создание библиотеки, лёгкой для использования, и со спрятанными под капотом сложностями. Но так зачастую не получается.
Если разрабатывать алгоритмы под конкретное приложение, под конкретную ситуацию, то всё получается значительно легче.

R>>>>>

R>>>

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

CVL>PS Обязуюсь в дальнешем побороть лень и все интересные сообщения оценивать, дабы хоть какой то отклик был

Ну это будет хотя бы что-то. А то иногда я пытаюсь вдаваться в какие-то детали, а реакции 0, ни плюсов, ни минусов, ни ответов, ни вопросов. Особенно учитывая, что времени на серьёзные ответы зачастую уходит много, это сильно деморализует.

Вот например пара сообщений, про которые я не понимаю, имеет ли смысл в дальнейшем писать что-то подобное или нет:
http://www.rsdn.ru/forum/message/2809217.1.aspx
http://www.rsdn.ru/forum/message/2911323.1.aspx

С некоторыми сообщениями вообще комическая ситуация — оценок, допустим, 10, а в избранное добавили 20

Вот лидеры:
оценок — 7, в избранном у 22:
http://www.rsdn.ru/Forum/message/1849716.1.aspx
оценок — 19, в избранном у 27:
http://www.rsdn.ru/Forum/message/2414109.1.aspx

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

E>Здравствуйте, Константин Л., Вы писали:

КЛ>>По поводу того, что дискуссии не получается ты зря, мы читаем и наматываем на ус. так что это все очень полезно.

E>Возможно, проблема в том, что наматывание RSDN-овцами себе на ус никак не отражается на материальном благосостоянии самого remark-а.

Бесспорно, если бы какой-то из способов сопровождался улучшением моего материального состояния, то он бы имел у меня значительно больший приоритет, я бы уделял ему больше времени, и делал бы всё с бОльшим усердием

Почву я уже начал прощупывать:
http://www.rsdn.ru/forum/message/2934232.aspx
Правда в итоге я так пока ничего и не понял...

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

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

R>>На месте, по крайней мере, я стоять не люблю

R>>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь

RO>Ты пишешь преимущественно в ФП, а это опасный для здоровья форум, пиши в C++

Да я и сам в раздумьях. В принципе на RSDN такое вообще некуда писать. Форума посвященного multithreading'у и всему, что с ним свзано, нет.
На последние сообщения я делал анонсы в C++. Всё таки только в С++, я думаю, будет значительно меньше аудитория.
По поводу здоровья. Слава богу самые вредители здоровья в ФП (не будем называть имён... их и так все знают

) пока похоже обходят стороной мои сообщения

RO>Лично мне твои сообщения весьма интересны, но пока только теоретически, вот не являются сверхскоростные сервера моей нынешней сферой деятельности. Хотя я и хотел бы.

RO>Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать

RO>Кстати, а что именно разрабатываешь ты? Можно ли посмотреть на высокие технологии в действии?

Многие считают, что я разрабатываю что-то экстремальное. Но на самом деле я ничего не разрабатываю. Это просто хобби. Желание есть, но такой работы в Росии пока нет. Хочется надеяться, что это временно.
Плюс ещё "жалко" остальную команду, они ещё от Егорушкина отходят, а тут ещё я со своими lock-free алгоритмами. Поэтому я стараюсь держать всё в рамках приличия

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

CC>У меня тоже есть интерес к lock-, wait-, obstruction-, atomic-free алгоритмам. Пока наращиваю "мускульную массу", читаю вумных людей, пробую что то реализовывать и с ним играться.

Можешь поглядеть тут:
http://groups.google.com/group/lock-free/topics
Если будут какие-то вопросы — постараюсь ответить.

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

R>С некоторыми сообщениями вообще комическая ситуация — оценок, допустим, 10, а в избранное добавили 20

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

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

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

R>>Для факультативного чтения могу предложить:
R>>Practical lock-freedom
R>>или более свежий:
R>>Concurrent Programming Without Locks
R>>Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

RRM>Я понял, что основа lock-free адгоритмов — CAS, multiple-CAS и STM?

Основа lock-free алгоритмов — всё, что не блокируется. Начиная от обычных сохранений/загрузок из памяти, и заканчивая CAS.
Есть FAA (fetch-and-add).
Есть просто атомарные and/or/xor.
Есть single-word CAS, обычно просто CAS.
Есть double-word CAS, DCAS или DWCAS.
Есть double CAS, DCAS — не присутствует на современных архитектурах.
MCAS — и никогда не присутствовал. Однако возможно построение MCAS поверх STM/HTM, хотя это уже не совсем честно.

Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.

RRM>Сейчас перечитываю вторую работу, кроме того примерно 1.5 года назад прочитал пару статей по STM.
RRM>Свои мысли на этот счет я изложил здесь

Ну в общем примерно так и обстоит дело.

1) Серьезное ограничение по сравнению с блокировками — невозможность синхронизировать ввод/вывод.
Транзацкии должны быть _перезапускаемы_ (автоматически или явно — это не важно) — этим все сказано.

Да.

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

Ну тут зависит от длительности транзакции и кол-ва конфликтов. Например, 10-30% перезапусков для небольших транзакций, я думаю, не страшно.

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

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

Оптимистический подход предполагает, что конкуренция должна быть не очень высокая. И перезапуск должен быть возможен. И перезапуск должен быть относительно недорогим. Т.е. для некоторых ситуаций, действительно, более разумно использовать мьютексы, даже при наличии хорошей STM/HTM.

Этот пункт вместе с первым говорит о том, что STM/HTM не серебрянная пуля:
http://groups.google.com/group/comp.arch/msg/88ce8bc80c3fc747

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

Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.

Достоинства:
1) Можно написать большими буквами. ОТСУТСВИЕ БЛОКИРОВОК и все проблемм с ними связянных

Какие проблемы ты имеешь в виду?
Очень много проблем выкрикивается как раз теми, кто сейчас начал продвигать STM/HTM. Т.е. небольшой участок кода под блокировкой, который захватывает только одну блокировку за раз, и не вызывает никакого стороннего кода, у него вобщем-то не так уж и много недостатков.

RRM>Больше всего сомнений/вопросов возникает по поводу достаточно длинных транзакций в связи
RRM>1) Возможно livelock — параллельные транзакции, ктр не дают закоммитить друг другу изменения

Если STM/HTM lock-free, то этого не будет. Если только obstruction-free, то это возможно.
Сейчас STM примерно 50 на 50 lock-free или obstruction-free. Но lock-free реализации значительно тяжелее.
Первая наклювывающаяся HTM очень сильно obstruction-free.

RRM>2) Вероятность того, что поток выполняющий транзакцию будет ведеть inconsistent состояние, как результат коммита параллельных транзакций.

Опять же зависит от реализации. Некоторые позволяют dirty-read, некоторые — нет. В некоторых языках (Java, C#, Haskell) с этим можно что-то сделать, в других (C/C++) — нет.
Но вообще такая проблема существует. Стратегия решения в лоб — валидировать транзакцию после каждого чтения. Она работает, но экстремально дорогая.

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

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

RRM>Очевидно, что алгоритм нужно писать соответствующим образом, но на первый взгляд это ничем не легче чем написать корректный код с блокировками.
RRM>Есть ли какой-то опыт появления таких проблем в реальных приложениях или это в большей степени теоретические проблемы?

Если интересно, то можешь поглядеть информацию по поводу первой HTM, которая будет доступна а этом году (там ссылка на PDF):
http://groups.google.com/group/comp.programming.threads/msg/32753ff0259e751d

A так же можешь проглядеть эти ветки:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8bef56a090c052d9
http://groups.google.com/group/comp.arch/browse_frm/thread/c3ab878bfcaffc03
http://groups.google.com/group/comp.arch/browse_frm/thread/91cb3fbfa2eb362a

А что если совместить lock-based и lock-free модели?..

Т.е., предположим, все фундаментальные взаимодействия между процессами исчерпываются двумя классами — pipe (один поток пишет, другой читает) и, не знаю как это назвать, пусть будет share — когда есть несколько потоков которые могут как читать, так и писать. Причем по определению первый класс взаимодействий применяется для передачи большого (хотя это необязательно) объема однородных данных, а второй — для совместного доступа к данным со сложной структурой.

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

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

К тому же, такую систему можно реализовать "прозрачно", что, имхо, вполне оправдает небольшую возможную потерю производительности.

Собственно, интересует полнота такой модели синхронизации. То есть, можно ли обойтись только этими двумя примитивами (lock-based pipe и STM-based share) для синхронизации потоков в приложении, или есть примеры, когда этого точно будет недостаточно, или будет очень большая потеря производительности?

... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>

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

MK>А что если совместить lock-based и lock-free модели?..

Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге?

з.ы. в принципе lock-based и lock-free прекрасно совмещаются даже в рамках одного объекта.

MK>Т.е., предположим, все фундаментальные взаимодействия между процессами исчерпываются двумя классами — pipe (один поток пишет, другой читает) и, не знаю как это назвать, пусть будет share — когда есть несколько потоков которые могут как читать, так и писать. Причем по определению первый класс взаимодействий применяется для передачи большого (хотя это необязательно) объема однородных данных, а второй — для совместного доступа к данным со сложной структурой.

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

А почему очередь lock-based, а не lock-free или STM?

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

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

MK>К тому же, такую систему можно реализовать "прозрачно", что, имхо, вполне оправдает небольшую возможную потерю производительности.

MK>Собственно, интересует полнота такой модели синхронизации. То есть, можно ли обойтись только этими двумя примитивами (lock-based pipe и STM-based share) для синхронизации потоков в приложении, или есть примеры, когда этого точно будет недостаточно, или будет очень большая потеря производительности?

Сложно что-либо прокомментировать по-существу пока не понятна ЦЕЛЬ.
Теоретически, даже какого-либо одного из этих примитивов достаточно для обеспечения полноты. Например, легко представить систему, состоящую из некоторого числа независимых потоков, которые взаимодействуют только посредством очередей сообщений. Так строятся системы на основе MPI. Разделяемые ресурсы в такой системе моделируются следующим образом. Какой-то поток объявляется владельцем, остальные потоки отправляют ему "запросы", он обрабатывает и отсылает назад "ответы".

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

R>Если интересно, то можешь поглядеть информацию по поводу первой HTM, которая будет доступна а этом году (там ссылка на PDF):
R>http://groups.google.com/group/comp.programming.threads/msg/32753ff0259e751d

Так так же есть 2 очень интересных примера применения TM.

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

Второй — lock elision (не знаю как перевести). Это как бы попытка оптимистической элиминация мьютекса. Почему это получается быстрее обычного мьютекса для меня правда загадка. Видимо особенность реализации HTM.

R>

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

R>Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.

Все таки "классический" вариант, когда коммит и соответвтенно валидация делаются в конце транзакции, — obstruction-free. Это исключительно imho

lock-free его может сделать валидация транзакции при каждом обращении к элементу транзакции, но это теоретически достаточно дорогая операция. При валидации необходимо _атомарно_ провалидировать все элементы и проапдейтить (если мы храним копии), т.е. сделать что-то похожее на MCAS. Я до сих пор не понял, как его предполагается делать эффективно, ведь MCAS нет на современной аппаратуте. Ну разве что использовать lock —

Ну или коммит реализовывать как некий lock-free алгоритм, т.е. lock-free внутри другого lock-free

R>Чем длинее транзакция и чем больше потоков могут потенциально пересечься тем меньше вероятность что транзакия не будет перезапушена, т.е. под нагрузкой производительность будет падать. Вопрос насколько?

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

R>Оптимистический подход предполагает, что конкуренция должна быть не очень высокая. И перезапуск должен быть возможен. И перезапуск должен быть относительно недорогим. Т.е. для некоторых ситуаций, действительно, более разумно использовать мьютексы, даже при наличии хорошей STM/HTM.

R>Этот пункт вместе с первым говорит о том, что STM/HTM не серебрянная пуля:
R>http://groups.google.com/group/comp.arch/msg/88ce8bc80c3fc747

Полностью согласен

R>3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
R>Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
R>Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
R>Причем чем длинее транзакция тем сильнее будут проявляться проблемы

R>Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.

Предположим, что транзакционная переменная не просто целое число, а действительно объект, ктр уже существует и не может быть изменен. Что будет если две транзакции будут в него одновременно писать? Тут вообще никаких гарантий нет, что он останется в согласованном состоянии.
Если делать копии, то возникнет проблема атомарного сравнения двух копий объектов при коммите/валидации транзакции.

Даже если транзакционные переменные простые слова, я не до конца уверен, что можно обойтись без их копирования. Интуиция подсказывает, что нужно, но объяснить пока не могу. В любом случае, если этого не делать, то dirty-read возможен даже из тех переменных, куда мы только что записали

R>

R>Достоинства:
R>1) Можно написать большими буквами. ОТСУТСВИЕ БЛОКИРОВОК и все проблемм с ними связянных

R>Какие проблемы ты имеешь в виду?
R>Очень много проблем выкрикивается как раз теми, кто сейчас начал продвигать STM/HTM. Т.е. небольшой участок кода под блокировкой, который захватывает только одну блокировку за раз, и не вызывает никакого стороннего кода, у него вобщем-то не так уж и много недостатков.

Ну это бы скорее сарказм

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

R>Так так же есть 2 очень интересных примера применения TM.

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

В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.

Ну или нужен _H_TM.

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

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

RRM>В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.

RRM>Ну или нужен _H_TM.

Вообще размыiляя над STM, я приходу к мысли, что эта концепция значительно сложнее как с точки зрения реализации так и использования. Естественно не рассматривая примитивные случаи.

Главная проблема STM — больше по сравнения с использованием блокировок возможных пересечений двух потоков и взаимных влияний. Если при использовании блокировок потоки влияют друг на друга в точках работы с блокировками и основная сложность — все варианты последовательностей, в которых потоки могут приходить в эти точки. То с STM добавляются dirty-read. Если STM реализована без dirty-reads, то видимо усложнится сама реализация.

Мне кажется STM займет свою нишу, но это будет специализированный инструмент. На роль серебрянной пули больше подходит идея Erlang-а с процессами обменивающимися сообщениями. IMHO

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

R>Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге?
Ну так как форум философский, возьмем крупномасштабный пример — сообщение между процессами и потоками в (серверной) ОС. Ну и цель в таком случае — большая производительность на многоядерных системах + хороший потенциал в плане масштабируемости (т.е. не так как ты описал, с экспоненциальным ростом времени

)

R>А почему очередь lock-based, а не lock-free или STM?
Для упрощения реализации. В данном случае взаимодействуют только 2 потока, и я предполагаю что можно реализовать с одной стороны простой и легковесный, а с другой стороны исключающий дедлоки примитив передачи данных.

R>В общем случае утверждение, что STM == одновременный доступ без большого оверхеда, неверно.
Согласен, это зависит от модели транзакционной памяти и ее реализации. Но имхо возможно реализовать ее именно так — чтобы была гарантия lock-free и "легкие" транзакции. Пожертвовать, видимо, в данном случае приходится сложной системой разрешения конфликтов транзакций с рассчетом на то, что транзакций, изменяющих объект будет меньше, чем операций чтения. В тех случаях когда это не вписывается в такую модель, придется использовать нужное количество pipe.

R>Теоретически, даже какого-либо одного из этих примитивов достаточно для обеспечения полноты. Например, легко представить систему, состоящую из некоторого числа независимых потоков, которые взаимодействуют только посредством очередей сообщений. Так строятся системы на основе MPI. Разделяемые ресурсы в такой системе моделируются следующим образом. Какой-то поток объявляется владельцем, остальные потоки отправляют ему "запросы", он обрабатывает и отсылает назад "ответы".
Я тут в качестве основного преимущества вижу простоту системы. Хотя мб упускаю какие-то еще преимущества.

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

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

R>

... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>

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

R>>Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге?
MK>Ну так как форум философский, возьмем крупномасштабный пример — сообщение между процессами и потоками в (серверной) ОС. Ну и цель в таком случае — большая производительность на многоядерных системах + хороший потенциал в плане масштабируемости (т.е. не так как ты описал, с экспоненциальным ростом времени

)

Ну что ж, цель достойная, мне нравится

Дабы не запутаться окончательно тут надо выделить 2 аспекта. Первый — высокоуровневый дизайн, второй — реализация конкретных структур данных.

Что касается дизайна, то лично я считаю такую модель (пайпы + шары) практически идеальной. С помощью пайпов (очередей сообщений) система хорошо структурируется на независимые части, каждая часть "однопоточно" (читай эффективно) работает со своими локальными данными, а всё взаимодействие с остальным миром очень чётко структурировано — можно только отправлять сообщения или принимать сообщения.
При этом, как ты правильно заметил, для некоторых структур данных работа на основе обмена сообщениями будет очень неэффективной. Во-первых, резко повышается латентность операций — вместо прямого обращения к разделяемой структуре, нам теперь надо отправить сообщение, другой поток "когда-то" его достанет из очереди, обработает, отправит ответ, потом исходный поток опять "когда-то" достанет ответ из очереди и продолжит обработку. Во-вторых, стоимость тоже не очевидна, т.к. каждая операция с сообщением — это обращение к разделяемой структуре данных, а у нас тут получается 4 таких операции. В третьих, если это центральная структура данных, и при этом с ней напрямую может работать только один поток, а остальные только с помощью сообщений, то получается, что у нас фактически производительность системы ограничена производительностью одного потока. Представь, например, 32-ух процессорную систему, на которой все процессоры обязаны постоянно обращаться к одному — 31 процессор будет большую часть времени простаивать.
Исходя из всего этого я лично считаю, что системы типа Eralng (основанные исключительно на обмене сообщениями) сливают в общем случае.
Тут целесообразно *некоторые* структуры реализовать именно как многопоточные разделяемые модифицируемые структуры, сделав реализацию оптимальную под данную задачу.

Что касается реализации.
Очереди типа single-producer/single-consumer можно реализовать экстремально эффективно без использования ни мьютексов, ни TM. В такой реализации каждая операция (enqueue/dequeue) занимает не более 10 машинных инструкций и не содержит никаких тяжёлых операций, типа InterlockedXXX или тяжёлых барьеров памяти. Бенчмарки такой очереди против реализаций на основе мьютексов, TM, InterlockedXXX похожи на кровопролитное массовое убийство невинных детей. Это единственный верный путь.
Что касается реализации других разделяемых структур — сложный вопрос. Он должен решаться индивидуально. Для каких-то структур STM может быть хорошим решением. Для каких-то не очень. STM — в общем случае не панацея.
Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился. При чём тут не важно STM obstruction-free или lock-free — всё равно операциям прохода будет тотально "невезти".
Как следствие, если разработчик оказывается в такой ситуации и слепо верит в STM/HTM и больше ничего не умеет, то он попадает в достаточно затруднительную ситуацию...

R>>

MK>

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

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

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

RRM>>В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.

RRM>>Ну или нужен _H_TM.

Нет, не обязательно. Сейчас я попробую подобрать ряд ссылок по поводу реализации различных видов STM.
STM обычно реализует на основе CAS. Я недавно делал небольшую тестовую реализацию вообще на основе только XCHG (InterlockedExchange).

RRM>Вообще размыiляя над STM, я приходу к мысли, что эта концепция значительно сложнее как с точки зрения реализации так и использования. Естественно не рассматривая примитивные случаи.

Реализация STM неимоверно сложная. Причём большинство решений компромиссные.
Использование... ну в идеале STM просто "магически" работает, а программист ни о чём не думает, т.е. просто заменяет mutex.lock()/mutex.unlock() на trx_begin()/trx_commit() или вообще atomic {}. Такие реализации есть, но они очень непроизводительные. Остальные реализации предоставляют некий компромисс.

RRM>Главная проблема STM — больше по сравнения с использованием блокировок возможных пересечений двух потоков и взаимных влияний. Если при использовании блокировок потоки влияют друг на друга в точках работы с блокировками и основная сложность — все варианты последовательностей, в которых потоки могут приходить в эти точки. То с STM добавляются dirty-read. Если STM реализована без dirty-reads, то видимо усложнится сама реализация.

В пределе в STM нет dirty-read.

RRM>Мне кажется STM займет свою нишу, но это будет специализированный инструмент. На роль серебрянной пули больше подходит идея Erlang-а с процессами обменивающимися сообщениями. IMHO

No silver bullet!
Смотри почему Erlang *не* серебрянная пуля:
http://gzip.rsdn.ru/forum/message/2961101.1.aspx

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

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

R>>Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.

RRM>Все таки "классический" вариант, когда коммит и соответвтенно валидация делаются в конце транзакции, — obstruction-free. Это исключительно imho

Достаточно просто отсортировать ячейки для захвата, что бы реализация стала lock-free.
Представь — есть массив ячеек, каждый поток пытается атомарно захватить некий случайный набор ячеек. Если ячейки отсортировать перед захватом, то какой-то один поток обязательно захватит все необходимые ему ячейки.

RRM>lock-free его может сделать валидация транзакции при каждом обращении к элементу транзакции, но это теоретически достаточно дорогая операция. При валидации необходимо _атомарно_ провалидировать все элементы и проапдейтить (если мы храним копии), т.е. сделать что-то похожее на MCAS. Я до сих пор не понял, как его предполагается делать эффективно, ведь MCAS нет на современной аппаратуте. Ну разве что использовать lock —

Не знаю, пошутил ты или нет, но самые производительные реализации STM сейчас как раз на основе fine-grained lock'ов.

RRM>Ну или коммит реализовывать как некий lock-free алгоритм, т.е. lock-free внутри другого lock-free

Такие тоже есть, но они на порядок более сложные.

R>>

R>>3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
R>>Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
R>>Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
R>>Причем чем длинее транзакция тем сильнее будут проявляться проблемы

R>>Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.

RRM>Предположим, что транзакционная переменная не просто целое число, а действительно объект, ктр уже существует и не может быть изменен. Что будет если две транзакции будут в него одновременно писать? Тут вообще никаких гарантий нет, что он останется в согласованном состоянии.
RRM>Если делать копии, то возникнет проблема атомарного сравнения двух копий объектов при коммите/валидации транзакции.

Копию делать не надо. Просто писать в старый объект. На то это и STM.

RRM>Даже если транзакционные переменные простые слова, я не до конца уверен, что можно обойтись без их копирования. Интуиция подсказывает, что нужно, но объяснить пока не могу. В любом случае, если этого не делать, то dirty-read возможен даже из тех переменных, куда мы только что записали

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

R>>

RRM>

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

[]

STM Это вот это — http://en.wikipedia.org/wiki/Software_transactional_memory ?

R>Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился.

с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?

При чём тут не важно STM obstruction-free или lock-free — всё равно операциям прохода будет тотально "невезти".
R>Как следствие, если разработчик оказывается в такой ситуации и слепо верит в STM/HTM и больше ничего не умеет, то он попадает в достаточно затруднительную ситуацию...

R>>>

MK>>

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

R>Нет, не обязательно. Сейчас я попробую подобрать ряд ссылок по поводу реализации различных видов STM.

А ну да, собственно ничего подбирать не надо. Тут есть много ссылок на реализации:
http://en.wikipedia.org/wiki/Software_transactional_memory

От себя могу добавить ещё следующее.
Реализация TL2 (одна из самых "лучших" реализаций) для x86 (язык — С/С++):
http://stamp.stanford.edu/archive/tl2-x86-0.9.4.tar.gz

Для Java:
http://sourceforge.net/project/showfiles.php?group_id=127837
(xmem)

Ещё вот здесь:
http://csl.stanford.edu/~christos/
и здесь:
http://www.cs.wisc.edu/trans-memory/biblio/
есть большое кол-во различного материала.

А здесь можно качнуть бенчмарк для различных реализаций STM:
http://stamp.stanford.edu/
Правда придётся потрудиться, что скомпилировать его с другими реализациями кроме TL2-x86.

Но вообще учти. Недавно прочитал занятную статью Dividing Transactional Memories by Zero (http://www.unine.ch/transact08/papers/Dragojevic-Dividing.pdf)

Abstract
Software transactional memory (STM) is a promising technique for
writing concurrent programs. So far, most STM approaches have
been experimentally evaluated with small-scale benchmarks. In
this paper, we present several surprising results from implementing
and experimenting with STMBench7 – a large scale benchmark for
STMs. First, all STMs we used crashed, at some point or another,
when running STMBench7. This was mainly due to memory management
limitations. This means that, in practice, none of the tested
STMs was truly unbounded and dynamic, which are the actual motivations
for moving away from hardware transactional memories
(HTM). Performance results we gathered also differ from previously
published results. We found, for instance, that conflict detection
and contention management have the biggest performance impact,
way more than other aspects, like the choice of lock-based or
obstruction-free implementation, as typically highlighted. Implementation
of STMBench7 with various STMs also revealed several
programming related issues such as the lack of support for external
libraries and only partial support for object oriented features.
These issues prove to be a major limitation when adapting STMs
for production use.

Здравствуйте, Константин Л., Вы писали:

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

КЛ>[]

КЛ>STM Это вот это — http://en.wikipedia.org/wiki/Software_transactional_memory ?

Это.

R>>Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился.

КЛ>с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?

Ты путаешь причину и следствие. Он не провалится, если мы имеем 100% консистентные данные. Но то, что мы их имеем не факт. Это будет факт только если STM реализована через один глобальный мьютекс. Тогда каждая операция будет 100% удаваться, но это определенно не то, что мы хотим.

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

[]

КЛ>>с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?

R>Ты путаешь причину и следствие. Он не провалится, если мы имеем 100% консистентные данные. Но то, что мы их имеем не факт. Это будет факт только если STM реализована через один глобальный мьютекс. Тогда каждая операция будет 100% удаваться, но это определенно не то, что мы хотим.

что значит не факт. это по определению мы имеем 100% конс. данные

R>

Здравствуйте, Константин Л., Вы писали:

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

КЛ>[]

КЛ>>>с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?

R>>Ты путаешь причину и следствие. Он не провалится, если мы имеем 100% консистентные данные. Но то, что мы их имеем не факт. Это будет факт только если STM реализована через один глобальный мьютекс. Тогда каждая операция будет 100% удаваться, но это определенно не то, что мы хотим.

КЛ>что значит не факт. это по определению мы имеем 100% конс. данные...

... возможно после нескольких повторов операции, когда мы видели не консистентные данные.

Т.е. с т.з. пользователя — да, транзакция как-будто всегда видит консистентные данные. Но сколько перед этим было перезапусков транзакции, когда был детектирован конфликт, не определено.

R>>

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

R>Плюс ещё "жалко" остальную команду, они ещё от Егорушкина отходят, а тут ещё я со своими lock-free алгоритмами. Поэтому я стараюсь держать всё в рамках приличия :)))

Это Егорушкин от нас отходит, причем куда-то очень далеко.

А чем таким он знаменит? Он вроде только про C++ писал, в один поток ;-)?

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

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

R>>Плюс ещё "жалко" остальную команду, они ещё от Егорушкина отходят, а тут ещё я со своими lock-free алгоритмами. Поэтому я стараюсь держать всё в рамках приличия

RO>Это Егорушкин от нас отходит, причем куда-то очень далеко.

RO>А чем таким он знаменит? Он вроде только про C++ писал, в один поток

?

Ну так от его С++ и отходят

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

R>При этом, как ты правильно заметил, для некоторых структур данных работа на основе обмена сообщениями будет очень неэффективной.
Вот это место у меня вызывает сомнения.
R> Во-первых, резко повышается латентность операций — вместо прямого обращения к разделяемой структуре, нам теперь надо отправить сообщение, другой поток "когда-то" его достанет из очереди, обработает, отправит ответ, потом исходный поток опять "когда-то" достанет ответ из очереди и продолжит обработку.
Ок, а какая, простите, была альтернатива? Поток 1 захватывает мьютекс, пишет в разделяемую структуру, отдает мьютекс, выставляет event и начинает ждать второго евента.
В хорошем случае Поток 2 уже спит в ожидании евента и просыпается более-менее сразу. В более плохом он в это время чем-то занят, и только когда-то в будущем выполнит WaitFor, чтобы узнать о приходе данных. В обратную сторону имеем ту же ситуацию.
R>Во-вторых, стоимость тоже не очевидна, т.к. каждая операция с сообщением — это обращение к разделяемой структуре данных, а у нас тут получается 4 таких операции.
Так ведь как раз вся фишка ровно в том, что сообщения — не разделяемые структуры данных! Поэтому там, где надо было жонглировать мьютексами, теперь достаточно прямого доступа.
Основная прелесть системы обмена сообщениями — в том, что есть шанс применить escape-analysis. Если поток 1 больше не выполняет операций над сообщением, то можно обойтись безо всякого копирования, и просто разрешить потоку 2 работать с той же разделяемой структурой напрямую без синхронизации.

Это как СУБД, которая заранее знает, нужно ли захватывать блокировки или эти данные всё равно никто не увидит.

R>В третьих, если это центральная структура данных, и при этом с ней напрямую может работать только один поток, а остальные только с помощью сообщений, то получается, что у нас фактически производительность системы ограничена производительностью одного потока.
R>Представь, например, 32-ух процессорную систему, на которой все процессоры обязаны постоянно обращаться к одному — 31 процессор будет большую часть времени простаивать.
Ты описываешь просто реализацию мьютекса через очередь сообщений. Естественно мы получим гарантию хреновой производительности в таком случае: мьютекс собственно и гарантирует то, что не более 1го потока выполняют прикрытую им работу. Для того, чтобы message-oriented cистемы работали, нужно размазать данные по очередям.
Это не то чтобы как-то очень сложно; это просто другой способ декомпозиции задачи. Ну вот представь себе, что ты разрабатываешь банальный SMTP Relay. Если ты — ООПшник, то у тебя там будет в памяти некоторый контейнер "очередь сообщений", в него будут добавлять мессаги потоки, обрабатывающие клиентов, и выгребать мессаги потоки, обрабатывающие доставку. Ты будешь тренироваться в обеспечении синхронизации, выбирая правильную гранулярность, чтобы не более одного потока пытались доставить некоторое сообщение и т.п. Этот контейнер может оказаться bottleneck-ом (в данном случае этого конечно же не случится, т.к. типичные времена доставки одного почтового сообщения в миллиарды раз выше расходов на синхронизацию, но для примера сойдет).
В message-oriented системе тебе вообще не нужен этот контейнер в явном виде. Один поток принял письмо от клиента — кинул его другому для отправки. Тот получил — выполнил попытку — если она не удалась, перекинул в поток ожидания, который тупо задержит форвард письма на, скажем 3600 секунд. И так далее.

R>Исходя из всего этого я лично считаю, что системы типа Eralng (основанные исключительно на обмене сообщениями) сливают в общем случае.
R>Тут целесообразно *некоторые* структуры реализовать именно как многопоточные разделяемые модифицируемые структуры, сделав реализацию оптимальную под данную задачу.

R>Что касается реализации.
R>Очереди типа single-producer/single-consumer можно реализовать экстремально эффективно без использования ни мьютексов, ни TM. В такой реализации каждая операция (enqueue/dequeue) занимает не более 10 машинных инструкций и не содержит никаких тяжёлых операций, типа InterlockedXXX или тяжёлых барьеров памяти. Бенчмарки такой очереди против реализаций на основе мьютексов, TM, InterlockedXXX похожи на кровопролитное массовое убийство невинных детей. Это единственный верный путь.
Вот я так понимаю, что продвинутая среда может опознавать очереди такого типа при помощи статического анализа, и получать офигительное быстродействие. Главная забота разработчика — следить, чтобы таких очередей было побольше.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

R>>При этом, как ты правильно заметил, для некоторых структур данных работа на основе обмена сообщениями будет очень неэффективной.

S>Вот это место у меня вызывает сомнения.

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

S>Ок, а какая, простите, была альтернатива? Поток 1 захватывает мьютекс, пишет в разделяемую структуру, отдает мьютекс, выставляет event и начинает ждать второго евента.
S>В хорошем случае Поток 2 уже спит в ожидании евента и просыпается более-менее сразу. В более плохом он в это время чем-то занят, и только когда-то в будущем выполнит WaitFor, чтобы узнать о приходе данных. В обратную сторону имеем ту же ситуацию.

Я рассматривал 2 следующие альтернативы.
Допустим у нас есть список неких данных, и потоку надо, например, произвести поиск по ключу и вернуть связанные с ключом данные.
Вариант 1. Используется lock-based/lock-free/STM/что-то-ещё структура данных и поток напрямую обращается к структуре и производит необходимые действия и получает результат.
Вариант 2. Поток посылает сообщение-запрос другому потоку, который "владеет" структурой. Тот поток обрабатывает сообщение, обращаясь к структуре в "однопоточном" режиме, и посылает сообщение-ответ исходному потоку.

В первом вариант нет ожиданий между потоками.

R>>Во-вторых, стоимость тоже не очевидна, т.к. каждая операция с сообщением — это обращение к разделяемой структуре данных, а у нас тут получается 4 таких операции.

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

Но очереди-то — разделяемые структуры данных. А во втором варианте получается 4 обращения к очередям.

Плюс данные сообщения, они хоть и не разделяемые, но они *передаются* между потоками. Т.е. они требуют "межядерного" трафика данных. Это тоже имеет ощутимую цену.

S>Основная прелесть системы обмена сообщениями — в том, что есть шанс применить escape-analysis. Если поток 1 больше не выполняет операций над сообщением, то можно обойтись безо всякого копирования, и просто разрешить потоку 2 работать с той же разделяемой структурой напрямую без синхронизации.

S>Это как СУБД, которая заранее знает, нужно ли захватывать блокировки или эти данные всё равно никто не увидит.

Я сейчас в С++ отлавливаю следующие ситуации:

post_msg(my_msg::create(1, 2, 3));

create() создаёт сообщение сразу со счетчиком 1. post_msg() видит, что ему передают временный объект и *крадёт* значение счетчика ссылок, т.е. сам не инкрементирует когда кладёт в очередь. Ну на принимающей стороне ещё проще — после обработки видим, что счётчик ссылок равен 1, и сразу удаляем объект.
Т.е. с помощью такого "псевдо escape анализа" и трюка при декременте, получается устранить все операции со счётчиком ссылок. Хотя в общем случае они поддерживаются — т.е. один поток может послать одно сообщение 10 потокам, а те ещё переслать и т.д.

С escape анализом, безусловно можно будет делать более интересные вещи — например разрулить вот это:

msg m = my_msg::create(1, 2, 3);
post_msg(m);

Хотя я, честно говоря, не в курсе что сейчас может escape анализ в Java/C#. Но мне кажется, что если речь идёт о нескольких функциях, то он сдаёт позиции.

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

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

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

S>Ты описываешь просто реализацию мьютекса через очередь сообщений. Естественно мы получим гарантию хреновой производительности в таком случае: мьютекс собственно и гарантирует то, что не более 1го потока выполняют прикрытую им работу. Для того, чтобы message-oriented cистемы работали, нужно размазать данные по очередям.
S>Это не то чтобы как-то очень сложно; это просто другой способ декомпозиции задачи. Ну вот представь себе, что ты разрабатываешь банальный SMTP Relay. Если ты — ООПшник, то у тебя там будет в памяти некоторый контейнер "очередь сообщений", в него будут добавлять мессаги потоки, обрабатывающие клиентов, и выгребать мессаги потоки, обрабатывающие доставку. Ты будешь тренироваться в обеспечении синхронизации, выбирая правильную гранулярность, чтобы не более одного потока пытались доставить некоторое сообщение и т.п. Этот контейнер может оказаться bottleneck-ом (в данном случае этого конечно же не случится, т.к. типичные времена доставки одного почтового сообщения в миллиарды раз выше расходов на синхронизацию, но для примера сойдет).
S>В message-oriented системе тебе вообще не нужен этот контейнер в явном виде. Один поток принял письмо от клиента — кинул его другому для отправки. Тот получил — выполнил попытку — если она не удалась, перекинул в поток ожидания, который тупо задержит форвард письма на, скажем 3600 секунд. И так далее.

Хорошо. Допустим нам надо добавить в эту систему спам фильтр, или антивирусную проверку, или рейтинги какие-то, или проверку орфографии, ну короче не важно, важно то, что у нас появляется большой массив каких-то данных, настолько большой, что реплицировать его не вариант, плюс он изменяется в течение времени. И нам надо делать обработку каждого сообщения используя данные их этого массива. Мы делаем на основе передачи сообщений, т.е. ни с какими мьютексами мы связываться не хотим, хотим сделать "однопоточную" реализацию массива данных.
Как ты предлагаешь это реализовать?

R>>Исходя из всего этого я лично считаю, что системы типа Eralng (основанные исключительно на обмене сообщениями) сливают в общем случае.
R>>Тут целесообразно *некоторые* структуры реализовать именно как многопоточные разделяемые модифицируемые структуры, сделав реализацию оптимальную под данную задачу.

R>>Что касается реализации.
R>>Очереди типа single-producer/single-consumer можно реализовать экстремально эффективно без использования ни мьютексов, ни TM. В такой реализации каждая операция (enqueue/dequeue) занимает не более 10 машинных инструкций и не содержит никаких тяжёлых операций, типа InterlockedXXX или тяжёлых барьеров памяти. Бенчмарки такой очереди против реализаций на основе мьютексов, TM, InterlockedXXX похожи на кровопролитное массовое убийство невинных детей. Это единственный верный путь.

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

Я правильно понимаю, что ты говоришь о ситуации, когда потоку посылает сообщения только один другой поток? Я не думаю, что детектирование таких вещей возможно в ближайшем будущем...
Тем более тут вопрос больше не оптимизации, а дизайна. Т.к. одну multi-producer/multi-consumer очередь всегда можно заменить на N multi-producer/single-consumer, или на N^2 single-producer/single-consumer.

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

R>Я рассматривал 2 следующие альтернативы.
R>Допустим у нас есть список неких данных, и потоку надо, например, произвести поиск по ключу и вернуть связанные с ключом данные.
R>Вариант 1. Используется lock-based/lock-free/STM/что-то-ещё структура данных и поток напрямую обращается к структуре и производит необходимые действия и получает результат.
R>Вариант 2. Поток посылает сообщение-запрос другому потоку, который "владеет" структурой. Тот поток обрабатывает сообщение, обращаясь к структуре в "однопоточном" режиме, и посылает сообщение-ответ исходному потоку.
Вариант 3. Используется read-only структура, доступ к которой осуществляется без блокировок. Все модификации порождают новую структуру

, и она атомарно заменяет старую.
R>В первом вариант нет ожиданий между потоками.

R>Но очереди-то — разделяемые структуры данных. А во втором варианте получается 4 обращения к очередям.
Да, к двум однонаправленным очередям того самого типа single producer — single consumer. Что, как ты сам написал, позволяет рассматривать вариант 1 как "кровопролитное массовое убийство невинных детей".
R>Плюс данные сообщения, они хоть и не разделяемые, но они *передаются* между потоками. Т.е. они требуют "межядерного" трафика данных. Это тоже имеет ощутимую цену.
Не вполне понятно. Ты имеешь в виду исполнение потока 2 на другом ядре с независимым кэшем? Ну, в таком случае я не могу себе представить никакого бесплатного способа обменяться данными. В остальном непонятно: я так понял, что в управляемой среде с программной изоляцией никакого копирования данных не происходит. Просто указатель на данные попадает в код потока 2.

R>Я сейчас в С++ отлавливаю следующие ситуации:
R>

R>post_msg(my_msg::create(1, 2, 3));
R>

R>create() создаёт сообщение сразу со счетчиком 1. post_msg() видит, что ему передают временный объект и *крадёт* значение счетчика ссылок, т.е. сам не инкрементирует когда кладёт в очередь. Ну на принимающей стороне ещё проще — после обработки видим, что счётчик ссылок равен 1, и сразу удаляем объект.
R>Т.е. с помощью такого "псевдо escape анализа" и трюка при декременте, получается устранить все операции со счётчиком ссылок. Хотя в общем случае они поддерживаются — т.е. один поток может послать одно сообщение 10 потокам, а те ещё переслать и т.д.

R>С escape анализом, безусловно можно будет делать более интересные вещи — например разрулить вот это:
R>

R>msg m = my_msg::create(1, 2, 3);
R>post_msg(m);
R>

R>Хотя я, честно говоря, не в курсе что сейчас может escape анализ в Java/C#. Но мне кажется, что если речь идёт о нескольких функциях, то он сдаёт позиции.
Нет, конечно же в Java/C# escape анализ мало полезен.
Его нужно применять в других языках, которые построены на message passing. Вот, к примеру, Comega мог применять такие оптимизации — потому что у него нет таких вещей как post_msg; там просто вызов аккорда имеет семантику передачи сообщения. И компилятор видит весь код, который эти пользуется, и вполне может статически понять, сколько там producers у аккорда
R>Но повторюсь, что это не снимает момента о том, очереди — разделяемые структуры данных, и о том, что данные сообщения надо физически передавать между ядрами/процессорами.
Угу.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

R>>Я рассматривал 2 следующие альтернативы.
R>>Допустим у нас есть список неких данных, и потоку надо, например, произвести поиск по ключу и вернуть связанные с ключом данные.
R>>Вариант 1. Используется lock-based/lock-free/STM/что-то-ещё структура данных и поток напрямую обращается к структуре и производит необходимые действия и получает результат.
R>>Вариант 2. Поток посылает сообщение-запрос другому потоку, который "владеет" структурой. Тот поток обрабатывает сообщение, обращаясь к структуре в "однопоточном" режиме, и посылает сообщение-ответ исходному потоку.

S>Вариант 3. Используется read-only структура, доступ к которой осуществляется без блокировок. Все модификации порождают новую структуру

, и она атомарно заменяет старую.

Если такой способ можно применить, то замечательно. Для read-mostly данных — это очень хороший способ.
Но приложения обычно имеют и какие-то "активные" данные, которые постоянно изменяются. Например, список сессий, в который постоянно добавляются записи, удаляются, и ищутся. Тут не особо покопируешь, если структура данных не совсем маленькая.

R>>Но очереди-то — разделяемые структуры данных. А во втором варианте получается 4 обращения к очередям.

S>Да, к двум однонаправленным очередям того самого типа single producer — single consumer. Что, как ты сам написал,
позволяет рассматривать вариант 1 как "кровопролитное массовое убийство невинных детей".

Если используются такие очереди, то замечательно. Но и с ними связаны некоторые проблемы. Например, что бы иметь полно-связанную систему, таких очередей надо иметь уже N^2. Плюс в некоторых ситуациях прибавляется необходимость ручного load-balancing'а.
Даже если мы всё это решили, то задержка передачи 2 сообщений и стоимость физической передачи данных никуда не деваются.

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

R>>Плюс данные сообщения, они хоть и не разделяемые, но они *передаются* между потоками. Т.е. они требуют "межядерного" трафика данных. Это тоже имеет ощутимую цену.

S>Не вполне понятно. Ты имеешь в виду исполнение потока 2 на другом ядре с независимым кэшем? Ну, в таком случае я не могу себе представить никакого бесплатного способа обменяться данными.

Да, именно это. Бесплатный способ обмена сообщениями — не обмениваться сообщениями

S>В остальном непонятно: я так понял, что в управляемой среде с программной изоляцией никакого копирования данных не происходит. Просто указатель на данные попадает в код потока 2.

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

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

R>Хорошо. Допустим нам надо добавить в эту систему спам фильтр, или антивирусную проверку, или рейтинги какие-то, или проверку орфографии, ну короче не важно, важно то, что у нас появляется большой массив каких-то данных, настолько большой, что реплицировать его не вариант, плюс он изменяется в течение времени. И нам надо делать обработку каждого сообщения используя данные их этого массива. Мы делаем на основе передачи сообщений, т.е. ни с какими мьютексами мы связываться не хотим, хотим сделать "однопоточную" реализацию массива данных.
R>Как ты предлагаешь это реализовать?
Это не интересная задача.
Делается это так:
Есть один процесс который принимает TCP/IP (или аналог) соединение.
Далие тупо ссоздает еще один процесс которому передает это соединение.
Это очень быстрый цикл.

Ессно ели у нас продвинутая ОС. (Потомок сингулярити.)

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

Теперь можно проверить письмо на спам, вирусы итп
В данном случае висит менеджер проверки на спам и смотрит чтобы одновременно проверяли не больше N писем на спам.
Менеджер антивируса следит чтобды проверяли не больше M писем на вирусы итп.
Результат складываем рядом с письмом.

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

Даже если делать без надежного хранилища то всеравно рулящие процессы только и будут рулить указателями и плодить процессы которые реально работают.
Просто данные нужно делать не изменяемыми на уровне системы типов и все.

Еще шедуллер ОС может отслеживать концы SP/SC очередей у процесса и держать его поближе к партнерам.

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

R>Тем более тут вопрос больше не оптимизации, а дизайна. Т.к. одну multi-producer/multi-consumer очередь всегда можно заменить на N multi-producer/single-consumer, или на N^2 single-producer/single-consumer.
MP/MC при наличии дешовых процессов ваще изврат.
MP/SC плюс процесс который спанит воркеров куда как эффективнее и надежнее.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Хорошо. Допустим нам надо добавить в эту систему спам фильтр, или антивирусную проверку, или рейтинги какие-то, или проверку орфографии, ну короче не важно, важно то, что у нас появляется большой массив каких-то данных, настолько большой, что реплицировать его не вариант, плюс он изменяется в течение времени. И нам надо делать обработку каждого сообщения используя данные их этого массива. Мы делаем на основе передачи сообщений, т.е. ни с какими мьютексами мы связываться не хотим, хотим сделать "однопоточную" реализацию массива данных.
R>>Как ты предлагаешь это реализовать?
WH>Это не интересная задача.
WH>Делается это так:
WH>Есть один процесс который принимает TCP/IP (или аналог) соединение.
WH>Далие тупо ссоздает еще один процесс которому передает это соединение.
WH>Это очень быстрый цикл.

WH>Ессно ели у нас продвинутая ОС. (Потомок сингулярити.)

WH>Далее процесс который получил соединение зачитывает письмо и кладет его в надежное хранилище. Ибо письма терять нельзя.

WH>Теперь можно проверить письмо на спам, вирусы итп
WH>В данном случае висит менеджер проверки на спам и смотрит чтобы одновременно проверяли не больше N писем на спам.
WH>Менеджер антивируса следит чтобды проверяли не больше M писем на вирусы итп.
WH>Результат складываем рядом с письмом.

Об этом я и говорю. Решения нет. Если у нас N = M = 1, то на вот он ботлнек на лицо.

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

WH>Теперь можно проверить письмо на спам, вирусы итп
WH>В данном случае висит менеджер проверки на спам и смотрит чтобы одновременно проверяли не больше N писем на спам.
WH>Менеджер антивируса следит чтобды проверяли не больше M писем на вирусы итп.
WH>Результат складываем рядом с письмом.

WH>Короче накладные расходы на кешь процессора ты тут никогда не увидишь.

А откуда такая уверенность? Сколько в "типичном" сервере на 32-процессорной машине занимают издержки на кэш?

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

WH>Даже если делать без надежного хранилища то всеравно рулящие процессы только и будут рулить указателями и плодить процессы которые реально работают.
WH>Просто данные нужно делать не изменяемыми на уровне системы типов и все.

Вот тут не очень понятно. Точнее совсем не понятно. Как можно логически изменяемые данные просто сделать не изменяемыми на уровне системы типов и все?
Покажи на примере. Допустим есть множество лицевых счетов. На сервер поступает поток транзакций вида: изменить баланс л/с, перевести сумму с одного л/с на другой л/с, получить баланс л/с, открыть новый л/с и т.д.
Как тут сделать данные не изменяемыми на уровне системы типов?

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

WH>Еще шедуллер ОС может отслеживать концы SP/SC очередей у процесса и держать его поближе к партнерам.

Зачем тут шедулер ОС?

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

WH>Смотри на каналы в сингулярити.
WH>Они как раз дают такие гарантии.

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

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

R>Об этом я и говорю. Решения нет. Если у нас N = M = 1, то на вот он ботлнек на лицо.
А если нет?
У меня таких ситуаций нет даже на отладочных демонах.
А на продакшене будет скорее что-то типа N = M = 100 это очень сильно зависит от задач и железа.
Так что изивини но мимио.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>А откуда такая уверенность? Сколько в "типичном" сервере на 32-процессорной машине занимают издержки на кэш?
По сравнению с фиксацией транзакции на винте?
Ты серьезно?

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Вот тут не очень понятно. Точнее совсем не понятно. Как можно логически изменяемые данные просто сделать не изменяемыми на уровне системы типов и все?
Данных которые можно очень легко сделать неизменяемыми сильно больше чем кажется.

R>Покажи на примере. Допустим есть множество лицевых счетов. На сервер поступает поток транзакций вида: изменить баланс л/с, перевести сумму с одного л/с на другой л/с, получить баланс л/с, открыть новый л/с и т.д.
R>Как тут сделать данные не изменяемыми на уровне системы типов?
Эти данные будут жить в базе данных по любому.
Те ACID в полный рост с фиксацией на гооооораздо более тормозных винтах.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>>Еще шедуллер ОС может отслеживать концы SP/SC очередей у процесса и держать его поближе к партнерам.
R>Зачем тут шедулер ОС?

А что как не шедуллер ОС раскидывает потоки по ядрам?

R>Я правильно понял мысль, что в канал потоку может писать произвольное кол-во других потоков. Но если в программе данному конкретному потоку пишет только один другой поток, то сингулярити это гарантированно детектирует и будет использовать более оптимальную реализацию очереди?
Концы каналов могут свободно мигрировать между потоками.
В том числе и внутри других каналов.
Но в один момент времени один конец может находится только в одном потоке.
Также зная состояние конца канала можно точно сказать является ли этот конец в данный момент потребителем или производителем.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Об этом я и говорю. Решения нет. Если у нас N = M = 1, то на вот он ботлнек на лицо.
WH>А если нет?
WH>У меня таких ситуаций нет даже на отладочных демонах.
WH>А на продакшене будет скорее что-то типа N = M = 100 это очень сильно зависит от задач и железа.
WH>Так что изивини но мимио.

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

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

Вот я и предлагаю рассмотреть вариант *НЕ* благоприятный для передачи сообщений. Когда структура часто модифицируется, поэтому копировать и реплицировать её не целесообразно. Структура очень большая, сравнимая с размером ОП.
Для кэшей вот например как бывает. Можно взять N = 100, но тогда и кэшировать сможем в 100 раз меньше информации. А если взять N = 1, то тогда кэшировать сможем в 100 раз больше информации.

Либо считаешь, что в принципе вообще нет таких ситуаций, когда нельзя применить полное копирование + атомарная подмена?

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

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

R>>А откуда такая уверенность? Сколько в "типичном" сервере на 32-процессорной машине занимают издержки на кэш?
WH>По сравнению с фиксацией транзакции на винте?
WH>Ты серьезно?

Да, именно по сравнению с фиксацией на винте. И я абсолютно серьезно.

Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с. Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с. А если размер транзакции 256 байт, то — 1.5 млн т/с.
Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.

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

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

R>>Вот тут не очень понятно. Точнее совсем не понятно. Как можно логически изменяемые данные просто сделать не изменяемыми на уровне системы типов и все?

WH>Данных которые можно очень легко сделать неизменяемыми сильно больше чем кажется.

Да, есть такое. Это идет от старого "одногопоточного" мышления разработчиков. Многие исторически привыкли просто не обращать на это внимания, т.к. в однопоточной среде нет никакой разницы между изменяемым и неизменяемым, между записью и чтением. Ну разьве что, если язык поддерживает константность, то можно сделать сделать логически немного более красиво, объявив что-то константным. В многопоточном же мире это имеет колоссальное значение.

Тем не менее, ЭТО НИКАК НЕ ИЗМЕНЯЕТ ТОГО ФАКТА, ЧТО ЕСТЬ И *ИЗМЕНЯЕМЫЕ* ДАННЫЕ.
С неизменяемым всё хорошо, пожалуйста, никаких возражений. Но давай же теперь наконец рассмотрим ситуацию, если у нас есть изменяемые данные, и не можем никак спроектировать вокруг этого!

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

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

R>Что бы понять насколько технология хороша в общем случае, т.е. для *всех* случаев, надо пытаться её противопоставить не благоприятным для неё условиям, а наиболее НЕблагоприятным.
R>Никто не спорит, что передача сообщений очень хороша в некоторых случаях. Можно противопоставлять благоприятным условиям, но это даёт практически 0 информации, не считая маркетинговой.
Нужно понимать что любую технологию можно сломать.
Другое дело что сделать это идя от реальной задачи оооочень сильно сложнее.

R>Поэтому я не понимаю твоей позиции в разговоре, никто не спорит, что WolfHound смог очень хорошо применить передачу сообщений для какой-то конкретной задачи. Но это никак не опровергает мой тезис, что системы исключительно на обмене сообщениями могут быть очень не оптимальными в некоторых ситуациях.
Каких?

R>Вот я и предлагаю рассмотреть вариант *НЕ* благоприятный для передачи сообщений. Когда структура часто модифицируется, поэтому копировать и реплицировать её не целесообразно. Структура очень большая, сравнимая с размером ОП.
Что за структура?

R>Для кэшей вот например как бывает. Можно взять N = 100, но тогда и кэшировать сможем в 100 раз меньше информации. А если взять N = 1, то тогда кэшировать сможем в 100 раз больше информации.
Для кешей ооочень хорошо работает url-хешь.
И этот самый url-хешь очень легко разрешает данную делему.

R>Либо считаешь, что в принципе вообще нет таких ситуаций, когда нельзя применить полное копирование + атомарная подмена?
Полное не обязательно.
Часто можно делать инкрементальные структуры в которых нужно создать O(log(N)) или вобще O(1) новых узлов.
Остальное старые данные.
А мосорщик со временем приберется.
Кстати на неизменяемых структурах данных он может быть реализован сильно эффективней.
У меня есть подозрение что ГЦ паузу на неизменяемых кучах можно будет свести к барьеру памямяти во всех потоках.

Можешь сам посмотреть на реализацию неизменяемых бинарных деревьев. Или на rope.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

WH>Ты их не представил.

Так бы и сказал, что нужен реалистичный пример.
Ну вот допустим сервер онлайн игры. Надо хранить модель мира. Игроки постоянно модифицируют модель своими действиями, плюс модификации по таймерам. Взаимодействия хаотичны, т.е. игроки постоянно взаимодействуют с разными частями мира. Потенциально возможно взаимодействие любого игрока с любой частью мира.
Если есть статическая неизменяемая часть мира, то она нас сейчас не интересует. Допустим, что она реализована как неизменяемая и бог с ней.

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

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

R>и не можем никак спроектировать вокруг этого!
Вот в это я почему то не верю.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с.
В самом самом благоприятном случае которого никогда не бывает.
Ибо необходимо обеспечить строго последовательную запись.

И я тебе больше скажу: В действиетльно критических местах RAID не используют. Уж больно они непредсказуемы и ненадежны.
Только софтовая репликация на простые винты без надстроек.

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

R>Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с. А если размер транзакции 256 байт, то — 1.5 млн т/с.
R>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
Тебе в любом случае понадобится процесс который будет писать все на винт.
И это будет один процесс. Те нужна по крайней мере одна MP/SC очередь.
Ибо если их будет больше то под такой нагрузкой ты сразу получишь деградацию производительности винтов на порядки.

Так что тут нужно ну очень сильно думать.
Причем нужно действовать от задачи.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>Ибо если их будет больше то под такой нагрузкой ты сразу получишь деградацию производительности винтов на порядки.
Кстати, на flash'евых винтах НУЖНО более одного процесса запускать (или использовать что-то типа AIO/Overlapped IO) — так как там они в несколько аппаратных каналов параллельно умеют писать.

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

R>>Либо считаешь, что в принципе вообще нет таких ситуаций, когда нельзя применить полное копирование + атомарная подмена?

WH>Полное не обязательно.
WH>Часто можно делать инкрементальные структуры в которых нужно создать O(log(N)) или вобще O(1) новых узлов.

А-а-а. Частично изменяемые структуры (PCOW, partial copy-on-write) это уже совсем другое. На высоком уровне они уже модифицируемые структуры со всеми вытекающими — потенциально надо делать блокировки, что бы обеспечить консистентность. То, что отдельные маленькие кусочки подменяются целиком, уже больше становится деталью реализации.
Со списками и деревьями реализация более-менее понятна, а вот с произвольными графами становится значительно труднее. Т.к. надо вычленить часть графа, сделать для него обновленную копию и как-то атомарно подменить, и как-то решить вопрос, если кто-то ещё меняет эту же часть графа.
И уж как это решать на основе обмена сообщениями, я совсем не представляю...

WH>Остальное старые данные.
WH>А мосорщик со временем приберется.
WH>Кстати на неизменяемых структурах данных он может быть реализован сильно эффективней.
WH>У меня есть подозрение что ГЦ паузу на неизменяемых кучах можно будет свести к барьеру памямяти во всех потоках.

А как быть с указателями в старых узлах? Они же должны обновляться, что бы указывать на новые. Это же уже не COW, это — PCOW.

WH>Можешь сам посмотреть на реализацию неизменяемых бинарных деревьев. Или на rope.

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

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

[]

Разрешу себе вклиниться в дискуссию. Вы с remark'ом просто говорите про разные задачи. Если между очередьми нужно слать реально большие данные, и они mutable по поред., то копирование не имеет никакого смысла. И тогда мы приходим к тому, что хранить их нужно где-то отдельно. Тогда получается, что все эти очереди не решают почти никаких проблем, кроме убирания всего синхронизирующего добра под капот.

Именно поэтому мы не видим всемирной экспансии эрланга.

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

R>>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с.
WH>В самом самом благоприятном случае которого никогда не бывает.
WH>Ибо необходимо обеспечить строго последовательную запись.

WH>И я тебе больше скажу: В действиетльно критических местах RAID не используют. Уж больно они непредсказуемы и ненадежны.
WH>Только софтовая репликация на простые винты без надстроек.

WH>RAID это для бедных.
WH>Ну или как вариант можно использовать десятый на одноранговых (одна сдохнет никто кроме админов и не заметит) реверсных проксях под дисковый кешь.

Я поражаюсь твоей способности уводить разговор в сторону!
Так что по сути? Я пока вижу только очень сравнимые цифры, того что бы запись на диск была бы на 3 порядка медленней я не вижу. Ну не RAID, а ещё что-нибудь. Ну не 320 Мб/с, а 100 Мб/с. Принципиально ничего не меняется.

R>>Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с. А если размер транзакции 256 байт, то — 1.5 млн т/с.
R>>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
WH>Тебе в любом случае понадобится процесс который будет писать все на винт.
WH>И это будет один процесс. Те нужна по крайней мере одна MP/SC очередь.

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

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

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

R>>Покажи на примере. Допустим есть множество лицевых счетов. На сервер поступает поток транзакций вида: изменить баланс л/с, перевести сумму с одного л/с на другой л/с, получить баланс л/с, открыть новый л/с и т.д.
R>>Как тут сделать данные не изменяемыми на уровне системы типов?

WH>Эти данные будут жить в базе данных по любому.
WH>Те ACID в полный рост с фиксацией на гооооораздо более тормозных винтах.

Ну так может мы сами и делаем специализированную БД.
Лог операций пишем в журнал. Учитывая скорость винтов, мы можем писать сотни тысяч записей в секунду.
Так что вопрос остается открытым — как нам реализовать "программную часть".

Если используется промышленная БД, то тоже вполне можно писать более 100'000 записей в секунду. Развитые БД специально для этого предоставляют интерфейс для потокового сохранения записей. В Oracle это Direct Path Loading, в PostgreSQL — COPY BINARY.
А что бы обеспечить обработку потока в 100'000 записей в секунду надо ого-го как потрудиться. Я не думаю, что вот так просто получится что-то тяп-ляп сделать, да что б ещё потом сказать "глядите, все упирается в диски, а наш сервер практически не загружен". И если речь идёт об SMP сервере, то вопрос о доступе к данным в многопоточном окружении тут будет одним из самых сложных.

Здравствуйте, Константин Л., Вы писали:

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

КЛ>[]

КЛ>Разрешу себе вклиниться в дискуссию. Вы с remark'ом просто говорите про разные задачи. Если между очередьми нужно слать реально большие данные, и они mutable по поред., то копирование не имеет никакого смысла. И тогда мы приходим к тому, что хранить их нужно где-то отдельно. Тогда получается, что все эти очереди не решают почти никаких проблем, кроме убирания всего синхронизирующего добра под капот.

Да вроде как не про разные. WolfHound говорит, что таких задач просто нет (по-крайней он не видит, а никто не может привести реалистичный пример):

http://www.rsdn.ru/forum/message/2969533.1.aspx
http://www.rsdn.ru/forum/message/2969579.1.aspx

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

R>>Я правильно понял мысль, что в канал потоку может писать произвольное кол-во других потоков. Но если в программе данному конкретному потоку пишет только один другой поток, то сингулярити это гарантированно детектирует и будет использовать более оптимальную реализацию очереди?
WH>Концы каналов могут свободно мигрировать между потоками.
WH>В том числе и внутри других каналов.
WH>Но в один момент времени один конец может находится только в одном потоке.
WH>Также зная состояние конца канала можно точно сказать является ли этот конец в данный момент потребителем или производителем.

Вообще интересно. Т.е. подсоединили к косумеру одного продьюсера — за кулисами создалась spsc очередь. Потом подключили второго — за кулисами очередь изменилась на mpsc. Потом убрали первого — очередь опять изменилась на spsc.
Надо подумать...

Здравствуйте, Константин Л., Вы писали:

КЛ>Разрешу себе вклиниться в дискуссию. Вы с remark'ом просто говорите про разные задачи. Если между очередьми нужно слать реально большие данные, и они mutable по поред., то копирование не имеет никакого смысла. И тогда мы приходим к тому, что хранить их нужно где-то отдельно. Тогда получается, что все эти очереди не решают почти никаких проблем, кроме убирания всего синхронизирующего добра под капот.
Задачу в студию.

КЛ>Именно поэтому мы не видим всемирной экспансии эрланга.
Не по этому.
Эрлаг динамически типизированный язык.
Динамически типизированные языки не могут работать быстро. Просто никак.
Именно по этому экспансии эрланга и не будет.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Именно. Я ничего против очередей вообще и не говорил. Я наоборот говорил, что если их можно применить, то замечательно. На всякий случай процитирую себя:
Еще раз: В данном случае нам просто необходим ровно один процесс который пишет на винт.
Иначе мы получим просто дикую деградацию винта.
Я сам видел деградацию винта на 60М/С (точно не помню) до 0.5М/С.
И это еще кешь файловой системы использовался... а тут нужно писать мимо кеша сразу на винт.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>А-а-а. Частично изменяемые структуры (PCOW, partial copy-on-write) это уже совсем другое.
Нет. ты не понял.
Они вобще неизменяемые.
Просто большая часть новой структуры это все таже старая.
При этом старая вобще не меняется. Ни на бит.
Без мусорщика это не работает. Но кто сказал что нам нужно мучатся без мусорщика?

R>На высоком уровне они уже модифицируемые структуры со всеми вытекающими — потенциально надо делать блокировки, что бы обеспечить консистентность. То, что отдельные маленькие кусочки подменяются целиком, уже больше становится деталью реализации.
С деревьями и списками вобще все просто.
Они очень лего реализуются вобще не изменяемыми.

R>Со списками и деревьями реализация более-менее понятна, а вот с произвольными графами становится значительно труднее. Т.к. надо вычленить часть графа, сделать для него обновленную копию и как-то атомарно подменить, и как-то решить вопрос, если кто-то ещё меняет эту же часть графа.
А с графами по любому звиздец.
Те что-бы мы не делали, а всеравно придется выкручитваться проблемнозависимыми методами.

R>А как быть с указателями в старых узлах? Они же должны обновляться, что бы указывать на новые. Это же уже не COW, это — PCOW.
Так в фоне обновляем. Причем если железо позволяет то пишем мимо кеша.
А дальше барьер памяти...

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

C>Кстати, на flash'евых винтах НУЖНО более одного процесса запускать (или использовать что-то типа AIO/Overlapped IO) — так как там они в несколько аппаратных каналов параллельно умеют писать.
Я с ними дел пока не имел.
Так что паттерны эффективной работы с такими винтами не знаю.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Так бы и сказал, что нужен реалистичный пример.
R>Ну вот допустим сервер онлайн игры. Надо хранить модель мира. Игроки постоянно модифицируют модель своими действиями, плюс модификации по таймерам. Взаимодействия хаотичны, т.е. игроки постоянно взаимодействуют с разными частями мира. Потенциально возможно взаимодействие любого игрока с любой частью мира.
R>Если есть статическая неизменяемая часть мира, то она нас сейчас не интересует. Допустим, что она реализована как неизменяемая и бог с ней.
В данном случае речь может идти только о кластере. Ибо если сервер не масштибируется то игра сдохнет как только станет хоть скольконибудь популярной.
А в случае кластера нам ну никак без обмена сообщениями не обойтись.
Ибо шарить нам нечего.
С произвольными частями мира игроки не взаимодействуют ни в одной из извесных мне игр. (хотя я не особо любитель MMORPG)
Везьде есть либо деление на сектора. Либо под группу просто создают клон вселенной.

... << RSDN@Home 1.2.0 alpha rev. 745>>

КЛ>>Именно поэтому мы не видим всемирной экспансии эрланга.
WH>Не по этому.
WH>Эрлаг динамически типизированный язык.
WH>Динамически типизированные языки не могут работать быстро. Просто никак.
WH>Именно по этому экспансии эрланга и не будет.

во-первых эрланг у нас не единственный, во-вторых в задачах, где он используется, его слабая скорость не играет роли

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

R>Вообще интересно. Т.е. подсоединили к косумеру одного продьюсера — за кулисами создалась spsc очередь. Потом подключили второго — за кулисами очередь изменилась на mpsc. Потом убрали первого — очередь опять изменилась на spsc.
Нет. В сингулярити каналы всегда spsc.
Другое дело что в зависимости от состояния канала производитель с потребителем иногда меняются местами.
Таким образом возможно создавать диалоги.
Временами оба конца могут находится в состоянии потребителя. Это случается когда один уже все сказал, а второй еще на все прочитал. Как только прочитает станет производителем.
А за тем чтобы оба не попытались говорить следит конечный автомат который проверяет система типов (в сингулярити сделано несколько тупее но такая система типов возможна).

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

C>>Кстати, на flash'евых винтах НУЖНО более одного процесса запускать (или использовать что-то типа AIO/Overlapped IO) — так как там они в несколько аппаратных каналов параллельно умеют писать.
WH>Я с ними дел пока не имел.
WH>Так что паттерны эффективной работы с такими винтами не знаю.
Пора присматриваться: http://www.i4u.com/article17560.html

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

WH>С произвольными частями мира игроки не взаимодействуют ни в одной из извесных мне игр. (хотя я не особо любитель MMORPG)
Есть такие. Например, Lineage II — там один большой мир, без деления на секторы. Как они это делают мне и самому интересно.

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

C>Есть такие. Например, Lineage II — там один большой мир, без деления на секторы. Как они это делают мне и самому интересно.
И все все игроки в одном мире?
Или есть куча паралельных миров в каждом из которых тусуется относительно небольшая (100-200) кучка игроков?

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, Константин Л., Вы писали:

КЛ>тут я не спец. remark пусть придумывает. только не надо говорить, что таких не существует

Что-то у него пока плохо получается.

КЛ>во-первых эрланг у нас не единственный,
И что еще?

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

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>Здравствуйте, Константин Л., Вы писали:

КЛ>>Разрешу себе вклиниться в дискуссию. Вы с remark'ом просто говорите про разные задачи. Если между очередьми нужно слать реально большие данные, и они mutable по поред., то копирование не имеет никакого смысла. И тогда мы приходим к тому, что хранить их нужно где-то отдельно. Тогда получается, что все эти очереди не решают почти никаких проблем, кроме убирания всего синхронизирующего добра под капот.

WH>Задачу в студию.

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

Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.

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

C>>Есть такие. Например, Lineage II — там один большой мир, без деления на секторы. Как они это делают мне и самому интересно.
WH>И все все игроки в одном мире?
WH>Или есть куча паралельных миров в каждом из которых тусуется относительно небольшая (100-200) кучка игроков?
Миров там несколько (штук 6), но в каждом мире запросто до 10000 игроков бывает.

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

[]

КЛ>>во-первых эрланг у нас не единственный,
WH>И что еще?

а что нам мешает делать подобный системы на стат. тип. языках?

КЛ>>во-вторых в задачах, где он используется, его слабая скорость не играет роли
WH>В любом случае низкая скорость фатальный недостаток.
WH>Причем она просто теоритически не может стать высокой.
WH>Ибо типизация динамическая, а значит ничего не наоптимизировать.

ну это понятно. Хотя где там у нас аннотации типов ввели?

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

C>Пора присматриваться: http://www.i4u.com/article17560.html

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

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Ну так может мы сами и делаем специализированную БД.
В случае специализированной базы можно использую лазейки в задаче срезать углы.
Так что нам по любому нужна конкретная задача чтобы ее анализировать.

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

R>Так что вопрос остается открытым — как нам реализовать "программную часть".
Зависит от задачи.
Возможно что и никак. Те вобще никак. Ни тушкой ни чучелом ни кластером.
А если можно кластеризовать то с SMP и подавно проблем не будет.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Вообще интересно. Т.е. подсоединили к косумеру одного продьюсера — за кулисами создалась spsc очередь. Потом подключили второго — за кулисами очередь изменилась на mpsc. Потом убрали первого — очередь опять изменилась на spsc.

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

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

Здравствуйте, Константин Л., Вы писали:

КЛ>а что нам мешает делать подобный системы на стат. тип. языках?
Ничего.
Но их пока нет.
Только и всего.
Вот когда будут тогда и посмотрем кто кого порвет.
.NET с жабкой не подходят.
Системой типов не вышли.

КЛ>ну это понятно. Хотя где там у нас аннотации типов ввели?
Бесполезно.
Нужна тотальная статическая типизация.
Максимум контролируемые касты к интерфейсам аля dynamic_cast.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Ну так может мы сами и делаем специализированную БД.

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

Задачка приведена несколькими постами выше, там где увёл разговор в сторону на диски.

R>>Лог операций пишем в журнал. Учитывая скорость винтов, мы можем писать сотни тысяч записей в секунду.

WH>Тут нужно по любому один пишущий процесс. Иначе не видать нам и близко нужной производительности.

Ну пожалуйста-пожалуйста, пишет один. Но у нас же у сервера задача не только писАть, он ещё что-то потом должен делать.
Теперь попытаемся вернуться к исходной теме разговора. Сервер. Лицевые счета. Переводы со счёта на счёт...

R>>Так что вопрос остается открытым — как нам реализовать "программную часть".

WH>Зависит от задачи.
WH>Возможно что и никак. Те вобще никак. Ни тушкой ни чучелом ни кластером.

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

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

R>Понятно... Но это опять же частный оптимизированный случай.
Достаточный в подавляющем большенстве случаев.

R>Не понятно как тут делать лоад-балансинг. Централизованные лоад-балансеры слишком дорогие, с ними не сделаешь элемент работы меньше десятка тысяч тактов. Децентрализованный на основе spsc очередей... задачка не тривиальная... и скорее всего тоже не имеющая эффективного решения. А на других типах очередей децентрализованный делается значительно легче...
Тут опять нужно смотреть что за балансер у нас.
Да никто и не говорил что нужно всегда жить только на spsc очередях.
mpsc + urlhash могут ой как сильно разгрузить систему.

А mpmc я что-то както побаиваюсь. Мутные они какието.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Именно. Я ничего против очередей вообще и не говорил. Я наоборот говорил, что если их можно применить, то замечательно. На всякий случай процитирую себя:
WH>Еще раз: В данном случае нам просто необходим ровно один процесс который пишет на винт.
WH>Иначе мы получим просто дикую деградацию винта.
WH>Я сам видел деградацию винта на 60М/С (точно не помню) до 0.5М/С.
WH>И это еще кешь файловой системы использовался... а тут нужно писать мимо кеша сразу на винт.

Хорошо. Записываем из одного потока. А вся остальная работа (должна же быть какая-то) делается из всех потоков.
Тут мы просто отвлеклись и установили, что диск НЕ будет особо узким местом.

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

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

R>>А-а-а. Частично изменяемые структуры (PCOW, partial copy-on-write) это уже совсем другое.
WH>Нет. ты не понял.
WH>Они вобще неизменяемые.
WH>Просто большая часть новой структуры это все таже старая.
WH>При этом старая вобще не меняется. Ни на бит.

Ааа. Ну так опять оптимизация применимая для очень частного случая. Что-то типа — в голову списка добавляются новые элементы. Правильно?

Я могу ещё круче предложить. Все данные сводим в одному int'у. Далее читаем и пишем их из произвольного числа потоков. Никакой синхронизации не надо. Все задачи, которые не сводятся к int'у объявляем не решаемыми. Серебрянная пуля готова!

WH>Без мусорщика это не работает. Но кто сказал что нам нужно мучатся без мусорщика?

Это совершенно не проблема. Именно для таких задач существуют экстремально эффективные алгоритмы сборки мусора, с которыми GC общего назначения просто не может конкурировать. Причём можно выбрать и настроить алгоритм под конкретную ситуацию: кол-во записей, размер мусора и т.д. На С++ они реализуются достаточно тривиально. И я знаю прецедент реализации такого алгоритма в Java, в обход штатного GC, т.к. он с такой задачей справлялся плохо.

R>>Со списками и деревьями реализация более-менее понятна, а вот с произвольными графами становится значительно труднее. Т.к. надо вычленить часть графа, сделать для него обновленную копию и как-то атомарно подменить, и как-то решить вопрос, если кто-то ещё меняет эту же часть графа.
WH>А с графами по любому звиздец.
WH>Те что-бы мы не делали, а всеравно придется выкручитваться проблемнозависимыми методами.

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

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

WH>А mpmc я что-то както побаиваюсь. Мутные они какието.

Я тоже

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

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

R>Ну пожалуйста-пожалуйста, пишет один. Но у нас же у сервера задача не только писАть, он ещё что-то потом должен делать.
R>Теперь попытаемся вернуться к исходной теме разговора. Сервер. Лицевые счета. Переводы со счёта на счёт...
Еще раз: Для того чтобы выжать из мурочки еще 100 грамм нужно знать задачу в мелочах.
В данном случае решение очень сильно начинает зависеть от того сколько этих счетов.
Как часто транзакции хотят иметь доступ к одному и томуже счету.
Какие еще действия нам нужны с этими счетами.
...

Скажем если у нас очень много коллизий то у нас просто нет выбора кроме как загнать все транзакции в один поток.
Хотя подготовительные (парсинг итп) действия можно и распаралелить.

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

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Ааа. Ну так опять оптимизация применимая для очень частного случая. Что-то типа — в голову списка добавляются новые элементы. Правильно?
Этих частных случаев сильно больше чем может показаться на первый взгляд.

R>Это совершенно не проблема. Именно для таких задач существуют экстремально эффективные алгоритмы сборки мусора, с которыми GC общего назначения просто не может конкурировать.
А ГЦ на неизменяемой куче?

R>Вот и нашли ещё один хороший пример.
R>А проблема такая, что нужен именно граф. Или ты хочешь сказать, что в программном обеспечении графы тоже вообще не применяются?
Сферические в вакууме?
Думаю что нет.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>Здравствуйте, Константин Л., Вы писали:

КЛ>>а что нам мешает делать подобный системы на стат. тип. языках?
WH>Ничего.
WH>Но их пока нет.
WH>Только и всего.
WH>Вот когда будут тогда и посмотрем кто кого порвет.
WH>.NET с жабкой не подходят.
WH>Системой типов не вышли.

почему не подошли? что-то не вижу причин

КЛ>>ну это понятно. Хотя где там у нас аннотации типов ввели?
WH>Бесполезно.
WH>Нужна тотальная статическая типизация.
WH>Максимум контролируемые касты к интерфейсам аля dynamic_cast.

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

C>>Пора присматриваться: http://www.i4u.com/article17560.html

WH>Выглядит круто.
WH>Но пака мало понятно что именно от него ждать.
WH>Вот когда он мне попадет в руки вот тогда и посмотрим что он может.
WH>И в каких сценариях работает хорошо, а в каких дохнет.
Угу, я жду пока мне пришлют экземпляр. Жаль только, что они пока будут стоить порядка $5000.

Здравствуйте, Константин Л., Вы писали:

WH>>.NET с жабкой не подходят.
WH>>Системой типов не вышли.
КЛ>почему не подошли? что-то не вижу причин
Их системы типов дырявые как решето.
Неизменяемых данных нет.
Отсутствие возможности на этапе компиляции отловить рейскондишены.
Есть статические переменные.
...
Даже в сингулярити все плохо.
Например наличие выделенного меня очень растроело

        public static int Main(String[] args)
        {
            ExtensionContract.Exp! ec = S3TrioResources.Values.ec.Acquire();
            ServiceProviderContract.Exp! ve = S3TrioResources.Values.video.Acquire();
            ServiceProviderContract.Exp! te = S3TrioResources.Values.console.Acquire();

            // Create the device
            device = new S3Device(S3TrioResources.Values);
            device.Initialize();

            // Signal I/O system that we are initialized.
            ec.SendSuccess();

            // create a set of all client endpoints connected to the video
            // interface.
            ESet<VideoDeviceContract.Exp:Ready> vs
                = new ESet<VideoDeviceContract.Exp:Ready>();
            // create a set of all client endpoints connected to the text
            // interface.
            ESet<ConsoleDeviceContract.Exp:Ready> ts
                = new ESet<ConsoleDeviceContract.Exp:Ready>();

.....

            // Close the device
            device.Finalize();

            Tracing.Log(Tracing.Audit, "Shutdown");
            delete ec;
            delete te;
            delete ve;
            vs.Dispose();
            ts.Dispose();

            return 0;
        }
    }

Само оно должно закрываться.

Короче от системы типов аля жабка в нормальной ВМ ничего не останется.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Ааа. Ну так опять оптимизация применимая для очень частного случая. Что-то типа — в голову списка добавляются новые элементы. Правильно?

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

Кстати, это ведь уже не обмен сообщениями, правильно? Это уже разделяемая структура? Или я чего-то не понимаю?

R>>Это совершенно не проблема. Именно для таких задач существуют экстремально эффективные алгоритмы сборки мусора, с которыми GC общего назначения просто не может конкурировать.

WH>А ГЦ на неизменяемой куче?

А GC будет несколько в приложении?

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

WH>Здравствуйте, Константин Л., Вы писали:

WH>>>.NET с жабкой не подходят.
WH>>>Системой типов не вышли.
КЛ>>почему не подошли? что-то не вижу причин
WH>Их системы типов дырявые как решето.

в каком плане?

WH>Неизменяемых данных нет.

будут в с# вроде

WH>Отсутствие возможности на этапе компиляции отловить рейскондишены.

будут неизменяемые, может и это придет

WH>Есть статические переменные.
WH>...
WH>Даже в сингулярити все плохо.
WH>Например наличие выделенного меня очень растроело
WH>

WH>        public static int Main(String[] args)
WH>        {
WH>            ExtensionContract.Exp! ec = S3TrioResources.Values.ec.Acquire();
WH>            ServiceProviderContract.Exp! ve = S3TrioResources.Values.video.Acquire();
WH>            ServiceProviderContract.Exp! te = S3TrioResources.Values.console.Acquire();

WH>            // Create the device
WH>            device = new S3Device(S3TrioResources.Values);
WH>            device.Initialize();

WH>            // Signal I/O system that we are initialized.
WH>            ec.SendSuccess();

WH>            // create a set of all client endpoints connected to the video
WH>            // interface.
WH>            ESet<VideoDeviceContract.Exp:Ready> vs
WH>                = new ESet<VideoDeviceContract.Exp:Ready>();
WH>            // create a set of all client endpoints connected to the text
WH>            // interface.
WH>            ESet<ConsoleDeviceContract.Exp:Ready> ts
WH>                = new ESet<ConsoleDeviceContract.Exp:Ready>();

WH>.....

WH>            // Close the device
WH>            device.Finalize();
WH>
WH>            Tracing.Log(Tracing.Audit, "Shutdown");
WH>            delete ec;
WH>            delete te;
WH>            delete ve;
WH>            vs.Dispose();
WH>            ts.Dispose();
WH>
WH>            return 0;
WH>        }
WH>    }
WH>

WH>Само оно должно закрываться.

Что это за язык

? а где же using???

WH>Короче от системы типов аля жабка в нормальной ВМ ничего не останется.

Здравствуйте, Константин Л., Вы писали:

КЛ>Что это за язык

? а где же using???
А using ничего не меняет — его тоже можно забыть поставить.

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

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

R>>Задачка приведена несколькими постами выше, там где увёл разговор в сторону на диски.

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

Да где ж она упирается? Пишем из одного потока 10^6 записей в секунду в журнал. А вся основная обработка идёт в разных потоках параллельно.

R>>Ну пожалуйста-пожалуйста, пишет один. Но у нас же у сервера задача не только писАть, он ещё что-то потом должен делать.
R>>Теперь попытаемся вернуться к исходной теме разговора. Сервер. Лицевые счета. Переводы со счёта на счёт...
WH>Еще раз: Для того чтобы выжать из мурочки еще 100 грамм нужно знать задачу в мелочах.
WH>В данном случае решение очень сильно начинает зависеть от того сколько этих счетов.
WH>Как часто транзакции хотят иметь доступ к одному и томуже счету.
WH>Какие еще действия нам нужны с этими счетами.
WH>...

Счетов — 10^6.
Операции:
Получение баланса по номеру л/с — 56%
Добавление л/с — 2%
Удаление л/с — 2%
Изменение баланса л/с — 20%
Перевод с одного л/с на другой — 20%
Считаем, что операции распределены равномерно по л/с, т.е. коллизии редки.

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

C>Здравствуйте, Константин Л., Вы писали:

КЛ>>Что это за язык

? а где же using???
C>А using ничего не меняет — его тоже можно забыть поставить.

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

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

R>>Ну вот об этом я начал разговор, что на обмене сообщениями некоторые задачи решаются плохо. Теперь согласен?
WH>Я сказал вобще ни как.
WH>Те ни обменом сообщений, ни какими либо другими плясками с бубном.

По крайней мере 3 способа РЕШЕНИЯ:
1. Крупнозернистые блокировки (применяется более 30 лет)
2. Мелкозернистые блокировки (применяется более 30 лет)
3. Программная транзакционная память (применяется более 5 лет)

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

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

R>>Так бы и сказал, что нужен реалистичный пример.
R>>Ну вот допустим сервер онлайн игры. Надо хранить модель мира. Игроки постоянно модифицируют модель своими действиями, плюс модификации по таймерам. Взаимодействия хаотичны, т.е. игроки постоянно взаимодействуют с разными частями мира. Потенциально возможно взаимодействие любого игрока с любой частью мира.
R>>Если есть статическая неизменяемая часть мира, то она нас сейчас не интересует. Допустим, что она реализована как неизменяемая и бог с ней.

WH>В данном случае речь может идти только о кластере. Ибо если сервер не масштибируется то игра сдохнет как только станет хоть скольконибудь популярной.

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

WH>А в случае кластера нам ну никак без обмена сообщениями не обойтись.

Даже если есть обмен сообщениями между машинами, то внутри машин как? Допустим машины — 2-процессорные, 4-ядерные xeon'ы, сами по себе серьёзные звери. И не загрузить их как следует просто не вариант.
Внутри машины-то как будем делать?

WH>Ибо шарить нам нечего.
WH>С произвольными частями мира игроки не взаимодействуют ни в одной из извесных мне игр. (хотя я не особо любитель MMORPG)
WH>Везьде есть либо деление на сектора. Либо под группу просто создают клон вселенной.

Ну вот, хорошо. Есть сектор. Его держит один 2-процессорный, 4-ядерный xeon.

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

Как будем решать?

Здравствуйте, Константин Л., Вы писали:

КЛ>т.е. проблема в том, что нам нужно гарантировать детерминированное удаление, или в том, что оно нужно само по себе? При чем здесь система типов?
При том что только на уровне системы типов можно гарантировать что объекты определенных типов будут детерминированно финализированны.

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, Константин Л., Вы писали:

WH>>Их системы типов дырявые как решето.
КЛ>в каком плане?
В прямом.
Хрен программу проанализируешь.

WH>>Неизменяемых данных нет.
КЛ>будут в с# вроде
Позно.
Вся стандартная библиотека пропитана изменяемыми данными.

WH>>Отсутствие возможности на этапе компиляции отловить рейскондишены.
КЛ>будут неизменяемые, может и это придет
Не придет.
Чтобы их исключить нужно очень сильно систему типов поменять.

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

Но ни из C# ни из жабы их никогда не уберут.

КЛ>Что это за язык

? а где же using???
В топку этот костыль.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>>Этих частных случаев сильно больше чем может показаться на первый взгляд.
R>Кстати, это ведь уже не обмен сообщениями, правильно? Это уже разделяемая структура? Или я чего-то не понимаю?
Неизменяемая структура данных.

WH>>А ГЦ на неизменяемой куче?
R>А GC будет несколько в приложении?
Да.
В любом случае ГЦ на неизменяемой куче может быть совсем паралельным.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

WH>>>А ГЦ на неизменяемой куче?
R>>А GC будет несколько в приложении?
WH>Да.
WH>В любом случае ГЦ на неизменяемой куче может быть совсем паралельным.
Он и на обычной куче может быть совсем параллельным. Тут вообще проблем нет.

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

R>>Для кэшей вот например как бывает. Можно взять N = 100, но тогда и кэшировать сможем в 100 раз меньше информации. А если взять N = 1, то тогда кэшировать сможем в 100 раз больше информации.
WH>Для кешей ооочень хорошо работает url-хешь.
WH>И этот самый url-хешь очень легко разрешает данную делему.

Что такое "url-хешь"? Не могу нагуглить...

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

КЛ>>т.е. проблема в том, что нам нужно гарантировать детерминированное удаление, или в том, что оно нужно само по себе? При чем здесь система типов?
WH>При том что только на уровне системы типов можно гарантировать что объекты определенных типов будут детерминированно финализированны.
Это ты вообще никак не гарантируешь с GC. Он тебе прикончит объекты только когда ему захочется.

А ещё шутки с:

public void finalize()
{
   Thread.sleep(50000000); //Happy new year!
}

Тут уж либо подход С++ нужен со статическими деструкторами хотя бы для подмножества объектов.

Здравствуйте, Константин Л., Вы писали:

КЛ>>>Что это за язык

? а где же using???
C>>А using ничего не меняет — его тоже можно забыть поставить.
КЛ>т.е. проблема в том, что нам нужно гарантировать детерминированное удаление, или в том, что оно нужно само по себе? При чем здесь система типов?
Обе проблемы. См. ниже..

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

C>Это ты вообще никак не гарантируешь с GC. Он тебе прикончит объекты только когда ему захочется.
Есть варианты.

C>А ещё шутки с:
В топку финалайзеры.

C>Тут уж либо подход С++ нужен со статическими деструкторами хотя бы для подмножества объектов.
Плохой подход.
Есть лучше.
Сейчас думаю 2 варианта. У одного одни неудобства при использовании, у другого другие.

При этом в отличии от объектов с деструкторами они оба совместимы с замыканиями и оптимизацией хвостовой рекурсии.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>Что такое "url-хешь"? Не могу нагуглить...
В общем случае это считаем от запроса или его части хешь и по остатку от деления хеша на N отправляем одному из N обработчиков.
В случае с HTTP считаем от url. Отсюда и пошло.
В частности это позволяет очень сильно повысить кешхит.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

[]

C>Тут уж либо подход С++ нужен со статическими деструкторами хотя бы для подмножества объектов.

да, черт возьми, именно к этому я клоню. Однако сейчас WolfHound вспомнить про using, хотя в данном контексте я не стал бы

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

WH>Здравствуйте, Константин Л., Вы писали:

WH>>>Их системы типов дырявые как решето.
КЛ>>в каком плане?
WH>В прямом.
WH>Хрен программу проанализируешь.

ну, ишь че захотел

[]

КЛ>>Что это за язык

? а где же using???
WH>В топку этот костыль.

хе-хе. помню совсем недавно всем известные личности чуть-ли не молились на него

Здравствуйте, Константин Л., Вы писали:

КЛ>да, черт возьми, именно к этому я клоню. Однако сейчас WolfHound вспомнить про using, хотя в данном контексте я не стал бы

Не угадал.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

C>>Это ты вообще никак не гарантируешь с GC. Он тебе прикончит объекты только когда ему захочется.
WH>Есть варианты.
С GC — никаких вариантов. В принципе, можно дать какую-то верхнюю границу времени финализации, но и это уже составляет проблемы.

C>>А ещё шутки с:
WH>В топку финалайзеры.
Точно.

C>>Тут уж либо подход С++ нужен со статическими деструкторами хотя бы для подмножества объектов.
WH>Плохой подход.
WH>Есть лучше.
WH>Сейчас думаю 2 варианта. У одного одни неудобства при использовании, у другого другие.
WH>При этом в отличии от объектов с деструкторами они оба совместимы с замыканиями и оптимизацией хвостовой рекурсии.
А можно хотя бы крактое описание?

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

R>Да, именно по сравнению с фиксацией на винте. И я абсолютно серьезно.
R>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с. Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с.
Это неправда. throughput почти никакого отношения к скорости транзакции не имеет.
Во-первых, он мерится в оптимальных условиях потоковой записи, когда винт выбирает порядок записи секторов самостоятельно. Одиночный Flush скорее всего потребует seek time, который испортит общую картину.
R>А если размер транзакции 256 байт, то — 1.5 млн т/с.
Во вторых, "размер транзакции" — это фикция. Винт оперирует блоками фиксированного размера; в современной жизни это как правило 64kb. Поэтому даже коммит 1 байта потребует flush 64 килобайт, и в самом удачном случае, когда идет только запись в журнал и на позиционирование тратиться не надо, ты получишь всего 5k транзакций в секунду. В реале — еще примерно на порядок меньше. Парни, которые получают 3 миллиона транзакций в минуту, оперируют очень далеким от потребительского железом.
R>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
Welcome to the real world.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

R>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.

Чесно говоря, я уже запутался в вашей длительной дискуссии. Но если вам нужен пример большого массива данных, то посмотрите в сторону словаря процессов в том же Erlang-е. Ведь Erlang хвастается тем, что там можно создавать сотни тысяч процессов в рамках одной VM. Получается, что если есть 100K процессов, и каждый процесс описывается хотя бы 20 байтами, то размер словаря составит ~20Mb.

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

Или это пример из другой оперы?

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

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

R>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.
Ну, если честно, то это не задача. Ведь это не просто данные; задача — в том, чтобы выполнять некоторые модификации. Что такое "изменяются", которое часто и регулярно?
Вот для стека мы знаем O(1) реализацию без модификаций. Там, конечно же, нет никакого массива — ровно потому, что от стека нужно поведение. Которое push и pop.
Массив — это значит get[i]/set[i]. C ним так просто не получится; но есть большой риск, что на самом деле в задаче массив вовсе не нужен. Что на самом деле он используется для хранения какой-то более высокоуровневой структуры, и все эти get и set получают какие-то неслучайные i, и мы можем придумать структуру, которая поддержит все эти вещи без модификаций.

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

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

R>>Что такое "url-хешь"? Не могу нагуглить...

WH>В общем случае это считаем от запроса или его части хешь и по остатку от деления хеша на N отправляем одному из N обработчиков.
WH>В случае с HTTP считаем от url. Отсюда и пошло.
WH>В частности это позволяет очень сильно повысить кешхит.

Блин, ну надо ж было так назвать

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

Я согласен, что это очень хороший приём и он позволяет в части случаев избавиться от "многопоточных" структур данных.
Но опять же не всегда. Во-первых, обязательное требование, что бы данные были связаны с запросами один-к-одному. Контр-пример с лицевыми счетами, который я приводил, я там специально указал операцию перевода с одного л/с на другой, которая делает невозможным партицирование по хэшу л/с. Контр-пример с игровым сервером, который я приводил, я там специально указал, что внутри "сцены" игроки произвольно взаимодействуют с моделью мира, что тоже делает партицирование внутри сцены невозможным. Второе требование — хэш должен быть равномерным, что может быть не так, если есть небольшой поток "тяжелых" запросов.

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

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

R>>Да, именно по сравнению с фиксацией на винте. И я абсолютно серьезно.
R>>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с. Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с.
S>Это неправда. throughput почти никакого отношения к скорости транзакции не имеет.
S>Во-первых, он мерится в оптимальных условиях потоковой записи, когда винт выбирает порядок записи секторов самостоятельно. Одиночный Flush скорее всего потребует seek time, который испортит общую картину.
R>>А если размер транзакции 256 байт, то — 1.5 млн т/с.
S>Во вторых, "размер транзакции" — это фикция. Винт оперирует блоками фиксированного размера; в современной жизни это как правило 64kb. Поэтому даже коммит 1 байта потребует flush 64 килобайт, и в самом удачном случае, когда идет только запись в журнал и на позиционирование тратиться не надо, ты получишь всего 5k транзакций в секунду. В реале — еще примерно на порядок меньше. Парни, которые получают 3 миллиона транзакций в минуту, оперируют очень далеким от потребительского железом.
R>>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
S>Welcome to the real world.

Я несколько раз проводил тесты скорости потоковой загрузки данных в БД. Компьютеры были самые обычные, "домашние", БД на отдельной машине от сервера, локалка 100Mbps частично загруженная. На Oracle и на PostgreSQL.
Скорость загрузки получалась порядка 80'000 записей в секунду. И она всегда упиралась в скорость винта на сервере БД — там стояли обычные IDE со скоростью несколько Мб/с.

Даже такую пропускную способность обеспечить далеко не просто. Что уж говорить, если 80'000 trx/s увеличить хотя бы в пару раз.

Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%. Для чего тогда все эти SMP серверы, если всё упирается в винт. Если бы у всех всё жёстко упиралось в винт, то все бы ставили всякие RAID, SAN и не знаю там чего ещё, а компьютеры бы оставались однопроцессорными.

Коммитить ествественно надо не по одной транзакции. Коммитить надо пачками. Тут вариантов несколько, самые простые:
1. Собирать пачку не более N транзакций, или ждать не более M времени, далее коммитить всё пачкой и только после этого всем отвечать, что транзакции приняты.
2. Сразу отвечать клиентам, что транзакции приняты, а коммитить пачкой потом. Тут есть возможность потерять транзакции. В каких-то ситуациях это допустимо. Тем более, что можно транзакции хранить в shared-memory, тогда что-то потеряется только если компьютер накроется.
3. Сразу отвечать клиентам, что транзакции приняты, а коммитить пачкой потом. Но при этом дополнительно уведомлять клиентов, что транзакция окончательно обработана. Тогда если клиент не получает уведомления об обработке в течение времени X, то он повторно отправляет транзакцию, и уж тут можно разбираться — транзакция в обработке, отложена, или потерялась. Это тоже надежная схема, но при этом с отложенным сохранением.

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

Исходя из всего этого, я считаю утверждение, что всегда все обязательно сохранять в БД, и что всегда всё обязательно жестко упрется в винт, и что поэтому вопросы эффективной организации программной обработки не имеют смысла, — полностью НЕ состоятельным.

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

E>Чесно говоря, я уже запутался в вашей длительной дискуссии. Но если вам нужен пример большого массива данных, то посмотрите в сторону словаря процессов в том же Erlang-е. Ведь Erlang хвастается тем, что там можно создавать сотни тысяч процессов в рамках одной VM. Получается, что если есть 100K процессов, и каждый процесс описывается хотя бы 20 байтами, то размер словаря составит ~20Mb.

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

E>Или это пример из другой оперы?

По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

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

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

R>>Кстати, это ведь уже не обмен сообщениями, правильно? Это уже разделяемая структура? Или я чего-то не понимаю?

WH>Неизменяемая структура данных.

А как новая голова списка распространяется до других потоков? Все потоки уведомляются с помощью сообщений?

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

R>Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%.

Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
Я всего лишь объяснил, почему невозможно получить полтора миллиона коммитов в секунду на винте с 320Mb/s. Потому что ваш дальнейший спор оперирует непониманием причин разницы в 3-4 десятичных порядка во временах дисковых коммитов по сравниению с RAM коммитами.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

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

R>>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.

S>Ну, если честно, то это не задача. Ведь это не просто данные; задача — в том, чтобы выполнять некоторые модификации. Что такое "изменяются", которое часто и регулярно?
S>Вот для стека мы знаем O(1) реализацию без модификаций. Там, конечно же, нет никакого массива — ровно потому, что от стека нужно поведение. Которое push и pop.
S>Массив — это значит get[i]/set[i]. C ним так просто не получится; но есть большой риск, что на самом деле в задаче массив вовсе не нужен. Что на самом деле он используется для хранения какой-то более высокоуровневой структуры, и все эти get и set получают какие-то неслучайные i, и мы можем придумать структуру, которая поддержит все эти вещи без модификаций.

Так я и не говорю, что это задача. Задачу я как раз прошу привести. Поэтому все эти моменты, о которых, ты говоришь должен доопределить тот, кто приведёт конкретную задачу.
И массив я не говорил, я специально написал — "множество" (массив, список, дерево — не важно)". Что угодно, любая структура данных.

S>Вообще, насколько я знаю, задач, для которых есть решение на константных структурах (с приличной асимптотикой), не так уж и много. Для deque, вроде бы, решение есть, но шибко сложное. Для произвольного графа, естественно нету.

Тут дело не только в константных структурах данных. Суть — задача, на которой подход на передаче сообщений ведёт себя не лучшим образом, и где можно более эффективно реализовать с помощью разделяемой структуры данных (даже если речь идёт просто об атомарном регистре — позволяющем атомарную подмену одного объекта другим).
Например, возможность т.н. партицирования по хэшу (url-хэшь) так же может сыграть в пользу обмена сообщениями. Например есть множество лицевых счетов, но все транзакции относятся исключительно к одному л/с. В таком случае мы можем разделить множество л/с на части по кол-ву потоков, и каждый поток будет "однопоточно" работать со своей частью. А управляющий поток будет считать хэш от номера л/с и раскидывать транзакции соотв. рабочим потокам. Такая архитектура хорошо подходит для обмена сообщениями, и как мы можем реализовать существенно лучше на основе разделяемых структур не видится.
Однако стоит ввести операцию перевода денег м одного л/с на другой, как возможность партицирования исчезает. Этот пример я приводил, но WolfHound постоянно уводит разговор в стороны — то на диск, то на то, что это — абстрактная недоопределенная задача...

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

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

R>>Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%.

S>Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
S>Я всего лишь объяснил, почему невозможно получить полтора миллиона коммитов в секунду на винте с 320Mb/s.

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

S>Потому что ваш дальнейший спор оперирует непониманием причин разницы в 3-4 десятичных порядка во временах дисковых коммитов по сравниению с RAM коммитами.

По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске), то получается время на одну транзакцию — 10 мкс. Ну не знаю, мне такое время пока не удавалось получить, максимум, что я получал — 50 мкс, да и то в немного упрощенной ситуации. Соотв. диск работал на 1/5 "мощности".

Не говоря уж о том, что в некоторых ситуациях вообще не надо сохранять на диск.

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

R>По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).

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

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

R>>По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

E>Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).

Я думаю, что WolfHound скажет, что тут слишком не детализировано. А если детализировать, то будет видно где какие углы можно срезать, что бы эффективно реализовать на основе сообщений.
Для маленьких объектов делать полную обновленную копию, и потом рассылать всем новую версию объекта.
Для больших делать частичное обновление, и опять же рассылать всем новую версию объекта.
Плюс использовать url-хэшь (партицирование данных по хэшу), что бы сделать оставшиеся данные вообще "однопоточными".

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

S>Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
И где я это сказал?

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, remark, Вы писали:
R>А как новая голова списка распространяется до других потоков? Все потоки уведомляются с помощью сообщений?
Что значит "все"? Те, кому нужно, получают структуру как сообщение от потока.

R>

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

R>Конкретными цифрами я готов поступиться. Можно их уменьшить на порядок. Я лишь хотел показать, что я не вижу прям ничего такого явного, что бы говорило, что диск — это гарантированный боттлнек с перевесом в несколько порядков, и что поэтому типа вообще не имеет смысла рассматривать вопросы эффективной организации программной обработки.
Я тебе показал. Неужели ты не видишь разницы между 1.5M и 5k? По мне так это 300 раз. Два с половиной десятичных порядка.

R>По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске),
Это ты называешь транзакцией что-то не то, что называют транзакцией все остальные. Еше раз: нельзя делить скорость линейной записи на объем данных коммита.
R>то получается время на одну транзакцию — 10 мкс. Ну не знаю, мне такое время пока не удавалось получить, максимум, что я получал — 50 мкс, да и то в немного упрощенной ситуации. Соотв. диск работал на 1/5 "мощности".

R>Не говоря уж о том, что в некоторых ситуациях вообще не надо сохранять на диск.

R>

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

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

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

S>Я тебе показал. Неужели ты не видишь разницы между 1.5M и 5k? По мне так это 300 раз. Два с половиной десятичных порядка.

Ну 80k я получал на обычном IDE диске... 5k это уж слишком!

R>>По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске),

S>Это ты называешь транзакцией что-то не то, что называют транзакцией все остальные. Еше раз: нельзя делить скорость линейной записи на объем данных коммита.

Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
А остальные что называют сохранением транзакции?

Здравствуйте, remark, Вы писали:
R>Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
R>А остальные что называют сохранением транзакции?
Для СУБД коммитом называют выполнение команды COMMIT, для локального файла — flush буфера, который гарантирует write-through.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

S>Здравствуйте, remark, Вы писали:
R>>Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
R>>А остальные что называют сохранением транзакции?

S>Для СУБД коммитом называют выполнение команды COMMIT, для локального файла — flush буфера, который гарантирует write-through.

Сохранение в БД, естественно, подразумевает COMMIT. Я просто думал, что это очевидно. Извиняюсь за возникшие недоразумения.
Я имел в виду — c COMMIT'ом 80k trx/s.

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

E>>Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).

В общем случае (хотя наверное как раз в частном, но тем не менее) все эти сотни тысяч объектов можно "партицировать" между потоками. Т.е. создаем по потоку на процессор, и далее распределяем все звонки/сессии между этими потоками используя хэш от идентификатора звонка/сессии. Т.е. надо как-то заставить все эти сотни тысяч объектов "смешаться в единое целое", дабы их нельзя было разделить на слабосвязанные множества.

Вот ещё пример. Будем бить по святому — сборщик мусора

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

От:	remark	http://www.1024cores.net/
Дата:	27.04.08 14:10
Оценка:	517 (48)

	От:	SergH
	Дата:	28.04.08 09:43
	Оценка:

	От:	Кодт
	Дата:	28.04.08 15:05
	Оценка:	1 (1) +2

От:	remark	http://www.1024cores.net/
Дата:	05.05.08 17:36
Оценка:

	От:	Константин Л.
	Дата:	06.05.08 23:02
	Оценка:

	От:	RailRoadMan
	Дата:	08.05.08 10:53
	Оценка:	2 (1)

От:	eao197	http://eao197.blogspot.com
Дата:	10.05.08 08:15
Оценка:	20 (1) +1

	От:	Roman Odaisky
	Дата:	12.05.08 19:14
	Оценка:	+2

От:	Sinclair	https://github.com/evilguest/
Дата:	29.05.08 02:39
Оценка:	18 (1)

	От:	WolfHound
	Дата:	29.05.08 10:16
	Оценка:	17 (1)

	От:	dip_2000
	Дата:	11.05.08 05:12
	Оценка:

	От:	CreatorCray
	Дата:	13.05.08 07:29
	Оценка:

	От:	CreatorCray
	Дата:	14.05.08 07:14
	Оценка:

	От:	MaxxK
	Дата:	15.05.08 21:18
	Оценка: