Re: Observer pattern limitations


Dmitry A. Kazakov wrote:
On 12 Jul 2006 03:01:48 -0700, David Barrett-Lennard wrote:

Dmitry A. Kazakov wrote:

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.

Ok. I have seen designs use a "change count" which is essentially
a logical time stamp.

Yes, though sequence numbers are incoherent. On the other side time stamps
require a more elaborated infrastructure, especially in distributed
systems.

As for graph closures, I don't think it is a good idea to evaluate them
each time, if you have a deep graph.

Huh? Are you talking about transitive closure of the graph?

Dependencies are transitive, so a container of observers is an observer.

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.

I have been building software for the last few years that allows the
end user to assemble complex persistent components like leggo, and use
formulae in various ways to wire them up in interesting ways. In that
domain I have to deal with complex dependency graphs that form at run
time and can't be abstracted away.

Interestingly, but this is what I am doing too. I have a persistency layer
for AI objects (classifiers, features, training sets etc).

But this is rather a simple case, therefore it works as Lego. It is easy
because:

1. The is no circular dependencies
2. It is synchronous (you store/restore all involved objects at once)
3. It is immutable, the action of storing does not change the object.


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.

I now look at the problem of cache management across the program from a
global, graph theoretic perspective, because a local view as suggested
by the observer pattern doesn't seem to work well in practice.

This reminds me of the problem of detecting garbage which is (often)
nicely handled by a global tracing GC, whereas local approaches such as
reference counting are difficult and painful to get right, and often at
odds with writing reusable components. I agree that "real time"
issues remain a problem with graph theoretic approaches.

No, as with observer, GC does not solve this problem. The perspective must
be not "graph theoretic." I should be *just* theoretic. The problem is that
you don't have formally specified the requirements on what we call cache,
notification, dependency etc. Once you had, you would quickly discover that
the requirements are contradictory. Then the actual work begins: to remove
contradictions from there.

I like the following perspective : You have a graph of objects that
are persisted on disk (perhaps using an OODBMS). Conceptually these
objects are behaviourless before main() begins and after main() exits.
Therefore the dependency graph has no need to persist. In fact,
dependents are generally transient and don't persist at all. All
behaviour in the objects is ultimately derived from an implicit
"liveliness" contract derived from main(). To help make the system
"operate", main() may directly or indirectly open a persistent store,
socket connections, create threads etc. A dependency graph results
from a liveliness contract in certain "observables" such as the
display. This requires that the display be redrawn at regular
intervals (say). The dependency graph can be complex or simple; it
depends on the problem at hand. Normally it won't contain cycles, so
for a given snapshot of all the independents, all the dependent values
(including the screen) are *precisely* defined as pure functional
dependencies. Now the independents typically correspond to the
persistent sub-graph of objects (ie a sub-graph of all the objects that
reside in memory). This sub-graph has ACID properties and requires
transactional access. This ensures atomicity of the persistent state.
It also allows for reasoning about the dependency graph : we are only
interested in its "atomic" recalculation *between* transactions.
Atomicity (and integrity) of the persistent objects leads to atomicity
and integrity in all the dependents, including the output display.
This conceptually eliminates the display of confusing, partly
calculated results, and aligns well with double buffered graphics that
atomically switch from one depiction to the next. The two-phase
approach to processing the dependency graph aligns well with this
perspective. During a mutative, transactional update to the persistent
objects, dirtiness is propagated eagerly through all affected
dependents, but they are *not* recalculated immediately. This allows
(mutative) transactions to take the shortest possible time, maximising
concurrency on the persistent objects. By contrast, recalculation of
dependents, which is CPU intensive only requires shared read mode
locking on the persistent state, leading to the possibility of
excellent parallelism.




If notification only propagates dirtiness eagerly through the
dependency graph then we eliminate all the problems I have discussed.
This includes the question of when to update the dependency graph
topology - because that happens in a separate phase when caches are
lazily evaluated.

You just have separated event and reaction (which are united in the
observer pattern). This solves some problems by bringing others. For
example, you might lose events. Sometimes it is acceptable (for state
variables), sometimes it is not (control variables).

However, I'm comparing it to the idea of only propagating dirtiness
during state change notifications. That eliminates the problem
completely.

It brings other problems, because events and reactions become decoupled.

Handle = smart pointer.

No, that won't solve the problem when you have pre-written components
in a third party library and you need to add the objects that represent
the "wiring". What deletes the wiring?

GC. You have a handle to it.

In my example only the subject does.

When the last handle goes out of scope, that
kills the wire. The thing that creates a wire is responsible to hold its
handle by itself or to pass it to a container serving as the scope. In my
component library weak references are collected objects.

Either subjects need to store strong references to the observers, or
else observers need a special notification for when the subject is
being destroyed. Neither of these approaches is done in typical
implementations of the observer pattern.

No, you mix things here. When objects can be observers, then there is no
need in any wiring you tell B: "take x from A." When they are not, then the
wire is the observer which tells B: "here is an x (from A), enjoy." In any
case the observer is a weak reference that gets a notification upon
finalization of A. This notification does not kill it directly. That's the
principle of "non-self-subject."

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.

This is a multi-threading issue. I was only addressing the problem of
cache management for a single thread.

No. In all scenarios the problem persist. Asynchronous propagation of
events and notification merely means that the order of execution of
reactions to the events might be wrong. In general, threading is irrelevant
to the problem. A separation of events and reactions makes possible a
brute-force synchronization: all events - all reactions - all events ..
This enforces some order, but it does not guaranty that it is the required
order. But for all, it is very ugly and very slow.

I haven't experienced anything like that in my designs. On the
contrary, if anything.

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.

I'm talking about examples like "c := a.get() + b.get()". The
act of executing that code causes a and b to be calculated *before* c
is calculated. Lazy evaluation is great for solving most order of
calculation problems.

It allows enforcing order on operands, but that does not solve problem when
get() has side effects.

But it shouldn't. As I said, I'm taking a functional programming
perspective.

You will also have aliasing problem and one of
ordering operands of "+".

I don't know why you say there is an ordering problem. The only rule
is that a,b are calculated before c.

Note also that when there is no side effects, there is also no need to have
it lazy. Marshal values of a and b to c, that's it. Lazy can be great for
dealing with side-effects, but it does not eliminate the ordering problem.
It is a tool.

The problem space has to be analysed to find a solution of the *narrower*
problem.

Hmmm. I don't understand what you mean.

Cheers,
David Barrett-Lennard

.

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
    ... 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
    ... The "eagerly propagate dirtiness through the dependency graph" ... Therefore Y and Z are marked as dirty. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... The nodes of the dependency graph are objects or members ... It is possible to implement a general solution to the dependency graph ... Observer pattern guaranties that under certain ...
    (comp.object)