Dependency Hell

Body

I suspect most readers have heard of this in reference to various Linux distributions. This describes the situation where package A requires package B that then requires package A, directly or indirectly, and you end up requiring a whole group of packages that seem to be entirely unrelated to installing package A, that include a lot of functionality of B. Well, that's just a higher level abstraction of what I will discuss in this article.

"I Am My Own Grandpa": When relationships get tangled

The song is about a situation that's technically impossible, which is a good thing, because it'd be the end of humanity as we know it. The song goes into a whole sordid list of relationships that are so tangled that it turns out that you are related to yourself by being your own ancestor. Perhaps this could happen in a time-travel paradox, and if time-travel was/is possible, I personally can't say how that would work out, except to say it'd be hard to figure out quite a few things. And yet, that's exactly what a lot of computer systems have in terms of their dependency graphs. The structure of a family tree is some variation of a Directed Acyclic Graph (DAG) even if relationships get tangled at some point with situations like "Kissing Cousins" and other things.

Perhaps the best analogy for structure that's easily understood and maintained is that of a military organization. I'll use the US military as an example. The Commander in Chief (AKA "Mr. President") is at the top of the hierarchy, and gives very few direct concrete orders for actions. The president sets the policy, and delegates the implementation of that policy to those that are in the field. There are other levels directly below him that are responsible for a slightly smaller scope that's more concrete in description and definition, such as the fifth army, or the third fleet. This continues to progressively lower levels of the organization, until you get to the individual soldier that's responsible for the concrete implementation of the abstract policy.

In a military organization, you can think of it as being client/server with N tiers, with the upper levels passing down orders, and asking the lower levels to return status reports so command decisions are (hopefully) made intelligently. In this case, the server at the lowest level is the individual soldier that has too low of a rank to command anyone. What you don't see is that enlisted soldier telling their superior officers what to do: this would be insubordination, besides making the keeping of order much more difficult.

The form of communication in a military organization can, in an ideal situation, be described as pushing commands from above, and pulling data from below, with the realization that every person involved knows as much as they need to know, and that the data they return to their superiors allows them to have a proper understanding of things at the more abstract level of implementing policy, such as "capture this land" at one level, to "get opponent to surrender" at the highest level. Military personnel don't need to know much more about their organization beyond where they fit in (who commands them and who they command, if any) and their area of responsibility. This makes them reusable, as they have skills that allow them to be placed under the command of anyone, anywhere they're needed, without needing to know too much about everything else going on around them, which is vital when those around them are reallocated and deleted from their scope.

Ok, so people don't get deleted like computer resources do, but the idea is the same, as are the general relationships (no pun intended! Yeah, right! :-) ) between the objects or functions and their related data in a program. A program with a DAG structure has many advantages over one that's cyclically dependent. I won't go into as much detail as absolutely possible, as there's a great book I recommend everyone buy and understand, that goes into the topic in great depth, with large examples. The book is "Large-Scale C++ Software Design" written by John Lakos, and the 14th printing was sometime last year. I will go into sufficient detail to whet your appetites, though, using BeOS-centric code to demonstrate the principles.

Global Warming: when relationships get hot and bothersome!

What I'm describing in a silly way is what happens when the abstraction of a system is logically upside-down or sideways, where push and pull have been replaced by pull and push, or push and push. This minimal code below demonstrates a common application abstraction that has too many enlisted soldiers pushing the general around:

//PushedAroundApplication.h

class PushyWindow;

class PushedAroundGeneralApplication:public BApplication
{
PushyWindow* m_PushesGeneral;

public:
void DisplayAboutBox();
};

//PushyWindow.h

class PushedAroundGeneralApplication;

class PushyWindow:public BWindow
{
public:
void PesterGeneralApplication()
{
PushedAroundGeneralApplication* App=be_app;

App->DisplayAboutBox();
}
};
//end of files

There's a lot I've omitted there: the #included headers, and the regular source files, among other things. Another thing I didn't put in there is proper locking between the BLoopers when accessing other threads. In such a minimal application, I could see someone saying, "Why bother? It's obvious what will happen, and locks aren't required!" which in this special case, is true, going on the presumption that DisplayAboutBox() doesn't do anything interesting.

What I've seen in many applications is for things of general interest to the system being placed in the application class, and accessed from everywhere else, like DisplayAboutBox(). It's perfectly reasonable to place things that are needed everywhere in the application in the application class, and that's really not a problem. Where the problem comes in is the chain of command: we've got PushyWindow objects and others demanding that the application class does something for them. If all they're doing is querying for static settings that don't change, this likely won't cause weird things to happen, and we can ignore threading issues with little worry. But what if something changes such that DisplayAboutBox() (as an example) modifies data in the PushedAroundGeneralApplication class that can also be modified by someone else, including the PushedAroundGeneralApplication object? We face two scenarios, neither one desirable: either we ignore locking and hope the race condition never happens, or we implement locking, and hope that we never deadlock.

