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

R>В очередной раз скачал AuthPack, теперь Avira находит в нём некий ADSPY/MDH.A.60 — стрёмно...

Ну, так снеси ее. Authoring Pack просто физически не менялся уже черт знает сколько времени.
Вот здесь можешь взять Authoring Pack 2. Это пока что бэта, но по возможностям она сильно удобнее и в сотни раз быстрее старой.

Она использует .Net Framework 3.5.

R>К тому же не вижу заявленной поддержки OpenOffice, а покупать из-за этого MSOffice...

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

Если Офиса нет, то статью можно присылать и в каком-нибудь другом формате который можно преобразовать в вордовский. Скажем RTF или HTML.

ЗЫ

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

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

NB>ну я краем уха слышал, что для получения к.ф.м.н. нужно сколько-то публикаций.
NB>так и для Дмитрия польза (если решит в аспирантуру пойти), и для народа.

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

Я буду исходить из реальных задач.
Ну например — есть у меня какой-то кусок работы, который я решил распараллелить с помощью OMP. Пусть у меня в нем есть vector в который я запихиваю элементы, в последовательной версии он был один, а в параллельной есть выбор
-я могу оставить его и сделать синхронизацию через criticalsection. Я знаю что один Interlocked займет тиков 70, ну плюс еще затраты на мутекс — пускай 200 тиков = 270 тиков из которых 70 не параллелятся
-могу присобачить lockfree контейнер (предположим что они у вас хорошего качества). Overhead на их использование неизвестен и неизвестно какая часть не распараллеливается в принципе
-могу использовать отдельные вектора и получить overhead только на слиянии. Конечно этим шагом я снижу распараллеливаемость, но эти затраты легко померять

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

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

R>Я буду исходить из реальных задач.
R>Ну например — есть у меня какой-то кусок работы, который я решил распараллелить с помощью OMP. Пусть у меня в нем есть vector в который я запихиваю элементы, в последовательной версии он был один, а в параллельной есть выбор
R>-я могу оставить его и сделать синхронизацию через criticalsection. Я знаю что один Interlocked займет тиков 70, ну плюс еще затраты на мутекс — пускай 200 тиков = 270 тиков из которых 70 не параллелятся
R>-могу присобачить lockfree контейнер (предположим что они у вас хорошего качества). Overhead на их использование неизвестен и неизвестно какая часть не распараллеливается в принципе
R>-могу использовать отдельные вектора и получить overhead только на слиянии. Конечно этим шагом я снижу распараллеливаемость, но эти затраты легко померять

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

И чего тут не хватает? Твоего представления о lock-free алгоритмах?
Если серьёзно, то во-первых никто и не говорит, что какое-то решение подходит для всех проблем. Т.е. постановка не понятна, ты взял какую-то конкретную проблему, и что дальше? Даже если бы ты однозначно заключил, что lock-free алгоритм для неё полностью не подходит, это бы практически ничего не говорило о применимости lock-free алгоритмов. Как говорится — "в Англии есть как минимум одна овца, белая как минимум с одного бока"
Во-вторых, lock-free алгоритм, который содержит 1 атомарную RMW инструкцию на операцию практически всего лучше аналогичного mutex-based алгоритма, т.к. спин-мьютекс всегда содержит эту же самую 1 атомарную RMW инструкцию, а не спин мьютекс будет содержать как минимум 2.
В-третьих, lock-free как таковой — это не о производительности

Автор: remark
Дата: 27.04.08

, и это не надо забывать. Lock-free — это только forward-progress и termination-safety. Наивное, но распространённое, мнение "что вот сейчас я добавлю lock-free, и всё станет быстро и масштабируемо" мягко говоря не верно. Это то же самое, что "вот сейчас я добавлю SSE оптимизации в мою пузырьковую сортировку, и она станет супер-быстрой".
А если делать упор на производительности и масштабируемости, то это несколько другая область алгоритмов, в целом они вполне могут и использовать мьютексы на каких-то путях, и обычно это затрагивает не просто какой-то компонент, а скорее симбиоз между всеми уровнями приложения, начиная с самых высоких, и до самых низких, где производительность и масштабируемость "подкрепляется" некоторыми "lock-free техниками" по необходимости.
Для конкретно твоего примера никакие специальные concurrent контейнеры не нужны, и третий вариант скорее всего самый лучший и намного лучший (тут можно обойтись вообще без мьютексов, достаточно pthread_create/pthread_join). Тем более, что фаза слияния тоже иногда распараллеливается (например, слияние в merge-sort).

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

Единственное что меня интересовало "Зато большинство lock-free алгоритмов ..... будут содержать больше тяжелых атомарных операций (2-5)."
Про все остальное — я в курсе, так что не переживайте — неправильно готовить я их не буду

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

R>Единственное что меня интересовало "Зато большинство lock-free алгоритмов ..... будут содержать больше тяжелых атомарных операций (2-5)."
R>Про все остальное — я в курсе, так что не переживайте — неправильно готовить я их не буду

Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.

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

R>Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.
С чего ты взял что не для скорости?

В условиях той задачи что я описал — скажем если merge займет 10% и не параллелиться (или параллелить его слишком сложно) от последовательного алгоритма, то на 16 процах я получу
10% + (100-10)/16 = ~16% времени т.е. скейл в 6-7 раз а не в 16

