Re: Observer pattern limitations

On 11 Jul 2006 06:41:49 -0700, David Barrett-Lennard wrote:

Dmitry A. Kazakov wrote:
On 10 Jul 2006 07:24:12 -0700, David Barrett-Lennard wrote:

Dmitry A. Kazakov wrote:
The general approach for replicas is time stamping. Unfortunately it does
not help you in reconstruction of a coherent system state. You'll also need
a history window. But even this does not give you an ability to reconstruct
the state for any given time point. Also it becomes a nightmare for
bidirectional connections.

Time stamping can be quite inefficient. For example a dependent in the
dependency graph may depend (indirectly) on thousands of inputs, and a
complete recurse of the graph is needed just to tell whether it is
dirty (ie to perform all the time stamp comparisons). Within a
process, propagation of dirtiness through a dependency graph seems a
better choice.

These are independent issues. You refer to a notification propagation. Time
stamping is for state reconstruction. Surely you could use it to
reconstruct state of "dirtiness", if you wanted.

Note also that when you have a circular dependency all caches along this
path are dirty at *any* given moment of time.

As for graph closures, I don't think it is a good idea to evaluate them
each time, if you have a deep graph. Probably you should encapsulate
notification service and cache closures in there. In a language for
programming virtual channels (data-flow) I cached dependencies. It was easy
to do during compilation of channel descriptions.

But all this does not solve the problem 1, routing notifications is an
independent issue.

IMO, the lesson to learn: go higher-level, use ADTs with behaviors
*specific* to the problem. There is no general solution at low level.

You'll need to elaborate please!

There is always some a-priori knowledge about publishers and subscribers.
Each piece of information is useful. If I know that two variables are
published synchronously I place them into a container variable and publish
the container. For example, a controller might have 20-30 variables with
rates under 1ms. That would break the neck of any publisher-subscriber
system, if it won't take into account that they are synchronous.

You can't always avoid the need for caching, and the need to know when
caches are dirty. Furthermore, some problems have complex dependency
graphs that can't be abstracted away.

I pack them in a tightly coupled object like a record variable above. That
would cut all dependencies.

PROBLEM 3: Observer attaches or detaches during a notification

It is racing condition, when allowed to happen asynchronously.

No I'm talking about a single thread that is in the process of
iterating through the observers of a subject in order to notify them,
and an observer decides that it wants to synchronously detach (say).
The problem doesn't exist if the detach is performed asynchronously.

The rule of thumb for good OO design is that objects aren't subjects of
their own. So I would say that objects detaching themselves is a bad
design. However, technically it is no problem.

Please elaborate.

It is an empiric principle, however maybe it could be supported by
analogies in set theory. My observation is whenever you try to make objects
which, for example, delete themselves, you end up with a mess. Same with
detaching. You want to be "functional" using "forall x in X P(x)" pattern,
and at the same time you break it by changing the quantifier (the set X)
from P. It is fundamentally inconsistent, so the mess.

The problem is that while a subject is notifying one of the observers,
an observer decides to attach or detach to/from the subject. This may
cause a crash depending on the data structure used by the subject to
store the observers.

This is not a problem, it is a bug. List and its iterators are objects. So
it is legal to modify the list while iterating it.

Double linked lists (std::list) will work, std::vector or std::deque
will not.

No. It is no matter how the list is implemented. If the contract reads:
iterators stay valid upon list modification, then, well, it is the
contract.

...which is the case for std::list, but not for std::vector and
std::deque.

For what it is worth, I am not a fan of STL design... (It is bad OO,
largely because Stepanov does not believe in it ... but does. (:-))

The very idea to change the list of observers while notifying them is
horrible to me. For example, does it matter whether the new observers
being attached also receive the notification?

Yes it does. In my implementation of persistent objects the weak reference
notification callback passes a set of objects, into which you can place new
objects. They will be notified as well. The set is held by the caller.

Sounds messy to me :)

It is much cleaner than to expose the list and iterators. How often new
objects are created upon notification? In fact, it is just a way to keep it
"functional", by replacing

forall x in X modify X

