asm, c, c++ are my all
-- Core In Computer
posts - 139,  comments - 123,  trackbacks - 0

/********************************************\
|    欢迎转载, 但请保留作者姓名和原文链接, 祝您进步并共勉!     |
\********************************************/


C++对象模型(12) - 3.4 Inheritance and the Data Member
作者: Jerry Cat
时间: 2006/11/16
链接: 
http://www.cppblog.com/jerysun0818/archive/2006/11/16/15269.html


3.4 Inheritance and the Data Member
;-----------------------------------------------------------------------

Under the C++ inheritance model, a derived class object is represented as the concatenation of its members with those of its base class(es). The actual ordering of the derived and base class parts is left unspecified by the Standard. In theory, a compiler is free to place either the base or the derived part first in the derived class object. In practice, the base class members always appear first, except in the case of a virtual base class. (In general, the handling of a virtual base class is an exception to all generalities, even, of course, this one.)

class Concrete1 {
public:
   // ...
protected:
   int val;
   char bit1;
};
class Concrete2 : public Concrete1 {
public:
   // ...
protected:
   char bit2;
};

class Concrete3 : public Concrete2 {
public:
   // ...
protected:
   char bit3;
};
From a design standpoint, this representation may make more sense. From an implementation standpoint, however, we may be distressed to find that a Concrete3 class object now has a size of 16 bytes—double its previous size.

What's going on? Recall that the issue is the integrity of the base class subobject within the derived class. Let's walk through the layout of the inheritance hierarchy to see what is going on.

The Concrete1 class contains the two members—val and bit1—that together take up 5 bytes. The size of a Concrete1 class object, however, is 8 bytes: the 5 bytes of actual size plus 3 bytes of padding to align the object on a machine word boundary. That's as true in C as it is in C++; generally, alignment constraints are determined by the underlying processor.

粗心的程序员可要倒霉咯!
Nothing necessarily to complain about so far. It's the layout of the derived class that typically drives the unwary programmer into fits of either perplexity or angry indignation. Concrete2 adds a single nonstatic data member, bit2, of type char. Our unwary programmer expects it to be packed into the base Concrete1 representation, taking up one of the bytes otherwise wasted as alignment padding. This layout strategy makes the Concrete2 class object also of size 8 bytes, with 2 bytes of padding.

The layout of the Concrete2 class, however, instead preserves the 3 bytes of padding within the Concrete1 base class subobject. The bit2 member is set down after that, followed by an additional 3 bytes of padding. The size of a Concrete2 class object is 12 bytes, not 8, with 6 bytes wasted for padding. The same layout algorithm results in a Concrete3 class object's being 16 bytes, 9 of which are wasted on padding.

Why? Let's declare the following set of pointers:

Concrete2 *pc2;
Concrete1 *pc1_1, *pc2_2;

Both pc1_1 and pc2_2 can address objects of either three classes. The following assignment

*pc1_1 = *pc2_2;
should perform a default memberwise copy of the Concrete1 portion of the object addressed. If pc1_1 addresses a Concrete2 or Concrete3 object, that should not be of consequence to the assignment of its Concrete1 subobject.

However, if the language were to pack the derived class members Concrete2::bit2 or Concrete3::bit3 into the Concrete1 subobject, these language semantics could not be preserved. An assignment such as

pc1_1 = pc2;

// oops: derived class subobject is overridden
// its bit2 member now has an undefined value
*pc1_1 = *pc2_2;
would overwrite the values of the packed inherited members. It would be an enormous effort on the user's part to debug this, to say the least.

二. Adding Polymorphism:
If we want to operate on a point independent of whether it is a Point2d or Point3d instance, we need to provide a virtual function interface within our hierarchy. Let's see how things change when we do that:

class Point2d {
public:
   Point2d( float x = 0.0, float y = 0.0 )
      : _x( x ), _y( y ) {};

   // access functions for x & y same as above
   // invariant across type: not made virtual

   // add placeholders for z — do nothing ...
   virtual float z(){ return 0.0 };
   virtual void z( float ) {}
   // turn type explicit operations virtual
   virtual void
   operator+=( const Point2d& rhs ) {
       _x += rhs.x(); _y += rhs.y(); }

