SharedHash/Set

[ViTech]

Ну а вообще что оте "итераторные сопли" всем уже осто<> - то я давно говорил (был заклеймлен в неграмотности  )

Расскажите тогда, как грамотно итерировать по ассоциативным контейнерам без "итераторных соплей" ?

[Igors]

А еще пачку других методов, чтобы не передавать в алгоритмы begin/end, а передавать контейнер целиком.

Я наблюдал по меньшей мере с пяток таких попыток, но у всех были свои неудобства.

Другое дело, что вместо итераторных соплей или хелпер-функций люди начинают итерироваться по keys() или values() и рассказывать всем какие же удобные кутешные контейнеры.
Или делают if (map.contains(key)) return map.value(key);

Это уже человеческий фактор, с философией босяка ("работать позорно") бороться бесполезно

Да, и ошибку-то все-таки покажите 

Расскажите тогда, как грамотно итерировать по ассоциативным контейнерам без "итераторных соплей" ?

Никак, в данном случае это неизбежно. Но тулить итераторы всегда и везде (напр даже когда есть индекс) - перегиб

Однако вернемся к Hash/Set. Поскольку базовые контейнеры (QHash/QSet) НЕ thread-safe, то очевидно что и порожденная конструкция тоже. Нужно засисяться локерами, причем как-то непросто. Но сначала нужно убедиться что с одной ниткой работает (корректна ли затея с итератором?). Не слышу критики (только ssoft), все вокруг да около..

[Авварон]

Да, и ошибку-то все-таки покажите 

Всё верно, вместо О(N) получили N*logN, ошибка уровня студента. А из-за лапши переменных приглядели это на ревью.

Не слышу критики (только ssoft), все вокруг да около..

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

Или вам нужен дополнительный контейнер со стабильными итераторами (линкед лист?) для хранения данных; а хэш будет только индексом на те данные. В зависимости от Т это может как давать выигрыш (если ключ std::string, копировать строку в лямбду глупо, куча памяти пожрется зазря), так и нет (ключ QString, они копируются быстрее чем аллоцируется нода списка)

[ViTech]

Тоже заглянул в пример .

Сам CSharedHash/Set данными не владеет и может быть безболезненно удален. В остальном логика шаред никак не меняется, ну разве что кастомный deleter нельзя, он уже занят.

А если после удаления CSharedHash/Set будут существовать шареды, запихнутые методом Put с тем кастомным Deleter, что в примере, они потом тоже могут быть безболезненно удалены?

[Igors]

Ну он прав, затея с вытиратором работать не будет для хэша.

Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после rehash? Не нашел такого (правда не видел и обратного). Кстати что там по этому поводу в std::unordered_map?

А если после удаления CSharedHash/Set будут существовать шареды, запихнутые методом Put с тем кастомным Deleter, что в примере, они потом тоже могут быть безболезненно удалены?

Да, для этого есть наблюдающий mLive. Правда вот здесь маленько насвистел

Код

C++ (Qt)
void clear( void ) { mHash.clear(); }

Нужно "передернуть затвор", правильно так

Код

C++ (Qt)
void clear( void ) { mHash.clear(); mLive.reset(new int(1)); }

Хотя может лучше вообще clear не давать.

[Авварон]

Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после rehash? Не нашел такого (правда не видел и обратного). Кстати что там по этому поводу в std::unordered_map?

Вас в гугле забанили?=)

Iterator validity
On most cases, all iterators in the container remain valid after the insertion. The only exception being when the growth of the container forces a rehash. In this case, all iterators in the container are invalidated.

Но, кстати:

References to elements in the unordered_map container remain valid in all cases, even after a rehash.

Это упростит жизнь и вместо вытиратора можно хранить ссылку на пару ключ/значение.

[ssoft]

Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после rehash? Не нашел такого (правда не видел и обратного). Кстати что там по этому поводу в std::unordered_map?

Про итераторы Qt https://wiki.qt.io/Iterators

[ssoft]

В качестве ключа следует использовать Raw указатель (Type *)

Интересная мысль. Но тогда как (или "из чего") отдать наружу шаред? Выходит weak нужен. Ну и шансов у (Type *) стать хламом столько же - только уже без проверки.

