Re[5]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 09.08.18 09:09
Оценка: +3
Здравствуйте, ·, Вы писали:

MD>>Ну, поинтересовался он. Услышал в ответ "вас тут не стояло", потому что контейнер с тех пор успели дважды очистить и заново наполнить. Что тогда делаем в плюс-плюсинге?

·>В его случае самым оптимальным было бы снапшотиться,

продумывать архитектуру.

Дело в том, что от постановки вопроса веет подходом "мы не знаем, сколько у нас будет потоков и вообще не подумали о межпоточном взаимодействии, поэтому нам нужен потокобезопасный контейнер".
Классический "Failing to plan is planning to fail".
www.blinnov.com
Re: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: LaptevVV Россия  
Дата: 02.08.18 17:12
Оценка: -2
ksd>возможен ли готовый хороший субж в природе?
ksd>(вектор, лист, сет или их аналоги -- все подойдет)
А что такое неинвалидирующие итераторы?
А то в С++17 контейнеры уже сделаны потокобезопасными вроде.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[7]: у него много обращений на чтение, и очень очень редко на запись
От: Кодт Россия  
Дата: 10.08.18 11:09
Оценка: 37 (1)
Здравствуйте, Sinclair, Вы писали:

S>Для такого случая с запасом подойдёт обычный односвязный список с lock-free операциями вставки/удаления через interlocked инструкции.

S>Единственные сложности — это управление временем жизни элементов списка; т.е. при erase мы рискуем выполнить delete на элементе, который всё ещё кто-то читает.

shared_ptr — lock-free.

Но тут другая история вылезет. Степень дробности того, какие операции мы считаем атомарными. И какие — согласованными по времени (Хоть lock, хоть не lock).
— вызов колбека у одного подписчика
— рассылка на всех подписчиков
— каскад рассылок (т.е. если те начнут сами что-то рассылать или добавлять-удалять...)
— рассылка и что-то плюс-минус вокруг неё на усмотрение рассылающей стороны (например, дождаться квитанции от подписчика — понятно, что на этом отрезке нельзя просто так взять и убить ни подписчика, ни отправителя)

— удаление синхронное (в деструкторе происходит содержательная работа, например, удаляется сеть зависимых объектов)
— сборка мусора асинхронная, "когда получится" (даже с shared_ptr)

— рассылка синхронная (отправитель знает, что когда он вернулся из функции "разослать всё" — всё разослано; возможно, не всем — кого-то убили, кого-то добавили, ну тем не повезло)
— асинхронная (заявку оформил, дальше оно само когда очередь дойдёт)

— каскады событий происходят в одном потоке или в разных (в первом случае синхронность нам навязана, во втором — мы ещё должны за неё побороться)

Это уже архитектурные вопросы.

Я видел некое дерьмо, когда невинная рассылка приводила к длительной вибрации всей сети объектов, причём даже в одном потоке. И вот там вышибание табуретки из-под цикла рассылки — как нефиг делать.
И естественно, никакое лок-фри тут не поможет, равно как рекурсивные мьютексы (а вот нерекурсивные помогут: предсказуемо повесят программу или кинут исключение).
Перекуём баги на фичи!
Re: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: a7d3  
Дата: 07.08.18 16:30
Оценка: 4 (1)
Здравствуйте, ksd, Вы писали:

ksd>возможен ли готовый хороший субж в природе?

ksd>(вектор, лист, сет или их аналоги -- все подойдет)

Держи «Потокобезопасный std::map с производительностью lock-free map»
общая вводная по либе «Lock-free структуры данных. Извне: введение в libcds»
Re[2]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: uzhas Ниоткуда  
Дата: 07.08.18 16:19
Оценка: +1
Здравствуйте, LaptevVV, Вы писали:

LVV>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.


о чем речь? что изменилось в плане потокобезопасности для старых контейнеров или какие-то новые контейнеры появились?
Re: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 08.08.18 11:30
Оценка: :)
Здравствуйте, ksd, Вы писали:

ksd>возможен ли готовый хороший субж в природе?