As unlikely as it may seem, another thread could call DisplayAboutBox() that modifies something in the PushedAroundGeneralApplication class. The most obvious thing that would exist is a member variable that points to the About Box. For this example, let's say that the About Box allocates resources, and is terminated by the application after a certain amount of time, or other event not driven by the user. There's only one pointer in the application class used, and it only expects one to ever exist at any given time. Let's ignore for a moment that we could test from the other thread whether or not the pointer is NULL: after all, unless we lock the thread, that can change at any time, due to the race condition. Let's pretend that we don't know of another way to ensure there's only one About Box at a time (I can see people saying, "Well, do this, don't be so silly!") and go along with the story of the race condition. The first About Box is allocated by a thread, then another thread comes in and allocates another one, storing the pointer in the same place. These are special About Boxes that don't have a close button. The first About Box is closed and deleted...or is it? Actually, the second one would be acted on: the first one had the pointer overwritten. The first About Box is still in limbo, with no record of where it's at within the application object, and the user can't close it normally. Then the other timeout happens, and (presuming the pointer wasn't cleared) the second About Box is deleted again: crash!

Now let's change that scenario above, where instead of no locking, we lock the application thread as needed from the calling thread. In most cases, the situation with the bad pointer will be avoided. Actually, in all the cases! In its place you have a solution where you will often get what you want: you ask the application to display the About Box from the other thread, and it does it for you. That's because you've ensured that there won't be any race conditions, by locking the thread like the diligent developer you are. But wait! What if? What if, for some strange reason, the application thread is attempting to call into the PushyWindow thread, telling it to do something, and the PushyWindow thread is trying to get the About Box displayed? The application object is waiting on the PushyWindow thread, and the PushyWindow thread is waiting on the application thread: deadlock! "Why not just put a timeout value on the locks and just retry?" I imagine some are mumbling to themselves. Well, that's one solution you could use, but things are often not as simple as this example for tracing how a deadlock or a race condition occurs. Debugging multithreaded applications is notoriously nasty, and is full of statements by developers convinced that users are imagining things, with a common retort to someone reporting a bug: "But it works on my machine!"

What I've just described above with deadlocks and race conditions is the threading version of Dependency Hell that results from threads that have cyclic dependencies amongst them. As the code dependencies go, the task dependency tends to follow: cyclic dependencies in the code result in cyclic dependencies in the threading model, and makes life far more difficult than desired.

The Friend of my Friend is my Enemy: A sign of poor relationships

C++ is, to some people, object-oriented, while others will argue that it's a horrible mess that isn't object-oriented. Ideally, everything would have proper encapsulation and everyone would be immune to the effects of someone changing how a class is defined. Well, C++ allows you to have a very well insulated (encapsulated) system if you wish, but there are usually performance costs when you take advantage of that. Encapsulation used appropriately is a great thing, but C++ doesn't force you to use it, and what's more, C++ makes it easy to completely bypass it when needed. The problem is there are many cases where encapsulation is bypassed because it was "convenient" but it isn't a good long-term solution. What am I talking about? The "friend" keyword, which allows you to specify that a function or a class external to a class has full access to everything within that class. There are great and valid uses for friend classes and functions, such as overloaded operators and iterator classes that are very tightly associated with the class. For all practical intents and purposes, those may be treated as an extension of the class interface, as they are tied that strongly to them. These friend functions and classes should be defined and declared in the same place as the class with which they are associated.

Outside of those situations noted above, a friend function or class isn't any friend you really want: they are codependent and entangle the class they are used within, as well as all the classes that are declared as friends, as one unhealthy whole. Why is that? They increase coupling to the point where you can't take the class that has friends anywhere without the friends tagging along. There's no reason for the friend classes or functions to exist but to have access to the innermost secrets of the class they are friends of: they're like a bunch of people confiding their intimate details to each other, and they all go to the bathroom together as a group. Where real problems start happening is when classes are friends in both directions: they both are mutual admirers of each other, if you will. Let's look at the above code, with the minor change to show what I mean:

//PushedAroundApplication.h

class PushyWindow;

class PushedAroundGeneralApplication:public BApplication
{
PushyWindow* m_PushesGeneral;

friend class PushyWindow;

public:

void DisplayAboutBox();
};

//PushyWindow.h
class PushedAroundGeneralApplication;

class PushyWindow:public BWindow
{
int m_PlayWithMe;

friend class PushedAroundGeneralApplication;

public:

void PesterGeneralApplication()
{
PushedAroundGeneralApplication* App=be_app;
App->DisplayAboutBox();
delete App->m_PushesGeneral;
}
};

With this declaration, PushedAroundGeneralApplication can play with PushyWindow::m_PlayWithMe at will, and PushyWindow can go and modify m_PushesGeneral at will. What if PushedAroundGeneralApplication isn't expecting m_PushesGeneral to disappear or change on it? It has no clue that it has changed out from under it, because it no longer has exclusive control over itself.

