Russian Qt Forum

Qt => Кладовая готовых решений => Тема начата: Igors от Май 13, 2019, 06:51



Название: SharedHash/Set
Отправлено: Igors от Май 13, 2019, 06:51
Добрый день

Цель: используя шаред_птр, иметь только уникальные экземпляры класса. Грубо говоря, шарить все, тотально. Так вроде бы шаред_птр для этого и предназначен?  Не совсем. Когда один шаред присваивается другому - все прекрасно. Но когда мы создаем его с нуля, напр данные читаются из файла, уникальность не обеспечивается
Код
C++ (Qt)
m_name = QSharedPointer<std::string> (new std::string("abc"));
// а если "abc" уже есть?
А задействовать QHash/QSet/QCache так просто не выходит т.к. все они владеют данными сами и с шаред не дружат.

Предлагаемый велик по сути имеет один метод Put для создания шаред
Код
C++ (Qt)
CSharedSet<std::string> theSet;
...
m_name = theSet.Put(new std::string("abc"));
Если "abc" уже есть, эти данные будут шариться, а новая строка удалена. Аргументом Put должен быть голый указатель созданный с помощью new, theSet, как говорится, "takes ownership". В случае CSharedSet шаред должен быть объявлен указателем на константу,  т.к. сами данные - ключ и изменены быть не могут
Код
C++ (Qt)
QSharedPointer<const std::string> m_name;
А если хотим менять, то нужно сделать копию используя new, изменить ее и перезарядить тем же Put, напр
Код
C++ (Qt)
std::string * temp = new std::string(*m_name.data());
*temp += " edit";
m_name = theSet.Put(temp);
Что вообще-то не очень красиво, но приемлемо. В случае CSharedHash этой мороки нет, т.к. ключ отдельно, сами решаем менять данные для всех шарящих или как.

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

Это все, попинайте, ну или расскажите о чудесных классах которые "уже давно написаны"  :)


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 14, 2019, 12:14
А что мешало сделать value-based обертку с использованием QExplicilySharedDataPointer и заюзать обычный QSet?

Проблему аллокаций вы так и не решили - вы экономите количество памяти, но не количество аллокаций. Имхо, задача решена только на половину=)

ЗЫ: QESDP проблему аллокаций также не решает но позволяет не писать свой велосипед=)


Название: Re: SharedHash/Set
Отправлено: Igors от Май 14, 2019, 13:11
А что мешало сделать value-based обертку с использованием QExplicilySharedDataPointer и заюзать обычный QSet?
Никогда не юзал Q(Explicitly)SharedDataPointer, только читал, идея кажется понятной. Не вижу разницы со стандартным Qt имплисит классом, напр QString, все так же не удается раскрутиться с hash/set. Если я туда посажу QString (QSharedDataPointer,  QExplicitlySharedDataPointer), то кто (или когда, или каким образом) удалит данные (ту же QString)?

Проблему аллокаций вы так и не решили - вы экономите количество памяти, но не количество аллокаций. Имхо, задача решена только на половину=)

ЗЫ: QESDP проблему аллокаций также не решает но позволяет не писать свой велосипед=)
Поясните в чем разница между этими понятиями (память/аллокация)? Кстати экономия памяти сейчас мало интересует, больше дорогие расчеты


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 14, 2019, 14:50
Никогда не юзал Q(Explicitly)SharedDataPointer, только читал, идея кажется понятной. Не вижу разницы со стандартным Qt имплисит классом, напр QString, все так же не удается раскрутиться с hash/set. Если я туда посажу QString (QSharedDataPointer,  QExplicitlySharedDataPointer), то кто (или когда, или каким образом) удалит данные (ту же QString)?

А, я не смотрел реализацию и не видел, что кэш данными не владеет. Да, Q(E)SDP тут не поможет.
Разница между QESDP и QSDP что первый не детачит в непонятных местах и оставляет это на разработчика класса.

Что вам надо сдеать, это вместо метода put сделать мутод getOrCreate - это позволит избежать ненужной аллокации.
Код:
template <class Key, class Val, class Args...>
std::shared_pointer<Val> getOrCreate(Key key, Args... args)
{
    const auto it = mHash.find(key);
    if (it != mHash.end()) {
        const auto result = it->second.lock();
        if (result) // нашли в кэше
             return result;
    }
    auto data = std::make_shared<Val>(std::forward(args));
    mHash.insert(key, data);
    return data;
}

Поясните в чем разница между этими понятиями (память/аллокация)? Кстати экономия памяти сейчас мало интересует, больше дорогие расчеты


Есть потребление памяти - это сколько программа занимает места в памяти вот прямо сейчас (в момент времени Х).
А есть количество аллокаций и общий объем аллокаций - это сколько памяти программа аллоцировала за всё время работы.
Например:
Код:
    for (int i = 0; i < 10; ++i) {
        std::string hello("hello");
    }
Перед циклом: потребление памяти 0 байт, количество аллокаций - 0, объем аллокаций 0.
Во время цикла - потребление памяти 6 байт (на 1 строку), количество аллокаций - i, объем аллокаций i*6.
После цикла - потребление памяти 0 байт, количество аллокаций - 10, объем аллокаций 10*6.
То есть в пике мы потребили 6 байт, но при этом нааллоцировали/наудаляли на 60.

Парные аллокации/удаления влияют в основном на скорость работы программы. На общее потребление памяти они тоже влияют, но опосредованно - за счет фрагментации программа может запрашивать новые страницы у ОС. А может и не запрашивать, тут как повезет, с фрагментацией сложно бороться.
Непарные аллокации, помимо времени, еще и требуют всё новой и новой памяти.
Шаредные данные решают проблему аллокации при копировании объекта (самый частый юзкейз до с++11). Начиная с 11х плюсов можно вообще побанить копирование и делать move-only объекты, которые "трансформируются" в новое состояние вместо изменения копии старого, но это не ваш случай.

В вашем случае надо понять, как достать объект из кэша так, чтобы не аллоцировать новый объект. Пример с Args... тоже решение частичное - он хорош когда мы создаем новый объект один-в-один как на старый, а когда мы читаем объект из файла, что делать?...


Название: Re: SharedHash/Set
Отправлено: Igors от Май 15, 2019, 06:00
Что вам надо сдеать, это вместо метода put сделать мутод getOrCreate - это позволит избежать ненужной аллокации.
Не считая наворотов Args так оно и сделано. Загвоздка в том что когда данные автоматом убьются - они должны быть (тоже автоматом) вычищены из хеша, в основном все посвящено этому.
В вашем случае надо понять, как достать объект из кэша так, чтобы не аллоцировать новый объект. Пример с Args... тоже решение частичное - он хорош когда мы создаем новый объект один-в-один как на старый, а когда мы читаем объект из файла, что делать?...
Ну в случае Hash (имеется ключ) можно провериться Get. А в случае Set думается решения объективно нет, сравниваются сами данные, а значит вторую копию надо иметь.

Вообще с фрагментацией и.т.п. по-моему явный перегиб. Применение гораздо прозаичнее. Те же текстуры что давеча упоминал, интенсивно шарятся. Вот мне надо (всего-навсего) распечатать какие текстуры сейчас загружены (ключ - имя файла), любой тест начнется с этого. И выясняется что, при всей безумной  крутизне современных средств, всяких мувов, форвардов и хз чего, какого-то простого, удобного решения не видно :'( Как бы срабатывает обратная сторона шаред_птр - да, грохнет автоматом - хорошо, но вот живы данные или как - не получить.

Возможен и др подход - забить на шаред_птр и считать ссылки самому. Тогда с помещением в hash/set нет проблем, но ценой общности - придется ковырять каждый используемый класс.


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 15, 2019, 07:59
Не считая наворотов Args так оно и сделано. Загвоздка в том что когда данные автоматом убьются - они должны быть (тоже автоматом) вычищены из хеша, в основном все посвящено этому.
А нельзя хранить в хеше в качестве значения weak_ptr и использовать deleter, который удалит этот weak из хеша при удалении объекта?


Название: Re: SharedHash/Set
Отправлено: Igors от Май 15, 2019, 12:08
А нельзя хранить в хеше в качестве значения weak_ptr и использовать deleter, который удалит этот weak из хеша при удалении объекта?
Вы бы исходники пролистали - ведь так там и сделано :) только в классах Qt. Тут, правда, пара мелких проблемок

а) хеш может быть удален/очищен - ну не беда, решается еще одним "наблюдающим" weak'ом (mLive)

б) а вот как передать итератор в deleter - не сообразил, сделал дубовым статиком, что, конечно, не есть хорошо. Что предложите?



Название: Re: SharedHash/Set
Отправлено: Авварон от Май 15, 2019, 16:07
Кстати, не советую юзать кутешый шаред поинтер, у него нет аналога std::make_shared, который делает одну аллокацию, вместо двух.

Ну а так, передавайте ключ в deleter вместо итератора, в чем проблема?


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 15, 2019, 17:03
Кстати, не советую юзать кутешый шаред поинтер, у него нет аналога std::make_shared, который делает одну аллокацию, вместо двух.

Аналог есть, QSharedPointer::create() называется. Но, не смотря на это, я тоже не советую его использовать.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 15, 2019, 17:15

Аналог есть, QSharedPointer::create() называется.

И правда. Ох уж этот NIH синдром...


Название: Re: SharedHash/Set
Отправлено: Igors от Май 16, 2019, 09:36
Ну а так, передавайте ключ в deleter вместо итератора, в чем проблема?
А для Set что вместо ключа? Да и для Hash - как минимум неаккуратно, ключ может быть весьма развесистым/расходным.

Кстати, не советую юзать кутешый шаред поинтер, у него нет аналога std::make_shared, который делает одну аллокацию, вместо двух.
Как у Вас все просто: тут есть, а там нет - ну стало быть этот лучше :) А по-моему уже само использование std:: ясно говорит: ни на какую "заточку" по памяти и/или скорости мы не претендуем. Зато выигрываем в скорости/легкости написания, ну в этом есть смысл. Да и чисто объективно тот make_shared - палка о двух концах, ведь при этом удаленный объект занимает память пока есть хоть один weak.

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

Аналог есть, QSharedPointer::create() называется. Но, не смотря на это, я тоже не советую его использовать.
Уже не первый раз наблюдаю такое "поджимание губок" при обсуждении Qt классов, мол, да это (ветхое) старье и.т.п. Можно узнать на чем основывается это мнение? Мелкие неудобства там и сям? (напр QSharedPointer не имеет доступа к счетчику ссылок, а надо). Что еще? Дешевые std-шные понты? Или чей-то заказ отрабатываем?  :)


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 16, 2019, 11:44
Аналог есть, QSharedPointer::create() называется. Но, не смотря на это, я тоже не советую его использовать.
Уже не первый раз наблюдаю такое "поджимание губок" при обсуждении Qt классов, мол, да это (ветхое) старье и.т.п. Можно узнать на чем основывается это мнение? Мелкие неудобства там и сям? (напр QSharedPointer не имеет доступа к счетчику ссылок, а надо). Что еще? Дешевые std-шные понты? Или чей-то заказ отрабатываем?  :)

Да Вы-то пользуйтесь на здоровье :). Я больше для других читателей форума писал.


Название: Re: SharedHash/Set
Отправлено: Igors от Май 16, 2019, 12:10
Я больше для других читателей форума писал.
Ну так вот Вам и карты в руки - развейте мысль(и) покажите как (или чем) std аналоги круче - и намного! А то пока выглядит как просто стремление "следовать моде" которому, увы, подвержены не только женщины. 

Да Вы-то пользуйтесь на здоровье :).
Думается Вы напрасно уделяете std столько времени и сил - эта штука всегда была и будет "ширпотребом", чего-то с ней достичь невозможно. Игнорировать ее конечно не стоит, но так "упиваться" синтаксическим сахаром ни к чему. Ну это тоже больше для других  :)


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 16, 2019, 12:49
Ну так вот Вам и карты в руки - развейте мысль(и) покажите как (или чем) std аналоги круче - и намного! А то пока выглядит как просто стремление "следовать моде" которому, увы, подвержены не только женщины.

Про недостатки Qt я на этом форуме достаточно писал. Если очень интересно - поищите и почитайте.

Если не отходить от темы, я бы поставил вопрос по другому: какие преимущества есть у QSharedPointer, чтобы пользоваться им, а не std::shared_ptr? QSharedPointer был актуален, пока в стандартной библиотеке С++ не было аналога (до С++11). Но сейчас std::shared_ptr должен поставляться с любым нормальным компилятором, а для QSharedPointer нужно Qt устанавливать. И даже если работать в рамках Qt, чем QSharedPointer превосходит std::shared_ptr?


Название: Re: SharedHash/Set
Отправлено: Igors от Май 16, 2019, 14:06
Про недостатки Qt я на этом форуме достаточно писал. Если очень интересно - поищите и почитайте.
Так Вы и в этой теме так же писали, мол, "не советую". А почему? Чем руководствуется советчик? Хз, наверное такому надо просто верить на слово :)

, я бы поставил вопрос по другому: какие преимущества есть у QSharedPointer, чтобы пользоваться им, а не std::shared_ptr? QSharedPointer был актуален, пока в стандартной библиотеке С++ не было аналога (до С++11). Но сейчас std::shared_ptr должен поставляться с любым нормальным компилятором, а для QSharedPointer нужно Qt устанавливать. И даже если работать в рамках Qt, чем QSharedPointer превосходит std::shared_ptr?
Да может и ничем не превосходит, может std::shared_ptr даже чуть больше имеет, что совершенно нормально, новая вещь учла предыдущий опыт. НО - достаточное ли это основание чтобы менять имеющийся код? Или хотя бы избегать QSharedPointer в новом коде? Считаю что совершенно НЕТ. Не видно явных, принципиальных плюсов (а их нет) - нечего тратить время на изучение "чуть лучшего".

Если не отходить от темы..
А тема совсем не от том :) И в теме неважно, тот шаред или этот. Важно другое, но оно Вас не интересует - понимаю, поглощены изучением std...


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 16, 2019, 14:31
Думается Вы напрасно уделяете std столько времени и сил - эта штука всегда была и будет "ширпотребом", чего-то с ней достичь невозможно. Игнорировать ее конечно не стоит, но так "упиваться" синтаксическим сахаром ни к чему. Ну это тоже больше для других  :)

Сто раз обсуждали, но давайте еще:
1. QtContainers требуют T(), что заставляет делать null state у T (QString::isNull/isEmpty), что не для любого T имеет смысл.
2. QtContainers требуют T(const T&). Хотите положить unique_ptr в вектор? забудьте.
3. QtContainers не имеют emplace* методов. Если не юзать pimpl то append(T&&) может быть более затратным (каждый мембер же надо мувнуть). Впрочем, это мелочь.
4. QtContainers не имеют range_insert методов. Хотите быстро вставить в вектор, не двигая полвектора на каждый элемент? Пишите руками.
5. QtContainers любят детачить в рандомных местах, что заставляют писать boilerplate код с qAsConst/временными переменными. Поглядите как "умело" обращаются с ними сами кутешники: https://codereview.qt-project.org/#/c/253792/ Куча таких мест делала дип-копию контейнера. Ухху!
6. QtContainers медленее за счет лишнего разыменования d_ptr. Это в Qt6 пофиксят, правда.
7. QtContainers медленее за счет постоянной проверки refcount, даже когда идет append в цикле.
8. QtContainers генерят больше бинарного кода: https://codereview.qt-project.org/#/c/261870/
9. QMap/QHash нельзя итерировать в range-for по ключу-значению, что либо заставляет писать говнокод с итераторами, либо говнокод с .keys() и последующим .value(). Ухху!

Вам мало?

ЗЫ: до с++11 кутешные контейнеры вцелом имели паритет - что-то быстрее\удобнее, что-то медленее\неудобнее, но в целом пофиг было. Но с 11х плюсов 2 и 9 просто киллер фичи std. А в 17х даже не надо богомерзкую пару в range-for юзать, просто пишем for (auto&& [key, value]: map) {...}


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 16, 2019, 14:33
Не видно явных, принципиальных плюсов (а их нет) - нечего тратить время на изучение "чуть лучшего".

Ну да, чтоб std::shared_ptr изучить, нужно потратить "неделю, не меньше!" :). Зато костыли для QHash пишутся легко и непринуждённо :). Кстати, какова сейчас политика партии: шаблоны - это хорошо или плохо?

Важно другое, но оно Вас не интересует - понимаю, поглощены изучением std...

Степень важности этой Вашей темы для меня Вы правильно определили, а вот с причиной ошиблись :).


Название: Re: SharedHash/Set
Отправлено: Igors от Май 16, 2019, 16:18
Вам мало?
Правду сказать - да, мало. Не думаю что перечисленные вещи имеют какое-то существенное значение (не говоря уже о "решающем"). Да, может где-то поприятнее (все-таки поновее), но не более того. Это никогда не сделает плохой код хорошим, ни наоборот.

Вот есть тот же QSharedPointer, он меня вполне устраивает, так какого <> без толку суетиться и менять его нв std? Впрочем обратное столь же верно.

Кстати пункт 4 не вполне точен: в QVector есть, а вот в QList нету.

Код
C++ (Qt)
9. QMap/QHash нельзя итерировать в range-for по ключу-значению, что либо заставляет писать говнокод с итераторами, либо говнокод с .keys() и последующим .value(). Ухху!
 
Здесь не понял проблему, расскажите подробнее. Спасибо

Вообще увлечение "общими" вещами на мой взгляд бесперспективно. Вы как бы оказываетесь в огромной толпе таких же (ну или говорящих что тоже знают :)) - и это невыгодно.

костыли для QHash пишутся легко и непринуждённо :).
...
Степень важности этой Вашей темы ..
Ну хорошо, вот Вы лягнули велосипедиста, как и положено фану std. А с задачей-то что? Может великое std имеет какие-то неведомые мне могучие средства чтобы достичь того же куда проще/эффективнее? Так пожалуйста, покажите, я ведь об этом и просил. Почему я ничего не слышу? Ах, это "частный случай", "не основной ф-ционал" и.т.п. - словом, задача дурацкая и никому не нужна. Или, еще лучше, "недостаточно инфы" - вот если бы я рассказал для чего текстуры - вот тогда, может быть... Все эти песни я слышал много раз, и думаю все проще: после столь усердного долбления std своих мыслей в голове не остается. И это отнюдь не компенсируется познаниями в тамошней хренотени. И ничего не поделаешь, так уж устроен человек.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 16, 2019, 16:33
Кстати пункт 4 не вполне точен: в QVector есть, а вот в QList нету.

Хде, покажите: https://doc.qt.io/qt-5/qvector.html#insert
Если что, range-insert это метод, принимающий 3 итератора: https://en.cppreference.com/w/cpp/container/vector/insert (4й оверлоад)

Здесь не понял проблему, расскажите подробнее. Спасибо

Код:
// c++17
std::map<QString, QVariant> map;
for (auto&& [key, value]: map) {
    qDebug() << "key:" << key << "value:" << value;
}

// qt good
QMap<QString, QVariant> map;
for (auto it = map.constBegin(), end = map.constEnd(); it != end; ++it) {
    qDebug() << "key:" << it.key() << "value:" << it.value();
}

// qt bad
QMap<QString, QVariant> map;
for (auto&& key: map.keys()) { // ой, аллокация и куча ref/deref строк
    qDebug() << "key:" << key << "value:" << map.value(key); // ой, поиск за log(N)
}
// а потом жалуются что "qt тормозит"

А с задачей-то что? Может великое std имеет какие-то неведомые мне могучие средства чтобы достичь того же куда проще/эффективнее? Так пожалуйста, покажите, я ведь об этом и просил.
Так с std::unordered_map "задачи" бы не возникло - где хотите, там и объявляете функтор std::hash, никаких проблем.


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 16, 2019, 16:49
Все эти песни я слышал много раз, и думаю все проще: после столь усердного долбления std своих мыслей в голове не остается. И это отнюдь не компенсируется познаниями в тамошней хренотени. И ничего не поделаешь, так уж устроен человек.

На самом деле всё ещё проще: нет желания тратить время на Ваши "задачи" :).


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 16, 2019, 20:12
Еще 5 копеек про Qt контейнеры. На последнее встрече в Москве было объявлено, что, вероятно, Qt откажутся от поддержки собственных контейнеров в Qt6. Но это все еще обсуждается.


Название: Re: SharedHash/Set
Отправлено: Igors от Май 17, 2019, 09:13
Хде, покажите: https://doc.qt.io/qt-5/qvector.html#insert
Да, он вставляет T(), потом самому данные надо вписать, не очень удобно. Ну хоть хвост (потенциально большой) сдвигается один раз.

Код:
// c++17
std::map<QString, QVariant> map;
for (auto&& [key, value]: map) {
    qDebug() << "key:" << key << "value:" << value;
}
Круто (червона рута). Но "killer feature" - да бог с Вами. Ну напишу тупенько с итераторами, не переломлюсь. Это всего лишь "красивая строка"

Так с std::unordered_map "задачи" бы не возникло - где хотите, там и объявляете функтор std::hash, никаких проблем.
Тут совсем не понял. Что за хвунктор и где его вставлять? Как это решит уникальность экземпляров? "Можно пример?"  :)

Код:
// qt bad
QMap<QString, QVariant> map;
for (auto&& key: map.keys()) { // ой, аллокация и куча ref/deref строк
    qDebug() << "key:" << key << "value:" << map.value(key); // ой, поиск за log(N)
}
// а потом жалуются что "qt тормозит"
Да, есть такой грех, Qt "подкармливает лохов". Классический пример: QString::split. Так ляпать контейнерами НЕЛЬЗЯ. Но.. это ф-ция страшно удобна. Ну и что что "затратна" - зато можно "взять готовое и не париться!". И таких юзеров много, и их мнение "весит" столько же как и нормальных, понимающих. Так почему бы их не привлечь такими "удобными" вызовами? В конце-концов юзать никто не заставляет. По-хорошему спички keys() давать детям не следовало.


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 17, 2019, 12:47
Заглянул в пример).
QWeakPointer и CWeakPointer ни в коем случае не должны использоваться в виде ключа, так как не управляют своим состоянием. В любой момент метод data может начать возвращать nullptr вместо какого-либо значения. Weak должен быть сугубо значением. В качестве ключа следует использовать Raw указатель (Type *). То есть любой set для weak использовать нельзя.
Итератор у hash и set запоминать и в дальнейшем использовать бесполезно, так как в любой момент при изменении hash или set может быть перераспределение узлов и итераторы станут не действительными.


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 17, 2019, 13:59
В любой момент метод data может начать возвращать nullptr вместо какого-либо значения.

Именно поэтому в std::weak_ptr нет метода get(). Из weak_ptr  доступ к объекту можно получить только принудительно продлив время его жизни с помощью lock(), чтобы не бояться, что объект в любой момент может превратиться в тыкву, если его грохнут из другого потока. Это к вопросу продуманности классов в std и Qt.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 17, 2019, 15:22
Круто (червона рута). Но "killer feature" - да бог с Вами. Ну напишу тупенько с итераторами, не переломлюсь. Это всего лишь "красивая строка"

Где ошибка?
Код:
const Item::PropertyMap &overriddenProperties = propertiesItem->properties();
for (Item::PropertyMap::ConstIterator it = overriddenProperties.constBegin();
    it != overriddenProperties.constEnd(); ++it) {
        loadedItem->setProperty(it.key(), overriddenProperties.value(it.key()));
}

Код:
for (const auto &kv : propertiesItem->properties()) {
    loadedItem->setProperty(kv.first, kv.second);
}


Название: Re: SharedHash/Set
Отправлено: Igors от Май 17, 2019, 18:53
Заглянул в пример).
QWeakPointer и CWeakPointer ни в коем случае не должны использоваться в виде ключа, так как не управляют своим состоянием. В любой момент метод data может начать возвращать nullptr вместо какого-либо значения.
Рассчитываю что перед этим должен сработать Deleter и до nullptr дело не дойдет.

Итератор у hash и set запоминать и в дальнейшем использовать бесполезно, так как в любой момент при изменении hash или set может быть перераспределение узлов и итераторы станут не действительными.
Этого я не проверял, из букваря видно что ++/--  меняются при rehash, ну думаю сам-то итератор валидный, иначе выходит что как у вектора "до первого милиционера" - наверняка написали бы. Ну это я так думаю  :)

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 17, 2019, 19:07
Где ошибка?
Код:
const Item::PropertyMap &overriddenProperties = propertiesItem->properties();
for (Item::PropertyMap::ConstIterator it = overriddenProperties.constBegin();
    it != overriddenProperties.constEnd(); ++it) {
        loadedItem->setProperty(it.key(), overriddenProperties.value(it.key()));
}
Не вижу прямой ошибки. Неясно зачем нужен еще поиск по ключу overriddenProperties.value(it.key()) если имеется итератор? Да и результат может быть разный если ключи не уникальны. Почему не it.value()?


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 17, 2019, 19:08
Не вижу прямой ошибки. Неясно зачем нужен еще поиск по ключу overriddenProperties.value(it.key()) если имеется итератор? Да и результат может быть разный если ключи не уникальны. Почему не it.value()?

Потому что лапша из итераторов и никто не замечал этого=)


Название: Re: SharedHash/Set
Отправлено: Igors от Май 17, 2019, 19:13
Потому что лапша из итераторов и никто не замечал этого=)
Не вижу где, поясните. Ну а вообще что оте "итераторные сопли" всем уже осто<> - то я давно говорил (был заклеймлен в неграмотности  :))


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 17, 2019, 19:34
Не вижу где, поясните. Ну а вообще что оте "итераторные сопли" всем уже осто<> - то я давно говорил (был заклеймлен в неграмотности  :))

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


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 17, 2019, 19:45
Ну а вообще что оте "итераторные сопли" всем уже осто<> - то я давно говорил (был заклеймлен в неграмотности  :))

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 18, 2019, 08:01
А еще пачку других методов, чтобы не передавать в алгоритмы begin/end, а передавать контейнер целиком.
Я наблюдал по меньшей мере с пяток таких попыток, но у всех были свои неудобства.

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

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

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

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


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 18, 2019, 12:45
Да, и ошибку-то все-таки покажите  :)
Всё верно, вместо О(N) получили N*logN, ошибка уровня студента. А из-за лапши переменных приглядели это на ревью.

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

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

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


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 18, 2019, 13:58
Тоже заглянул в пример :).

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

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 18, 2019, 16:27
Ну он прав, затея с вытиратором работать не будет для хэша.
Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после 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 не давать.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 18, 2019, 17:18
Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после 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.
Это упростит жизнь и вместо вытиратора можно хранить ссылку на пару ключ/значение.


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 18, 2019, 23:00
Не уверен. Разве где-то сказано что итераторы хеша становятся (сами) невалидными после rehash? Не нашел такого (правда не видел и обратного). Кстати что там по этому поводу в std::unordered_map?

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


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 18, 2019, 23:08
В качестве ключа следует использовать Raw указатель (Type *)
Интересная мысль. Но тогда как (или "из чего") отдать наружу шаред? Выходит weak нужен. Ну и шансов у (Type *) стать хламом столько же - только уже без проверки.
Указатель raw должен быть сугубо ключом, и ни в коем случае нельзя через него осуществлять доступ к членам (обращаться с ним, как с указателем). Даже если он "протухнет", соответствующее ему weak значение станет нулевым.