Нет. Но если возник такой вопрос, то самый правильный ответ — нужно продумывать архитектуру.

ksd>(вектор, лист, сет или их аналоги -- все подойдет)


Сферической потокобезопасности в вакууме не бывает. Ее можно натянуть на контейнеры, которые используются исключительно через операции единичной вставки/чтения (очередь, к примеру)

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

for (auto i = container.begin(); i != container.end(); ++i)
{
    auto some_value = do_something_with(*i);
    call_some_other_code(some_value);
    // another 100500 lines of code
}


Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.
www.blinnov.com
Отредактировано 08.08.2018 11:39 landerhigh . Предыдущая версия .
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: a7d3  
Дата: 09.08.18 08:53
Оценка: +1
Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, landerhigh, Вы писали:


L>>
L>>for (auto i = container.begin(); i != container.end(); ++i)
L>>{
L>>    auto some_value = do_something_with(*i);
L>>    call_some_other_code(some_value);
L>>    // another 100500 lines of code
L>>}
L>>


L>>Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.


BFE>Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?


И тем не менее правда на стороне .
А все попытки натянуть сову на глобус с неуместными аналогиями — это просто капризы дилетантов, незнакомых с элементарными, базисными вещами. Тем, как именно, в какую сторону продумывается архитектура и взаимодействие со структурами данным в объектной модели малтитредового софта.
Из разряда: «да, мы пишем на С++, но давайте чтобы без эксепшенов, а то как-то сложно с ними получается».

Зачем цепляться за идиому итераторов в плане многопоточного доступа к контейнеру? Чтобы героически бороться с мельницами?
Что афтар топика решает своим итерированием по контейнеру? Делает последовательный проход, для чего? Чтобы последовательно вызвать несколько обработчиков/действий.
Не уж то это же самое нельзя сделать иначе как через последовательный доступ итератором?

Содержимое этого контенера — есть пачка заданий для треда, с вероятностью 1/(10³×10³) в процессе выполнения может потребоваться добавить или убрать что-то из этой пачки из другого треда. И что, это конец света? Иначе чем через итераторы не сделать?
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: Ops Россия  
Дата: 09.08.18 10:52
Оценка: +1
Здравствуйте, B0FEE664, Вы писали:

BFE>Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?


Контейнер — это не база данных. Если нужна база данных, КО советует взять базу данных.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: ksd Россия  
Дата: 02.08.18 16:24
Оценка:
возможен ли готовый хороший субж в природе?
(вектор, лист, сет или их аналоги -- все подойдет)
Отредактировано 02.08.2018 16:25 ksd . Предыдущая версия .
Re[2]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: placement_new  
Дата: 02.08.18 17:23
Оценка:
Здравствуйте, LaptevVV, Вы писали:

ksd>>возможен ли готовый хороший субж в природе?

ksd>>(вектор, лист, сет или их аналоги -- все подойдет)
LVV>А что такое неинвалидирующие итераторы?
LVV>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.
Re[2]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: ksd Россия  
Дата: 03.08.18 09:35
Оценка:
Здравствуйте, LaptevVV, Вы писали:

ksd>>возможен ли готовый хороший субж в природе?

ksd>>(вектор, лист, сет или их аналоги -- все подойдет)
LVV>А что такое неинвалидирующие итераторы?
в треде 1 получаем итератор и перебираем элементы в контейнере, в треде 2 делаем insert или erase -- итератор в треде 1 не отваливается.


LVV>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.

это замечательно!
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: IID Россия  
Дата: 04.08.18 18:28
Оценка:
Здравствуйте, ksd, Вы писали:

LVV>>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.

ksd>это замечательно!

Внутренняя потокобезопасность это тормоза.
kalsarikännit
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: Mr.Delphist  
Дата: 06.08.18 16:23
Оценка:
Здравствуйте, ksd, Вы писали:

ksd>в треде 1 получаем итератор и перебираем элементы в контейнере, в треде 2 делаем insert или erase -- итератор в треде 1 не отваливается.


