I'm a programmer. Or at least, I intend to be a programmer but it's taking an awfully long time. I'm starting to wonder whether being a programmer is more about the journey towards being a programmer than being a programmer. Edmund is a DZone MVB and is not an employee of DZone and has posted 33 posts at DZone. You can read more from them at their website. View Full User Profile

Code Autopsy

04.29.2013
| 1499 views |
  • submit to reddit

PICT0039.JPG

A mystery unsolved.

When last examined, the structure of Apache Ant looked odd.

Something didn't quite fit.

The problem concerns function dependency tuples: Ant boasts a shocking 504776 of the little blighters.

That is, if you line-up all of Ant's functions on which there are no dependencies and try to trace all source code paths from them - essentially enumerating all the system's transitive dependencies - you will find half a million different function chains.

Half a million.

By comparison, JUnit has 2700 dependency tuples. Of course Ant sprawls three-times larger than JUnit, Ant having 4500 functions, JUnit, 1300. The relationship, furthermore, between number of functions and number of function dependency tuples is complex so you might expect that three-times the number of functions might account for five-times the number of dependency tuples, say, or perhaps ten-times. But increasing that number by two orders of magnitude?

A strangeness lies here.

Nor is this a mere academic curiosity. Each time a programmer updates a function a non-zero probability exists that such an update will cause ripple-effect changes to other dependent functions, with consequent increased potential costs. Oddly-soaring numbers of dependency tuples certainly do not reduce such potential costs. Corporate responsibility demands an explanation.

So let us drag Ant's carcass to the mortuary and indulge in a gratuitous montage of serious-looking physicians, slicing scalpels and bloodied organs being weighed in stainless-steel scales, all to a painfully-hip soundtrack.

Amplification.

Actually, even before we look at Ant, let us take a quick peek at some of the quirks of dependency tuples. Consider a single-class system comprising the functions shown in figure 1.

First, simple system

Figure 1: A simple system.

In figure 1, we have four dependency tuples: {a(), c(), d()}, {a(), c(), f()}, {a(), c(), g()} and {a(), c(), e()}, all arranged in the noble and classic sunburst pattern.

Why investigate so trivial a system before delving into the monster? Well, hand-carving half a million dependency tuples from flawless digital marble sounds inordinately time-consuming. What if some combinatorial effect lurks out-of-sight? What if, rather then having the programmer explicitly create these dependency tuples, some configurations of functions amplify the number of dependency tuples beyond those, "Intentionally," created?

These are the configurations we seek, those in which adding a single dependency yields more than one extra dependency tuple. In figure 1, for instance, what happens if we add another function, h(), called by c()? This is shown in figure 2.

Extra function child added

Figure 2: Extra function called.

Figure 2 now yields five dependency tuples: {a(), c(), d()}, {a(), c(), h()}, {a(), c(), f()}, {a(), c(), g()} and {a(), c(), e()}. Thus by adding one more dependency we have added just one more dependency tuple. No amplification has occurred here.

Consider, however, if we add a new function, b(), which calls c() rather then being called by it.

Extra function parent added

Figure 3: A new function creating amplification.

Suddenly figure 3 shows ten dependency tuples, twice as many as figure 2 even though we have added only one new function and one new dependency. Though precisely the effect we sought, this strikes, now lying limp before us, as underwhelming. The extra five tuples stem from the calling of a function which in turn has five dependencies. Is this not obvious?

Subtlety moves beneath the surface, however. For the programmer has had to create a new function to trigger the amplification and to create - on what we see now as figure 3's key-stone, function c() - a new dependency. Both entail a deliberacy and explicitness that a wary programmer might notice, were that programmer concerned by such matters.

Yet some cases operate on more devious levels, perhaps most pernicious being those with links to the shady underworld of circular dependencies.

You might think that simply adding a dependency from d() back to b() would trigger all sorts of circular shenanigans but it does not. Spoiklin Soice, producer of these diagrams, must like all such dependency analyzers ensure against infinite loops where circular dependencies arise, and so dependency on a function which already resides in the dependency tuple being analyzed causes analysis to terminate, marking that tuple as circular.

The, "Trick," is to include a dependency on the hub that does not come directly from the two parent functions, a() or b(), and this alas happens all too often.

Preparing the circular

Figure 4: A pre-circular trap is set.

Figure 4 shows the same functions as figure 3 only with an extra dependency added, that of a() on h(). This triggers no amplification and creates just one extra dependency tuple: where figure 3 had ten, figure 4 has eleven. In the next figure, however, we shall see the effect of introducing our circular dependency between h() and the hub, c().

A circular arrival

Figure 5: A circular amplification.

Figure 5 demonstrates the amplification caused by the new circular dependency. Where figure 4 has eleven dependency tuples, the addition of just one more dependency - and no new functions - in figure 5 now creates fifteen dependency tuples. (Note: not sixteen dependency tuples. Why?)

All this, observe, in a trivial system of eight functions which despite its size offers a non-trivial challenge to predicting dependency-tuple amplification. This phenomenon, again, concerns the real-world problem of cost-management in the face of geometrically-increased ripple-effect vectors in real software products. Imagine how much more painful this problem grows in a system of a thousand functions, or four-thousand.

To wit ...

Once more into the Ant.

Despite the mind-shredding complexity of the Ant's five-hundred-and-four thousand, seven-hundred-and-seventy-six dependency tuples, finding a place to pierce the insanity-maze proves unproblematic. One function sticks out.

That function is Path.list() and through it cascade 356440 dependency tuples, more than half of the entire system's burden. Here we discover our hub, our typhoid Mary.

The list method

Figure 6: Path.list()

