"Export" Restrictions, Part 1

This article appeared in C/C++ Users Journal, 20(9), September 2002.

The standard C++ template export feature is widely misunderstood, with more restrictions and consequences than most people at first realize. This column takes a closer look at our experience to date with export.

“What experience with export?” you might ask. After all, as I write this in early June, there is still no commercially available compiler that supports the export feature. The Comeau compiler [1], built on the Edison Design Group (EDG) [2] front-end C++ language implementation which has just added support for export, has been hoping since last year to become the first shipping export-capable compiler. As of this writing that product is currently still in beta, though they continue to hope to ship soon and may be available by the time you read this. Still, the fact that no capable compilers yet exist naturally means that we have practically no experience with export on real-world projects; fair enough.

What we do have for the first time ever, however, is real-world nuts-and-bolts experience with what it takes to implement export, what effects export actually has on the existing C++ language, what the corner cases and issues really are, and how the interactions are likely to affect real-world users — all this from some of the world’s top C++ compiler writers at EDG who have actually gone and done the work to implement the feature. This is a huge step forward from anything we knew for certain even a year ago (although in fairness a few smart people, including some of those selfsame compiler writers, saw many of the effects coming and warned the committee about them years ago). Now that EDG has indeed been doing the work to create the world’s first implementation of export, confirming suspicions and making new technical discoveries along the way, it turns out that the confirmations and discoveries are something of a mixed bag.

Here’s what this column and the next cover:

A Tale of Two Models

The C++ standard supports two distinct template source code organization models: the inclusion model that we’ve been using for years, and the export model which is relatively new.

In the inclusion model, template code is as good as all inline from a source perspective (though the template doesn’t have to be actually inline): The template’s full source code must be visible to any code that uses the template. This is called the inclusion model because we basically have to #include all template definitions right there in the template’s header file.[3]

If you know today’s C++ templates, you know the inclusion model. It’s the only template source model that has gotten any real press over the past ten years because it’s the only model that has been available on standard C++ compilers until now. All of the templates you’re likely to have ever seen over the years in C++ books and articles up to the time of this writing fall into this category.

On the other hand, the export model is intended to allow “separate” compilation of templates. (The “separate” is in quotation marks for a reason.) In the export model, template definitions do not need to be visible to callers. It’s tempting to add, “just like plain functions,” but that’s actually incorrect — it’s a similar mental picture, but the effects are significantly different, as we shall see when we get to the surprises. The export model is relatively new — it was added to the standard in the mid-1990s, but the first commercial implementation, by EDG [2], didn’t appear until the summer of 2002.[4]

Bear with me as I risk delving too deeply into compilerese for one paragraph: A subtle but important distinction to keep in mind is that the inclusion and export models really are different source code organization models. They’re about massaging and organizing your source code. They are not different instantiation models; this means that a compiler must do essentially the same work to instantiate templates under either source model, inclusion or export. This is important because this is part of the underlying reason why export’s limitations, which we’ll get to in a moment, surprise many people, especially that using export is unlikely to greatly improve build times. For example, under either source model the compiler can still perform optimizations like relying on the ODR (one definition rule) to only instantiate each unique combination of template parameters once, no matter how often and widely that combination is used throughout your project. Such optimizations and instantiation policies are available to compiler writers regardless of whether the inclusion or export model is being used to physically organize the template’s source code; while it’s true that the export model allows the optimizations, so does the inclusion model.

Illustrating the Issues

To illustrate, let’s look at some code. We’ll look at a function template under both the inclusion and export models, but for comparison purposes I’m also going to show a plain old function under the usual inline and out-of-line separately-compiled models. This will help to highlight the differences between today’s usual function separate compilation and export’s “separate” template compilation. The two are not the same, even though the terms commonly used to describe them look the same, and that’s why I put “separate” in quotes for the latter.

Consider the following code, a plain old inline function and an inclusion-model function template:

// Example 1(a):
// A garden-variety inline function
//

// --- file f.h, shipped to user ---
namespace MyLib
{
  inline void f( int )
  {
    // natty and quite dazzling implementation,
    // the product of many years of work, uses
    // some other helper classes and functions
  }
}

The following inclusion-model template demonstrates the parallel case for templates:

// Example 1(b):
// An innocent and happy little template,
// using the inclusion model
//

// --- file g.h, shipped to user ---
namespace MyLib
{
  template<typename T>
  void g( T& )
  {
    // avant-garde, truly stellar implementation,
    // the product of many years of work, uses
    // some other helper classes and functions
    // -- not necessarily inline, but the body’s
    // code is all here in the same file
  }
}

In both cases, the Example 1 code harbors issues familiar to C++ programmers:

Export InAction [sic]

Can we solve, or at least mitigate, these problems? For the function, the answer is an easy “of course,” because of separate compilation:

// Example 2(a):
// A garden-variety separately compiled function
//

// --- file f.h, shipped to user ---
namespace MyLib
{
  void f( int ); // MYOB
}

// --- file f.cpp, optionally shipped ---
namespace MyLib
{
  void f( int )
  {
    // natty and quite dazzling implementation,
    // the product of many years of work, uses
    // some other helper classes and functions
    // -- now compiled separately
  }
}

Unsurprisingly, this solves both problems, at least in the case of f(): (The same idea can be applied to whole classes using the Pimpl Idiom. [5])

That’s all well and good for the function, but we already knew all that. We’ve been doing the above since C, and since before C (which is a very very long time ago). The real question is: What about the template?

The idea behind export is to get something like this effect for templates. One might naïvely expect the following code to get the same advantages as the code in Example 2(a). One would be wrong, but one would still be in good company because this has surprised a lot of people including world-class experts:

// Example 2(b):
// A more independent little template?
//

// --- file g.h, shipped to user ---
namespace MyLib
{
  export template<typename T>
  void g( T& ); // MYOB
}

// --- file g.cpp, ??shipped to user?? ---
namespace MyLib
{
  template<typename T>
  void g( T& )
  {
    // avant-garde, truly stellar implementation,
    // the product of many years of work, uses
    // some other helper classes and functions
    // -- now “separately” compiled
  }
}

Highly surprisingly to many people, this does not solve both problems in the case of g(). It might have ameliorated one of them, depending. Let’s consider the issues in turn.

Issue the First: Source Exposure

Indeed, in the only existing (and almost-available) implementation of export, the compiler requires that the template’s full definition be shipped — the full source code. [6] One reason is that a C++ compiler still needs the exported template definition’s full definition context when instantiating the template elsewhere as it’s used. For just one example why, consider 14.6.2 from the C++ standard about what happens when instantiating a template:

[Dependent] names are unbound and are looked up at the point of the template instantiation in both the context of the template definition and the context of the point of instantiation.

A dependent name is a name that depends on the type of a template parameter; most useful templates mention dependent names. At the point of instantiation, or a use of the template, dependent names must be looked up in two places. They must be looked up in the instantiation context; that’s easy, because that’s where the compiler is already working. But they must also be looked up the definition context, and there’s the rub, because that includes not only knowing the template’s full definition, but also the context of that definition inside the file containing the definition, including what other relevant function signatures are in scope and so forth so that overload resolution and other work can be performed.

Think about Example 2(b) from the compiler’s point of view: Your library has an exported function template g() with its definition nicely ensconced away outside the header. Well and good. The library gets shipped. A year later, one fine sunny day, it’s used in some customer’s translation unit h.cpp where he decides to instantiate g<CustType> for a CustType that he just wrote that morning... what does the compiler have to do to generate object code? It has to look, among other places, at g()’s definition, at your implementation file. And there’s the rub... export does not eliminate such dependencies on the template’s definition, it merely hides them.

Exported templates are not truly “separately compiled” in the usual sense we mean when we apply that term to functions. Exported templates cannot in general be separately compiled to object code in advance of use; for one thing, until the exact point of use, we can’t even know the actual types the template will be instantiated with. So exported templates are at best “separately partly compiled” or “separately parsed.” The template’s definition needs to be actually compiled with each instantiation.

Issue the Second: Dependencies and Build Times

The template code still has to be compiled in full later, when each instantiation context is known. Here is the key concept, as explained by export expert Daveed Vandevoorde:

export hides the dependencies. It does not eliminate them.

It’s true that callers no longer visibly depend on g()’s internal details, inasmuch as g()’s definition is no longer openly brought into the caller’s translation unit via #included code; the dependency can be said to be hidden at the human-reading-the-source-code level.

But that’s not the whole story, because we’re talking compilation-the-compiler-must-perform dependencies here, not human-reading-the-code-while-sipping-a-latte dependencies, and compilation dependencies on the template definitions still exist. True, the compiler may not have to go recompile every translation unit that uses the template; but it must go away and recompile at least enough of the other translation units that use the template such that all the combinations of template parameter types on which the template is ever used get reinstantiated from scratch. It certainly can’t just go relink truly-separately-compiled object code.

For an example why this is so, and one that actually shows that there’s a new dependency being created here that we haven’t talked about yet, recall again that quote from the C++ standard:

[Dependent] names are unbound and are looked up at the point of the template instantiation in both the context of the template definition and the context of the point of instantiation.