А теперь следующий вопрос: что должно произойти про инкременте/декременте этого итератора? От этого и плясать.
Re[4]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: sergey2b ЮАР  
Дата: 06.08.18 16:39
Оценка:
Здравствуйте, IID, Вы писали:

IID>Здравствуйте, ksd, Вы писали:


LVV>>>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.

ksd>>это замечательно!

IID>Внутренняя потокобезопасность это тормоза.


может у него в контейнере 100 элементов и обращения к нему пару раз в минуту
если это не так ТС написал об этом в первом сообщение
Re[5]: у него много обращений на чтение, и очень очень редко на запись
От: ksd Россия  
Дата: 08.08.18 09:44
Оценка:
Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, IID, Вы писали:


IID>>Здравствуйте, ksd, Вы писали:


LVV>>>>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.

ksd>>>это замечательно!

IID>>Внутренняя потокобезопасность это тормоза.


S>может у него в контейнере 100 элементов и обращения к нему пару раз в минуту

S>если это не так ТС написал об этом в первом сообщение
++ "у него" в контейнере ~10 элементов, но много обращений на чтение:
    struct Subsc_t {
        virtual void doSome() = 0;
    };

    set<Subsc_t*> subscribers;

    for (auto s: subscribers) {
        s->doSome();
    }

и с очень маленькой вероятностью в миллионы раз реже может быть из другого треда subscribers.insert(some) или erase;
завернуть for в критическую секцию не вариант.
Re[2]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: ksd Россия  
Дата: 08.08.18 12:13
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, ksd, Вы писали:


ksd>>возможен ли готовый хороший субж в природе?


L>Нет. Но если возник такой вопрос, то самый правильный ответ — нужно продумывать архитектуру.


ksd>>(вектор, лист, сет или их аналоги -- все подойдет)


L>Сферической потокобезопасности в вакууме не бывает. Ее можно натянуть на контейнеры, которые используются исключительно через операции единичной вставки/чтения (очередь, к примеру)


L>Попытка сделать "потокобезопасными" контейнеры, по которым необходимо итерироваться, в конечном итоге приводит к куче проблем и выкорчевыванию "изобретения" из проекта.


L>
L>for (auto i = container.begin(); i != container.end(); ++i)
L>{
L>    auto some_value = do_something_with(*i);
L>    call_some_other_code(some_value);
L>    // another 100500 lines of code
L>}
L>


L>Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.

это еще почему?! итератор может же в операторе ++ поинтересоваться, обновился контейнер или нет?
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 08.08.18 12:58
Оценка:
Здравствуйте, ksd, Вы писали:

L>>Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.

ksd>это еще почему?! итератор может же в операторе ++ поинтересоваться, обновился контейнер или нет?

Может. Ну, допустим, обновился (если раньше не упадет, см. ниже). Дальше что?

Далее:

some_type do_something_with(const some_other_type& what)
{
    //....
}

for (auto i = container.begin(); i != container.end(); ++i)
{
    auto some_value = do_something_with(*i);      // А в этот прекрасный момент другой поток делает контейнеру clear()
}



Иными словами, попытка изобрести универсальный потокобезопасный контейнер ни к чему хорошему не приводит.
www.blinnov.com
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: Mr.Delphist  
Дата: 08.08.18 13:07
Оценка:
Здравствуйте, ksd, Вы писали:

ksd>это еще почему?! итератор может же в операторе ++ поинтересоваться, обновился контейнер или нет?


Ну, поинтересовался он. Услышал в ответ "вас тут не стояло", потому что контейнер с тех пор успели дважды очистить и заново наполнить. Что тогда делаем в плюс-плюсинге?
Re[4]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: · Великобритания  
Дата: 08.08.18 14:33
Оценка:
Здравствуйте, Mr.Delphist, Вы писали:

ksd>>это еще почему?! итератор может же в операторе ++ поинтересоваться, обновился контейнер или нет?

MD>Ну, поинтересовался он. Услышал в ответ "вас тут не стояло", потому что контейнер с тех пор успели дважды очистить и заново наполнить. Что тогда делаем в плюс-плюсинге?
В его случае самым оптимальным было бы снапшотиться, т.е. старый итератор должен будет продолжать обход старой коллекции. С случае наличия gc (в java) я бы делал так:

    volatile Set<Subsc_t> subscribers = Collections.emptySet();

public void doSome()
{//тут локи не нужны, т.к. коллекция никогда не меняется
    for (var s: subscribers) {
        s->doSome();
    }
}
public void add(Subscrber s)
{
    synchronized(lock) {
        var newSubscribers = new HashSet<>(subscribers);//потому что мы всегда создаём новую
        newSubscribers.add(s);
        subscribers = newSubscribers;
    }
}

Без gc что-то даже не знаю как это нормально сделать... Идеи?
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: B0FEE664  
Дата: 09.08.18 08:03
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>
L>for (auto i = container.begin(); i != container.end(); ++i)
L>{
L>    auto some_value = do_something_with(*i);
L>    call_some_other_code(some_value);
L>    // another 100500 lines of code
L>}
L>


L>Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.


Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?
И каждый день — без права на ошибку...
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 09.08.18 09:04
Оценка:
Здравствуйте, B0FEE664, Вы писали:

L>>Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера.

BFE>Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?

Речь идет о контейнерах.
Попытка сделать из контейнера базу данных с преферансом, барышнями и transaction isolation только потому, что авторам лень или не хватает терпения продумать архитектуру ведет к эпичному провалу более чем всегда.

Когда нужно именно хранилище с транзакционностью, со снапшотами и т.п., тогда и вопрос ставят именно так
www.blinnov.com
Re[6]: у него много обращений на чтение, и очень очень редко на запись
От: Кодт Россия  
Дата: 09.08.18 09:57
Оценка:
Здравствуйте, ksd, Вы писали:

ksd>++ "у него" в контейнере ~10 элементов, но много обращений на чтение:

ksd>и с очень маленькой вероятностью в миллионы раз реже может быть из другого треда subscribers.insert(some) или erase;
ksd>завернуть for в критическую секцию не вариант.

А завернуть в read-write lock — вариант?

В С++17 это называется std::shared_mutex.
Перекуём баги на фичи!
Re[3]: нужен контейнер, потокобезопасный, с неинвалидирующимися ите
От: LaptevVV Россия  
Дата: 09.08.18 11:40
Оценка:
LVV>>А то в С++17 контейнеры уже сделаны потокобезопасными вроде.
U>о чем речь? что изменилось в плане потокобезопасности для старых контейнеров или какие-то новые контейнеры появились?
Да фигню спорол.
Параллельныее версии алгоритмов появились, которые нормально со стандартными контейнерами работают.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: B0FEE664  
Дата: 09.08.18 12:07
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Речь идет о контейнерах.

И?

L>Попытка сделать из контейнера базу данных с преферансом, барышнями и transaction isolation только потому, что авторам лень или не хватает терпения продумать архитектуру ведет к эпичному провалу более чем всегда.


Может приводит, а может и нет, только вот к "Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера" это отношения не имеет.
И каждый день — без права на ошибку...
Re[7]: у него много обращений на чтение, и очень очень редко на запись
От: ksd Россия  
Дата: 09.08.18 12:11
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, ksd, Вы писали:


ksd>>++ "у него" в контейнере ~10 элементов, но много обращений на чтение:

ksd>>и с очень маленькой вероятностью в миллионы раз реже может быть из другого треда subscribers.insert(some) или erase;
ksd>>завернуть for в критическую секцию не вариант.

К>А завернуть в read-write lock — вариант?


К>В С++17 это называется std::shared_mutex.

возможно, это самое простое решение...
Re[4]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: B0FEE664  
Дата: 09.08.18 12:21
Оценка:
Здравствуйте, Ops, Вы писали:

BFE>>Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?

Ops>Контейнер — это не база данных. Если нужна база данных, КО советует взять базу данных.

Это вы просто не знакомы с безумными реалиями современного софтостроения. Например, деятели из Массачусетса сделали из базы данных real-time (sic!) систему обмена данными и на её основе пишут бортовой софт для боевых самолётов США.
И каждый день — без права на ошибку...
Re[5]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 09.08.18 12:26
Оценка:
Здравствуйте, B0FEE664, Вы писали:

L>>Речь идет о контейнерах.

BFE>И?

Что "И"?

L>>Попытка сделать из контейнера базу данных с преферансом, барышнями и transaction isolation только потому, что авторам лень или не хватает терпения продумать архитектуру ведет к эпичному провалу более чем всегда.

BFE>Может приводит, а может и нет, только вот к "Код выше нельзя в общем случае сделать потокобезопасным средствами контейнера" это отношения не имеет.

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

База данных != контейнер.
www.blinnov.com
Re[6]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: ksd Россия  
Дата: 09.08.18 12:35
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, ·, Вы писали:


MD>>>Ну, поинтересовался он. Услышал в ответ "вас тут не стояло", потому что контейнер с тех пор успели дважды очистить и заново наполнить. Что тогда делаем в плюс-плюсинге?

L>·>В его случае самым оптимальным было бы снапшотиться,

L>продумывать архитектуру.


++ хорошо. примеры или решения есть как то можно посмотреть / почитать о?
Re[6]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: B0FEE664  
Дата: 09.08.18 12:46
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>>>Речь идет о контейнерах.

BFE>>И?
L>Что "И"?
Чем таблица в базе данных не контейнер?

L>В общем слуае — нельзя.

L>В частных случаях вроде очереди, а при определенных юзкейсах и другие контейнеры тоже можно. А в общем — нельзя.
Погодите. Указан был вполне конкретный код с итераторами, а не абы какой.
И каждый день — без права на ошибку...
Re[5]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: Ops Россия  
Дата: 09.08.18 12:47
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>Это вы просто не знакомы с безумными реалиями современного софтостроения. Например, деятели из Массачусетса сделали из базы данных real-time (sic!) систему обмена данными и на её основе пишут бортовой софт для боевых самолётов США.


Так базу данных или контейнер они взяли?
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[6]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: B0FEE664  
Дата: 09.08.18 13:03
Оценка:
Здравствуйте, Ops, Вы писали:

Ops>Так базу данных или контейнер они взяли?


Базу данных.
И каждый день — без права на ошибку...
Re[7]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 09.08.18 13:11
Оценка:
Здравствуйте, ksd, Вы писали:

L>>продумывать архитектуру.

ksd>++ хорошо. примеры или решения есть как то можно посмотреть / почитать о?

Вряд ли смогу с наскоку порекомендовать литературу.

Все начинается с постановки задачи.
Сначала нужно понять, из чего появилось желание иметь потокобезопасный контейнер.
www.blinnov.com
Re[7]: троллинг детектед (-)
От: landerhigh Пират  
Дата: 09.08.18 13:12
Оценка:
www.blinnov.com
Re[8]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: ksd Россия  
Дата: 09.08.18 13:14
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, ksd, Вы писали:


L>>>продумывать архитектуру.

ksd>>++ хорошо. примеры или решения есть как то можно посмотреть / почитать о?

L>Вряд ли смогу с наскоку порекомендовать литературу.


L>Все начинается с постановки задачи.

L>Сначала нужно понять, из чего появилось желание иметь потокобезопасный контейнер.
++ чтобы не переписывать имеющийся код. кривовато, конечно, но...
Re[7]: у него много обращений на чтение, и очень очень редко на запись
От: · Великобритания  
Дата: 09.08.18 13:34
Оценка:
Здравствуйте, Кодт, Вы писали:

ksd>>завернуть for в критическую секцию не вариант.

К>А завернуть в read-write lock — вариант?
К>В С++17 это называется std::shared_mutex.
Чем это принципиально будет отличаться от критической секции?
readers так же друг-друга могут блокировать во время write.
Впрочем, если ему не нужно low latency, то это не должно быть проблемой.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[4]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: · Великобритания  
Дата: 09.08.18 13:37
Оценка:
Здравствуйте, Ops, Вы писали:

BFE>>Представьте, что ваш контейнер — это база данных. Не существует баз данных, с которыми можно работать из нескольких потоков?