в услових lock-free и полного параллелизма
100/16 + х = 6.25% + х, где х — затраты на lockfree

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

PS: ты случаем не с интеля?

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

R>>Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.
R>С чего ты взял что не для скорости?

R>В условиях той задачи что я описал — скажем если merge займет 10% и не параллелиться (или параллелить его слишком сложно) от последовательного алгоритма, то на 16 процах я получу
R>10% + (100-10)/16 = ~16% времени т.е. скейл в 6-7 раз а не в 16

R>в услових lock-free и полного параллелизма
R>100/16 + х = 6.25% + х, где х — затраты на lockfree

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

Может быть и так.
Хотя обычно ситуация несколько сложнее: во-первых, нераспараллеливаемая часть зачастую тоже зависит от N, т.е. может составлять например для mergesort (1/k*logN) (т.е. уменьшается в ростом размерности задачи), во-вторых оверхед решения с разделяемым контейнером тоже будет зависеть от размерности, т.е. будет "100/16 + 100/х". Ну ладно, это всё детали.
Всё равно не понятно при чём тут lock-free. В случае с разделяемым контейнером тебе опять же нужен просто *быстрый* контейнер, а не lock-free контейнер. Контейнер, основанный на мьютексе, может быть просто быстрее при низкой конкуренции; а при высокой и lock-free контейнер начнёт так же отвратительно деградировать.
Хотя, конечно, может так случиться, что lock-free контейнер будет и быстрее. Но в общем случае QoS медленне best-effort, а real-time медленнее не real-time, т.к. им приходится обеспечивать дополнительные гарантии.

з.ы. ради справедливости надо отметить, что очередь в первом посте тоже не lock-free, она скорее больше ориентируется на скорость... насколько это возможно для MP/MC очереди.

R>PS: ты случаем не с интеля?

Нет, я сам по себе.

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

[skipped]

Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?
Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

Спасибо.

Здравствуйте, Мишень-сан, Вы писали:

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

МС>[skipped]

МС>Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?
МС>Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

МС>Спасибо.

А, извиняюсь, прозевал, что там или nothrow, или тривиальный конструктор, или POD, а не всё вместе.
Тогда такой вопрос: насколько сильно может нарушить работу очереди вызов деструктора для изымаемого объекта?

Здравствуйте, Мишень-сан, Вы писали:

МС>>Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?
МС>>Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

МС>А, извиняюсь, прозевал, что там или nothrow, или тривиальный конструктор, или POD, а не всё вместе.
МС>Тогда такой вопрос: насколько сильно может нарушить работу очереди вызов деструктора для изымаемого объекта?


В этой очереди можно сделать частичную поддержать исключений следующим образом. Если исключение происходит при добавлении элемента, то помечаем ячейку специальным флажком. Если при извлечении элемента мы обнаруживаем этот флажок, то помечаем ячейку как потребленную и пробуем извлечь элемент снова. Однако если исключение происходит при копировании во время извлечения элемента, то нам ничего не останется как просто "проигнорировать" этот элемент (т.е. он по-тихому потеряется). Так работает tbb::concurrent_queue.
Изначально я не хотел затуманивать алгоритм этой логикой. Да и в целом считаю, что передавать объекты, которые кидают, и в частности смарт-поинтеры — это не особо нужная затея. Обычно передают или поинтеры или POD структуры.
Хотя в C++0x это можно будет решить и элегантно и эффективно одновременно с помощью move semantics (это как раз то, что доктор прописал — мы же хотим *передать* элемент).

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

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).

а нет ли у тебя случаем lock-free FIFO очереди (с фиксированной длиной) для случая single-producer, single-consumer?
или может есть реализация atomic_uint для linux?

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

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

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

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

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок.

Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?

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

vf>Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?

Ограничений нет, они просто переполнятся в 0, и это должно быть корректно обработано алгоритмом.

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

F> Маленькая запоздалая поправочка — помечать удалённые элементы специальным образом, вызвано тем, что Клиф использует хэш таблицу с открытой адресацией и только.

Очевидно, что это не так. Однопоточные таблицы с открытой адресацией таких проблем не имеют.

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

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

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

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

R>>Очевидно, что это не так. Однопоточные таблицы с открытой адресацией таких проблем не имеют.
R>>
F> Имеют-имеют, когда у нас есть операция удаления. Если удалённый элемент сбросить в пустой, то мы можем разорвать цепочку коллизий, и поиск поломается.

Там мы можем элементарно переместить последний элемент из цепочки на место удаляемого, а тут не может.
Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.
Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).

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

R>    struct cell_t
R>    {
R>        std::atomic<size_t>     sequence_;
R>        T                       data_;
R>    };

Вопрос: а не будет ли тут false sharing'а при такой структуре элемента очереди? Может в нее тоже стоит выравнивание до размера линии кэша добавить?

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

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

R>Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.
R>Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).
Опять же, имхо, но реализация Клифа настолько не прозрачна... оптимизации все эти я думаю он сделал исходя из практики, а не каких-то аналитических заключений. Без доступа к такому железу самому что-то подобное написать — нереально.

PS: Мои изыскания (для C#) показали, что lock-free hashtable с separate chaining для небольших таблиц оказывается быстрее, чем открытая адресация. Но потом открытая конечно рвёт всех. =)