In the above very simple hierarchy, node F wants to inherit a method that is defined at both A and C (marked with an asterisk). Because C is a subclass of A, and therefore overrides A’s definition, the version F should pick is at C. The search is of a tree, because there’s a choice at F as to which parent to look at first. If it looked at its parents left-to-right, the effective tree that the search for a method would follow is:

If it looked at its parents right-to-left, the tree would be:

(Node A doesn’t appear twice because searches stop when they reach a node they’ve visited before).

Alarmingly, a blind, left-to-right, depth-first search would reach the A node before the C node, which is severely wrong. In general, a depth-first search up a class hierarchy is a Very Bad Idea. A breadth-first search wouldn’t necessarily be any better, either — it could visit the above nodes in the order F B E A D C and would therefore also find A before C.

The solution is to put a partial ordering on the nodes in the tree, so that a directed search can be performed which guarantees nodes are found in the right order (in the above example, that means F first, then E before D before C before A, also B before A; whether B is checked before E, D or C is irrelevant). The algorithm isn’t all that hard to figure out for any half-decent programmer, but if enough people moan to me about it I guess I could outline it in a later article.

In practice, it turns out that for the class hierarchies we see in MUDs, the directed search that we’re forced to perform anyway is very efficient — it can find a node almost as quickly as can the list search up a class tree. I use this approach for MUD2, which has 7,700 nodes in a hierarchy 16 levels deep, and it averages 5,000 to 10,000 hierarchy lookups per command. Nevertheless, the game can handle 50+ commands a second without noticeable slowdown (I’ve no idea what the maximum is because I’ve never tried more than 50). Frankly, if I wanted to increase the efficiency of MUD2 then its inheritance system is one of the last places I’d look to squeeze out some extra performance.

The Case for Multiple Inheritance

Some die-hard advocates of single-inheritance programming are so used to hacking solutions in C++ or Java that they refuse to accept that multiple inheritance is necessary. They believe that a solution can always be programmed using single-level inheritance.

They’re right, it can! But then, a solution can always be programmed in flat assembler. What’s more, it would run faster, too. That doesn’t mean it’s a good idea, though... The fact is, multiple inheritance makes adding new concepts to a MUD so easy, and it extends the range of concepts that can be considered so much, that suggesting single inheritance is somehow superior is almost laughable.

Single inheritance is marginally easier to code, but multiple inheritance is a great deal easier to code with. If you have a MUD with decent multiple inheritance, the chance that someone will be able to persuade you that you should switch to single inheritance is pretty damned low.

Whatever you decide, however, there’s another trap concerning inheritance that practically every MUD programmer who ever walked has fallen into. It concerns the word "object", and I’ll discuss it next time.

Recent Discussions on Notes from the Dawn of Time: