From: bs@alice.att.com (Bjarne Stroustrup)
Newsgroups: comp.lang.c++
Subject: Re: My objects are too big - why?
Date: 11 Oct 92 01:14:24 GMT
Distribution: comp
Organization: AT&T Bell Laboratories, Murray Hill NJ




doug@monet.ads.com (Doug Morgan) writes


 > The upshot for C++ is that a programming style using many abstract
 > virtual base classes can put an almost unbelievably high memory
 > overhead on each instance.  (What, your "simple" edge object takes 758
 > bytes and you need 100,000 of them per image?)  As Stroustrup said:
 > "My impression is that people seriously underestimate the value of
 > abstract classes."  Unfortunately, current C++ implementions may
 > justify such underestimates.

Hmm. I recommend abstract classes, not ``many abstract virtual base
classes.'' In my experience the precense of many virtual bases in
a single object is a fairly typical beginner's design error caused
by someone getting carried away by the idea of having ``everything
a separate class.''

Anyway, to put things in perspective let's see what the overheads
are for some common styles of classes:

#0 empty class

	class dummy { };
	
	sizeof(dummy) == 1;	// implementation dependent
				// I'm using Cfront figures
				// from my VAX

	(the reason the size isn't zero is that we need to
	maintain the identity of objects:

		dummy v[10];	// &v[1] != &v[2]
	)

#1 simple ``concrete'' class:

	class Point {
		int x, y;
	public:
		// as many non-virtual functions as you like
	};

	sizeof(Point) == 2*sizeof(int) == 8

	assuming that sizeof(int)==4

#2 simple polymorphic class:

	class Shape {
		Point center;
	public:
		virtual void rotate(int) = 0;
		// as many virtual and non-virtual
		// functions as you like
	};

	sizeof(Shape) == sizeof(Point)+sizeof(pointer) == 12

	assuming that sizeof(pointer)==4

#3 simple abstract class:

	class Set {
		// no representation
	public:

		// as many pure virtual functions as you like
		virtual ~Set() {}
	};

	sizeof(Set) == sizeof(pointer) == 4

#4 implementation of simple abstract class:

	class slist_set : Public Set, private slist {
		slink* current_element;
	public:
		// constructors
		// functions overriding the Set virtual functions
	};

	sizeof(slist_set) == sizeof(pointer)+sizeof(slist)+sizeof(slink*) == 12

	(you can find the slist class - really a template -
	in Chapter 8 of my 2nd edition)

So far the overheads have been minimal: one pointer in whatever class that
had or inherited virtual functions.

We can loose space to alignments:

#5 example of alignment

	class X {
		int a;
		char c;
	};

	sizeof(X) == 2*sizeof(int) == 8.

	The reason is that sizeof(X) must be rounded up to something
	that allows alignment of int to allow arrays.

	Note that this ``wasted'' space can sometimes be ``reclaimed:''

	class Y : public X {
		char c2,c3;
	};

	sizeof(Y) == sizeof(X) == 8

#6 simple use of virtual base (union of interfaces):

	class ios {
		int data;	// virtual bases often have
				// data
		virtual f();	// virtual bases often have
				// virtual functions
	};

	class istream : public virtual ios {
		// worst  case: no data
	};

	class ostream : public virtual ios {
		// worst  case: no data
	};

	class iostream : public istream, public ostream {
		// worst  case: no data
	};

	sizeof(ios)== 8		// data + vptr
	sizeof(istream)== 12	// ios + pointer to ios 
	sizeof(ostream)== 12 
	sizeof(iostream)== 16 	// ios + two pointers to ios 

#7 overblown (in my opinion) use of virtual bases:

	class one_way_iter { int i; virtual void suc(); };
	class two_way_iter
		: public one_way_iter { int i; virtual void pre(); };

	class insertion { int i; virtual void add(); };
	class deletion { int i; virtual void del(); };

	class one_way_iter_with_insertion
		: public virtual one_way_iter,
		  public virtual insertion { int i; /* ... */ };

	class one_way_iter_with_insertion_and_deletion
		: public virtual one_way_iter,
		  public virtual insertion,
		  public virtual deletion { int i; /* ... */ };

	class two_way_iter_with_insertion
		: public virtual two_way_iter,
		  public virtual insertion { int i; /* ... */ };

	class two_way_iter_with_insertion_and_deletion
		: public virtual two_way_iter,
		  public virtual insertion,
		  public virtual deletion { int i; /* ... */ };

	sizeof one_way_iter == 8	// data 4, overhead 4
	sizeof two_way_iter == 12	// data 8, overhead 4
	sizeof insertion == 8		// data 4, overhead 4
	sizeof deletion == 8		// data 4, overhead 4
	sizeof one_way_iter_with_insertion == 28		// data 8, overhead 20
	sizeof one_way_iter_with_insertion_and_deletion == 40	// data 12, overhead 28
	sizeof two_way_iter_with_insertion == 32		// data 12, overhead 20
	sizeof two_way_iter_with_insertion_and_deletion == 44	// data 16, overhead 28

	Here Cfront's sub-optimal layout algorithm starts to show
	(for example,the overhead for two_way_iter_with_insertion_and_deletion
	could easily be cut to 20; other compilers ought to do better).
	However, I don't see this overhead as a killer argument against
	anything (except maybe against overelaborate design). There are
	indeed cases where space overhead can make an otherwise reasonable
	design unsuitable, but they are in my experience not common.

	The reason abstract classes are underused in C++ (in my opinion)
	is not implementation problems, but ignorance about their uses and
	overuse of hierarchies based on ``universal'' classes.

	Of course, abstract classes does not provide a silver bullet, but
	they have uses in expressing idea, in providing interfaces, and
	in cutting compilation overheads that are widely underappreciated.
	For discussion and examples see ``The C++ Programming Language
	(2nd edition)'' sections 12.1.3, 12.4, 13.3, 13.6.
Newsgroups: comp.lang.c++