Design Patterns in GUF

This document describes some of the concepts and patterns used in GUF's design.

Smart Pointers

The mechanics of smart pointers are described in the documentation of GSmartPointer. I will assume that the reader is familiar with their use. Note that in this document I use "smart pointer" and "pointer" to mean the same thing. If I want to refer to non-smart pointers, I will call them "regular pointers" or some such.

Smart pointers work through reference counting. That is, they keep track of how many pointers are pointing at an object, and delete the object when that count reaches zero.

The obvious problem with this comes when you have a recursive link. That is, you have an object which references itself, or an object which references another object which references the first again, etc. In this case, none of the objects in the chain will ever be destroyed because they will always be referencing each other!

Languages such as Java have real garbage collectors which catch this problem. One might think that such techniques are "better" than reference counting. I disagree. Why? Reference counting forces better design.

Let me explain with an example. I am writing a 3D game engine called GAUGE^3D ("the Grand Unified 3D Game Engine"), which is closely linked to GUF. In it, worlds are [going to be] represented using sectors and portals -- All of the open space is divided up into sectors. Sectors are then linked together with portals. For example, a room would typically be a single sector, and the doors and windows in the room would be portals connecting to other sectors. Portals are actually just special polygons within a sector. You need two portals to link two sectors -- one portal in each sector.

In my original design, a portal would contain a pointer to the sector it connected to. Of course, this would usually result in recursive links. To solve the problem, I had to change the design. Under the new design, the world is represented as one big sector, but that sector can have sub-sectors. Each sector can have portals, but the portals do not point to their targets. Instead, they are just numbered. Then, the super-sector specifies which portals link to which sectors.

The new design has many advantages over the old one. For example, If the world contains multiple areas that look exactly the same, they can use the same sector object to save space -- the super-sector simply defines different portal links each time. Another feature is that sectors can be sub-divided internally without having to update the sectors that connect to them. And, of course, the new design does not have the recursive link problem.

This is not the only time this happenned to me. I often run into problems with recursive links in my designs. However, every time I do, I rethink the design to fix the problem, and I *always* end up with a much better design. Thus, reference counting actually forces you to design better systems, which I can't see as anything other than a good thing.

Of course, reference counting has some other advantages as well:

  • Objects are deleted the moment their reference count hits zero. Thus, you can insure that objects are deleted exactly when you want them to be, and the objects don't take up memory when they are no longer in use. Java's garbage collector leaves garbage in memory until the next GC sweep.
  • Reference counting can be much faster than other GC methods. GUF implements reference counting using inline assembly. The counting is done as part of program execution, and only when pointers to various object are acutally being manipulated. Most GC algorithms require periodically stopping all threads and searching through all memory for garbage. The difference between these two techniques is comparable to the difference between polling versus event-driven input. Also, most GC algorithms will take longer if you have more data in memory, whereas reference counting will not.

Garbage collection has advantages in some situations. For any particular project, you should use the right tools for the job. In my case, I am trying to write a 3D game engine. Reference counting is the right tool for this.

Object Trees

As we have seen, reference counting forces you to make better designs. However, given the task of adapting a design for reference counting, how do you go about it? Do you just have to think about it until a new design comes to you? If so, it certainly seems like a bad way to go about it. Who knows how long it will take?

Fortunately, there is a very good design pattern to handle this problem. I call it "Object Trees". The idea is to arrange your objects into a tree-like structure, so that one object contains several sub-objects, which in turn contain more objects. An example of this is the sector tree system for modelling 3D worlds described above.

"Tree" is not exactly the right word to describe the arrangement. In this system, an object can have multiple parents. In other words, multiple objects may contain the same sub-object. This is not typically allowed in tree arangements. The correct term for this structure is "directed acyclic graph". Now you understand why I prefer "tree". :) I supposed you could call them "inbred trees"...

This pattern is actually a combination of two already existing patterns: composite and flyweight. (See the book _Design_Patterns_ by Gamma et al.) The pattern has been used numerous times before. Here are a few examples:

  • directory trees (with unix-style hard links)
  • 3D modeling
  • GUI frameworks (usually pure trees, though)
  • Office-style documents
  • Class hirearchies

You get the idea. :)

Abstract Class Factories

This is not an original design pattern by any means. However, GUF and GAUGE use it to a much greater extent than most programs.

The purpose of this pattern in extendability. We would like to be able to integrate new objects into a program without modifying the old ones. The solution is to use class factories to construct objects. You tell the factory what kind of object you need, and what interfaces it has to support, and the factory finds and instatiates a class which suits your needs. You only access the object through its abstract interface without ever knowing exactly what class you are talking to.

In GUF and GAUGE, abstract class factories are provided which actually load program modules dynamically. That is, the classes which they construct may be stored in external libraries (DLL's or SO's) which are loaded on demand. This allows new modules to be added to programs without even re-compiling the original program. These modules are commonly called "plugins".

For example, one plugin which GUF will provide is a decoder for MP3-compressed music files. Usually, programs which use this plugin will not even know that they are manipulating an mp3 file. All they will know is that they have some sort of sound file. The then say to the abstract class factory, "Hey, I have this file, and I know it contains some sort of sound. I need a class which will get the sound out for me!" Then, the class factory looks at the file and somehow determines that it is an mp3 file. It then loads up the mp3 decoder plugin and constructs an instance of the mp3 decoder class. It returns this to the caller, saying "This gadget here should do the trick." The caller can then use the object to decode the file.