Ops>Контейнер — это не база данных. Если нужна база данных, КО советует взять базу данных.
Он написал "завернуть for в критическую секцию не вариант". А обычная база данных как раз это и сделает, правда очень неявно, через 100500 слоёв абстракции. Так что КО немного поспешил.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: Ops Россия  
Дата: 09.08.18 13:43
Оценка:
Здравствуйте, ·, Вы писали:

·>Он написал "завернуть for в критическую секцию не вариант". А обычная база данных как раз это и сделает, правда очень неявно, через 100500 слоёв абстракции. Так что КО немного поспешил.


КО отвечал B0FEE664, а не ТС.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[9]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: landerhigh Пират  
Дата: 09.08.18 13:54
Оценка:
Здравствуйте, ksd, Вы писали:

L>>Все начинается с постановки задачи.

L>>Сначала нужно понять, из чего появилось желание иметь потокобезопасный контейнер.
ksd>++ чтобы не переписывать имеющийся код. кривовато, конечно, но...

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

Если дело в рефакторинге, то есть три пути. Либо отрефакторить код, из-за которого возникает такое желание. Либо потратить человекомесяцы на понимание его логики. Тогда, возможно, повезет и можно будет придумать контейнер, который сделает код потокобезопасным. Еще можно попробовать убрать многопоточность совсем.
www.blinnov.com
Re[6]: у него много обращений на чтение, и очень очень редко на запись
От: VVV Россия  
Дата: 09.08.18 15:10
Оценка:
Здравствуйте, ksd, Вы писали:

ksd>++ "у него" в контейнере ~10 элементов, но много обращений на чтение:

ksd>
ksd>    struct Subsc_t {
ksd>        virtual void doSome() = 0;
ksd>    };

ksd>    set<Subsc_t*> subscribers;

ksd>    for (auto s: subscribers) {
        s->>doSome();
ksd>    }
ksd>

ksd>и с очень маленькой вероятностью в миллионы раз реже может быть из другого треда subscribers.insert(some) или erase;
ksd>завернуть for в критическую секцию не вариант.

Сделать потокобезопасно в данном случае можно, если insert/erase делать в этом же потоке, где и обработка. Примерно так: завести ещё 2 контайнера insertedItems/erasedItems и критикал секшин на доступ к этим контейнерам.

псевдокод:
insert(some)
{
  cs.lock()
  insertedItems.insert(some)
  cs.unlock()
}
erase(some)
{
  cs.lock()
  erasedItems.insert(some)
  cs.unlock()
}

doSome()
{
  for(){...}
  if(insertedItems.size()+erasedItems.size() > 0)
  {
     cs.lock();
     //insert or erase to/from subscribers
     cs.unlock();
  }
}
Re[7]: у него много обращений на чтение, и очень очень редко
От: · Великобритания  
Дата: 09.08.18 15:27
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>doSome()
VVV>{
VVV>  for(){...}
VVV>  if(insertedItems.size()+erasedItems.size() > 0)
VVV>  {
VVV>     cs.lock();
VVV>     //insert or erase to/from subscribers
VVV>     cs.unlock();
VVV>  }
VVV>}

Не выйдет. size() тоже вообще-то надо внутрь lock засовывать, что делает всю затею бессмысленной.
Можно вместо size() использовать atomic int или что-то подобное, но тоже непригодно для low latency, т.к. doSome может ВНЕЗАПНО лочиться.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Отредактировано 09.08.2018 15:28 · . Предыдущая версия .
Re[8]: у него много обращений на чтение, и очень очень редко
От: VVV Россия  
Дата: 09.08.18 16:13
Оценка:
Здравствуйте, ·, Вы писали:

·>Не выйдет. size() тоже вообще-то надо внутрь lock засовывать, что делает всю затею бессмысленной.

·>Можно вместо size() использовать atomic int или что-то подобное, но тоже непригодно для low latency, т.к. doSome может ВНЕЗАПНО лочиться.