   // ... more members
protected:
   float _x, _y;
};
It makes sense to introduce a virtual interface into our design only if we intend to manipulate two- and three-dimensional points polymorphically, that is, to write code such as

where p1 and p2 may be either two- or three-dimensional points. This is not something that any of our previous designs supported. This flexibility, of course, is at the heart of OO programming. Support for this flexibility, however, does introduce a number of space and access-time overheads for our Point2d class:

(1). Introduction of a virtual table associated with Point2d to hold the address of each virtual function it declares. The size of this table in general is the number of virtual functions declared plus an additional one or two slots to support runtime type identification.

(2). Introduction of the vptr within each class object. The vptr provides the runtime link for an object to efficiently find its associated virtual table.

(3). Augmentation of the constructor to initialize the object's vptr to the virtual table of the class. Depending on the aggressiveness of the compiler's optimization, this may mean resetting the vptr within the derived and each base class constructor. (This is discussed in more detail in Chapter 5.)

(4). Augmentation of the destructor to reset the vptr to the associated virtual table of the class. (It is likely to have been set to address the virtual table of the derived class within the destructor of the derived class. Remember, the order of destructor calls is in reverse: derived class and then base class.) An aggressive optimizing compiler can suppress a great many of these assignments.

Here is our new Point3d derivation:

class Point3d : public Point2d {
public:
   Point3d( float x = 0.0, float y = 0.0, float z = 0.0 )
      : Point2d( x, y ), _z( z ) {};
   float z() { return _z; }
   void z( float newZ ) { _z = newZ; }

   void operator+=( const Point2d& rhs ) {
      Point2d::operator+=( rhs );
      _z += rhs.z();
   }
   // ... more members
protected:
   float _z;
};

Although the syntax of the class's declaration has not changed, everything about it is now different: The two z() member functions and the operator+=() operator are virtual instances. Each Point3d class object contains an additional vptr member object (the instance inherited from Point2d). There is also a Point3d virtual table. The invocation of each member function made virtual is also more complex (this is covered in Chapter 4).

Placing the vptr at the start of the class is more efficient in supporting some virtual function invocations through pointers to class members under multiple inheritance (see Section 4.4). Otherwise, not only must the offset to the start of the class be made available at runtime, but also the offset to the location of the vptr of that class must be made available. The trade-off, however, is a loss in C language interoperability.

三. Multiple Inheritance:
Single inheritance provides a form of "natural" polymorphism regarding the conversion between base and derived types within the inheritance hierarchy. Look at Figures 3.1(b), 3.2(a), or 3.3, where you can see that the base and derived class objects both begin at the same address. They differ in that the derived object extends the length of its nonstatic data members. The assignment, such as

Point3d p3d;
Point2d *p = &p3d;
of the derived class object to a pointer or reference to the base class (regardless of the depth of the inheritance hierarchy) requires no compiler intervention or modification of the address. Instead, it happens "naturally," and in that sense, it provides optimal runtime efficiency.

From Figure 3.2(b), note that placing the vptr at the beginning of the class object breaks the natural polymorphism of single inheritance in the special case of a base class without virtual functions and a derived class with them. The conversion of the derived object to the base in this case requires the intervention of the compiler in order to adjust the address being assigned by the size of the vptr. Under both multiple and virtual inheritances, the need for compiler intervention is considerably more pronounced.

Multiple inheritance is neither as well behaved nor as easily modeled as single inheritance. The complexity of multiple inheritance lies in the "unnatural" relationship of the derived class with its second and subsequent base class subobjects. Consider, for example, the following multiply derived class, Vertex2d:

class Point2d {
public:
   // ...
protected:
   float _x, _y;
};

class Vertex {
public:
   // ...
protected:
   Vertex *next;
};

class Vertex2d :
   public Point2d, public Vertex {
public:
   //...
protected:
   float mumble;
};
The problem of multiple inheritance primarily affects conversions between the derived and second or subsequent base class objects, either directly

extern void mumble( const Vertex& );
Vertex3d v;
...
// conversion of a Vertex3d to Vertex is ``unnatural''
mumble( v );
or through support for the virtual function mechanism. The problems with supporting virtual function invocation are discussed in Section 4.2.