Указатель raw должен быть сугубо ключом, и ни в коем случае нельзя через него осуществлять доступ к членам (обращаться с ним, как с указателем). Даже если он "протухнет", соответствующее ему weak значение станет нулевым.

[Igors]

Да, согласен, дама теория права - хранить итератор плохо. Уже сам факт того что надо выяснять "валидный али как" = плохо, тем более оказывается выяснить не так уж просто.

Хорошо, переделал, перезалил в стартовый пост. Для юзера все так же. Теперь Deleter получает просто шаред (число трупиков) и инкрементирует его при удалении - и все, в хеш не лезет. А при добавлении в хеш проверяется число сдохших, и, если оно достаточно велико, хеш чистится. Доступ к хешу прикрыл локером, надеюсь что реализация thread-safe.

Указатель raw должен быть сугубо ключом, и ни в коем случае нельзя через него осуществлять доступ к членам (обращаться с ним, как с указателем). Даже если он "протухнет", соответствующее ему weak значение станет нулевым.

Не очень понял что Вы хотели сказать. По-моему поиск по weak вполне возможен

Код

C++ (Qt)
bool operator == ( const CWeakPointer & other ) const
{
	QSharedPointer<T> other2 = other.toStrongRef();  
	if (other2.isNull()) return false;
	return *(this->data()) == *(other2.data());
}
 

Сначала лочим weak, потом сравниваем. Да, при этом найденный итератор может оказаться null (после выполнения деструктора other2), ну так мы это опять проверим после find

Прошу завалить 

[ViTech]

А если после удаления CSharedHash/Set будут существовать шареды, запихнутые методом Put с тем кастомным Deleter, что в примере, они потом тоже могут быть безболезненно удалены?

Да, для этого есть наблюдающий mLive.

Действительно, это железобетонная защита, ни один гейзенбаг не проскочит .

Теперь Deleter получает просто шаред (число трупиков) и инкрементирует его при удалении - и все, в хеш не лезет. А при добавлении в хеш проверяется число сдохших, и, если оно достаточно велико, хеш чистится.

Теперь Deleter по-настоящему полезным делом занят, без него никак .

[Авварон]

Прошу завалить 

Ваш спинлок полон data race=)

[Авварон]

охохохо, свершилось!

[Igors]

Ваш спинлок полон data race=)

Обоснуйте. Возможно Вас смутило сравнение "не под мутексом", но оно корректно. И сразу прям уж "полон"

охохохо, свершилось!

Радует глаз, работают товарищи

[ssoft]

Не очень понял что Вы хотели сказать. По-моему поиск по weak вполне возможен.

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

Если же следить за тем, чтобы weak был корректным, то исчезает сам смысл использования weak. С таким же успехом можно хранить raw с меньшими потерями на data race.

Data race возникает из-за того, что в связке shared/weak используется, как минимум, два атомарных счетчика, которые постоянно инкрементируются и декрементируются при преобразованиях weak<->shared или копировании shared. Конкурентные операции с атомарными счетчиками приводят к частому сбросу процессорного кэша и иногда к существенному к замедлению. С raw такого эффекта не возникает. Если нужно через raw указатель получить shared, то можно использовать либо ассоциативный массив вида {raw, weak}, либо использовать наследование от std::enable_shared_from_this (https://ru.cppreference.com/w/cpp/memory/enable_shared_from_this).

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

[Авварон]

Обоснуйте. Возможно Вас смутило сравнение "не под мутексом", но оно корректно. И сразу прям уж "полон"

Я не силен в лок-фри алгоритмах но кажется проверка id != mThreadID может сбоить.
Читаем доку (лучше с cpp ref потому что у кутешников не совсем валидное определение, но более простое для понимания):

memory_order_acquire
[Applies to loading operations]
The operation is ordered to happen once all accesses to memory in the releasing thread (that have visible side effects on the loading thread) have happened.

То есть в после testAndSetAcquire mThreadID будет равен 0... А вот строчкой выше этого никто не гарантировал, ведь мемори-забор стоит под ифом.

ЗЫ: на х86 оно конечно же будет работать потому что там нет relaxed операций, все read ведут себя как acquire а write как release.