size() имеется в виду функция типа size_t size() { return m_size; }, в данном случае lock вызывать не надо, нам совсем не важно правильная ли сумма вернётся, важно только что сумма больше 0. Поэтому тут lock не нужен. И да — это был псевдокод — можно вместо size() завести булевскую переменную.

Про ВНЕЗАПНО лочиться — при многопоточном доступе к данным такое случается. В предложенном мной подходе lock будет вызываться только в случае реального добавления/удаления данных.

Ещё алгоритм придумался: использовать кольцевой буфер новых/удаляемых объектов. insert/erase двигают tail, doSome двигает head.

doSome()
{
  for(){...}
  //for insert objects
  if(head != tail)
  {
    tail_=atomicget(tail);
    from(head to tail_){...}
    head=tail_;
  }
}

insert(some)
{
  insertedObjects[(tail+1)%bufsize]=some;
  atomicset(tail, (tail+1)%bufsize);
}


Если insert/erase случаются редко, как говорит ТС, то размер буфера можно подобрать исходя из здравого смысла.
Re[9]: у него много обращений на чтение, и очень очень редко
От: · Великобритания  
Дата: 09.08.18 16:40
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>·>Не выйдет. size() тоже вообще-то надо внутрь lock засовывать, что делает всю затею бессмысленной.

VVV>·>Можно вместо size() использовать atomic int или что-то подобное, но тоже непригодно для low latency, т.к. doSome может ВНЕЗАПНО лочиться.
VVV>size() имеется в виду функция типа size_t size() { return m_size; }
Т.е. завязываешься на конкретную реализацию конкретного контейнера...

VVV>, в данном случае lock вызывать не надо, нам совсем не важно правильная ли сумма вернётся, важно только что сумма больше 0. Поэтому тут lock не нужен. И да — это был псевдокод — можно вместо size() завести булевскую переменную.

... но всё равно без разницы. Чтение переменной из одного потока, когда она меняется из другого просто так, без всяких многопоточных штуковин — вещь как повезёт. Например, значение 0 может закешироваться в регистре одного потока и из памяти никогда не читаться и изменения в памяти другим потоком не будут видны. Как мининмум нужен membar.
Приведённый ранее код — ошибочен. Если ты так делаешь в реальном коде — обязательно исправь, это бага.

VVV>Про ВНЕЗАПНО лочиться — при многопоточном доступе к данным такое случается. В предложенном мной подходе lock будет вызываться только в случае реального добавления/удаления данных.

Это зависит от требований. В low latecny code такое не должно случаться. Поэтому там нужны специальные lock-free подходы.

VVV>Ещё алгоритм придумался: использовать кольцевой буфер новых/удаляемых объектов. insert/erase двигают tail, doSome двигает head.

Да, такое вроде сработает, но только если doSome выполняется из максимум одного потока.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[10]: у него много обращений на чтение, и очень очень редко
От: VVV Россия  
Дата: 09.08.18 17:36
Оценка:
Здравствуйте, ·, Вы писали:

·>Здравствуйте, VVV, Вы писали:


VVV>>size() имеется в виду функция типа size_t size() { return m_size; }

·>Т.е. завязываешься на конкретную реализацию конкретного контейнера...

Товарищ! Это _ПСЕВДОКОД_, иллюстрирующий идею. Нет тут никаких конкретных реализаций. Это может быть size(), isChanged(), hasNewItems() и т.д. — это просто ИДЕЯ!

·>... но всё равно без разницы. Чтение переменной из одного потока, когда она меняется из другого просто так, без всяких многопоточных штуковин — вещь как повезёт. Например, значение 0 может закешироваться в регистре одного потока и из памяти никогда не читаться и изменения в памяти другим потоком не будут видны. Как мининмум нужен membar.

·>Приведённый ранее код — ошибочен. Если ты так делаешь в реальном коде — обязательно исправь, это бага.

Есть волшебное слово volatile — оно спасёт. И не будь столь категоричным. Приведи пример, КАК такой код может сработать неправильно?

VVV>>Ещё алгоритм придумался: использовать кольцевой буфер новых/удаляемых объектов. insert/erase двигают tail, doSome двигает head.