The assignment of the address of a multiply derived object to a pointer of its leftmost (that is, first) base class is the same as that for single inheritance, since both point to the same beginning address. The cost is simply the assignment of that address (Figure 3.4 shows the multiple inheritance layout). The assignment of the address of a second or subsequent base class, however, requires that that address be modified by the addition (or subtraction in the case of a downcast) of the size of the intervening base class subobject(s).

What about access of a data member of a second or subsequent base class? Is there an additional cost? No. The member's location is fixed at compile time. Hence its access is a simple offset the same as under single inheritance regardless of whether it is a pointer, reference, or object through which the member is being accessed.

四. Virtual Inheritance:
A semantic side effect of multiple inheritance is the need to support a form of shared subobject inheritance. The classic example of this is the original iostream library implementation:

//pre-standard iostream implementation
class ios { ... };
class istream : public ios { ... };
class ostream : public ios { ... };
class iostream :
   public istream, public ostream { ... };
Both the istream and ostream classes contain an ios subobject. In the layout of iostream, however, we need only a single ios subobject. The language level solution is the introduction of virtual inheritance:

class ios { ... };
class istream : public virtual ios { ... };
class ostream : public virtual ios { ... };
class iostream :
   public istream, public ostream { ... };

The general implementation solution is as follows. A class containing one or more virtual base class subobjects, such as istream, is divided into two regions: an invariant region and a shared region. Data within the invariant region remains at a fixed offset from the start of the object regardless of subsequent derivations. So members within the invariant region can be accessed directly. The shared region represents the virtual base class subobjects. The location of data within the shared region fluctuates with each derivation. So members within the shared region need to be accessed indirectly. What has varied among implementations is the method of indirect access. The following example illustrates the three predominant strategies. Here is the data portion of a virtual Vertex3d inheritance hierarchy:

class Point2d {
public:
   ...
protected:
   float _x, _y;
};

class Vertex : public virtual Point2d {
public:
   ...
protected:
   Vertex *next;
};

class Point3d : public virtual Point2d {
public:
   ...
protected:
   float _z;
};
class Vertex3d :
   public Point3d, public Vertex {
public:
   ...
protected:
   float mumble;
};
The general layout strategy is to first lay down the invariant region of the derived class and then build up the shared region.

However, one problem remains: How is the implementation to gain access to the shared region of the class? In the original cfront implementation, a pointer to each virtual base class is inserted within each derived class object. Access of the inherited virtual base class members is achieved indirectly through the associated pointer. For example, if we have the following Point3d operator:

void
Point3d::
operator+=( const Point3d &rhs )
{
   _x += rhs._x;
   _y += rhs._y;
   _z += rhs._z;
};
under the cfront strategy, this is transformed internally into

// Pseudo C++ Code
__vbcPoint2d->_x += rhs.__vbcPoint2d->_x;
__vbcPoint2d->_y += rhs.__vbcPoint2d->_y;
_z += rhs._z;

A conversion between the derived and base class instances, such as

Vertex *pv = pv3d;
under the cfront implementation model becomes

// Pseudo C++ code
Vertex *pv = pv3d ? pv3d->__vbcPoint2d : 0;

3.4 Inheritance and the Data Member
Under the C++ inheritance model, a derived class object is represented as the concatenation of its members with those of its base class(es). The actual ordering of the derived and base class parts is left unspecified by the Standard. In theory, a compiler is free to place either the base or the derived part first in the derived class object. In practice, the base class members always appear first, except in the case of a virtual base class. (In general, the handling of a virtual base class is an exception to all generalities, even, of course, this one.)

Given this inheritance model, one can ask: What is the difference in providing two abstract data types for the representation of two- and three-dimensional points, such as

// supporting abstract data types
class Point2d {
public:
   // constructor(s)
   // operations
   // access functions
private:
   float x, y;
};

class Point3d {
public:
   // constructor(s)
   // operations
   // access functions
private:
   float x, y, z;
};
and providing a two- or three-level hierarchy in which each additional dimension is a class derived from the lower dimension? In the following subsections, the effects of single inheritance without the support of virtual functions, single inheritance with virtual functions, multiple inheritance, and virtual inheritance are examined. Figure 3.1(a) pictures the layout of Point2d and Point3d objects. (In the absence of virtual functions, they are equivalent to C struct declarations.)

Figure 3.1(a). Data Layout: Independent Structs


Inheritance without Polymorphism
Imagine that the programmer wishes to share an implementation but continue to use type-specific instances of either the two- or three-dimensional point. One design strategy is to derive Point3d from our Point2d class, with Point 3d inheriting all the operations and maintenance of the x- and y-coordinates. The effect is to localize and share data and the operations upon that data among two or more related abstractions. In general, concrete inheritance adds no space or access-time overhead to the representation.

class Point2d {
public:
   Point2d( float x = 0.0, float y = 0.0 )
      : _x( x ), _y( y ) {};

   float x() { return _x; }
   float y() { return _y; }

   void x( float newX ) { _x = newX; }
   void y( float newY ) { _y = newY; }

   void operator+=( const Point2d& rhs ) {
      _x += rhs.x();
      _y += rhs.y();
   }
      // ... more members
   protected:
      float _x, _y;
   };

   // inheritance from concrete class
   class Point3d : public Point2d {
   public:
      Point3d( float x = 0.0, float y = 0.0, float z = 0.0 )
         : Point2d( x, y ), _z( z ) {};

      float z() { return _z; }
      void z( float newZ ) { _z = newZ; }

      void operator+=( const Point3d& rhs ) {
         Point2d::operator+=( rhs );
         _z += rhs.z();
      }
      // ... more members
   protected:
      float _z;
   };
The benefit of this design strategy is the localization of the code to manage the x- and y-coordinates. In addition, the design clearly indicates the tight coupling of the two abstractions. The declaration and use of both Point2d and Point3d class objects do not change from when the two classes were independent, so clients of these abstractions need not be aware of whether the objects are independent class types or related through inheritance. Figure 3.1(b) shows the layout of the Point2d and Point3d inheritance layout without the declaration of a virtual interface.

Figure 3.1(b). Data Layout: Single Inheritance without Virtual Functions


What are the possible pitfalls of transforming two independent classes into a type/subtype relationship through inheritance? A naive design might, in fact, double the number of function calls to perform the same operations. That is, say the constructor or operator+=() in our example were not made inline (or the compiler could not for some reason support the inlining of the member functions). The initialization or addition of a Point3d object would be the cost of the partial Point2d and Point3d instances. In general, choosing candidate functions for inlining is an important, if unglamorous, aspect of class design. Confirming that they are in fact inlined is necessary before final release of the implementation.

A second possible pitfall in factoring a class into a two-level or deeper hierarchy is a possible bloating of the space necessary to represent the abstraction as a class hierarchy. The issue is the language guarantee of the integrity of the base class subobject within the derived class. It's slightly subtle. A walk-through of an example might best explain it. Let's begin with a concrete class:

class Concrete {
public:
   // ...
private:
   int val;
   char c1;
   char c2;
   char c3;
};
On a 32-bit machine, the size of each Concrete class object is going to be 8 bytes, broken down as follows:

4 bytes for val

1 byte each for c1, c2, and c3

1 byte for the alignment of the class on a word boundary

Say, after some analysis, we decide that a more logical representation splits Concrete into a three-level inheritance hierarchy as follows:

class Concrete1 {
public:
   // ...
protected:
   int val;
   char bit1;
};
class Concrete2 : public Concrete1 {
public:
   // ...
protected:
   char bit2;
};

class Concrete3 : public Concrete2 {
public:
   // ...
protected:
   char bit3;
};
From a design standpoint, this representation may make more sense. From an implementation standpoint, however, we may be distressed to find that a Concrete3 class object now has a size of 16 bytes—double its previous size.

What's going on? Recall that the issue is the integrity of the base class subobject within the derived class. Let's walk through the layout of the inheritance hierarchy to see what is going on.

The Concrete1 class contains the two members—val and bit1—that together take up 5 bytes. The size of a Concrete1 class object, however, is 8 bytes: the 5 bytes of actual size plus 3 bytes of padding to align the object on a machine word boundary. That's as true in C as it is in C++; generally, alignment constraints are determined by the underlying processor.

