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

N>>Видя слово "reprobing loop" можно дальше не читать.:) То есть, может, какое-то ускорение там есть. Но от принципиальной проблемы, что пока твоя нить думает, что делать с данными, другая в них вмешивается — ты таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и вылезти боком — если у тебя работа более сложная, чем установка лока.
BZ>ты в курсе, что основные задежрки в современных cpu идёт при кеш-промахах? обращение в память стоит порядка 50-100 тактов. типичная операция над хешем — это где-то пара обращений к памяти мимо кеша, не меньше. если залочить отдельноо каждую ячейку (или блок ячеек) хеша и его заголовок, то блокировка на ячейке станет очень маловероятна, а блокировка на заголовке будет идти считанные такты поскольку сам он находится в кеше cpu. я думаю, соотношение времени блокировки может быть порядка 200 тактов на обычном хеше к 10 на необычном :)

Блокировка на заголовке — в многопроцессорной системе — не будет "идти считанные такты", потому что требует обязательной записи в память. Write-back поведение кэша здесь недопустимо в принципе. В реализацию общей шины по типу "мы тут сначала кидаем нотификацию, что по адресу XXX чего-то записали, сбросьте его из кэша; а потом уже реально запишем" я слабо верю (хотя сейчас могут и такие появляться... чем чёрт не шутит). А теперь сравним. Считаем по 100 тактов на запись в память, и в сумме 30 тактов на все остальные действия, и что данные уже в кэше (то есть читать обходится очень дёшево). Тогда:
— с мьютексом при удачном занятии с первого раза: 430, ибо 4 записи в память (мьютекс занять, локальные данные записать, центральные данные записать, мьютекс отпустить)
— с мьютексом при задержке от ожидания освобождения другим процессором: 430 + неизвестно_сколько
— lock-free с первой удачной попытки: 230 (локальные данные записать просто так, центральные данные записать через CAS)
— lock-free со второй удачной попытки: 360 (ибо весь алгоритм надо повторить => прибавляем цену всего кроме несостоявшейся записи, ибо CAS обнаружил подмену данных)
— lock-free с третьей удачной попытки: 490
.....
А теперь хохма — вспоминаем мануал по x86 и исправляем, ибо там CAS (в виде CMPXCHG, XADD) не умеет обойтись без записи:
— lock-free на x86 со второй удачной попытки: 460 (просто умножаем на 2)
— lock-free на x86 с третьей удачной попытки: 690
.....

Ну и какой из них быстрее?;)) В сильноконкурирующей среде, похоже, lock-free явно начнёт проигрывать. И я ещё взял достаточно дешёвый вариант действий (всего две записи в память, кэш всё содержит).

BZ>при этом вероятность попасть на блокировку одновременно с другим тредом ждолжна снизиться имхо даже больше чем в 20 раз, но тут моя мысль останавливается :) а в той статье разве нет никакого анализа?

Вероятность попасть и на блокировку, и на перезапуск действия считается примерно одинаково — плотность действий (в герцах;)) умножаем на оценочную длительность действия, а затем полученную "плотность конкуренции" переводим методами теории вероятностей в собственно вероятность (плотность растёт вверх => вероятность асимптотически стремится к 1). В нашем примере lock-free исполняется где-то в два раза быстрее, значит, и вероятность соответственно меньше. Но если внутренняя работа сложнее — они уже могут сравняться.

В случае обсуждаемого хэша именно вероятность попасть в одно действие одновременно с другой нитью, как я понял, очень мала. И всё равно — как видно, среднее улучшение — всё те же два раза. Кстати, при 32 процессорах улучшение там вообще ничтожно.

Для правильной оценки работы ещё надо понять, что это за системы на 384 и 768 процессоров.
UMA? (ой;)) NUMA — с каким методом синхронизации кэшей? Метод тут будет очень существенно влиять.