SharedHash/Set

[Igors]

проверка id != mThreadID может сбоить.

Да, код вызывающий

Код

C++ (Qt)
if (id == mTreadID)

И при этом mTreadID может писаться любой ниткой! Обычно в multu-threading такие проверки - мертвому припарка (c оператором != то же самое). Но в данном случае они работают верно "по построению".

Вариант 1: пусть было "равно". Тогда локер уже захвачен текущей ниткой, а значит никто не сможет изменить mThreadID (только захвативший может освободить локер)

Вариант 2: пусть было "неравно". Локер свободен или захвачен др ниткой, и, да, mThreadID может измениться. НО оно никогда не станет равным (уникальному) id текущей нитки. Т.е. false останется false (пусть глуповато звучит)

Выходит булевское значение всегда верно, и на него можно опираться.

[Igors]

В общем случае - нет. Weak не контролирует свое состояние!
Предположим, есть ассоциативный массив, в качестве ключа которого используется weak. Узлы такого массива упорядочены между собой исходя из определенного правила сравнения ключей (оператор <, хеш или др.) и свойства их постоянности. Если каким-либо внешним способом (например, weak) изменить значение ключа в узле ассоциативного массива, то существующее упорядочивание узлов станет не корректным, и от ассоциативного контейнера можно ожидать непредвиденного поведения.

Считаю это верно для мапы, но не для хеша. Давайте я расскажу как вижу, а Вы если надо поправьте

Каждый эл-т хеша хранит вычисленный хеш-ключ (qHash). При поиске/вставке вычисляется хеш-ключ аргумента и остатком от деления находится "корзина" (bin). Но хеш-ключ не уникален, поэтому в корзине эл-т ищется оператором == (перебор по списку). Др словами в рамках корзины "отношения упорядоченности" не существует, а значит и нет требования постоянства для == (только для хеш-ключа). Rehash тупо делает большее или меньшее число корзин, никогда не вызывая ==. Вот с мапой - да, все развалится как Вы говорите, там нельзя на шару вернуть "меньше" если было "больше"

PS: Если есть возможность использовать std вместо Qt, используйте std. Решения Qt были сформированы, когда в std был недостаточно развит. Теперь же функциональность std по базовым вещам превосходит Qt, притом существенно. Именно поэтому Qt рассматривает вопрос о прекращении поддержки своих решений в пользу стандартных.

Я стремлюсь к решениям как можно меньше зависящим от реализации. Жизнь заставит перевести на std - переведу, пока Qt вполне устраивает.

Вот тесты слабоваты, ничего не приходит в голову. Есть идейки?

[Авварон]

НО оно никогда не станет равным (уникальному) id текущей нитки. Т.е. false останется false (пусть глуповато звучит)

Ну вот в этом и проблема, у вас уже вызвано UB, а значит, там может лежать что угодно.
Можно конечно долго рассуждать о том "да как же так у меня всё работает, да ни на одной архитектуре этого не будет", но с тз стандарта код не валиден.
Вот эта имплементация мне нравится больше, вместо 0\1 они используют ид треда как признак того, что лок занят нами. lock_count при это не должен быть атомиком, так как манипуляции с ним _внутри_ acquire/release заборов.

Я стремлюсь к решениям как можно меньше зависящим от реализации. Жизнь заставит перевести на std - переведу, пока Qt вполне устраивает.

Ну так у вас как раз куте гвоздями забито и _зависит_ от реализации=)

[Igors]

Ну вот в этом и проблема, у вас уже вызвано UB, а значит, там может лежать что угодно.
Можно конечно долго рассуждать о том "да как же так у меня всё работает, да ни на одной архитектуре этого не будет", но с тз стандарта код не валиден.

Какое UB? mThreadID - вовсе не "что угодно", а id одной из ниток, их уникальность гарантируется. Др словами "если текущее mThreadID - не мое, то сделать его моим никто не сможет кроме меня". Обратное тоже верно. Нам-то нужно не само mThreadID а "мое или нет"

По-моему это уже моя 4-я попытка (с интервалами неск лет) объяснить этот прием. Увы "не заходит" 

[Авварон]

Какое UB? mThreadID - вовсе не "что угодно", а id одной из ниток, их уникальность гарантируется. Др словами "если текущее mThreadID - не мое, то сделать его моим никто не сможет кроме меня". Обратное тоже верно. Нам-то нужно не само mThreadID а "мое или нет"

По-моему это уже моя 4-я попытка (с интервалами неск лет) объяснить этот прием. Увы "не заходит" 

У меня коллега думает, что если написать

Код:

ptr = std::make_shared<Data>();
data_ready = true;

/// и в другом треде

if (data_ready)
   foo(ptr.get());

то мьютексы и атомики не нужны, ну а чо, у него ж работает, он же проверил!

Читаем cppref:

When an evaluation of an expression writes to a memory location and another evaluation reads or modifies the same memory location, the expressions are said to conflict. A program that has two conflicting evaluations has a data race unless

