Зависимые объекты и цепочка обновлений

[Dmitriy40]

EUgeneUS в сообщении #1479517 писал(а):

Dmitriy40 в сообщении #1479509 писал(а):

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

Ну да. Надежность. Аккуратный подсчет my.local требует внимательности при каждом изменени логики. И как-то заметно менялся при модификациях выше.

ОК, спасибо, понятно. Думаю это стоило проговорить прямо, в чём преимущество. Теперь можно сравнивать плюсы и минусы.

[george66]

Dmitriy40 в сообщении #1479152 писал(а):

По моему на сигналах задача решается двумя сигналами invalidate и done и двумя глобальными счётчиками signals и objects (их модификация должна быть защищена разделением доступа) и локальным счётчиком my.local принятых сигналов в каждом объекте и глобальным указателем ObjectStart на изначальный изменённый объект (ему защита не обязательна) (он заменяет пустой цикл ожидания обнуления signals в ModifyObject() перед посылкой себе сигнала done для начала пересчёта).

А как, кстати, доказать, что signals обнуляется в точности когда все оповещены? Потому что для сигналов "умер" это не так! Рассмотрим схему А-В-С, А-С (треугольник). Объект А умирает, шлёт сигнал "умер" двум детям, signals=2. Объект В умирает, signals=2 (один сигнал получил, один послал). Объект С получает первый сигнал "умри" и умирает, signals=1, второй сигнал обработать уже некому.

[Dmitriy40]

george66 в сообщении #1479639 писал(а):

А как, кстати, доказать, что signals обнуляется в точности когда все оповещены?

По "индукции": для каждого объекта для любого количества потомков каждый посланный потомку сигнал увеличит счётчик на 1, а после принятия его потомком счётчик будет уменьшен на 1, увеличение счётчика предшествует его уменьшению, значит обнулиться он может только в самом конце.

george66 в сообщении #1479639 писал(а):

Потому что для сигналов "умер" это не так!

Ну значит окончание волны смерти нельзя ждать таким же образом как и волны инвалидации. Но объекты хотя бы умирают правильно.

Если нужно ожидание окончания волны смерти, то я вижу минимум два решения:
1. Предварять волну смерти волной инвалидации, а смерть пускать аналогично done, только не ждать всех родителей, а по первому же сигналу смерти уменьшать objects и умирать. Момент окончания волны смерти — обнуление objects, легко проверяется аналогично обработке done в самом объекте.
2. При получении сигнала смерти перед умиранием переключить приёмник сигналов с текущего объекта на "очень специального" всеобщего потомка (общего для всей сцены), который просто уменьшает signals и только проверяет обнуление signals и отсылает тогда уведомление об окончании волны смерти.

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

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

[EUgeneUS]

george66 в сообщении #1479639 писал(а):

Потому что для сигналов "умер" это не так! Рассмотрим схему А-В-С, А-С (треугольник). Объект А умирает, шлёт сигнал "умер" двум детям, signals=2. Объект В умирает, signals=2 (один сигнал получил, один послал). Объект С получает первый сигнал "умри" и умирает, signals=1, второй сигнал обработать уже некому.

С "логической" точки зрения - всё должно работать нормально. Если С умер по сигналу от A, то для B уже нет этого потомка, и он ему сигнал не посылает.
С практической точки зрения, много чего контролировать нужно. Например, когда A и B посылали сигналы, С был ещё жив. Сигналы сложились в очередь для C. С достал первый сигнал "умри" и... умер. Второй сигнал обрабатывать нЕкому. То есть "обрастаем" проверками: уже умершим не посылаем, пока не выгребем всю свою очередь сообщений - не умираем...

Можно пускать пожар\волну "заразы" - по сигналам метить объекты флагом ToDie, а как signals станет нулем, слать бродкаст "умрите уже".

Dmitriy40 в сообщении #1479650 писал(а):

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

плюс один.

[Dmitriy40]

EUgeneUS в сообщении #1479671 писал(а):

Можно пускать пожар\волну "заразы" - по сигналам метить объекты флагом ToDie, а как signals станет нулем, слать бродкаст "умрите уже".

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

EUgeneUS в сообщении #1479671 писал(а):

То есть "обрастаем" проверками: уже умершим не посылаем, пока не выгребем всю свою очередь сообщений - не умираем...

Ещё и проверять обнуление signals, иначе можем умереть раньше чем волна дойдёт до какого-то родителя и он уже соберётся послать нам сигнал, но тот ещё не попал к нам в очередь (вполне возможная ситуация при многопоточном выполнении). А у меня в коде сначала увеличивается signals, а уже потом реально рассылаются сигналы, и в промежутке от увеличения signals до попадания сигнала в очередь потомок может умереть по сигналу другого родителя. Короче гонки тут, и как их аккуратно исключить надо додумывать.

george66
Ещё возможный вариант, уже со списком родителей в каждом объекте: при получении от любого родителя сигнала умри оповещаем всех родителей (подсчитывая их количество) что собираемся умереть, при получении подтверждения от всех из них о приёме уведомления (и исключении из своего списка потомков) умираем. Это разумеется кроме оповещения всех потомков. И тоже возможны гонки: даже если исключать из опроса родителя от которого пришёл сигнал умри, всё равно возможна ситуация когда мы шлём потомку сигнал умри, а он в этот момент шлёт нам уведомления "собираюсь умереть" (о чём мы ещё не знаем), мы же получили сигналы от всех своих родителей и умираем. Не уверен что ожидание опустошения своей очереди сигналов будет достаточно для исключения гонок. Да и вообще мне такое усложнение ещё менее нравится.

