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

>> C>Ну и самое главное преимущество по сравнению со спинлоками —
>> атомарность. В случае со спинлокам нас могут за-preemt'ить пока мы его
>> держим, тогда остальные потоки будут курить бамбук в течение долгого
>> времени.
>> Я не вижу принципиальной разницы с другой ситуацией, когда, например,
>> для некоего ресурса есть менеджер, который обеспечивает изоляцию
>> операций и транзакции, и работает с сообщениями, но у него заполнился
>> буфер незавершенных транзакций. Точно так же все остальные будут стоять
>> и курить бамбук.
C>А как мы в его буффер будем писать? Под блокировкой? :)

C>Проблема в том, что если тебя за-preemt'ят пока ты держишь спинлок — то
C>остальные потоки будут активно продолжать его крутить (офигительные
C>потери производительности на SMP).

Блин. Так потому спинлоки в их стандартном виде и не могут использоваться в среде с насильным preemption в принципе! Причём случай пришедшего "сбоку" процесса ещё как-то реален (хоть и с сильной потерей производительности), а если например обработчик прерывания придёт допущенный — всё, система умер). Если может быть вытеснение текущего процесса — используется какой-нибудь вариант с очередями ожидания на объекте исключения.

И какое отношение это имеет к Вашему тезису — не понимаю. Разве что в том, что я не обратил внимания на "крючок" в Вашем тексте про вытеснение процесса со спинлоком и стал возражать тезису целиком, а не на этот крючок. Согласен, не заметил. Но я и не предполагаю столь намеренно диверсионного дизайна.

C>netch80 wrote:
>> C> А еще есть и wait-free алгоритмы, в которых мы гарантировано никогда
>> не будем ждать. Кстати, доказано, что *любой* параллельный алгоритм
>> можно сделать wait-free. Правда, для многих алгоритмов такая реализация
>> потребует слишком больших расходов памяти.
>> URL? А то что-то по словам "wait-free algorithms" находится только общая
>> вода.
C>Нашел вот тут:
C>http://en.wikipedia.org/wiki/Non-blocking_synchronization#Wait-freedom

Ага. Так там есть замечательная цитата по поводу:

However, the resulting performance does not in general match even naive blocking designs. It has also been shown[3] that the widely-available atomic conditional primitives, compare-and-swap and LL/SC, cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads. Wait-free algorithms are therefore rare, both in research and in practice.

То есть перейти на них, конечно, можно, но результат будет ужасен (см. первое предложение). А по дальнейшему — так как вместо CAS и LL/SC ничего пока не придумали — то вообще думать в эту сторону смысла нет.

>> Видя слово "reprobing loop" можно дальше не читать.:) То есть, может,
>> какое-то ускорение там есть. Но от принципиальной проблемы, что пока
>> твоя нить думает, что делать с данными, другая в них вмешивается — ты
>> таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и
>> вылезти боком — если у тебя работа более сложная, чем установка лока.
C>Нет, нет и еще раз нет. Пока ты думаешь что делать с данными — ты НЕ
C>держишь блокировок в lock-free. Другие потоки могут спокойно в него
C>продолжать писать.

А я, по-Вашему, о чём говорю?;)) Да, не держишь блокировок. Именно поэтому, когда ты уже пошёл менять данные так, как тебе нужно — будь готов, что данные к этому времени изменились и замена может обломиться. А тогда — начинать всё сначала — тот самый reprobing loop. Да, и цитата из того же:

Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion.

C> То что твоя очередь за время думанья может стать
C>длиннее экватора Юпитера — это уже другая проблема.

Нет, это не проблема как таковая. Проблема в том, что в случае lock-free получается та же блокировка, но вид сбоку. Потребителю результата (например, автору кода который использует malloc()) обычно совершенно по барабану, как там сделано — мьютекс или lock-free. При одновременном входе с двух процессоров в случае мьютекса один процессор успеет быстрее другого сделать CAS на объект мьютекса, а в случае lock-free — на общие данные, а второй будет или сонно, или решительно, но курить бамбук и уходить на следующий круг. Решительно не вижу, чем второй вариант выгоднее первого для всех случаев. При редких столкновениях за доступ — да, он выгоднее. При частых — скорее наоборот.

C>Собственно, та hash map масштабируется до 4 тысяч одновременно пишущих и
C>читающих процессоров :) Неплохо, ИМХО.

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

В остальном — да, симпатичная работа.:)