* both evaluations execute on the same thread or in the same signal handler, or
* both conflicting evaluations are atomic operations (see std::atomic), or
* one of the conflicting evaluations happens-before another (see std::memory_order)
If a data race occurs, the behavior of the program is undefined.

и делаем выводы. Ни один из трех пунктов не подходит - один тред пишет пременную под забором (т.е. выполнен 3), а второй читает с нарушением happens-before (т.е. 3 не выполнен). 1 и 2 не выполнены "по построению".

[Авварон]

Давайте я вам попробую объяснить, как на самом деле работает acquire/release fence.
Читаем доку кутешников:

Acquire - memory access following the atomic operation (in program order) may not be re-ordered before the atomic operation.
Release - memory access before the atomic operation (in program order) may not be re-ordered after the atomic operation.

Пишем код:

Код:

// 0. делаем что-то нерелевантное
// 1. acquire resource (testAndSetAcquire и друзья)
// 2. что-то делаем с ресурсом:
m_data = 1;

// 3. что-то делаем с ресурсом:
m_data = 0;
// 4. release resource

Кутешная дока говорит, что будет выполнено в таком порядке: сперва 1, затем 2, аналогично 3, затем 4 (но не 2, 1, например).
Так вот, это нихрена не верно.
На самом деле, release говорит, что записи\чтения должны быть выполнены до следующего acquire. То есть 1, 2, 4, 3, 1 - валидный порядок! 3 должно быть выполнено до 1, а не до 4.
И если в 0 вы обращаетесь к ресурсу, то вас ждут неприятности, потому что обращение к нему неатомарно само по себе. И вы уже начинаете полагаться на текущую архитектуру - что инт у вас не пишется половинками и что кэши процессора у вас когерентны. Мало ли какой мусор там может быть? Ну да, вероятность мусора попасть в "чужой" тред ид примерно около 1\2^32, но мы же пишем не на квантовом компьютере, чтобы уповать на вероятности?

PS: вероятность файр резиста крайне мала

[ssoft]

Считаю это верно для мапы, но не для хеша. Давайте я расскажу как вижу, а Вы если надо поправьте

Каждый эл-т хеша хранит вычисленный хеш-ключ (qHash). При поиске/вставке вычисляется хеш-ключ аргумента и остатком от деления находится "корзина" (bin). Но хеш-ключ не уникален, поэтому в корзине эл-т ищется оператором == (перебор по списку). Др словами в рамках корзины "отношения упорядоченности" не существует, а значит и нет требования постоянства для == (только для хеш-ключа). Rehash тупо делает большее или меньшее число корзин, никогда не вызывая ==. Вот с мапой - да, все развалится как Вы говорите, там нельзя на шару вернуть "меньше" если было "больше"

1. После обнуления weak остается не в своей корзине и найти его уже не представляется возможным, так как weak (ключ) уже нулевой, и хеш соответственно другой.
2. Rehash делает не только больше или меньше корзин, но и перераспределяет отношения своих узлов (элементов) по этим корзинам.

Контейнер со временем может распухнуть от нулевых weak, которые можно удалить только с помощью полного перебора всех элементов контейнера.

[Igors]

1. После обнуления weak остается не в своей корзине и найти его уже не представляется возможным, так как weak (ключ) уже нулевой, и хеш соответственно другой.

Хеш тот же самый, он вычисляется один раз при вставке и хранится (qHash может быть затратным)

Контейнер со временем может распухнуть от нулевых weak, которые можно удалить только с помощью полного перебора всех элементов контейнера.

Последняя реализация так и делает, особого греха не вижу, многие контейнеры имеют пул. Число нулевых отслеживается deleter'ом чтобы воздух не гонять.

Хорошо, посмотрим др решения. Что с использованием ключа - голого указателя (насколько понял Вы его здесь называете Raw)? Не полнимаю чем/как он поможет. Для оператора == все равно к данным/содержимому лезть надо. Ну можно пару weak/raw, а смысл? Если weak сдох, какой толк от raw?

[Igors]

У меня коллега думает, что если написать

Код:

ptr = std::make_shared<Data>();
data_ready = true;

/// и в другом треде

if (data_ready)
   foo(ptr.get());

то мьютексы и атомики не нужны, ну а чо, у него ж работает, он же проверил!

Вы, право, слишком строги к коллегам Ну да, гипотетически возможен "некий компилятор на некой платформе" где присваивание булевского data_ready "неатомарно". Интересно как - сначала запишет в младший байт 0 (затирая имеющуюся там единичку), а потом 1? Хммм... Ну ладно, лучше не искать приключений и объявить data_ready атомиком

Кутешная дока говорит, что будет выполнено в таком порядке: сперва 1, затем 2, аналогично 3, затем 4 (но не 2, 1, например).
Так вот, это нихрена не верно.
На самом деле, release говорит, что записи\чтения должны быть выполнены до следующего acquire. То есть 1, 2, 4, 3, 1 - валидный порядок! 3 должно быть выполнено до 1, а не до 4.