If either the context of the template’s instantiation or the context of the template’s definition changes, both get recompiled. That’s why, if the template definition changes, we have to go back to all the points of instantiation and rebuild those translation units. (In the case of the EDG compiler, the compiler recompiles all the calling translation units needed to recreate every distinct specialization, in order to recreate all of the instantiation contexts, and for each of those calling translation units it also recompiles the file containing the template definition in order to recreate the definition context.) Note that compilers could be made smart enough to handle inclusion-model templates the same way — not rebuilding all files that use the template but only enough of them to cover all the instantiations — if the code is organized as shown in Example 2(b) but with “export” removed and a new line “#include “g.cpp”” added to g.h.

But there’s actually a new dependency created here that wasn’t there before, because of the reverse case: If the template’s instantiation context changes — that is, if you change one of the files that use the template — the compiler also has to go back to the template definition and rebuild the template definition too. EDG rebuilds the whole translation unit where the template definition resides — yes, the one that many people expected export to compile “separately” only once — because it’s too expensive to keep a database of copies of all the current template definition contexts. This is exactly the reverse of the usual build dependency, and probably more work than the inclusion model for at least this part of the compilation process because the whole translation unit containing the template definition is compiled anew. It’s possible to avoid this rebuilding of the template definition, of course, simply by keeping around a database of all the template instantiation contexts. One reason EDG chose not to do this is because such a database quickly gets extremely large and caching the definition contexts could easily become a pessimization. (“But why not keep them around like object files?” one might ask, “just like for nontemplate code we don’t rebuild translation units every time, we keep around the object files.” The problem is that exported templates’ definition contexts are not object files, and are usually much larger than object files.)

Further, remember that many templates use other templates, and therefore the compiler next performs a cascading recompilation of those templates (and their translation units) too, and then of whatever templates those templates use, and so on recursively, until there are no more cascading instantiations to be done. (If, at this point in our discussion, you are glad that you personally don’t have to implement export, that’s a normal reaction.)

Even with export, it is not the case that all callers of a changed exported template ‘just have to relink.’ The experts at EDG report that, unlike the situation with true separate function compilation where builds will speed dramatically, they expect that export-ized builds will in general be the same speed or slower except for carefully constructed cases.

Summary

So far, we’ve looked at the motivation behind export, and why it’s not truly “separate” compilation for templates in the same way we have separate compilation for nontemplates. Many people expect that export means that template libraries can be shipped without full definitions, and/or that build speeds will be faster. Neither outcome is promised by export. The community’s experience to date is that source or its direct equivalent must still be shipped, and that build speeds are expected to be the same or slower, rarely faster, principally because dependencies, though masked, still exist, and the compiler still has to do at least the same amount of work in common cases.

Next time, we’ll see why export complicates the C++ language and makes it trickier to use, including that export actually changes the fundamental meaning of parts of the rest of the language in surprising ways that it is not clear were foreseen. We’ll also see some initial advice on how to use export effectively if you happen to acquire an export-capable compiler. More on those topics, when we return.

Acknowledgments

Many thanks to Steve Adamczyk, John Spicer, and Daveed Vandevoorde — also known as Edison Design Group (EDG) [2] — for being the first to be brave enough to implement export, for imparting their valuable understanding and insights to me and to the community, and for their comments on drafts of this material. As of this writing, they are the only people in the world who have experience implementing export, never mind that they are already regarded by many as the best C++ compiler writers on the planet. For one small but public measure of their contribution to the state of our knowledge, do a Google search for articles in the newsgroups comp.lang.c++.moderated and comp.std.c++ by Daveed this year (2002). Happy reading!

References

[1] See www.comeaucomputing.com.

[2] See www.edg.com.

[3] Or the equivalent, such as stripping the definitions out into a separate .cpp file but having the template’s .h header file #include the .cpp definition file, which amounts to the same thing.

[4] It’s true that Cfront had some similar functionality a decade earlier. But Cfront’s implementation was slow, and it was based on a “works most of the time” heuristic such that, when Cfront users encountered template-related build problems, a common first step to get rid of the problem was to blow away the cache of instantiated templates and reinstantiate everything from scratch.

[5] H. Sutter. Exceptional C++ (Addison-Wesley, 2000).

[6] “But couldn’t we ship encrypted source code?” is a common question. The answer is that any encryption that a program can undo without user intervention (say to enter a password each time) is easily breakable. Also, several companies have already tried “encrypting” or otherwise obfuscating source code before, for a variety of purposes including protecting inclusion-model templates in C++; those attempts have been widely abandoned because the practice annoys customers, doesn’t really protect the source code well, and the source code rarely needs such protection in the first place because there are other and better ways to protect intellectual property claims — obfuscation comes to the same end here.

Copyright © 2009 Herb Sutter