Здравствуйте, Jolly Roger, Вы писали:
R>>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение?
JR>По-моему, это можно решить счётчиком производителей. Будет два дополнительных CAS в enqueue, вне цикла. Тогда dequeue сможет возвращать одно из значений перечисления — OK, empty, busy, а внешний код, соответственно, реагировать либо повтором попытки, либо переходом к другим занятиям. Немного замедлится enqueue, но зато, возможно, получится выигрыш во внешнем по отношению к очереди коде.
Счётчики уже есть — это enqueue_ и dequeue_, через их разницу можно понять. Но речь не об этом, речь о том, что сделать это можно, но это будет бессмысленное усложнение АПИ. Если есть другая работать поделать, то делаем её, зачем вообще ждать. Иначе, попробовать ещё несколько раз имеет смысл *всегда*, т.к. это дешевле переключения потока. Пробовать бесконечное число раз не имеет смысл *никогда*, т.к. это чрезмерно прожигает такты.
З.ы. а за два дополнительных CAS можно поиметь и lock-free очередь без таких нюансов... только это будет еже компромиссное решение относительно мьютекса — медленнее, но lock-free. Моя же очередь win-win относительно мьютекса — и быстрее, и по по гарантиям прогресса лучше.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, vf, Вы писали:
vf>>Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.
R>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?
Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".
R>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
Если он заблокируется на бесконечных попытках — то да это фигня, но это проблемы очереди, но я все же считаю что такое маловероятно, и при малом числе повторных попыток получить элемент поток его все таки получит. Ты же предлагаешь менять архитектуру приложения под очередь, причем под маловероятное событие в этой очереди. Во первых не всегда возможно, во вторых в данном случае не обосновано.
R>Или ты хочешь вставить в код: R>
Вот так, причем хочу я его вставить в саму очередь:
while (message_is_unavailable_but_the_queue_is_not_empty)
item = queue.get();
R>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...
vf>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.
R>Ну так ты покажи, как бы у тебя код различался.
while(x == null)
{
if(queue.isEmpty)
x = create_expensive_object();
else
x = queue.cheap_try_to_get_item();
}
Здравствуйте, vf, Вы писали:
R>>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?
vf>Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".
Если есть другая работа, то надо занимать ей поток сразу. Вероятность вероятностью, а можно очень долго ждать сообщения, которое вроде как в очереди; и с другой стороны можно очень быстро получить сообщение, которого ещё нет в очереди. Это действительно не должно делать принципиальной разницы.
R>>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
vf>Если он заблокируется на бесконечных попытках — то да это фигня, но это проблемы очереди, но я все же считаю что такое маловероятно, и при малом числе повторных попыток получить элемент поток его все таки получит. Ты же предлагаешь менять архитектуру приложения под очередь, причем под маловероятное событие в этой очереди. Во первых не всегда возможно, во вторых в данном случае не обосновано.
Я не предлагаю менять архитектуру, наоборот, я говорю, что не надо различать эти ситуации вообще.
который есть надмножество этого. Ничего больше делать не надо. QED.
R>>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...
vf>>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.
R>>Ну так ты покажи, как бы у тебя код различался.
vf>while(x == null) vf>{ vf>if(queue.isEmpty) vf> x = create_expensive_object(); vf>else vf> x = queue.cheap_try_to_get_item(); vf>}
Замени это на:
for (int try = 0; try != TRY_COUNT; try += 1)
{
if (x = queue.cheap_try_to_get_item())
break;
}
if (x == null)
x = create_expensive_object();
и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, vf, Вы писали:
R>>>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.
vf>>Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.
R>Ну так она и есть переполнена — производители дошли до элемента, который всё ещё не закончил потреблять *самый старый* потребитель. R>Я не понимаю, почему ты в этом пытаешься увидеть плохое. Есть очереди, основанные на мьютексах, с поведением, которое ни у кого не вызывает вопросов. Эта очередь во всех отношениях ведёт себя только лучше. Ты подумай, что было бы если у тебя в мьютекс очереди поток заснул бы посреди операции добавления под мьютексом. Правильно — всё бы встало. Эта же очередь даём там, где это можно, другим потокам спокойно поработать. Например, можно потреблять из других частей очереди, можно добавлять элементы дальше. А блокировать работу других потоков она будет только там, где без этого абсолютно не обойтись.
Вот здесь принципиальный момент — нельзя потреблять из других частей очереди, можно только добавлять!
R>Гляди, что происходит в этой очереди. Допустим очередь пустая. Приходит производитель, начинает класть сообщение в очередь, но перед тем, как установить seq, засыпает. Дальше приходит ещё один производитель и полностью кладёт сообщение в очередь (т.е. возвращается из enqueue()). Дальше приходит потребитель и не находит сообщения. Приходит ещё один потребитель и тоже не находит. Дальше первый тормозной производитель просыпается и устанавливает seq. Теперь возвращаются 2 наших потребителя и забирают сообщения. Правильно?
Правильно, только оцени затраты на ушел пришел и вероятность того что производитель заснул (скорее всего просто шестеренки не так встали), и какой смысл уходить-возвращаться потребителям в этой ситуации, когда каждый из них с очень большой вероятностью повторив попытку получить положительный ответ??? Так еще и архитектура приложения не слабо портиться из-за ушел-пришел, и ведь где-то там куда они ушли им все равно нужно будет как-то учитывать кол-во элементов, чтобы знать что нужно прийти, разве не так?
R>Теперь, что происходит в мьютекс-очереди. После того, как первый поток засыпает под мьютексом, все нафиг блокируются (первый негативный момент — второй производитель мог бы на самом деле положить сообщение). Дальше первый поток просыпается и освобождает мьютекс. Мьютекс захватывает первый потребитель и забирает сообщение (заметь не раньше чем в моей очереди! т.е. только после того, как первый производитель закончил). Теперь мьютекс захватывает второй потребитель и получает отбой — сообщений нет (второй негативный момент — в моей очереди он бы уже получил сообщение). Мьютекс захватывает второй производитель, кладёт сообщение. Мьютекс захватывает второй потребитель, берёт сообщение.
Про мьютексы никто не спорит. Если выбирать между lock vs. lock-free я за lock-free
R>Ты берёшь за отправную точку, что сообщения в очереди есть, а моя очередь такая-плохая не даёт их забирать. Это не так. Отправная точка — это когда всё нафиг обламываются, а моя очередь наоборот даёт во многих ситуациях потокам успешно отработать без блокировки.
Это не нормальное поведени для очереди в класическом ее понимании, как минимум на это нужно было указать в первом посте. Если она себя так ведет то это не совсем очередь. Помимо поток и блокировок, существуют еще данные, вот я приводил пример с сервером, приходит запрос поток пытается положить его в очередь и обламывается, что он должен сделать? Дать отлуп пользователю, при небольшой нагрузке, или куда деть данные чтобы заняться другими вещами??!
R>Когда приходит второй производитель у нас есть 2 выбора: (1) дать ему без блокировки спокойно положить сообщение и пойти заниматься другой полезной работой, или (2) заблокировать и его, не получив ничего взамен. Гляди, когда в очереди блокировки мьютекса заблокирован производитель с готовым сообщением, ты рассматриваешь это сообщение как уже произведённое? Нет? А почему? В чём отличие? Я просто вместо блокировки и переключения контекста даю ему "забуферизировать" своё сообщение.
Где забуферизировать?! У нас очередь для этого, ты предлагаешь городить другой паралельный механизм? Не проще ли повторить попытку?
R>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение? Можно заблокировать второго производителя, что бы он вместо того, что бы положить сообщение в очередь и пойти заниматься полезным делом, бесполезно болтался на мьютексе. Тогда ты не будешь считать, что сообщение "уже произведено", правильно? И? Что ты получил кроме ухудшения ран-тайм свойств? Ничего. Мы стали чаще блокировать потоки, только для того, что бы ты не называл очередь такой-секой, не отдающий уже произведенные сообщения.
Я предлагаю не блокировать, я предлагаю повторять попытки.
Каким полезным делом куда потоку данные пристроить? Выкнуть?
R>Т.е. всё, что мы будем делать, — это дополнительно задерживать некоторые потоки в некоторых местах, только что бы поведение выглядело более логичным для "однопоточного мозга программиста". Совершенно не будет такого, что какие сообщения вдруг станут доступны раньше, ничего подобного, дополнительные задержки не могу к этому привести.
R>Если ты привык работать с алгоритмами, основанными на мьютексах (которые под всеми имеющими смысл взглядами — однопоточные алгоритмы), то тебе надо немного поломать свой мозг, что бы понять как вещи происходят в действительно concurrent системах. Тут зачастую нету порядка между событиями, или сообщение потока может появиться в очереди через долго после того, как он вышел из enqueue() (мы просто не будет задерживать его до этого момента в enqueue()), и т.д.
Ну.. я привык считать приложения с несколькими потоками — многопоточными, а мьютексы или lock-free это лишь способы синхронизации.
Здравствуйте, vf, Вы писали:
vf>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!
Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.
vf>Там нет таких случаев, если ты про ABA.
Что такое ABA?
vf>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...
В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
R>и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.
Это уже вопрос деталей, а именно величины TRY_COUNT = [1..INFINITY], а зависит она от стоимости объекта и вероятности облома при повторной попытке, я вероятность оцениваю как стремящуюся к нулю(даже в твоем примере с высоко-приоритетном потоком), и зависимость здесь обратнопропорциональная следовательно TRY_COUNT -> INF
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, vf, Вы писали:
vf>>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!
L>Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.
vf>>Там нет таких случаев, если ты про ABA.
L>Что такое ABA? http://en.wikipedia.org/wiki/ABA_problem
vf>>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...
L>В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
Здравствуйте, remark, Вы писали:
R>>>Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут: R>>>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc
vf>>Если это так, тогда совсем плохо.
R>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так. R>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать. R>Эта моя очередь тоже не linearizablе.
Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?
Здравствуйте, vf, Вы писали:
R>>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так. R>>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать. R>>Эта моя очередь тоже не linearizablе.
vf>Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?
Мой аргумент очень простой — вот пример кода, который прекрасно работает с мьютекс-очередью, заменяем её на M&S очередь — начинает падать. А это есть основное практическое следствие из linearizability — можно спокойно так заменять и не должно быть никаких видимых изменений в поведении. Они доказывали свойство linearizability в неком академическом абстрактном коне в вакууме, в котором объекты не создаются и не удаляются динамически.
struct tcp_connection
{
queue_t q;
...
};
void connection_thread(tcp_connection* c)
{
for (;;)
{
msg_t* m = c->dequeue();
if (m->type == MSG_DISCONNECT)
{
delete c;
return;
}
process(m);
}
}
void io_dispatch_thread()
{
for (;;)
{
select(...);
for_each(SOCKET s in read_set)
{
recv(s, buf, size);
tcp_connection* c = find_connection(s);
c->enqueue(msg_t(MSG_PACKET, data, size));
}
for_each(SOCKET s in exception_set)
{
tcp_connection* c = find_connection(s);
c->enqueue(msg_t(MSG_DISCONNECT));
}
}
}
Здравствуйте, remark, Вы писали:
R>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера
1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)
2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.
Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой
intptr_t dif = (intptr_t)seq — (intptr_t)pos;
и этой проверкой
if (dif == 0)
значение pos может быть изменено в другом потоке, и проверка будет не валидной. Intel Parallel Inspector это подтверждает:
ID Description Problem Source Function Module State
X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed
X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed
X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed
X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information
Здравствуйте, brankovic, Вы писали:
B>Здравствуйте, remark, Вы писали:
R>>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера
B>1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)
Да, всё правильно. Пока поток работает с ячейкой (копирует в неё или из неё), она фактически залочена.
B>2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.
Тут нет ничего, что бы делало его не "продакш-реди". Попробуй её вставить и увидишь
Здравствуйте, pif_pif, Вы писали:
_>Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой _> intptr_t dif = (intptr_t)seq — (intptr_t)pos; _>и этой проверкой _> if (dif == 0) _>значение pos может быть изменено в другом потоке, и проверка будет не валидной.
Тогда последующий CAS не сработает.
_> Intel Parallel Inspector это подтверждает: _>ID Description Problem Source Function Module State _>X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed _>X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed _>X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed _>X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information
Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?
Здравствуйте, pif_pif, Вы писали:
_>Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?
Разобрался в коде, дезавуирую "мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь". На счет датарейсов пока сказать не могу, продолжаю анализировать.
Здравствуйте, remark, Вы писали:
R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).