Позвольте, а как же пункт 1 выше?

* both evaluations execute on the same thread

И вы уже начинаете полагаться на текущую архитектуру - что инт у вас не пишется половинками

Совершенно верно, полагаюсь что присваивание указателя (Qt::HANDLE) атомарно. Как, впрочем, и авторы lock-free примеров. Ну если уж хочется "всеобъемлющего" то надо его делать атомиком. На мой взгляд - ненужная перестраховка и засорение кода, но своего мнения не навязываю.

..и что кэши процессора у вас когерентны. Мало ли какой мусор там может быть?

Не вижу откуда возьмется мусор. Кеши процессоров могут быть не синхронизированы, т.е. процессоры могут читать разные значения, но все они вовсе не "мусор", это ID разных ниток, и все соображения выше столь же справедливы.

[Авварон]

Ну да, гипотетически возможен "некий компилятор на некой платформе" где присваивание булевского data_ready "неатомарно". Интересно как - сначала запишет в младший байт 0 (затирая имеющуюся там единичку), а потом 1? Хммм... Ну ладно, лучше не искать приключений и объявить data_ready атомиком

Некая платформа - это, например, ARM, то есть - все мобилки. Но откуда же это знать убеленными сединами профессорам, которые 30 лет пишут одну софтину под одну платформу?

Вы написали в коде

Код:

a = 10;
ready = true;

А ARM исполнил это так:

Код:

ready = true;
a = 10;

Просто потому что захотел. И это не что-то гипотетическое, это так работает армовский процессор, потому что так быстрее (по сравнению с strong-ordered x86й архитектурой).
Если хотите, я вам даже на x86 могу привести пример, как схлопотать reordering, просто это надо постараться, чтобы сделать.
Зато можно провести пару дней в отладчике, пытаясь понять "откуда же в A ноль, ведь в B единичка, не может там нуля быть, A пишется до B!"

[Авварон]

Позвольте, а как же пункт 1 выше?

Один тред пишет 0, второй читает этот 0 (или не 0), переменная не атомарна - UB.

[Авварон]

1. После обнуления weak остается не в своей корзине и найти его уже не представляется возможным, так как weak (ключ) уже нулевой, и хеш соответственно другой.

Я в упор не вижу откуда пошло обсуждение weak_ptr как ключа, у Igors weak - это значение, а ключ, например, строка

[ssoft]

Я в упор не вижу откуда пошло обсуждение weak_ptr как ключа, у Igors weak - это значение, а ключ, например, строка

Файл HashUtils.h

Код

C++ (Qt)
template <class T>
class CWeakPointer : public QWeakPointer<T> {
public:
	CWeakPointer( const QSharedPointer<T> & other ) : QWeakPointer<T>(other) {}
	bool operator == ( const CWeakPointer & other ) const
	{
		QSharedPointer<T> other2 = other.toStrongRef();  // must lock hash value with multi-threading
		if (other2.isNull()) return false;
		return *(this->data()) == *(other2.data());
	}
};
 
template <class T>
uint qHash( const T & val );
 
template <class T>
uint qHash( const CWeakPointer<T> & ptr )
{
	const T & val = *ptr.data();
	return qHash(val);
}
 

[Авварон]

Файл HashUtils.h

Ну такое...

[Igors]

Некая платформа - это, например, ARM, то есть - все мобилки. Но откуда же это знать убеленными сединами профессорам, которые 30 лет пишут одну софтину под одну платформу?

Ну почему под одну? Гребаное Вындоуз тоже поддерживаем - под две  

Вы написали в коде

Код:

a = 10;
ready = true;

А ARM исполнил это так:

Код:

ready = true;
a = 10;

Просто потому что захотел. И это не что-то гипотетическое, это так работает армовский процессор, потому что так быстрее (по сравнению с strong-ordered x86й архитектурой).
Если хотите, я вам даже на x86 могу привести пример, как схлопотать reordering, просто это надо постараться, чтобы сделать.
Зато можно провести пару дней в отладчике, пытаясь понять "откуда же в A ноль, ведь в B единичка, не может там нуля быть, A пишется до B!"

Здесь согласен, не увидел. Однако мы изрядно отвлеклись, вернемся к хешам

1) Сравнение weak актуально только для Set, для Hash проблемы нет - ну найденное по ключу значение null, значит "не считается" - такого в хеше нет.

2) Хорошо, допустим сравнение weak выше некорректно (хотя я не вижу почему), тогда что? Не видно вообще никакого решения, так что ли? Неужели "столь сложная задача?". Да вроде нет, банальное кеширование, только с учетом шаред. А как же современные средства, которые намного, намного превосходят... ?  

Да, и кстати о птичках: где там в std спиннер? Там тоже велик писать? Нуу...