Russian Qt Forum
Март 28, 2024, 23:38 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 ... 3 4 [5]   Вниз
  Печать  
Автор Тема: SharedHash/Set  (Прочитано 48520 раз)
ssoft
Программист
*****
Offline Offline

Сообщений: 574


Просмотр профиля
« Ответ #60 : Май 21, 2019, 08:08 »

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

std::atomic_flag https://en.cppreference.com/w/cpp/atomic/atomic_flag
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #61 : Май 21, 2019, 08:35 »

Ага, рекомендация писать велик. И уже не в первый раз замечаю - std пример "сыроват" (мягко говоря)
Код:
while (lock.test_and_set(std::memory_order_acquire))  // acquire lock
       ; // spin
И все, управился. Хоть бы yield воткнул для приличия. Напр в tbb это место (прокрутка) занимает не одну страницу (сначала просто, потом nop'ы, а потом уж yield). Да и вообще такая ходовая вещь давно штатная даже в ОС (напр OSSpinLockLock/Unlock)
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #62 : Май 21, 2019, 11:14 »

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

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #63 : Май 21, 2019, 16:25 »

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

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

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

Ну вот, опять "растекаемся мыслью по древу", что с хешем/сетом?
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #64 : Май 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...)});
}
« Последнее редактирование: Май 21, 2019, 16:47 от Авварон » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #65 : Май 22, 2019, 07:41 »

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

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

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

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

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

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

Спасибо всем участникам
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #66 : Май 22, 2019, 09:58 »

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

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

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

3) Очевидно ли?=)
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #67 : Май 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);
}
« Последнее редактирование: Май 23, 2019, 11:45 от Авварон » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #68 : Май 23, 2019, 07:13 »

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

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

Сообщений: 3257


Просмотр профиля
« Ответ #69 : Май 23, 2019, 10:19 »

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #70 : Май 23, 2019, 12:28 »

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

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

Сообщений: 3257


Просмотр профиля
« Ответ #71 : Май 23, 2019, 12:54 »

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

Сообщений: 81


Просмотр профиля
« Ответ #72 : Октябрь 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).
Записан
Страниц: 1 ... 3 4 [5]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.058 секунд. Запросов: 23.