Data processing: software development – installation – and managem – Software program development tool – Linking
Reexamination Certificate
2000-04-28
2004-06-15
Nguyen-Ba, Antony (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Linking
C719S332000, C707S793000, C715S252000
Reexamination Certificate
active
06751793
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention pertains to hierarchical structures in object oriented languages. More particularly, it pertains to the growth of hierarchical structures with new virtual base classes while preserving release-to-release binary compatibility (RRBC).
2. Prior Art
Release-to-release binary compatibility (RRBC) is the ability for client code to continue to operate without recompilation, even when shared libraries upon which such code depends are updated with newer versions.
RRBC problems in the C++ programming language are introduced when information about a class is compiled into client code, such as the offset and location of class members, instance size, and the offset to parent class data. As a result, a simple change to a class, such as adding a new member or adding a new base class, may require recompilation of any derived class or client code.
There is a requirement for class libraries to allow adding new base classes in a class hierarchy without impacting RRBC. There is also a requirement to allow adding a new virtual base only on the non-leftmost path of a class hierarchy without impacting RRBC and the performance of single or leftmost path inheritance. There is also a requirement to minimize the cost to performance ratio in any solution to these requirements.
From the experience of class library designers, a class hierarchy can never be right in the first couple of releases without extensive use by its customers. Changes to class hierarchies are likely to happen in subsequent releases, especially when adding new bases. In the current design of most class libraries, use of non-virtual and single inheritance is far more common than virtual and multiple inheritance. The performance of virtual and multiple inheritance discourages class designers from using it. So to them, allowing the addition of non-virtual base classes in single inheritance without impacting RRBC is required and they need to be able to add the new classes at the end or in the middle of the hierarchy. To satisfy this requirement from designers of class libraries is possible but comes with a performance penalty.
Accessing Data in a Non-virtual Base Class
Current inheritance implementations, such as the IBM®Visual Age® and Taligent C++, forego all indirection, except for accessing a virtual base; that is, the data members of a base class subobject are directly stored within the derived class object. Access of a data member requires the addition of the beginning address of the class object with the offset location of the data member.
The offset is known at compile time even if the member belongs to a base class subobject derived through a single or multiple inheritance chain. This offers the most compact and most efficient access of non-virtual base class members.
TABLE 1
IBM and Taligent use direct data access in non
virtual inheritance:
//* (obj+member_offset)=value
move [this+member_offset],value
//direct assign “value” to data member
In Table 1, the move statement moves a “value” to the address of a data member in a base class. The address of the data member is obtained by addition of the “this” pointer which points to the beginning of the object to the offset of the member within the object. “obj” and “this” are here used interchangeably, and refer to the beginning address of an object. [this+member_offset] refers to the address of the data member.
Accessing Data in a Virtual Base Class:
Currently, IBM VisualAge C++ access to a virtual base class subobject is done through a virtual base pointer located inside the class object. The location of the virtual base pointer is fixed and known during compile time so an extra level of indirection is required to access data in the virtual base.
Instead of using virtual base pointer, currently Taligent C++ access to a virtual base class subobject is done through a virtual function table VFT pointer. If a given class directly or indirectly inherits from a virtual base class, the VFT (also referred to as vtable) of that given class contains offsets to find the virtual base subobjects. Use of virtual base offsets results in more instructions to do virtual base accesses, but smaller object size or less initialization time is needed during the program startup time.
TABLE 2
IBM VisualAge C++ data access in virtual
inheritance : 1 extra memory access compared to
direct access in non-virtual case
//* (this+*this—>vbp+member_offset)=value
move
eax,[this+virtual_base_pointer_offset]
//eax=virtual base pointer
move
[eax+member_offset_within_base], value
//indirect assign “value” to //virtual base's data member
In Table 2, the first move statement moves the virtual base pointer (vbp) to register eax. The location of the vbp is obtained by addition of the “this” pointer to the offset of the virtual base pointer within the object. The next move statement moves a “value” to the member of the virtual base. The address of the data member is obtained by addition of the vbp to the offset of the member within the virtual base class. The first move statement denotes the extra memory access which is not required in the non-virtual case.
TABLE 3
Taligent C++ data access in virtual
inheritance: 2 extra memory accesses compared to direct
access in non-virtual case
//* (this+this>vft{vbaseoffset_index}+member_offset)=value
move
eax,[this]
//eax=virtual function table address
move
eax,vbase_index[eax]
//eax=virtual base class offset
add
eax, this
//eax=this+virtual base offset
move
[eax+member_offset_within_base],value
//indirect assign “value” to
// virtual base's data member
In Table 3, the first move statement moves the virtual function table (VFT) address to register eax. This is the first extra memory access. The VFT address is stored in the memory pointed to by the “this” pointer. The second move statement moves the offset of the virtual base to register eax from an index to the VFT. This is the second extra memory access. The add statement gets the address of the virtual base class in register eax by adding the “this” pointer to the offset of the virtual base within the object. The last move statement moves the value to the data member address. The data member address is obtained by adding the member offset to the address of the virtual base.
Supporting Addition of New Bases:
To support adding new base classes, both virtual and non-virtual, the offset locations of the base within the object are no longer fixed and known during compile time. One way to solve the problem is to introduce a base class table to keep track of the offset or address of an associated base class and use an extra level of indirection to access base class members. This is similar to accessing a virtual base but the table has to be completed at run-time to achieve RRBC.
TABLE 4
Data access using run-time base offset table in
virtual and non-virtual inheritance: 2 extra
memory access compare to direct data access
//* (this+base_table[base_index]+member_offset)=value
move
eax,[base_table]
//eax=address of base offset table
move
eax,base_index[eax]
//eax=base class offset
add
eax,this
move
[eax+member_offset],value
//assign “value” to base's data member
In Table 4, the first move statement is the first extra memory load and the second move statement is the second extra memory load. In the normal case, both IBM VisualAge and Taligent C++ do not require any memory load in accessing a data member in a non-virtual base.
Thus, in accessing data in a virtual or non-virtual base, two extra memory loads are required compared to direct data access. Since the majority of time spent in executing most applications is spent on accessing data, extra memory loads slow down the program significantly.
Calling a Virtual Function in a Base Class
Lung Catherine Y.
Thomson Brian W.
Ludwin Richard M.
Nguyen-Ba Antony
Scully Scott Murphy & Presser
LandOfFree
System and method for growing a hierarchical structure with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for growing a hierarchical structure with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for growing a hierarchical structure with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359423