Reducing template bloat with inheritance

Question

Does anyone have experience reducing template code bloat using inheritance?

i hesitate rewriting our containers this way:

class vectorBase
{
  public:
    int size();
    void clear();
    int m_size;
    void *m_rawData;
    //....
};

template< typename T > 
class vector : public vectorBase
{
    void push_back( const T& );
    //...

};

I should keep maximum performance while reducing compile time

I'm also wondering why stl implementations do not uses this approach

Thanks for your feedbacks

Answer 1

I think this is a premature optimization. In general except in embedded systems, disk space and memory are plentiful and cheap, so there's no reason to try to optimize for a small amount of code space. By keeping it all in the template code it makes it more obvious what's going on rather than using inheritance which would complicate things.

Additionally most applications aren't going to be generating hundreds of instantiations, and for each T not all methods may be used, reducing the code footprint further.

Only if there were extremely tight memory considerations (embedded) would I consider different possible approaches (including the one you presented).

EDIT: I'm not sure that there's much gain to be had in a little of standard container cases since they still need a lot of template code. For internal classes that have only a small amount of template-specific code and lots of common logic this could definitely help both generated code and compilation speed. I suspect it isn't used often because it's more complex and the benefits are restricted to certain scenarios.

Answer 2

IIRC, Qt uses (or used?) a similar approach for their QList et al.

Basically, it would work, but you have to make sure you put everything that depends on T inside vector template. Unfortunately, that is almost all code there is in the vector class (in many cases, the code needs to call some T constructor or destructor), except for allocating raw storage and size()/capacity(). I'm not sure that it pays off, so double-check.

It does certainly pay of when you can abstract away from some template parameter (eg. set<T>::iterator need not be aware of the set's comparator) or if you can brew a full implementation for a large class of types (eg. with trivial copy-ctor and dtor).

Answer 3

The code you've posted is just plain wrong. If the class you're storing in the vector has a destructor, that destructor won't be called, because the compiler vectorBase has lost all information about when to call the destructor by casting to void*.

To do this properly, calling the right destructor, you need to generate different copies of the code that each call the right destructor, and this work is simplified by using templates.

(To use your approach with a non-template base class, you need to generate just as much machine code, but you need to write a whole lot more C++ code by hand.)

That's why this approach really isn't worthwhile.

Answer 4

Only very few operations on a vector make sense if you don't know what type the stored elements are. For example the clear() method you added to your base class needs to call the destructors of the elements removed from the vector, so it needs to know their type and needs to be templated.

There is also really not much you can do with the a void *m_rawData without knowing the types of the things inside it, basically all operations on it at least have to know the size of the stored type. The only thing I can think of would be that you can free() it if you know that it contains no elements (if it contains elements you have to call their destructors). Allocating, setting and accessing elements all doesn't work if you don't know where the individual elements start and end. Also the implementation of all the methods would be much cleaner and simpler if m_rawData would be a properly typed T* instead.

A size() method in the base class would only work if its only job is to return a m_size member variable, but a vector doesn't necessarily have to store the size explicitly (the implementations I know of don't). You could probably implement is so that the size is stored explicitly, but then again size() is probably not a method that takes long to compile, even if it's templated.

All together I don't think there are a lot of methods remaining, that are implementable in a base class. Most operation on a vector need to know about the elements stored in it.

Answer 5

The short of it:

Yes, this approach will [probably] work in limited, specialized circumstances. I don't suspect std::vector (or the rest of STL) to be among those circumstances.

The long of it:

As others have mentioned (and I agree), outside of an embedded system, code bloat isn't much of a problem on a compiled binary.

But, many of us suffer the compilation cost of building magnitudes more code during the compilation step than we might if there were compiled libraries to link against (instead of compiling header files). Add to it the difficulty of changing one of those templated header files and watch your entire project recompile from scratch. Long compile times make for sad developers :(

It may not affect a large percent of developers - depending on the size of your company's codebase, and how you structure your build environment. It certainly taxes us at my company.

As some answers have pointed out, there isn't much to abstract from a std::vector that would make it fair any better in your example. Certainly you need to be able to create and destroy individual elements, and making any methods virtual would hinder run-time performance (which is more important than compile-time performance). In addition, the compiler will lose the ability to optimize the void* library for templated code, this could result in a large performance loss.

I'm more interested in the more complex structures - would std::map benefit from abstraction? What if you took the red-black tree (the SGI implementation) out and linked against a red-black tree library. You would (probably) need to store the elements outside of the std::map, so it doesn't need to call the destructors, but that might (again) cause a run-time performance loss due to doubling your indirection.

I'm fairly certain that you couldn't use this method to improve on STL's implementation.

If you had better knowledge of the data structures you were storing, or you had a very specific templated type (not necessarily a container), you could probably improve your performance. But, then the question becomes - how often will you use this new templated type such that the overhead of compiling it will be noticeably improved? Certainly it would help compile times for std::vector, but maybe not for my_domain_specific_ptr_container. If you save 50% of compile time for my_domain_specific_ptr_container, how many times would you have to use it to notice a significant enough build boost to justify the added complexity to the class (and reduced debug ability).

If you haven't already, your time may be better spent distributing your build tools :)

If, on the other hand, you try this and it works for STL containers... please post back. I want a faster build! ;)

Answer 6

I understand your approach.

To be frank I have used it... although obviously not for STL containers: their code is virtually bug-free and optimized and I am highly unlikely to come up with a better implementation on my own!

I don't care much about compile-time: it's an embarrassingly parallel problem (apart from link) and distcc etc take care of all the troubles you can have even with a large codebase. And I mean large, I work at a company which required a new compiler from HP because the version we had didn't not support more than 128Ko... in the command line of the linker. And it was only one of the application, and it was a few years ago, and they thankfully splitted it up in several chunks since.

However, as much as I don't care about compile-time, I do care a lot about reduced dependencies and binary compatibility. And thus when I write templated code of my own I do check if it's possible to factor some operations outside of the templated code.

The first task is to isolate those point where you can really gain. Getting one line of code out is not worth your time, you want to get full functions.

The second task is to decide whether or not you wish to keep them inlined. It depends whether or not you care about performance, the overhead of a function call may or may not be important to you.

However I would certainly not use inheritance for the job. Inheritance is a IS-A relationship: it defines an interface, not an implementation. Either use Composition or simply free functions that you stash in a utility namespace (detail like in Boost ?).

Answer 7

Some implementations do use (a form of) the above approach. Here is GCC's

  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>
    {
    ... 
    }

In this case, the goal is to delegate memory management to _Vector_base. If you do choose to spend your time reinventing STL, please follow up here with your results. Perhaps your efforts will help put an end to the old "code bloat" cries still heard from time to time.