You may not think, just by looking at list() in figure 6, that it was such a bully. Yes, sixteen functions depend on it and it depends on seventeen others, so it's not shy of company but that hardly singles it out for special treatment.

Nor is it what you might call a, "Looker."

Take a glance for yourself though it is displayed here entirely for completeness; don't bother trying to unravel it:

    /**
     * Returns all path elements defined by this and nested path objects.
     * @return list of path elements.
     */
    public String[] list() {
        if (!isChecked()) {
            // make sure we don't have a circular reference here
            Stack stk = new Stack();
            stk.push(this);
            dieOnCircularReference(stk, getProject());
        }

        Vector result = new Vector(2 * elements.size());
        for (int i = 0; i < elements.size(); i++) {
            Object o = elements.elementAt(i);
            if (o instanceof Reference) {
                Reference r = (Reference) o;
                o = r.getReferencedObject(getProject());
                // we only support references to paths right now
                if (!(o instanceof Path)) {
                    String msg = r.getRefId() + " doesn\'t denote a path " + o;
                    throw new BuildException(msg);
                }
            }

            if (o instanceof String) {
                // obtained via append
                addUnlessPresent(result, (String) o);
            } else if (o instanceof PathElement) {
                String[] parts = ((PathElement) o).getParts();
                if (parts == null) {
                    throw new BuildException("You must either set location or"
                        + " path on ");
                }
                for (int j = 0; j < parts.length; j++) {
                    addUnlessPresent(result, parts[j]);
                }
            } else if (o instanceof Path) {
                Path p = (Path) o;
                if (p.getProject() == null) {
                    p.setProject(getProject());
                }
                String[] parts = p.list();
                for (int j = 0; j < parts.length; j++) {
                    addUnlessPresent(result, parts[j]);
                }
            } else if (o instanceof DirSet) {
                 DirSet dset = (DirSet) o;
                 DirectoryScanner ds = dset.getDirectoryScanner(getProject());
                String[] s = ds.getIncludedDirectories();
                File dir = dset.getDir(getProject());
                addUnlessPresent(result, dir, s);
            } else if (o instanceof FileSet) {
                FileSet fs = (FileSet) o;
                DirectoryScanner ds = fs.getDirectoryScanner(getProject());
                String[] s = ds.getIncludedFiles();
                File dir = fs.getDir(getProject());
                addUnlessPresent(result, dir, s);
            } else if (o instanceof FileList) {
                FileList fl = (FileList) o;
                String[] s = fl.getFiles(getProject());
                File dir = fl.getDir(getProject());
                addUnlessPresent(result, dir, s);
            }
        }
        String[] res = new String[result.size()];
        result.copyInto(res);
        return res;
    }

Again: nasty though not obviously 356440-dependency-tuples nasty.

But wait, wait, wait: we can distill the problem if we cheat a little. Let us pretend that the list() function appears not as it does above but finds itself reduced to the following:

    /**
     * Returns all path elements defined by this and nested path objects.
     * @return list of path elements.
     */
    public String[] list() {
        Object o = elements.elementAt(0);
        DirSet dset = (DirSet) o;
        DirectoryScanner ds = dset.getDirectoryScanner(getProject());
        return null;
    }

Yes, this function now makes no sense, even returning a lethal null that would certainly bring Ant tumbling down. This, however, is not an analysis of Ant's user-experience realisation but of its structure and structural analyses pull odd stunts like this all time, in this instance performing a local structural reduction, run-time consequences be damned. With the cartoonish refactoring above, the number of Ant's dependency tuples falls from 504776 to 450259.

You might think it impressive that dropping a few dozen lines of code could slash 50000 dependency tuples but the beast remains: four-hundred-and-fifty thousand dependency tuples still weave a mat incomprehensible. Now consider what happens now if delete that single line:

        DirectoryScanner ds = dset.getDirectoryScanner(getProject());

The number of dependency tuples plummets to 149014.

That single line of code generates three-hundred thousand dependency tuples, surely the greatest example of amplification since the bouncing-baby universe finished inflating.

And why? Because getDirectoryScanner() has a transitive dependency on list(): they reside in the same dependency tuple, so once list() invokes getDirectoryScanner() a long tortuous circuit completes connecting chain after chain of amplifying functions, feeding back on themselves, cascading mindlessly.

At which specific functions between getDirectoryScanner() and list() do these amplifications take place? Who can say? The answer requires even more meticulous tracing, perhaps hours tugging ligaments to see which twitching organs are ultimately connected.

And herein lies the point: poorly-structured systems impede dependency analysis and this translates directly to a difficulty in predicting update costs.

Are poorly-structured systems always more costly to update than well-structured systems? Of course not, but the cost of updating poorly-structured systems is always more difficult to predict.

Ant finds itself in this situation because it has broken at least two tenets of good structure: it has too many circular dependencies and it is too deep.

But finding a cure was never part of this analysis's remit: we wanted to find the source of the disease and even in this task a conclusive identification remains elusive. With some slicing and drilling and cautious speculation, however, we are at least within a House-hunch.

(Note that the version of Ant discussed here is 1.6.0 and in a later version list() has been refactored yet even that version has a similarly-enormous number of dependency tuples, so whatever refactoring has been done merely moved the amplifiers elsewhere.)

Summary.

Ant remains a great piece of software, providing fantastic value to businesses world-wide. It continues to deserve its place one of the most-popular building tools of the day.

This analysis, however, concerned itself not with Ant the user-experienced tool but Ant the structure and attempted to explain why Ant contains a number of dependency tuples vastly disproportionate to its size.

Photo credit attribution.

CC Image PICT0039.JPG courtesy of the_lost_drones on Flickr.


 

Published at DZone with permission of Edmund Kirwan, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags: