SharedHash/Set

[ssoft]

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

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

[Igors]

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)

[Авварон]

Ага, рекомендация писать велик. И уже не в первый раз замечаю - std пример "сыроват" (мягко говоря)

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

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

[Igors]

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

Premature Optimisation всегда была (и будет) любимым аргументом всех сачков и говнокодеров Ну и 99% взято с потолка, напр на рендере обычно только спиннеры.

Типа вот вы сели, потратили 2 дня..

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

Вас удивит, но задротская lock-free-queue на линкед листе..

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

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

[Авварон]

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

А чо с ним?) Попробуйте сделать так:

Код:

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...)});
}

[Igors]

О боже! move, reference_wrapper, make_shared, forward, args - ничего из этого я (пока) не использую (на С++ 11 переполз только в этом году). Ну ладно, все-таки рискну покритиковать

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

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

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

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

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

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

[Авварон]

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

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

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

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

[Авварон]

Предыдущий вариант был совсем на коленке и я не учел что делетер на стеке, а значит референс не получить.
Но можно сделать так:

Код:

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);
}

[Igors]

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

Такой ключ - адрес, а искать (хоть в мапе) нужно содержимое (стартовый пост "а если "abc" уже есть?") которое может сидеть по любому адресу.

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

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

[Авварон]

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

Не очевидна, делетер получает управление ДО того, как weak занулится.
Там что-то типа такого:

Код:

if (!strong.deref())
    deleteValue();
if (!weak.deref())
    deleteControlBlock();

Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .

[Igors]

Там что-то типа такого:

Код:

if (!strong.deref())
                              <---  point A
    deleteValue();
if (!weak.deref())
    deleteControlBlock();

Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .

Пусть так, покатаем. Пусть в точке А данная нитка вытеснена, до deleter'а дело еще не дошло. В это время др нитка захватила лок и находит "дырку" где значение уже null (strong.deref отработал), вписывает туда новые данные по тому же ключу, освобождает лок и уходит. Теперь просыпается deleter, захватывает лок и грохает итератор по тому же ключу. Итог: мапа/хеш потеряла шаред.

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

[Авварон]

Ну эта проблема лечится очень просто - надо проверять, что в мапе лежит "наш" шаред.
Я лишь описал идею, там много кейзов, которые я не расписал - ключ есть в мапе, но значение равно 0 (идет удаление), то, что вы описали, ключ есть в мапе и зачение != 0 (знач ничего делать не надо?).

[AkonResumed]

Сто раз обсуждали, но давайте еще:
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).