Nothing necessarily to complain about so far. It's the layout of the derived class that typically drives the unwary programmer into fits of either perplexity or angry indignation. Concrete2 adds a single nonstatic data member, bit2, of type char. Our unwary programmer expects it to be packed into the base Concrete1 representation, taking up one of the bytes otherwise wasted as alignment padding. This layout strategy makes the Concrete2 class object also of size 8 bytes, with 2 bytes of padding.

The layout of the Concrete2 class, however, instead preserves the 3 bytes of padding within the Concrete1 base class subobject. The bit2 member is set down after that, followed by an additional 3 bytes of padding. The size of a Concrete2 class object is 12 bytes, not 8, with 6 bytes wasted for padding. The same layout algorithm results in a Concrete3 class object's being 16 bytes, 9 of which are wasted on padding.

"That's stupid," is the unwary programmer's judgment, which more than one has chosen to share with me over e-mail, on the phone, and in per-son. Do you see why the language behaves as it does?

Let's declare the following set of pointers:

Concrete2 *pc2;
Concrete1 *pc1_1, *pc2_2;
Both pc1_1 and pc2_2 can address objects of either three classes. The following assignment

*pc1_1 = *pc2_2;
should perform a default memberwise copy of the Concrete1 portion of the object addressed. If pc1_1 addresses a Concrete2 or Concrete3 object, that should not be of consequence to the assignment of its Concrete1 subobject.

However, if the language were to pack the derived class members Concrete2::bit2 or Concrete3::bit3 into the Concrete1 subobject, these language semantics could not be preserved. An assignment such as

pc1_1 = pc2;

// oops: derived class subobject is overridden
// its bit2 member now has an undefined value
*pc1_1 = *pc2_2;
would overwrite the values of the packed inherited members. It would be an enormous effort on the user's part to debug this, to say the least.

Adding Polymorphism
If we want to operate on a point independent of whether it is a Point2d or Point3d instance, we need to provide a virtual function interface within our hierarchy. Let's see how things change when we do that:

class Point2d {
public:
   Point2d( float x = 0.0, float y = 0.0 )
      : _x( x ), _y( y ) {};

   // access functions for x & y same as above
   // invariant across type: not made virtual

   // add placeholders for z — do nothing ...
   virtual float z(){ return 0.0 };
   virtual void z( float ) {}
   // turn type explicit operations virtual
   virtual void
   operator+=( const Point2d& rhs ) {
       _x += rhs.x(); _y += rhs.y(); }

   // ... more members
protected:
   float _x, _y;
};
It makes sense to introduce a virtual interface into our design only if we intend to manipulate two- and three-dimensional points polymorphically, that is, to write code such as

void foo( Point2d &p1, Point2d &p2 ) {
   // ...
   p1 += p2;
   // ...
}
where p1 and p2 may be either two- or three-dimensional points. This is not something that any of our previous designs supported. This flexibility, of course, is at the heart of OO programming. Support for this flexibility, however, does introduce a number of space and access-time overheads for our Point2d class:

Introduction of a virtual table associated with Point2d to hold the address of each virtual function it declares. The size of this table in general is the number of virtual functions declared plus an additional one or two slots to support runtime type identification.

Introduction of the vptr within each class object. The vptr provides the runtime link for an object to efficiently find its associated virtual table.

Augmentation of the constructor to initialize the object's vptr to the virtual table of the class. Depending on the aggressiveness of the compiler's optimization, this may mean resetting the vptr within the derived and each base class constructor. (This is discussed in more detail in Chapter 5.)

Augmentation of the destructor to reset the vptr to the associated virtual table of the class. (It is likely to have been set to address the virtual table of the derived class within the destructor of the derived class. Remember, the order of destructor calls is in reverse: derived class and then base class.) An aggressive optimizing compiler can suppress a great many of these assignments.

The impact of these overheads depends on the number and lifetime of the Point2d objects being manipulated and the benefits gained in programming the objects polymorphically. If an application knows its use of point objects is limited to either (but not both) two- or three-dimensional points, the overheads of this design may become unacceptable. [1]

[1] I am not aware of any production system actually making use of a polymorphic Point hierarchy.

Here is our new Point3d derivation:

class Point3d : public Point2d {
public:
   Point3d( float x = 0.0, float y = 0.0, float z = 0.0 )
      : Point2d( x, y ), _z( z ) {};
   float z() { return _z; }
   void z( float newZ ) { _z = newZ; }