·>Да, такое вроде сработает, но только если doSome выполняется из максимум одного потока.

ну это ТС пусть смотрит, подходит ему или нет. Судя по этому куску кода — это похоже на код игры, где doSome — в UI потоке, а insert/erase в потоке gameEngine.
Re[11]: у него много обращений на чтение, и очень очень редко
От: · Великобритания  
Дата: 09.08.18 21:10
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>·>... но всё равно без разницы. Чтение переменной из одного потока, когда она меняется из другого просто так, без всяких многопоточных штуковин — вещь как повезёт. Например, значение 0 может закешироваться в регистре одного потока и из памяти никогда не читаться и изменения в памяти другим потоком не будут видны. Как мининмум нужен membar.

VVV>·>Приведённый ранее код — ошибочен. Если ты так делаешь в реальном коде — обязательно исправь, это бага.
VVV>Есть волшебное слово volatile — оно спасёт. И не будь столь категоричным. Приведи пример, КАК такой код может сработать неправильно?
Да, если сделать отдельную volatile переменную рядышком с контейнером, то всё в порядке. Просто со стандартными контейнерами не прокатит, там m_size не volatile.

VVV>>>Ещё алгоритм придумался: использовать кольцевой буфер новых/удаляемых объектов. insert/erase двигают tail, doSome двигает head.

VVV>·>Да, такое вроде сработает, но только если doSome выполняется из максимум одного потока.
VVV>ну это ТС пусть смотрит, подходит ему или нет. Судя по этому куску кода — это похоже на код игры, где doSome — в UI потоке, а insert/erase в потоке gameEngine.
Каждый своё увидел. Я увидел что insert/erase это подключение/оключение клиентов, а doSome используется из критических потоков для быстрой раздачи большого количества данных клиентам.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[6]: у него много обращений на чтение, и очень очень редко на запись
От: Sinclair Россия https://github.com/evilguest/
Дата: 10.08.18 02:16
Оценка:
Здравствуйте, ksd, Вы писали:
ksd>и с очень маленькой вероятностью в миллионы раз реже может быть из другого треда subscribers.insert(some) или erase;
ksd>завернуть for в критическую секцию не вариант.
Для такого случая с запасом подойдёт обычный односвязный список с lock-free операциями вставки/удаления через interlocked инструкции.
Единственные сложности — это управление временем жизни элементов списка; т.е. при erase мы рискуем выполнить delete на элементе, который всё ещё кто-то читает.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: Кодт Россия  
Дата: 10.08.18 10:48
Оценка:
Здравствуйте, ·, Вы писали:

·>Он написал "завернуть for в критическую секцию не вариант". А обычная база данных как раз это и сделает, правда очень неявно, через 100500 слоёв абстракции. Так что КО немного поспешил.


В критическую секцию, или, всё-таки, в RWLock?
Или RWLock — удел необычных СУБД?
Перекуём баги на фичи!
Re[6]: нужен контейнер, потокобезопасный, с неинвалидирующимися
От: · Великобритания  
Дата: 10.08.18 10:52
Оценка:
Здравствуйте, Кодт, Вы писали:

К>·>Он написал "завернуть for в критическую секцию не вариант". А обычная база данных как раз это и сделает, правда очень неявно, через 100500 слоёв абстракции. Так что КО немного поспешил.

К>В критическую секцию, или, всё-таки, в RWLock?
К>Или RWLock — удел необычных СУБД?
Критическая секция лочит всегда, rwlock — иногда, на этом разница заканчивается. Но lock он и в африке lock... Впрочем, топискстартеру может и не надо избавляться от локов, а достаточно уменьшить их количество.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[8]: у него много обращений на чтение, и очень очень редко на запись
От: uzhas Ниоткуда  
Дата: 10.08.18 12:43
Оценка:
Здравствуйте, Кодт, Вы писали:

К>shared_ptr — lock-free.


ну вот не надо вводить читателей в заблуждение
чтение еще можно назвать lock-free. запись в shared_ptr не делают lock-free

К>Но тут другая история вылезет.


тут вылезет как минимум ABA-problem
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.