Beyond the point of the classes not having full control of what's going on anymore, there's another problem that is hinted at when you find two classes that are mutual friends: even if you don't see a pointer, reference, or object within the interface of the other, it still clearly implies that they are dependent on each other. Let's modify that code sample one more time to demonstrate what I mean:

//PushedAroundApplication.h

class PushyWindow;

class PushedAroundGeneralApplication:public BApplication
{
friend class PushyWindow;

public:

void DisplayAboutBox();
};



//PushyWindow.h

class PushedAroundGeneralApplication;

class PushyWindow:public BWindow
{
int m_PlayWithMe;

friend class PushedAroundGeneralApplication;

public:

//Implementation is now in the source file

void PesterGeneralApplication();
};

Because I showed enough implementation above, we can guess that they are still dependent on each other, even without the friend declaration. What if we didn't write the code and we saw friend declarations? It's very instructive to get out a piece of paper and draw arrows going from one class to the class(es) that are friends of it, and then put all those classes in the drawing as well, with arrows pointing to their friends. This is often possible to do just from using the class declarations, which will give you a good idea of what the dependencies are in the system of classes. I invite you to take a look at your favorite OS headers with a piece of paper and a pen, or perhaps your favorite vector graphics application that runs on that OS.

You often find in a system where you've got a header file with friend declarations for other non-iterator classes or overloaded operators that you have more than one header file with such declarations: friends are rarely friends alone. What's more, the relationships are often more indirect than the example above, describing friends of friends that eventually know each other through six degrees of separation, or perhaps even more. When you try to use one of the lowest friends in the pecking order, you discover that you are stuck requiring a bus, or perhaps even a cruise ship!

Interrogating Your Prisoners: Dependencies and their effects on build times, testing, etc.

Now you might be seeing applications and systems in a new way: as a big happy group of friends. Well, social organizations work much better for people than they do for computer systems. If you've ever tried to decipher the interrelationships amongst a large group of people you've decided to try to involve yourself with, that's a good way to think of what happens in a system where you have cyclic dependencies. You can't determine who does what with certainty, and it's not easy to learn all that quickly. The friends in the group know each other well, and don't like to change too much. It's difficult to change one of them without upsetting the balance in unexpected ways. Even worse, you can't get one of them in isolation to see how they interact: you try to take one, and they all follow you into the bathroom together! This all takes a lot longer to determine if things work one way or another than it should. It takes a long time to gather together all the information as to who is necessary to ask to do something for someone else.

All of this has parallels in software development. If each class has a dependency structure where one class depends only on classes below it in a hierarchy, you can start with the classes at the bottom of the hierarchy, understand what they do, test them with test code that completely exercises all the cases the class was meant to solve in isolation, and then do the same with each of the classes that depend on that class, one layer at a time, until you get to main(). This allows you to write the simplest possible test scenarios with the minimal number of outside variables. Once you know that all the classes at lower levels work as intended, it's immediately obvious when you test a class that doesn't do what's expected as to where the error most likely exists. You can quickly build a test application for each class. Because you can do that, you can also readily take that class (and all those below it that it depends on) and reuse them in any application without needing to edit the code.

If you have a system that's like a group of friends, it becomes impossible to test and build as described above: there's no clear structure where you can start from the lowest level class, test that, and move up a level at a time. You cannot do focused unit tests on each individual class that push a class to its limits. Instead, you are forced to test a large group of classes as though they are one very large and complex class that is much harder to test: what you've got is what you could expect from a mathematical terrorist: a combinatorial explosion! When you compile these classes and link them together, the compile and link time grows longer and longer as you add more classes/friends into the group. It soon gets to the point where using any one of those classes ends up dragging in many extra header files you don't care to know about each time you try to use it, and linking one of the classes requires linking all of the other classes, even if you never use their functions. In other words, you end up with a bloated system that takes a lot longer to understand, build, and test, and is impossible to easily reuse. The compile and link times often grow in a very non-linear relationship to the number of files: the more classes/files on average that one file depends on, the more memory and disk space is required, as is the I/O time for reading all the files. When all the files and the object code fit within physical RAM, the build process is still processor-bound. Eventually, a system may grow large enough that the compiling or linking process no longer fits in RAM, and then the process is limited by the speed of the hard drive.

There are people that have the idea that cyclic dependencies are a weakness of C++. However, cyclic dependencies are possible in any language that allows forward declarations and allow the applications to link or be fully interpreted with such dependencies. This means you can do this in Pascal, Java, old C, etc. just as readily as in C++. But software doesn't need to have cyclic dependencies like I have described. I've worked on large applications that are cyclic in design, and I've also worked on large applications that aren't cyclic in design, and the book I recommended at the start of this article goes into far more detail than I could hope to cover in one article, with a complete application as a demonstration. It has been my personal experience that systems that aren't cyclic are less prone to problems, and are much easier to extend and test, while requiring a minimal system for building them on. A little thought into the structure of an application will save you the time and effort many times over during the lifetime of the system. So, until next time, say goodbye to all your friends!