   void operator+=( const Point2d& rhs ) {
      Point2d::operator+=( rhs );
      _z += rhs.z();
   }
   // ... more members
protected:
   float _z;
};
Although the syntax of the class's declaration has not changed, everything about it is now different: The two z() member functions and the operator+=() operator are virtual instances. Each Point3d class object contains an additional vptr member object (the instance inherited from Point2d). There is also a Point3d virtual table. The invocation of each member function made virtual is also more complex (this is covered in Chapter 4).

One current topic of debate within the C++ compiler community concerns where best to locate the vptr within the class object. In the original cfront implementation, it was placed at the end of the class object in order to support the following inheritance pattern, shown in Figure 3.2(a):

Figure 3.2(a). Vptr Placement and End of Class


struct no_virts {
   int d1, d2;
};
class has_virts: public no_virts {
public:
   virtual void foo();
   // ...
private:
   int d3;
};

no_virts *p = new has_virts;
Placing the vptr at the end of the class object preserves the object layout of the base class C struct, thus permitting its use within C code. This inheritance idiom is believed by many to have been more common when C++ was first introduced than currently.

Subsequent to Release 2.0, with its addition of support for multiple inheritance and abstract base classes, and the general rise in popularity of the OO paradigm, some implementations began placing the vptr at the start of the class object. (For example, Martin O'Riordan, who led Microsoft's original C++ compiler effort, persuasively argues for this implementation model.) See Figure 3.2(b) for an illustration.

Figure 3.2(b). Vptr Placement at Front of Class


Placing the vptr at the start of the class is more efficient in supporting some virtual function invocations through pointers to class members under multiple inheritance (see Section 4.4). Otherwise, not only must the offset to the start of the class be made available at runtime, but also the offset to the location of the vptr of that class must be made available. The trade-off, however, is a loss in C language interoperability. How significant a loss? What percentage of programs derive a polymorphic class from a C-lan-guage struct? There are currently no empirical numbers to support either position.

Figure 3.3 shows the Point2d and Point3d inheritance layout with the addition of virtual functions. (Note: The figure shows the vptr placement at the end of the base class.)

Figure 3.3. Data Layout: Single Inheritance with Virtual Inheritance


Multiple Inheritance
Single inheritance provides a form of "natural" polymorphism regarding the conversion between base and derived types within the inheritance hierarchy. Look at Figures 3.1(b), 3.2(a), or 3.3, where you can see that the base and derived class objects both begin at the same address. They differ in that the derived object extends the length of its nonstatic data members. The assignment, such as

Point3d p3d;
Point2d *p = &p3d;
of the derived class object to a pointer or reference to the base class (regardless of the depth of the inheritance hierarchy) requires no compiler intervention or modification of the address. Instead, it happens "naturally," and in that sense, it provides optimal runtime efficiency.

From Figure 3.2(b), note that placing the vptr at the beginning of the class object breaks the natural polymorphism of single inheritance in the special case of a base class without virtual functions and a derived class with them. The conversion of the derived object to the base in this case requires the intervention of the compiler in order to adjust the address being assigned by the size of the vptr. Under both multiple and virtual inheritances, the need for compiler intervention is considerably more pronounced.

Multiple inheritance is neither as well behaved nor as easily modeled as single inheritance. The complexity of multiple inheritance lies in the "unnatural" relationship of the derived class with its second and subsequent base class subobjects. Consider, for example, the following multiply derived class, Vertex3d:

class Point2d {
public:
   // ...
protected:
   float _x, _y;
};

class Vertex {
public:
   // ...
protected:
   Vertex *next;
};

class Vertex2d :
   public Point2d, public Vertex {
public:
   //...
protected:
   float mumble;
};
The problem of multiple inheritance primarily affects conversions between the derived and second or subsequent base class objects, either directly

extern void mumble( const Vertex& );
Vertex3d v;
...
// conversion of a Vertex3d to Vertex is ``unnatural''
mumble( v );
or through support for the virtual function mechanism. The problems with supporting virtual function invocation are discussed in Section 4.2.

The assignment of the address of a multiply derived object to a pointer of its leftmost (that is, first) base class is the same as that for single inheritance, since both point to the same beginning address. The cost is simply the assignment of that address (Figure 3.4 shows the multiple inheritance layout). The assignment of the address of a second or subsequent base class, however, requires that that address be modified by the addition (or subtraction in the case of a downcast) of the size of the intervening base class subobject(s). For example, with

