Здравствуйте, vf, Вы писали:
vf>Но основная находка именно в том коде который я уже выложил, с push все более-менее понятно, а вот pop имхо интересный получился. По поводу проверок, я этот класс мучал в тестах — несколько потоков выполняю pop-push и проверяют. И плюс, в процессе поиска решения наткнулся на МС-оский CHESS — тоже запускал — не знаю насколько я правильно это сделал — но он проблем тоже не выявил.
CHESS использует т.н. context-bound планировщик потоков с ограничением на кол-во недобровольных прерываний потоков по-умолчанию 2. Эта же ошибка проявляется только при 3 потоках и как минимум 5 (!) недобровольных прерываниях. Подозреваю, что у CHESS уйдут недели, что бы её найти.
Relacy же по-умолчанию использует случайный планировщик, которому фиолетово на кол-во прерываний. Как следствие он находит ошибку пока я отпускаю кнопку enter
Здравствуйте, remark, Вы писали:
R>И добавить к нему ABA-counter вместо постоянно создания и разрушения вспомогательных объектов.
Да, идея понятна. Но не несет ли такой подход потенциальную опасность, по сути мы же просто снижаем вероятность ABA, понятно что очень сильно. А с ростом производительности вероятность растет. Я продумывал, вариант, когда ABA-counter будет свой у каждого элемента — но опять же это вероятность, хотя по логике и чуть меньше. А что там за второй подход, с упором на GC?
Здравствуйте, vf, Вы писали:
R>>И добавить к нему ABA-counter вместо постоянно создания и разрушения вспомогательных объектов.
vf>Да, идея понятна. Но не несет ли такой подход потенциальную опасность, по сути мы же просто снижаем вероятность ABA, понятно что очень сильно. А с ростом производительности вероятность растет. vf>Я продумывал, вариант, когда ABA-counter будет свой у каждого элемента — но опять же это вероятность, хотя по логике и чуть меньше.
Да, такая вероятность есть.
Есть несколько способов снизить её ещё сильнее.
Первое, как ты правильно заметил, счётчик можно привязать к каждому элементу. Ведь нам важно, что бы в head не появилась именно такая же пара (указатель, счётчик), если счетчик будет таким же, а указатель другим — то это нормально. При таком подходе, что бы скомпрометировать алгоритм, уже требуется, что бы поток проспал внутри Pop() пока один *конкретный* элемент не будет снят и добавлен в стек *ровно* 2^32 раз.
Второе, т.к. ты используешь индексы, от них можно легко "откусить" кусочек в пользу счётчика. Например, 2^20 макс элементов + 2^44 счётчик.
Я думаю, эти 2 меры снизят вероятность до пренебрежимой.
Здравствуйте, remark, Вы писали:
R>Я думаю, эти 2 меры снизят вероятность до пренебрежимой.
Согласен. В качестве академического интереса, а без ABA счетчиков красивый алгоритм стека, очереди или кучи существует? Или только спин-локи?
И практический вопрос мучает, насколько я понимаю interlocked операции очень малозатратны на ресурсы cpu, x86 есть именно такая команда, то есть разница с обычными операциями минимальна. Тогда почему в lock-free алгоритмах пытаются уменьшить число, считают эффективность именно по интерлокед операциям? Конкретно, для ABA счетчика требуется несколько доп. операций, но всего одна CAS и это считается эффективным. Может быть другой алгоритм с большим число CAS операций но меньшим простых будет эффективнее?
Здравствуйте, vf, Вы писали:
R>>Я думаю, эти 2 меры снизят вероятность до пренебрежимой.
vf>Согласен. В качестве академического интереса, а без ABA счетчиков красивый алгоритм стека, очереди или кучи существует? Или только спин-локи?
vf>И практический вопрос мучает, насколько я понимаю interlocked операции очень малозатратны на ресурсы cpu, x86 есть именно такая команда, то есть разница с обычными операциями минимальна. Тогда почему в lock-free алгоритмах пытаются уменьшить число, считают эффективность именно по интерлокед операциям? Конкретно, для ABA счетчика требуется несколько доп. операций, но всего одна CAS и это считается эффективным. Может быть другой алгоритм с большим число CAS операций но меньшим простых будет эффективнее?
interlocked выполняются примерно в 100 раз дольше обычных инструкций (сильно зависит от архитектуры и от того, что подразумевать под обычными инструкциями, для x86 это где-то допустим 50-200 медленнее).
Уменьшить пытаются не кол-во interlocked, сколько кол-во обращений к разделяемым данным. interlocked операции дороги, но хорошо масштабируются; обращения же к разделяемым данным гораздо медленнее, и полностью не масштабируются.
vf>>Согласен. В качестве академического интереса, а без ABA счетчиков красивый алгоритм стека, очереди или кучи существует? Или только спин-локи?
R>Так вот же он: R>http://www.rsdn.ru/forum/dotnet/3722678.aspx
А с перламутровыми пуговицами есть? На самом, я наверное не указал, не хочется использовать GC, мне как бы для lock-free коллекция и нужна для того чтобы хранить не используемые буфера, и если я при push буду создавать элемент стека, как то не совсем логично получается. Поэтому в оригинальном посте и выложил array-based стек.
R>interlocked выполняются примерно в 100 раз дольше обычных инструкций R>(сильно зависит от архитектуры и от того, что подразумевать под обычными инструкциями, для x86 это где-то допустим 50-200 медленнее).
Не совсем понятно, сейчас смотрю книгу по 80x86 и Pentium (устаревшая конечно инфа но не думаю что на порядки) — инструкция CMPXCHG — 6 тактов на пентиуме, на 486 — 6 или 7, используется вместе с префиксом LOCK — один такт -- откуда тогда 50-200 раз.
R>Уменьшить пытаются не кол-во interlocked, сколько кол-во обращений к разделяемым данным. interlocked операции дороги, но хорошо масштабируются; обращения же к разделяемым данным гораздо медленнее, и полностью не масштабируются.
Это высказывание имеет отношение к .net, к стеку или очереди на одном компе? Или это вообщем про проблематику больших систем? Если имеет, не могли бы пояснить — реально не понял.
Здравствуйте, vf, Вы писали:
vf>>>Согласен. В качестве академического интереса, а без ABA счетчиков красивый алгоритм стека, очереди или кучи существует? Или только спин-локи?
R>>Так вот же он: R>>http://www.rsdn.ru/forum/dotnet/3722678.aspx
vf>А с перламутровыми пуговицами есть? На самом, я наверное не указал, не хочется использовать GC, мне как бы для lock-free коллекция и нужна для того чтобы хранить не используемые буфера, и если я при push буду создавать элемент стека, как то не совсем логично получается. Поэтому в оригинальном посте и выложил array-based стек.
Есть алгоритмы, которые реализуют фактически то же, что и GC только самостоятельно. Но они сложные. Если есть желание я могу дать ссылки, но рекомендую всё же смотреть в сторону ABA счётчиков. С теми двумя улучшениями они будут *очень* надёжными. Вон Microsoft в своём InterlockedSList API использовал вообще 9-битные счётчики, и ничего, работало как-то.
R>>interlocked выполняются примерно в 100 раз дольше обычных инструкций R>>(сильно зависит от архитектуры и от того, что подразумевать под обычными инструкциями, для x86 это где-то допустим 50-200 медленнее).
vf>Не совсем понятно, сейчас смотрю книгу по 80x86 и Pentium (устаревшая конечно инфа но не думаю что на порядки) — инструкция CMPXCHG — 6 тактов на пентиуме, на 486 — 6 или 7, используется вместе с префиксом LOCK — один такт -- откуда тогда 50-200 раз.
LOCK на Pentium4 100 тактов.
На последних Core меньше порядка 40.
Для сравнения, передача кэш-линии между ядрами порядка 200-300 тактов (вплоть до 1000 в зависимости от размера системы).
R>>Уменьшить пытаются не кол-во interlocked, сколько кол-во обращений к разделяемым данным. interlocked операции дороги, но хорошо масштабируются; обращения же к разделяемым данным гораздо медленнее, и полностью не масштабируются.
vf>Это высказывание имеет отношение к .net, к стеку или очереди на одном компе? Или это вообщем про проблематику больших систем? Если имеет, не могли бы пояснить — реально не понял.
Это про многоядерные/многопроцессорные системы. Такие системы — физически распределенные (конечно, если положить процессор на ладонь, то он не кажется особо распределенным, но учитывая частоты, на которых он работает, получается вполне даже распределенным). В такой системе обращения к разделяемым данным вызывают физическую передачу данных от одного ядра к другому, это дорого и может ограничивать масштабируемость системы, если пропускная способность межсоединителя (считай — мини локальная сеть) закончится.
Сама по себе атомарная операция же полностью локальная для ядра, и никоим образом не компрометирует масштабируемость.
Здравствуйте, vf, Вы писали:
vf>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
Здравствуйте, Caracrist, Вы писали:
vf>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>Вот тут лежит на с++. C>http://www.rsdn.ru/forum/src/3725942.aspx
Здравствуйте, remark, Вы писали:
R>Здравствуйте, Caracrist, Вы писали:
vf>>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>>Вот тут лежит на с++. C>>http://www.rsdn.ru/forum/src/3725942.aspx
Здравствуйте, Caracrist, Вы писали:
C>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, Caracrist, Вы писали:
vf>>>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>>>Вот тут лежит на с++. C>>>http://www.rsdn.ru/forum/src/3725942.aspx
Здравствуйте, Caracrist, Вы писали:
vf>>>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>>>Вот тут лежит на с++. C>>>http://www.rsdn.ru/forum/src/3725942.aspx
vf>>>>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>>>>Вот тут лежит на с++. C>>>>http://www.rsdn.ru/forum/src/3725942.aspx
Здравствуйте, remark, Вы писали:
vf>>>>>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
C>>>>Вот тут лежит на с++. C>>>>http://www.rsdn.ru/forum/src/3725942.aspx
Вроде как обычный lock-based, нет?
"Нормальные герои всегда идут в обход!"