Название: Re: SharedHash/Set
Отправлено: Igors от Май 19, 2019, 11:09
Да, согласен, дама теория права - хранить итератор плохо. Уже сам факт того что надо выяснять "валидный али как" = плохо, тем более оказывается выяснить не так уж просто.

Хорошо, переделал, перезалил в стартовый пост. Для юзера все так же. Теперь 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

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


Название: Re: SharedHash/Set
Отправлено: ViTech от Май 19, 2019, 13:14
А если после удаления CSharedHash/Set будут существовать шареды, запихнутые методом Put с тем кастомным Deleter, что в примере, они потом тоже могут быть безболезненно удалены?
Да, для этого есть наблюдающий mLive.

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

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

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


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 19, 2019, 15:32
Прошу завалить  :)

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


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 01:33
охохохо, свершилось (https://doc-snapshots.qt.io/qt5-dev/qvector.html#QVector-6)!


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 03:58
Ваш спинлок полон data race=)
Обоснуйте. Возможно Вас смутило сравнение "не под мутексом", но оно корректно. И сразу прям уж "полон" :)

охохохо, свершилось (https://doc-snapshots.qt.io/qt5-dev/qvector.html#QVector-6)!
Радует глаз, работают товарищи


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 20, 2019, 08:10
Не очень понял что Вы хотели сказать. По-моему поиск по 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 рассматривает вопрос о прекращении поддержки своих решений в пользу стандартных.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 09:52
Обоснуйте. Возможно Вас смутило сравнение "не под мутексом", но оно корректно. И сразу прям уж "полон" :)

Я не силен в лок-фри алгоритмах но кажется проверка 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.


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 13:51
проверка id != mThreadID может сбоить.
Да, код вызывающий
Код
C++ (Qt)
if (id == mTreadID)
И при этом mTreadID может писаться любой ниткой! Обычно в multu-threading такие проверки - мертвому припарка (c оператором != то же самое). Но в данном случае они работают верно "по построению".

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

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

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 14:26
В общем случае - нет. Weak не контролирует свое состояние!
Предположим, есть ассоциативный массив, в качестве ключа которого используется weak. Узлы такого массива упорядочены между собой исходя из определенного правила сравнения ключей (оператор <, хеш или др.) и свойства их постоянности. Если каким-либо внешним способом (например, weak) изменить значение ключа в узле ассоциативного массива, то существующее упорядочивание узлов станет не корректным, и от ассоциативного контейнера можно ожидать непредвиденного поведения.
Считаю это верно для мапы, но не для хеша. Давайте я расскажу как вижу, а Вы если надо поправьте

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


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

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


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 14:31
НО оно никогда не станет равным (уникальному) id текущей нитки. Т.е. false останется false (пусть глуповато звучит)

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

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

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 14:53
Ну вот в этом и проблема, у вас уже вызвано UB, а значит, там может лежать что угодно.
Можно конечно долго рассуждать о том "да как же так у меня всё работает, да ни на одной архитектуре этого не будет", но с тз стандарта код не валиден.
Какое UB? mThreadID - вовсе не "что угодно", а id одной из ниток, их уникальность гарантируется. Др словами "если текущее mThreadID - не мое, то сделать его моим никто не сможет кроме меня". Обратное тоже верно. Нам-то нужно не само mThreadID а "мое или нет"

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



Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 15:15
Какое UB? mThreadID - вовсе не "что угодно", а id одной из ниток, их уникальность гарантируется. Др словами "если текущее mThreadID - не мое, то сделать его моим никто не сможет кроме меня". Обратное тоже верно. Нам-то нужно не само mThreadID а "мое или нет"

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

У меня коллега думает, что если написать
Код:
ptr = std::make_shared<Data>();
data_ready = true;

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

if (data_ready)
   foo(ptr.get());
то мьютексы и атомики не нужны, ну а чо, у него ж работает, он же проверил!