Figure 3.4. Data Layout: Multiple Inheritance


Vertex3d v3d;
Vertex  *pv;
Point2d *pp;
Point3d *p3d;
the assignment

pv = &v3d;
requires a conversion of the form

// Pseudo C++ Code
pv = (Vertex*)(((char*)&v3d) + sizeof( Point3d ));
whereas the assignments

pp  = &v3d;
p3d = &v3d;
both simply require a copying of the address. With

Vertex3d *p3d;
Vertex   *pv;
the assignment

pv = p3d;
cannot simply be converted into

// Pseudo C++ Code
pv = (Vertex*)((char*)p3d) + sizeof( Point3d );
since, if p3d were set to 0, pv would end up with the value sizeof(Point3d). So, for pointers, the internal conversion requires a conditional test:

// Pseudo C++ Code
pv = p3d
   ? (Vertex*)((char*)p3d) + sizeof( Point3d )
   : 0;
Conversion of a reference need not defend itself against a possible 0 value, since the reference cannot refer to no object.

The Standard does not require a specific ordering of the Point3d and Vertex base classes of Vertex3d. The original cfront implementation always placed them in the order of declaration. A Vertex3d object under cfront, therefore, consisted of the Point3d subobject (which itself consisted of a Point2d subobject), followed by the Vertex subobject and finally by the Vertex3d part. In practice, this is still how all implementations lay out the multiple base classes (with the exception of virtual inheritance).

An optimization under some compilers, however, such as the MetaWare compiler, switch the order of multiple base classes if the second (or subsequent) base class declares a virtual function and the first does not. This shuffling of the base class order saves the generation of an additional vptr within the derived class object. There is no universal agreement among implementations about the importance of this optimization, and use of this optimization is not (at least currently) widespread.

What about access of a data member of a second or subsequent base class? Is there an additional cost? No. The member's location is fixed at compile time. Hence its access is a simple offset the same as under single inheritance regardless of whether it is a pointer, reference, or object through which the member is being accessed.

Virtual Inheritance
A semantic side effect of multiple inheritance is the need to support a form of shared subobject inheritance. The classic example of this is the original iostream library implementation:

//pre-standard iostream implementation
class ios { ... };
class istream : public ios { ... };
class ostream : public ios { ... };
class iostream :
   public istream, public ostream { ... };
Both the istream and ostream classes contain an ios subobject. In the layout of iostream, however, we need only a single ios subobject. The language level solution is the introduction of virtual inheritance:

class ios { ... };
class istream : public virtual ios { ... };
class ostream : public virtual ios { ... };
class iostream :
   public istream, public ostream { ... };
As complicated as the semantics of virtual inheritance may seem, its support within the compiler has proven even more complicated. In our iostream example, the implementational challenge is to find a reasonably efficient method of collapsing the two instances of an ios subobject maintained by the istream and ostream classes into a single instance maintained by the iostream class, while still preserving the polymorphic assignment between pointers (and references) of base and derived class objects.

The general implementation solution is as follows. A class containing one or more virtual base class subobjects, such as istream, is divided into two regions: an invariant region and a shared region. Data within the invariant region remains at a fixed offset from the start of the object regardless of subsequent derivations. So members within the invariant region can be accessed directly. The shared region represents the virtual base class subobjects. The location of data within the shared region fluctuates with each derivation. So members within the shared region need to be accessed indirectly. What has varied among implementations is the method of indirect access. The following example illustrates the three predominant strategies. Here is the data portion of a virtual Vertex3d inheritance hierarchy: [2]

[2] This hierarchy is suggested by [POKOR94], an excellent 3D Graphics textbook using C++.

class Point2d {
public:
   ...
protected:
   float _x, _y;
};

class Vertex : public virtual Point2d {
public:
   ...
protected:
   Vertex *next;
};

class Point3d : public virtual Point2d {
public:
   ...
protected:
   float _z;
};
class Vertex3d :
   public Point3d, public Vertex {
public:
   ...
protected:
   float mumble;
};
The general layout strategy is to first lay down the invariant region of the derived class and then build up the shared region.

