Evolution of the Observer Pattern

Back in the early 1990s four wise men began a voyage of discovery. They were trying to trace the origins of good software design. They crossed great deserts of featureless software and fought through almost impenetrable jungles of code. What they found changed the way we think about software development. Eric Gamma, Richard Helm, Ralph Johnson and John Vlissides discovered a plethora of Design Pattern species falling into 23 separate genera.

The "Gang of Four", as they have become known, published their findings in 1995 [GoF] and "patternologists" have been studying these creatures ever since. I have taken a particular interest in the Observer pattern and I have evidence for changes in its morphology and behaviour. The Observer pattern is evolving rapidly and this paper presents some recent and, I believe, important changes.

In their description of the Observer pattern the Gang of Four assumed that a Subject has a single point of attachment and that Observers attach directly to their Subjects. I have argued ([Bass2002], [Bass2003]) that Subjects can have multiple attachment points (Events) and that Observers may attach indirectly via structures known as Callbacks. Indeed, it is possible to understand the Observer pattern purely in terms of Events and Callbacks. From this perspective, a Subject is anything that publishes Events and an Observer is anything that attaches Callbacks to Events.

Formally, a Subject provides registries of event handlers, while Observers add handlers to these registries and subsequently remove them again. State change events in a Subject are communicated to the Observers by calling the registered handlers. In this paper, however, we will use 'Event' to mean "registry of event handlers" and 'Callback' to mean "registered event handler". This terminology is slightly unusual, but it simplifies the discussion considerably.

In the Gang of Four pattern, detaching an Observer required the Subject to search its collection of attached Observers. I proposed a more efficient mechanism in which the Observer stores an iterator returned when a Callback is attached to an Event and passes the iterator back to the Event when the Callback is detached. Although more efficient, this approach requires more client code and is more vulnerable to programmer error. (I call this the correctness vs. efficiency problem.)

Until recently, my own research has been confined to Events based on lists of pointers to a polymorphic callback base class. For example, here is a complete specimen of the common Event (Eventus Vulgaris)^[1] as described in [Bass2003].

// Abstract Function interface class.
template<typename Arg>
struct AbstractFunction {
  virtual ~AbstractFunction() {}
  virtual void operator() (Arg) = 0;
};
// Event class template.
template<typename Arg>
struct Event : list<AbstractFunction<Arg>*> {
  void notify(Arg arg) {
    typedef AbstractFunction<Arg> Func;

    for_each(begin(), end(),
           bind2nd(mem_fun(&Func::operator()),
                   arg));
  }
};

Specimen 1 - An Event from early 2003

We will compare this with several specimens of a newly discovered species (Eventus Adaptabilis) that is able to use different types of container and different types of callback. These adaptive changes allow E. Adaptabilis to thrive in a much wider range of programming environments. They also provide a solution to the correctness vs. efficiency problem, as we shall see shortly.

The key to the greater adaptability of E. Adaptabilis is a second template parameter, which specifies the type of container and, hence, the type of the callback pointers stored within it.

template<
    typename Arg,
    typename Container =
        std::list<Callback::Function<Arg>*> >
struct Event;

Specimen 2 - The defining feature of Eventus Adaptabilis.

This tiny fragment suggests answers to several questions that have puzzled patternologists. It explains, for example, why most E. Adaptabilis individuals are almost indistinguishable from their E. Vulgaris cousins. Because, by default, E. Adaptabilis uses the same container type as E. Vulgaris the two species often have identical external appearance and behaviour. It is also clear from this fragment how E. Adaptabilis is able to adapt so easily to different environments. Simply by specifying a different Container argument E. Adaptabilis can acquire any of the characteristics of that Container.

It is not clear, however, from Specimen 2 whether E. Adaptabilis acquires its behavioural traits through inheritance, nor can we deduce which types of container constitute valid parameters to the E. Adaptabilis template. To answer such questions we must look inside the Event. Our next specimen is instructive, here.