Читаем cppref (https://en.cppreference.com/w/cpp/language/memory_model):
Цитировать
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 не выполнены "по построению".


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 15:31
Давайте я вам попробую объяснить, как на самом деле работает 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: вероятность файр резиста крайне мала


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 20, 2019, 15:41
Считаю это верно для мапы, но не для хеша. Давайте я расскажу как вижу, а Вы если надо поправьте

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

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

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 16:04
1. После обнуления weak остается не в своей корзине и найти его уже не представляется возможным, так как weak (ключ) уже нулевой, и хеш соответственно другой.
Хеш тот же самый, он вычисляется один раз при вставке и хранится (qHash может быть затратным)

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

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


Название: Re: SharedHash/Set
Отправлено: Igors от Май 20, 2019, 16:49
У меня коллега думает, что если написать
Код:
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 разных ниток, и все соображения выше столь же справедливы.


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 17:12
Ну да, гипотетически возможен "некий компилятор на некой платформе" где присваивание булевского 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!"


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 17:28
Позвольте, а как же пункт 1 выше?

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


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 18:03
1. После обнуления weak остается не в своей корзине и найти его уже не представляется возможным, так как weak (ключ) уже нулевой, и хеш соответственно другой.

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


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 20, 2019, 22:24
Я в упор не вижу откуда пошло обсуждение 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);
}
 


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 20, 2019, 23:52
Файл HashUtils.h

Ну такое...


Название: Re: SharedHash/Set
Отправлено: Igors от Май 21, 2019, 07:42
Некая платформа - это, например, 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 спиннер? Там тоже велик писать? Нуу...


Название: Re: SharedHash/Set
Отправлено: ssoft от Май 21, 2019, 08:08
Да, и кстати о птичках: где там в std спиннер? Там тоже велик писать? Нуу...

std::atomic_flag https://en.cppreference.com/w/cpp/atomic/atomic_flag


Название: Re: SharedHash/Set
Отправлено: Igors от Май 21, 2019, 08:35
std::atomic_flag https://en.cppreference.com/w/cpp/atomic/atomic_flag
Ага, рекомендация писать велик. И уже не в первый раз замечаю - std пример "сыроват" (мягко говоря)
Код:
while (lock.test_and_set(std::memory_order_acquire))  // acquire lock
       ; // spin
И все, управился. Хоть бы yield воткнул для приличия. Напр в tbb это место (прокрутка) занимает не одну страницу (сначала просто, потом nop'ы, а потом уж yield). Да и вообще такая ходовая вещь давно штатная даже в ОС (напр OSSpinLockLock/Unlock)


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 21, 2019, 11:14
Ага, рекомендация писать велик. И уже не в первый раз замечаю - std пример "сыроват" (мягко говоря)

Просто спинлок надо применять в умом и в 99% случаев вам нужен банальный мьютекс. Не надо пытаться делать Premature Optimisation.

Вас удивит, но задротская lock-free-queue на линкед листе быстрее тупого std::vector+std::mutex всего процентов на 10... из-за аллокаций нодов списка!
Типа вот вы сели, потратили 2 дня на написание "супер быстрого класса" и вот облом, выигрыш мизерный. Или теперь еще свой аллокатор пиши. Который должен быть thread-safe. А значит иметь мьютекс внутри? Проблема, да?
Хотя иногда 10% прироста это дофига, но, опять же, 1% случаев.


Название: Re: SharedHash/Set
Отправлено: Igors от Май 21, 2019, 16:25
Просто спинлок надо применять в умом и в 99% случаев вам нужен банальный мьютекс. Не надо пытаться делать Premature Optimisation.
Premature Optimisation всегда была (и будет) любимым аргументом всех сачков и говнокодеров :) Ну и 99% взято с потолка, напр на рендере обычно только спиннеры.

Типа вот вы сели, потратили 2 дня..
Ничего я не сидел, сам юзаю tbb, но не тащить же его сюда - ну идею помню, оформил на Qt, жалко десяток строчек, что ли?

Вас удивит, но задротская lock-free-queue на линкед листе..
Не удивит, lock-free даже сам по себе не всегда быстрее. Но главный его минус - капитальный "вынос мозга", слишком трудоемко, часто лучше по-простому залочить - и все дела, чем так париться.

Ну вот, опять "растекаемся мыслью по древу", что с хешем/сетом?


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 21, 2019, 16:41
Ну вот, опять "растекаемся мыслью по древу", что с хешем/сетом?

А чо с ним?) Попробуйте сделать так:
Код:
template<typename Key, typename Value, typename Args...>
void insert(Key key, Args args...)
{
    struct Deleter
    {
        Key key;
        Hash *hash; // тут weak_ptr возможно?
        Deleter(Key key, Hash *hash) : key(std::move(key)), hash(hash) {}
        void operator(Value *)
        {
             const auto it = hash->find(key);
             if (it != hash->end())
             erase(it);
             delete ptr;
        }
    };
    Deleter deleter(key, this);
    m_map.insert({std::reference_wrapper(deleter.key), std::make_shared<Value, deleter>(std::forward(args...)});
}


Название: Re: SharedHash/Set
Отправлено: Igors от Май 22, 2019, 07:41
О боже! move, reference_wrapper, make_shared, forward, args - ничего из этого я (пока) не использую (на С++ 11 переполз только в этом году). Ну ладно, все-таки рискну покритиковать

1) Если есть ключ - ясно что в принципе все решается, проблема с Set где ключ - сами данные

2) Хранение еще одной копии ключа в Deleter'е не "смертный грех", но точно не украшает

3) thread-safe просто нет, причем хз как добавить. Просто так залочить Deleter::operator() + тело insert очевидно не проходит.

У меня впечатление что все беды от сильно вумного deleter'а, т.е. мы напрасно поручаем ему ф-ционал чистки. Чем тупее deleter - тем лучше, а еще лучше без него (ну здесь не выходит, ото пусть счетчик увеличивает).