However, one problem remains: How is the implementation to gain access to the shared region of the class? In the original cfront implementation, a pointer to each virtual base class is inserted within each derived class object. Access of the inherited virtual base class members is achieved indirectly through the associated pointer. For example, if we have the following Point3d operator:

void
Point3d::
operator+=( const Point3d &rhs )
{
   _x += rhs._x;
   _y += rhs._y;
   _z += rhs._z;
};
under the cfront strategy, this is transformed internally into

// Pseudo C++ Code
__vbcPoint2d->_x += rhs.__vbcPoint2d->_x;
__vbcPoint2d->_y += rhs.__vbcPoint2d->_y;
_z += rhs._z;
A conversion between the derived and base class instances, such as

Vertex *pv = pv3d;
under the cfront implementation model becomes

// Pseudo C++ code
Vertex *pv = pv3d ? pv3d->__vbcPoint2d : 0;

There are two primary weaknesses with this implementation model:

(1). An object of the class carries an additional pointer for each virtual base class. Ideally, we want a constant overhead for the class object that is independent of the number of virtual base classes within its inheritance hierarchy. Think of how you might solve this.

(2). As the virtual inheritance chain lengthens, the level of indirection increases to that depth. This means that three levels of virtual derivation requires indirection through three virtual base class pointers. Ideally, we want a constant access time regardless of the depth of the virtual derivation.

MetaWare and other compilers still using cfront's original implementation model solve the second problem by promoting (by copying) all nested virtual base class pointers into the derived class object. This solves the constant access time problem, although at the expense of duplicating the nested virtual base class pointers. MetaWare provides a compile-time switch to allow the programmer to choose whether to generate the duplicate pointers. Figure 3.5(a) illustrates the pointer-to-base-class implementation model.

There are two general solutions to the first problem. Microsoft's compiler introduced the virtual base class table. Each class object with one or more virtual base classes has a pointer to the virtual base class table inserted within it. The actual virtual base class pointers, of course, are placed within the table. Although this solution has been around for many years, I am not aware of any other compiler implementation that employs it. (It may be that Microsoft's patenting of their virtual function implementation effectively prohibits its use.)

The second solution, and the one preferred by Bjarne (at least while I was working on the Foundation project with him), is to place not the address but the offset of the virtual base class within the virtual function table. (Figure 3.5(b) on page 100 shows the base class offset implementation model.) I implemented this in the Foundation research project, interweaving the virtual base class and virtual function entries. In the recent Sun compiler, the virtual function table is indexed by both positive and negative indices. The positive indices, as previously, index into the set of virtual functions; the negative indices retrieve the virtual base class offsets. Under this strategy, the Point3d operator is translated into the following general form (leaving off casts for readability and not showing the more efficient precalculation of the addresses):

// Pseudo C++ Code
(this + __vptr__Point3d[-1])->_x += (&rhs + rhs.__vptr__Point3d[-1])->_x;
(this + __vptr__Point3d[-1])->_y += (&rhs + rhs.__vptr__Point3d[-1])->_y;
_z += rhs._z;

Although the actual access of the inherited member is more expensive under this strategy, the cost of that access is localized to a use of the member. A conversion between the derived and base class instances, such as

Vertex *pv = pv3d;
under this implementation model becomes

// Pseudo C++ code
Vertex *pv = pv3d
   ? pv3d + pv3d->__vptr__Point3d[-1])
   : 0;

Each of these are implementation models; they are not required by the Standard. Each solves the problem of providing access to a shared subobject whose location is likely to fluctuate with each derivation. Because of the overhead and complexity of virtual base class support, each implementation is somewhat different and likely to continue to evolve over time.

Access of an inherited virtual base class member through a nonpolymorphic class object, such as

Point3d origin;
...
origin._x;
can be optimized by an implementation into a direct member access, much as a virtual function call through an object can be resolved at compile time. The object's type cannot change between one program access and the next, so the problem of the fluctuating virtual base class subobject in this case does not hold.

In general, the most efficient use of a virtual base class is that of an abstract virtual base class with no associated data members.抽象基才是王道!

posted on 2006-11-16 23:48 Jerry Cat 阅读(1009) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2006年11月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(7)

随笔档案

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