Russian Qt Forum
Март 28, 2024, 23:38
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Qt
>
Кладовая готовых решений
(Модератор:
Пантер
) >
SharedHash/Set
Страниц:
1
...
3
4
[
5
]
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: SharedHash/Set (Прочитано 48520 раз)
ssoft
Программист
Offline
Сообщений: 574
Re: SharedHash/Set
«
Ответ #60 :
Май 21, 2019, 08:08 »
Цитата: Igors от Май 21, 2019, 07:42
Да, и кстати о птичках: где там в std спиннер? Там тоже велик писать? Нуу...
std::atomic_flag
https://en.cppreference.com/w/cpp/atomic/atomic_flag
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: SharedHash/Set
«
Ответ #61 :
Май 21, 2019, 08:35 »
Цитата: ssoft от Май 21, 2019, 08:08
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)
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #62 :
Май 21, 2019, 11:14 »
Цитата: Igors от Май 21, 2019, 08:35
Ага, рекомендация писать велик. И уже не в первый раз замечаю - std пример "сыроват" (мягко говоря)
Просто спинлок надо применять в умом и в 99% случаев вам нужен банальный мьютекс. Не надо пытаться делать Premature Optimisation.
Вас удивит, но задротская lock-free-queue на линкед листе быстрее тупого std::vector+std::mutex всего процентов на 10... из-за аллокаций нодов списка!
Типа вот вы сели, потратили 2 дня на написание "супер быстрого класса" и вот облом, выигрыш мизерный. Или теперь еще свой аллокатор пиши. Который должен быть thread-safe. А значит иметь мьютекс внутри? Проблема, да?
Хотя иногда 10% прироста это дофига, но, опять же, 1% случаев.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: SharedHash/Set
«
Ответ #63 :
Май 21, 2019, 16:25 »
Цитата: Авварон от Май 21, 2019, 11:14
Просто спинлок надо применять в умом и в 99% случаев вам нужен банальный мьютекс. Не надо пытаться делать Premature Optimisation.
Premature Optimisation всегда была (и будет) любимым аргументом всех сачков и говнокодеров
Ну и 99% взято с потолка, напр на рендере обычно только спиннеры.
Цитата: Авварон от Май 21, 2019, 11:14
Типа вот вы сели, потратили 2 дня..
Ничего я не сидел, сам юзаю tbb, но не тащить же его сюда - ну идею помню, оформил на Qt, жалко десяток строчек, что ли?
Цитата: Авварон от Май 21, 2019, 11:14
Вас удивит, но задротская lock-free-queue на линкед листе..
Не удивит, lock-free даже сам по себе не всегда быстрее. Но главный его минус - капитальный "вынос мозга", слишком трудоемко, часто лучше по-простому залочить - и все дела, чем так париться.
Ну вот, опять "растекаемся мыслью по древу", что с хешем/сетом?
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #64 :
Май 21, 2019, 16:41 »
Цитата: Igors от Май 21, 2019, 16:25
Ну вот, опять "растекаемся мыслью по древу", что с хешем/сетом?
А чо с ним?) Попробуйте сделать так:
Код:
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
Сообщений: 11445
Re: SharedHash/Set
«
Ответ #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
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #66 :
Май 22, 2019, 09:58 »
Цитата: Igors от Май 22, 2019, 07:41
1) Если есть ключ - ясно что в принципе все решается, проблема с Set где ключ - сами данные
2) Хранение еще одной копии ключа в Deleter'е не "смертный грех", но точно не украшает
3) thread-safe просто нет, причем хз как добавить. Просто так залочить Deleter::operator() + тело insert очевидно не проходит.
1) Сет реализуется через мапу. Храните weak как значение а ключ - raw pointer.
2) Референт_враппер и нужен для того, чтобы хранить ключ _один_ раз - например, в делетере. Я не уверен, правда, что это сработает=) Но попробовать стоит.
3) Очевидно ли?=)
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #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
Сообщений: 11445
Re: SharedHash/Set
«
Ответ #68 :
Май 23, 2019, 07:13 »
Цитата: Авварон от Май 22, 2019, 09:58
1) Сет реализуется через мапу. Храните weak как значение а ключ - raw pointer.
Такой ключ - адрес, а искать (хоть в мапе) нужно содержимое (стартовый пост "а если "abc" уже есть?") которое может сидеть по любому адресу.
Цитата: Авварон от Май 22, 2019, 09:58
3) Очевидно ли?=)
Да. Очевидна "щель" между моментом когда weak обнулился но deleter еще не получил упр-е. За это время напр мапа/хеш опять заполняются по тому же ключу, и "привет".
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #69 :
Май 23, 2019, 10:19 »
Цитата: Igors от Май 23, 2019, 07:13
Да. Очевидна "щель" между моментом когда weak обнулился но deleter еще не получил упр-е. За это время напр мапа/хеш опять заполняются по тому же ключу, и "привет".
Не очевидна, делетер получает управление ДО того, как weak занулится.
Там что-то типа такого:
Код:
if (!strong.deref())
deleteValue();
if (!weak.deref())
deleteControlBlock();
Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: SharedHash/Set
«
Ответ #70 :
Май 23, 2019, 12:28 »
Цитата: Авварон от Май 23, 2019, 10:19
Там что-то типа такого:
Код:
if (!strong.deref())
<--- point A
deleteValue();
if (!weak.deref())
deleteControlBlock();
Если кто-то придет за значением после делетера - ну ой, не повезло, стронгРеф == 0, а значит значения уже как бы и нет .
Пусть так, покатаем. Пусть в точке А данная нитка вытеснена, до deleter'а дело еще не дошло. В это время др нитка захватила лок и находит "дырку" где значение уже null (strong.deref отработал), вписывает туда новые данные по тому же ключу, освобождает лок и уходит. Теперь просыпается deleter, захватывает лок и грохает итератор по тому же ключу. Итог: мапа/хеш потеряла шаред.
Впрочем это обычное дело с lock-free: ф-ционала еще с гулькин нос, а вот мозголомки уже хватает
Не нужно в это ввязываться без нужды, изначальная задумка "удалять итератор из deleter'а" была неудачной
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: SharedHash/Set
«
Ответ #71 :
Май 23, 2019, 12:54 »
Ну эта проблема лечится очень просто - надо проверять, что в мапе лежит "наш" шаред.
Я лишь описал идею, там много кейзов, которые я не расписал - ключ есть в мапе, но значение равно 0 (идет удаление), то, что вы описали, ключ есть в мапе и зачение != 0 (знач ничего делать не надо?).
Записан
AkonResumed
Чайник
Offline
Сообщений: 81
Re: SharedHash/Set
«
Ответ #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
]
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...