template<typename Arg, typename Container>
struct Event : Container {
  struct notify_function {
    notify_function(Arg a) : arg(a) {}
    typedef typename
            element<Container>::type pointer;
    void operator()(const pointer& ptr)
                               {(*ptr)(arg);}
    Arg arg;
  };
  // ...  indistinct features
  void notify(Arg arg) {
    // for_each(begin(), end(),
    //          notify_function(arg)); ???
  }
};

Specimen 3 - Some internal structure of E. Adaptabilis.

Unfortunately, the details of the notify() function have not been preserved. When this specimen was first discovered we assumed that the notify() function is similar to that of E. Vulgaris, as shown by the comment. In fact, this assumption turned out to be incorrect, but Specimen 3 does clearly show several interesting features. It is immediately clear, for example, that E. Adaptabilis inherits all the characteristics of its Container.

The most striking feature of Specimen 3, however, is the nested function object class, notify_function. It is perfectly adapted to its assumed role in the notify() function. It provides exactly the right interface for the for_each() algorithm and yet makes only the minimum assumptions about the container element types. Where E. Vulgaris is restricted to using std::list<>, E. Adaptabilis is free to use vectors, lists, sets, user-defined containers, etc. And where E. Vulgaris requires the container element type to be a built-in pointer to an AbstractFunction<Arg>, E. Adaptabilis accepts built-in pointers and smart pointers to ordinary functions and function objects of any type that can be called with an argument convertible to Arg.

It is interesting to note that the notify_function is public and, therefore, available to client code. This seems to be a violation of encapsulation, but it also provides benefits, as we shall see later.

Another note-worthy feature of the notify_function is the element<Container> meta-function. The implementation of this meta-function was missing from Specimen 3, but an intact sample was discovered later and is shown here as Specimen 4.

template<typename Container>
struct element {
  typedef typename Container::value_type type;
};

Specimen 4 - The element meta-function.

In itself this is an unremarkable structure. It just extracts the value_type from a container that conforms to the standard requirements. In evolutionary terms, however, its existence is quite interesting. E. Adaptabilis can only benefit from the element<> meta-function when it uses a non-standard container and only then if the meta-function is specialised for that container. As yet, there are no known cases of E. Adaptabilis and non-standard containers co-existing like this in the wild. It must be a matter of speculation, therefore, whether this feature has any real benefit.

The internal structure of the notify() function was a surprise. Instead of the ubiquitous for_each() function it uses a hitherto unknown algorithm, slither(). The notify() function can be seen in Specimen 5 and the slither() algorithm itself is shown in Specimen 6.

template<typename Arg, typename Container>
struct Event : Container {
  // ...

  void notify(Arg arg) {
    slither(this->begin(),
            this->end(),
            notify_function(arg));
  }
};

Specimen 5 - E. Adaptabilis notify() function.

template<typename Iterator, typename Function>
void slither(Iterator first, Iterator last,
             Function function) {
  if(first != last) {
    for(Iterator next = first;
        ++next != last;) {
      function(*first), first = next;
    }
    function(*first);
  }
}

Specimen 6 - The slither() algorithm.

Like for_each(), slither() applies a given function to the result of dereferencing every iterator in the range [first, last). However, slither() uses two iterators. At the start of the for loop body first points to the function about to be called and next points to the next one. At that point the function is called, first is moved forward to next by assignment, and next is incremented. The loop then proceeds to the next iteration or terminates. The overall effect is the same as for_each() and yet the algorithm is more complex.

Patternologists puzzled over this for a long time. Natural selection is a powerful mechanism for reducing the costs associated with unnecessary complexity. It should prefer for_each() over slither(). And yet here was an example of evolution proceeding in the wrong direction. Several explanations were proposed to account for this anomaly. Perhaps slither() is just a transient mutation that hasn't yet been weeded out by competition with for_each(). Or, perhaps there is some hidden benefit to slither() that more than compensates for the cost.

I have made a crude attempt to measure the relative costs of for_each() and slither(). As is often the case when measuring speed of execution I found the result surprising. There was no difference in speed between the two algorithms. (I used GCC 3.2.3 on Linux Red Hat 9 with full optimisation.) In fact, my attempt to extend the running time by increasing the number of function pointers in the container just consumed all the available RAM and triggered swapping, which made further measurements meaningless. However, I saw approximately 200 million loop iterations per second on my 700 MHz PC before swapping kicked in. I tentatively concluded, therefore, that there is no significant cost associated with the slither() algorithm.