george66
Вы бы это, сказали наконец предполагается ли многопоточное выполнение или обработка сообщений всей сцены строго в один поток? Это принципиально. В один поток можно исключить много проверок и тонкостей с взаимным расположением операций. Но тогда при попытке запустить многопоточно оно практически гарантированно обрушится.
Второй вопрос, лично меня волнующий: система должна быть распределённой (в смысле иметь доступ только к своему объекту и возможно глобальным переменным, а всё прочее только сигналами) или допускается обращение к любой переменной любого объекта всей сцены? Во втором случае лучшим может оказаться решение rockclimber с добавлением объектов в список, который потом вычерпывается от готовых к операции объектов, может даже и выполняемое многопоточно.
Или задача учебная и Вам важны все возможные варианты?

-- 18.08.2020, 13:50 --

george66
Кстати, в распределённой системе собственно не может быть глобальных переменных, только локальные и среда обмена сигналами, тогда пул глобальных переменных засовываем в отдельный объект со своей очередью сообщений/сигналов и для любой модификации "глобальной переменной" шлём сигнал этому объекту о необходимом изменении нужной переменной. А он уже занимается подсчётами и уведомляет систему об окончании волн (и начальный объект об завершении волны invalidate). В такой ситуации можно поставить вопрос оптимизации обмена сигналами (исключении глобальных переменных или минимизации операций с ними).

Плюс обычно в сигналах/сообщениях предусматривается поле для параметра (обычно одного, если надо больше то передаётся ссылка на структуру, создать и переслать которую в память принимающего объекта отдельная задача), тогда вполне можно передавать значения глобальных счётчиков прямо в самом сигнале и отказаться от глобальных переменных. А указатель на начальный объект или добавить в структуру сигнала, или послать сигналом специальному объекту, вся роль которого будет лишь в запоминании начального объекта и перенаправлении ему сигнала done от любого объекта когда завершится волна invalidate.
В принципе, заведение отдельных объектов на каждое глобальное свойство и действие вполне обычная практика, ведь это дешёво в realtime, неисполняющиеся объекты ресурсов процессора не занимают, а памяти всегда достаточно (на штучное количество служебных объектов в дополнение к тысячам [десяткам/сотням тысяч] обычных).

Вообще, проектирование распределённых систем (в смысле доступности лишь локальных свойств, всё же прочее только через обмен сигналами) интересное занятие, любой шаг в сторону (смена порядка операций, добавление или убавление сигналов, добавление глобальных свойств/статистики, да много всего) часто рушит всю систему: или сигналы перестают распространяться, или часть сцены попадает в взаимную блокировку, или сеть заспамивается сигналами. Зато как в клеточных автоматах, одинаковый простой алгоритм в каждом объекте приводит к сложному поведению всей сцены, красота.

[EUgeneUS]

Dmitriy40 в сообщении #1479704 писал(а):

Фактически Вы лишь заменили вторую волну на броадкаст сигнал.

Да.

Две волны (первой волной - пометить объекты, второй - выполнить для помеченных) на одно действие (пересчитать или убить), имхо, будут работать надежно.

Но убивать (при должном контроле) можно одной волной, а не двумя, так как объект может помирать, если помер любой из родителей, а не все.
Пустить две волны, или одну волну с последующим бродкастом - упрощает реализацию "должного контроля".

Dmitriy40 в сообщении #1479704 писал(а):

Ещё и проверять обнуление signals,

Это понятно.

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

[Dmitriy40]

EUgeneUS в сообщении #1479710 писал(а):

А вот глобальный счетчик объектов для пересчета уже не достигнет нуля.

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

-- 18.08.2020, 14:54 --

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

[george66]

Я уже попробовал запускать каждую фигуру в отдельном потоке. При удалении фигуры действительно рисуется фигня, как и предсказано:)
Кажется, я понял, как правильно доказывать свойства счётчиков. Например, у нас есть конфигурация А-В-С, А-С. Переделаем дерево так А-В-С1, А-С2 (объект С разделился на два, зато у каждого объекта один родитель). Объекты, до которых сигнал дошёл только что, будем как-то помечать. В первый момент времени пометим объект А (корень дерева). В каждый следующий момент снимаем метку с одного из помеченных объектов, но помечаем всех его детей (сигнал идёт). Тогда значение signals при "грубом" способе подсчёта как раз равно числу помеченных объектов. Доказываем три вещи
1) Объект, с которого снята метка, никогда не будет помечен второй раз (если будет, значит, его родитель был помечен второй раз и так по цепочке до корня);
2) Рано или поздно помеченных объектов не останется (на каждом шаге один помеченный объект удаляется навсегда, а объектов конечное число);
3) Каждый объект в какой-то момент времени помечается (если какой-то никогда не помечается, то и его родитель никогда не помечается и так по цепочке до корня).