Все-таки жаль что новые фишки никак здесь не помогают. Ну ладно, похоже осуждение выдохлось, уже начинаем ходить по кругу. Ничего, не всякая вещь должна иметь простой и ясный "правельный ответ"

Спасибо всем участникам


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 22, 2019, 09:58
1) Если есть ключ - ясно что в принципе все решается, проблема с Set где ключ - сами данные
2) Хранение еще одной копии ключа в Deleter'е не "смертный грех", но точно не украшает
3) thread-safe просто нет, причем хз как добавить. Просто так залочить Deleter::operator() + тело insert очевидно не проходит.

1) Сет реализуется через мапу. Храните weak как значение а ключ - raw pointer.

2) Референт_враппер и нужен для того, чтобы хранить ключ _один_ раз - например, в делетере. Я не уверен, правда, что это сработает=) Но попробовать стоит.

3) Очевидно ли?=)


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 22, 2019, 10:40
Предыдущий вариант был совсем на коленке и я не учел что делетер на стеке, а значит референс не получить.
Но можно сделать так:

Код:
template<typename Key, typename Value, typename Args...>
void insert(Key key, Args args...)
{
    auto &data = m_map[key];
    const auto &keyRef = data.first; // нам гарантируют стабильность ссылок
    auto deleter = [this, keyRef](Value *)
    {
        if (const auto it = m_map.find(keyRef); it != m_map.end())
            erase(it);
        delete ptr;
    };
    data.second = std::shared_ptr<Value, ???>(new Value(std::forward(args...)), deleter);
}


Название: Re: SharedHash/Set
Отправлено: Igors от Май 23, 2019, 07:13
1) Сет реализуется через мапу. Храните weak как значение а ключ - raw pointer.
Такой ключ - адрес, а искать (хоть в мапе) нужно содержимое (стартовый пост "а если "abc" уже есть?") которое может сидеть по любому адресу.

3) Очевидно ли?=)
Да. Очевидна "щель" между моментом когда weak обнулился но deleter еще не получил упр-е. За это время напр мапа/хеш опять заполняются по тому же ключу, и  "привет".


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 23, 2019, 10:19
Да. Очевидна "щель" между моментом когда weak обнулился но deleter еще не получил упр-е. За это время напр мапа/хеш опять заполняются по тому же ключу, и  "привет".

Не очевидна, делетер получает управление ДО того, как weak занулится.
Там что-то типа такого:
Код:
if (!strong.deref())
    deleteValue();
if (!weak.deref())
    deleteControlBlock();
Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .


Название: Re: SharedHash/Set
Отправлено: Igors от Май 23, 2019, 12:28
Там что-то типа такого:
Код:
if (!strong.deref())
                              <---  point A
    deleteValue();
if (!weak.deref())
    deleteControlBlock();
Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .
Пусть так, покатаем. Пусть в точке А данная нитка вытеснена, до deleter'а дело еще не дошло. В это время др нитка захватила лок и находит "дырку" где значение уже null (strong.deref отработал), вписывает туда новые данные по тому же ключу, освобождает лок и уходит. Теперь просыпается deleter, захватывает лок и грохает итератор по тому же ключу. Итог: мапа/хеш потеряла шаред.

Впрочем это обычное дело с lock-free: ф-ционала еще с гулькин нос, а вот мозголомки уже хватает :) Не нужно в это ввязываться без нужды, изначальная задумка "удалять итератор из deleter'а" была неудачной


Название: Re: SharedHash/Set
Отправлено: Авварон от Май 23, 2019, 12:54
Ну эта проблема лечится очень просто - надо проверять, что в мапе лежит "наш" шаред.
Я лишь описал идею, там много кейзов, которые я не расписал - ключ есть в мапе, но значение равно 0 (идет удаление), то, что вы описали, ключ есть в мапе и зачение != 0 (знач ничего делать не надо?).


Название: Re: SharedHash/Set
Отправлено: AkonResumed от Октябрь 18, 2020, 20:09
Цитировать
Сто раз обсуждали, но давайте еще:
1. QtContainers требуют T(), что заставляет делать null state у T (QString::isNull/isEmpty), что не для любого T имеет смысл.
2. QtContainers требуют T(const T&). Хотите положить unique_ptr в вектор? забудьте.
3. QtContainers не имеют emplace* методов. Если не юзать pimpl то append(T&&) может быть более затратным (каждый мембер же надо мувнуть). Впрочем, это мелочь.
4. QtContainers не имеют range_insert методов. Хотите быстро вставить в вектор, не двигая полвектора на каждый элемент? Пишите руками.
5. QtContainers любят детачить в рандомных местах, что заставляют писать boilerplate код с qAsConst/временными переменными. Поглядите как "умело" обращаются с ними сами кутешники: https://codereview.qt-project.org/#/c/253792/ Куча таких мест делала дип-копию контейнера. Ухху!
6. QtContainers медленее за счет лишнего разыменования d_ptr. Это в Qt6 пофиксят, правда.
7. QtContainers медленее за счет постоянной проверки refcount, даже когда идет append в цикле.
8. QtContainers генерят больше бинарного кода: https://codereview.qt-project.org/#/c/261870/
9. QMap/QHash нельзя итерировать в range-for по ключу-значению, что либо заставляет писать говнокод с итераторами, либо говнокод с .keys() и последующим .value(). Ухху!
Для некоторых алгоритмов фатальный недостаток QtContainers - нет возможности выравнивания данных (нет аллокатора, идущего параметром шаблона в контейнерах stl).