The negligible cost of slither() may explain how it manages to compete with for_each(), but it doesn't explain why it came into existence. For that we need to look at E. Adaptabilis in a hostile environment. Consider the following sample program:

#include "Event.hpp"
// Callback that detaches itself from the
// event when called.
struct Disconnect : Callback::Function<int> {
  Disconnect(Event<int>& e)
    : event(e),
      position(e.insert(e.end(),this)) {}
  void operator()(int i) {
    event.erase(position);
  }
  Event<int>&          event;
  Event<int>::iterator position;
};
int main() {
  Event<int> event;
  Disconnect disconnect(event);
  event.notify(7);   // !
  event.notify(7);
  return 0;
}

Specimen 7 - E. Adaptabilis in a hostile environment.

Here we have a callback that connects itself to an event in its constructor and disconnects itself when it is called. Such callbacks are extremely poisonous to E. Vulgaris, but E. Adaptabilis is immune. To see why, consider the Event::notify() call. E. Vulgaris iterates through its list of callback pointers using for_each() which (invariably) increments a single iterator. When the iterator reaches a Disconnect callback for_each() invokes the callback, which erases itself from the list, invalidating the iterator. The for_each() algorithm then tries to increment the invalid iterator and continue the sequence of function calls, typically with disastrous results. E. Adaptabilis, however, uses the slither() algorithm. When it gets to the Disconnect callback it invokes the callback, which erases itself from the list, invalidating the iterator as before. But slither() doesn't increment the invalid iterator, it simply assigns a new value to it. This is, of course, a valid operation, so the algorithm completes normally and E. Adaptabilis lives to notify another event.

Together these features provide an answer to the question of what constitutes a valid Container argument to the E. Adaptabilis template, Event<Arg,Container>. The Container must be a class with begin() and end() member functions returning Forward iterators. It must contain a nested typedef, value_type, that defines the type of the container elements, or it must provide a specialisation of the element<> meta-function for that purpose. The element type must define a dereference operation. And the result of dereferencing an element must be a function or function object that can be called with an argument of type Arg.

These are very general requirements. They can be summarised informally as:

Programmers working with E. Vulgaris must remember to store the iterator returned when a callback is attached and pass it back to the event when the callback is disconnected. This is tedious and it is tempting to leave the callback attached "for ever" to avoid having to manage the iterator. This usually leads to disaster and is always frustrating for the hapless programmer.

The need to store the iterator can be removed by searching the list of pointers before disconnecting the callback. However, in E. Vulgaris this technique carries a significant performance penalty because the std::list<> it uses only supports search algorithms with linear complexity. With E. Adaptabilis, however, there is an alternative. Specimen 8 provides a good example.

#include <iostream>
#include <set>
#include "Event.hpp"
using namespace std;
void log(int i) {
  clog << "void log(" << i << ")" << endl;
}

int main() {
  typedef std::set<void (*)(int)> container;
  Event<int,container> event;
  event.insert(log); // no need to store an
                     // iterator
  event.notify(8);
  event.erase(log); // efficient search and
                    // erase
  return 0;
}

Specimen 8 - E. Adaptabilis using a std::set<>

This variant uses a std::set<> of function pointers as its container. The insertion, removal and iteration operations are all "fairly efficient". By that I mean that, for most applications, efficiency is not an issue. And for very demanding applications it is always possible to use a variant of E. Adaptabilis based on specialised containers. It's even possible to use a specialised iteration algorithm thanks to the public access of the nested notify_function class.

This paper has described a recently discovered species of Event (Eventus Adaptabilis) with a remarkably wide range of habitats. E. Adaptabilis is closely related to the more common Eventus Vulgaris but is more adaptable in the following ways:

It achieves all this without sacrificing efficiency and without forcing the programmer to store iterators. A rare specimen indeed.