with

forall x in X modify Y; forall y in Y modify Z ...

PROBLEM 4: Memory management problems

There seems to only be one general solution (that I can think of). A
subject needs to hold strong references on its observers.

Well, usually it is a weak reference observer->subject. Clearly each weak
reference is a strong one in the backward direction. But implementations
don't care about it, because finalization of an observer finalizes the
reference with it. So there is nothing to care about.

Your typical C++ implementation of the observer pattern won't be able
to solve the memory management problem in the example I gave.

It does (and it is not C++, though it were also possible in C++ albeit
through much more sweat and tears). It uses handles.

I don't see how. Please elaborate

Handle = smart pointer.

You have to do a closure of all publisher-subscriber relations. Its result
will be a new observation relation. In general, observations are not
composable. Consider:

c ::= a + b

Let a and b change synchronously, then asynchronous notification
propagation would produce rubbish in c due to race condition.

I don't know what you mean. If a,b both change and they both mark c
as dirty, then later when c is requested it is recalculated and will
simply use the new values of a,b, and therefore give the correct
result. Where is the race condition?

Race condition is in c. When notification about a arrives before one of b,
c thinks that b's cache is OK, which is wrong. Note that even when c does
not cache anything, there is always some hidden cache present. When c reads
a, somebody else might be busy with changing a or b. You must lock
something, somewhere to kill transition processes.

I think I have more of a functional programming perspective on this
than you. I try to promote the idea that the order of calculation is
driven naturally by functional dependencies. This is a powerful
approach to help write code that is both correct and very efficient.

Hmm, that's the observer pattern is all about: triggering things =
determining the order.

The problem is that there might be no order compatible with the semantics.
To determine this or to find a right order is a very difficult task. Note
that more or less elaborated observation primitives (whatever they be) are
not composable. I.e. you cannot keep the invariant "the order is correct"
per construction. One way is to limit them to a composable subset, this is
what SPARK and Ravenscar profiles do. Unfortunately, the subsets obtained
are quite weak. The framework must be enough powerful to implement, say, a
network layer, but weak to create two waitable mutexes. It is quite
challenging...

I'm not sure to what extent we have a basis for comparison because you
seem to be interested in a fully asynchronous and perhaps distributed
system, whereas I'm talking specifically about a single process and
avoiding multi-threading issues.

In that setting there is nothing simpler that the idea to eagerly
propagate dirtiness through the dependency graph, and avoid all the
problems I have discussed in this thread. To me, the only quandary is
to somehow avoid unnecessary work when intermediate nodes end up having
the same value after recalculation. In the problems I have dealt with
this happens more often than not.

This way of thinking seems simple and elegant.

It could turn even worse. You can play a little with data flow languages
like MatLab/Simulink, DiaDem which basically postpone everything to the
next iteration step. It is the idea taken to an extreme. The major problem
with it is that is extremely slow [in order of magnitudes] as compared with
an asynchronous design. Another problem is that being so slow it severely
suffers from oversampling. You will deal with phantoms, state changes which
are not. The example with differential is an oversampling problem.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
.

Relevant Pages

  • Re: Observer pattern limitations
    ... dependency graph may depend on thousands of inputs, ... complete recurse of the graph is needed just to tell whether it is ... You refer to a notification propagation. ... and an observer decides that it wants to synchronously detach. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... You refer to a notification propagation. ... so a container of observers is an observer. ... some problems have complex dependency ... you don't have formally specified the requirements on what we call cache, ...
    (comp.object)
  • Re: Observer pattern limitations
    ... You refer to a notification propagation. ... so a container of observers is an observer. ... some problems have complex dependency ... Therefore the dependency graph has no need to persist. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... Use asynchronous notification services. ... you might wish to split "data change" and "visual ... an observer decides to attach or detach to/from the subject. ... usually it is a weak reference observer->subject. ...
    (comp.object)
  • Re: Observer - Redundant Updates
    ... After the change occurs, the observer ... will receive a notification that subject has changed. ... a user moves a slider representing some value. ... Notifications receive UID stamps and the ...
    (comp.object)