标签: padding

I've written a couple of articles on dynamic allocation in C and C++ emphasizing the distinction between allocating objects and allocating raw (uninitialized) storage. When a program allocates an object, it not only allocates storage for the object, but also initializes that storage with a value appropriate for the type of object that will occupy that storage. When a program just allocates storage, it leaves that storage uninitialized.   I have also explained the distinction between deallocating objects and deallocating storage. When a program deallocates an object, it releases not only the storage occupied by the object, but also any other resources the object was using.   I also sketched out how C++ compilers translate new-expressions into more primitive operations. I also showed how to write C code that emulates the behavior of new-expressions. However, I stalled out when I got to array delete-expressions. I also left some details out of the code for both the C++ implementation and the C emulation of array new-expressions. I'll fill in most of the missing pieces in my future blogs.   A recap New-expressions in C++ allocate objects. Each new-expression is conceptually, if not actually, a two-step process: (1) allocate storage for an object, and (2) initialize it. For objects of class types, initializing an object usually involves calling a constructor.   For example, suppose class widget is defined as:   class widget { public: widget(); // a constructor ~widget(); // a destructor // ... };   Then a new-expression such as:   pw = new widget ();   translates more-or-less into something like:   pw = static_cast(operator new(sizeof(widget))); pw-widget();   The first statement acquires storage for a widget object by calling operator new , and converts the address of that storage from type void * to type widget * . The second statement initializes the storage by applying widget 's default constructor. (That second statement—an explicit constructor call—is not something you can actually write in C++.)   Delete-expressions in C++ deallocate objects. Each delete-expression is also a two-step process: (1) release resources that the object was using, and (2) deallocate the storage for the object. For objects of class types, releasing resources involves calling a destructor.   If pw is a pointer to an object of class type widget , a delete-expression such as delete pw; translates more-or-less into something like:   if (pw != NULL) { pw-~widget(); operator delete(pw); }   A delete-expression applied to a null pointer does nothing. If the pointer is non-null, the delete-expression applies the destructor to the soon-to-be-deleted object, and then deallocates the object's storage by passing the object's address to operator delete .   In contrast to a new-expression, a call to the Standard C malloc function, as in:   pw = (widget *)malloc(sizeof(widget));   merely allocates storage for a widget , leaving the storage uninitialized. In contrast to a delete-expression, a call to the Standard C free function, as in:   free(pw);   merely deallocates the storage for a widget , without any regard for any additional resources that the widget may have been using.   Although C doesn't have classes with constructors and destructors, you can emulate them by using structs and functions. For example, you can implement a C++ widget class as a C struct:   typedef struct widget widget; struct widget { // widget data members go here };   (The typedef immediately before the struct definition elevates the name widget from a mere tag to a full-fledged type name.)   You can also implement each widget class member function in C++ as a non-member function in C whose first parameter is a pointer to the widget to be manipulated, possibly along with other parameters. For example, you might declare the C implementation of the widget default constructor and destructor as:   void widget_construct(widget *pw); void widget_destroy(widget *pw);   You can closely approximate the behavior of a C++ new-expression as an inline C function:   inline widget *new_widget() { widget *pw = (widget *)malloc(sizeof(widget)); if (pw != NULL) widget_construct(pw); return pw; }   Thereafter, you can construct a dynamically-allocated widget with a default initial value using just:   pw = new_widget();   which is a pretty good approximation for the C++ new-expression:   pw = new widget;   Similarly, you can mimic the behavior of a C++ delete-expression by using another inline function:   inline void delete_widget(widget *pw) { if (pw != NULL) { widget_destroy(pw); free(pw); } }   Then, if pw points to a dynamically-allocated widget , you can delete it by calling:   delete_widget(pw);   which is a pretty fair approximation for the C++ delete-expression:   delete pw;   Allocating and deallocating arrays A C++ array new-expression as in:   pw = new widget ;   allocates an array of 10 properly initialized widget s. As with other new-expressions, an array new-expression is still a two-step process: (1) allocate storage, and (2) initialize it. However, with an array new-expression the second step is a loop, which applies the default widget constructor to each array element in ascending order by element address.   An array delete-expression such as:   delete ;   You can mimic the behavior of an array delete-expression as a function declared as:   void delete_widget_array(widget *pw);   but the implementation isn't as straightforward as it is for new_widget_array . Whereas the array dimension appears explicitly in an array new-expression, it never appears in an array delete-expression nor in the declaration of delete_widget_array . Each array delete-expression specifies the address of (the initial element of) the array, but not the array's dimension. The delete-expression and delete_widget_array have to obtain the array dimension another way.     A common technique for passing the array dimension to the delete-expression is for the array new-expression to stash the array dimension in a location just before the array itself, as illustrated in the Figure 1 . Inasmuch as that additional location stores an array dimension, it should be declared as type size_t , the same as the parameter to new_widget_array .   Previously, new_widget_array allocated space for the array using:   widget *pw = (widget *)malloc(n * sizeof(widget));   In the new version, it allocates space for the array plus storage for the array dimension using:   size_t size = sizeof(size_t) + n * sizeof(widget); size_t *ps = (size_t *)malloc(size);   If ps is non-null ( malloc returns a pointer to the requested storage), then new_widget_array can proceed to place the array dimension at the beginning of that storage:   *ps = n;   and then compute the address of the first element in the array itself:   ++ps;   The allocated array is an array of widgets , but ps is a pointer to a size_t , so new_widget_array needs a cast to obtain a pointer it can use to access the array elements:   pw = (widget *)ps;   Altogether, the new version of new_widget_array looks like:   widget *new_widget_array(size_t n) { widget *pw = NULL; size_t size = sizeof(size_t) + n * sizeof(widget); size_t *ps = (size_t *)malloc(size); if (ps != NULL) { widget *p; *ps = n; pw = (widget *)++ps; for (p = pw; p != pw + n; ++p) widget_construct(p); } return pw; }   The delete_widget_array function assumes that its parameter, pw , is a pointer returned from some prior call to new_widget_array . Therefore, delete_widget_array must obtain the array dimension by effectively reversing the pointer computation done in new_widget_array . A complete implementation of the function looks like:   void delete_widget_array(widget *pw) { if (pw != NULL) { size_t *ps = (size_t *)pw; size_t n = *—ps; widget *p = pw + n; while (p != pw) widget_destroy(—p); free(ps); } }   Padding and alignment, again These implementations of new_widget_array and delete_widget_ array will work just fine on any processor in which no type has an alignment stricter than that of size_t . However, it could produce undefined behavior on any machine with more strictly aligned types. I'll explain why, and what you can do about it, in a future article.    

I've written a couple of articles on dynamic allocation in C and C++ emphasizing the distinction between allocating objects and allocating raw (uninitialized) storage. When a program allocates an object, it not only allocates storage for the object, but also initializes that storage with a value appropriate for the type of object that will occupy that storage. When a program just allocates storage, it leaves that storage uninitialized.   I have also explained the distinction between deallocating objects and deallocating storage. When a program deallocates an object, it releases not only the storage occupied by the object, but also any other resources the object was using.   I also sketched out how C++ compilers translate new-expressions into more primitive operations. I also showed how to write C code that emulates the behavior of new-expressions. However, I stalled out when I got to array delete-expressions. I also left some details out of the code for both the C++ implementation and the C emulation of array new-expressions. I'll fill in most of the missing pieces in my future blogs.   A recap New-expressions in C++ allocate objects. Each new-expression is conceptually, if not actually, a two-step process: (1) allocate storage for an object, and (2) initialize it. For objects of class types, initializing an object usually involves calling a constructor.   For example, suppose class widget is defined as:   class widget { public: widget(); // a constructor ~widget(); // a destructor // ... };   Then a new-expression such as:   pw = new widget ();   translates more-or-less into something like:   pw = static_cast(operator new(sizeof(widget))); pw-widget();   The first statement acquires storage for a widget object by calling operator new , and converts the address of that storage from type void * to type widget * . The second statement initializes the storage by applying widget 's default constructor. (That second statement—an explicit constructor call—is not something you can actually write in C++.)   Delete-expressions in C++ deallocate objects. Each delete-expression is also a two-step process: (1) release resources that the object was using, and (2) deallocate the storage for the object. For objects of class types, releasing resources involves calling a destructor.   If pw is a pointer to an object of class type widget , a delete-expression such as delete pw; translates more-or-less into something like:   if (pw != NULL) { pw-~widget(); operator delete(pw); }   A delete-expression applied to a null pointer does nothing. If the pointer is non-null, the delete-expression applies the destructor to the soon-to-be-deleted object, and then deallocates the object's storage by passing the object's address to operator delete .   In contrast to a new-expression, a call to the Standard C malloc function, as in:   pw = (widget *)malloc(sizeof(widget));   merely allocates storage for a widget , leaving the storage uninitialized. In contrast to a delete-expression, a call to the Standard C free function, as in:   free(pw);   merely deallocates the storage for a widget , without any regard for any additional resources that the widget may have been using.   Although C doesn't have classes with constructors and destructors, you can emulate them by using structs and functions. For example, you can implement a C++ widget class as a C struct:   typedef struct widget widget; struct widget { // widget data members go here };   (The typedef immediately before the struct definition elevates the name widget from a mere tag to a full-fledged type name.)   You can also implement each widget class member function in C++ as a non-member function in C whose first parameter is a pointer to the widget to be manipulated, possibly along with other parameters. For example, you might declare the C implementation of the widget default constructor and destructor as:   void widget_construct(widget *pw); void widget_destroy(widget *pw);   You can closely approximate the behavior of a C++ new-expression as an inline C function:   inline widget *new_widget() { widget *pw = (widget *)malloc(sizeof(widget)); if (pw != NULL) widget_construct(pw); return pw; }   Thereafter, you can construct a dynamically-allocated widget with a default initial value using just:   pw = new_widget();   which is a pretty good approximation for the C++ new-expression:   pw = new widget;   Similarly, you can mimic the behavior of a C++ delete-expression by using another inline function:   inline void delete_widget(widget *pw) { if (pw != NULL) { widget_destroy(pw); free(pw); } }   Then, if pw points to a dynamically-allocated widget , you can delete it by calling:   delete_widget(pw);   which is a pretty fair approximation for the C++ delete-expression:   delete pw;   Allocating and deallocating arrays A C++ array new-expression as in:   pw = new widget ;   allocates an array of 10 properly initialized widget s. As with other new-expressions, an array new-expression is still a two-step process: (1) allocate storage, and (2) initialize it. However, with an array new-expression the second step is a loop, which applies the default widget constructor to each array element in ascending order by element address.   An array delete-expression such as:   delete ;   You can mimic the behavior of an array delete-expression as a function declared as:   void delete_widget_array(widget *pw);   but the implementation isn't as straightforward as it is for new_widget_array . Whereas the array dimension appears explicitly in an array new-expression, it never appears in an array delete-expression nor in the declaration of delete_widget_array . Each array delete-expression specifies the address of (the initial element of) the array, but not the array's dimension. The delete-expression and delete_widget_array have to obtain the array dimension another way.  A common technique for passing the array dimension to the delete-expression is for the array new-expression to stash the array dimension in a location just before the array itself, as illustrated in the Figure 1 . Inasmuch as that additional location stores an array dimension, it should be declared as type size_t , the same as the parameter to new_widget_array .   Previously, new_widget_array allocated space for the array using:   widget *pw = (widget *)malloc(n * sizeof(widget));   In the new version, it allocates space for the array plus storage for the array dimension using:   size_t size = sizeof(size_t) + n * sizeof(widget); size_t *ps = (size_t *)malloc(size);   If ps is non-null ( malloc returns a pointer to the requested storage), then new_widget_array can proceed to place the array dimension at the beginning of that storage:   *ps = n;   and then compute the address of the first element in the array itself:   ++ps;   The allocated array is an array of widgets , but ps is a pointer to a size_t , so new_widget_array needs a cast to obtain a pointer it can use to access the array elements:   pw = (widget *)ps;   Altogether, the new version of new_widget_array looks like:   widget *new_widget_array(size_t n) { widget *pw = NULL; size_t size = sizeof(size_t) + n * sizeof(widget); size_t *ps = (size_t *)malloc(size); if (ps != NULL) { widget *p; *ps = n; pw = (widget *)++ps; for (p = pw; p != pw + n; ++p) widget_construct(p); } return pw; }   The delete_widget_array function assumes that its parameter, pw , is a pointer returned from some prior call to new_widget_array . Therefore, delete_widget_array must obtain the array dimension by effectively reversing the pointer computation done in new_widget_array . A complete implementation of the function looks like:   void delete_widget_array(widget *pw) { if (pw != NULL) { size_t *ps = (size_t *)pw; size_t n = *—ps; widget *p = pw + n; while (p != pw) widget_destroy(—p); free(ps); } }   Padding and alignment, again These implementations of new_widget_array and delete_widget_ array will work just fine on any processor in which no type has an alignment stricter than that of size_t . However, it could produce undefined behavior on any machine with more strictly aligned types. I'll explain why, and what you can do about it, in a future article.

For the most part, C code that defines and uses structures behaves the same when compiled and executed as C++. However, C++ generalizes structures into classes. A C++ class can have elements that a C structure cannot, such as access specifiers, member functions, static data members, and base classes. In one of my blogs, I explained how some of these elements can alter the physical layout of class objects. 1 This month, I'll expand my discussion of alignment, padding and member ordering to include access control. Access specifiers C++ class members can have different levels of accessibility: - A public member of a class is accessible anywhere in the program where the class itself is visible and accessible. - A private member of a class is accessible only to members and friends of that class. - A protected member of a class is accessible only to members and friends of that class or to members and friends of classes derived from that class. For example, a class widget defined as: class widget { public: widget(); protected: ~widget(); private: char m1; int m2; char m3; static int k; }; has one public member function (a default constructor), one protected member function (a destructor), and four private data members (three non-static and one static). Each access-specifier can appear more than once, and in any order. For example, you could rewrite the previous definition for widget as: class widget { protected: ~widget(); private: char m1; int m2; private: char m3; static int k; public: widget(); }; Here the keyword private appears twice and the public member is at the end (rather than the beginning) of the class definition. These changes aren't likely to alter the size or alignment of widg et objects. Member allocation order Within a given C structure, the members have offsets that increase in the order in which they are declared. In C++, a structure is just a class in which the members (and base classes) are public by default. Thus, in a class with only public members, such as: class widget { public: widget(); ~widget(); char m1; int m2; char m3; static int k; }; compilers allocate storage within each widget object for the non-static data members m1 , m2 , and m3 in that order. As I explained bfore, the constructor, destructor and static data member k add no storage to each widget object. What about a class with private or protected members? The relevant words in the draft of the next C++ Standard differ somewhat from the words in the current (2003) C++ Standard. I believe the draft's words are a better description of current practice. The draft states, "Non-static data members of a ... class with the same access control are allocated so that later members have higher addresses within a class object." 2 Storage allocation for a class in which all non-static data members have the same access—all public, or all private, or all protected—behaves just like storage allocation in a C structure. For example, the storage layout for widget objects when widget is defined as: class widget { public: widget(); ~widget(); static int k; private: char m1; int m2; char m3; }; is the same as when widget is defined as: class widget { public: widget(); ~widget(); char m1; int m2; char m3; static int k; }; which is the same as when widget is defined as: struct widget { char m1; int m2; char m3; }; These different class definitions aren't functionally equivalent, but they yield objects with the same size, alignment and member arrangement. Freedom to rearrange things The draft Standard also states that "The order of allocation of non-static data members with different access control is unspecified." This means that, if it wishes, a compiler can allocate members with different accessibility to reduce or eliminate the need for padding. For example, suppose class widget is defined as: class widget { public: char m1; protected: int m2; private: char m3; }; When compiled for a target machine in which each int occupies four bytes aligned to an address that's a multiple of four, the compiler can allocate storage for the members in the order in which they're declared and insert padding as if the class were defined as: class widget { public: char m1; char padding_after_m1 ; protected: int m2; private: char m3; char padding_after_m3 ; }; This layout requires six bytes of padding. On the other hand, the compiler can reorder the members to reduce the need for padding bytes, as either: class widget { public: char m1; private: char m3; char padding ; protected: int m2; }; or as: class widget { protected: int m2; public: char m1; private: char m3; char padding ; }; Using either rearrangement eliminates four padding bytes and shrinks the size of each widget object by that much. A C++ compiler can reorder members with different access specifiers, but can't reorder members within the same access specifier. For example, given: class widget { public: char m1; int m2; private: char m3; }; the compiler can't reorder the members so that m2 is allocated before m1 , as in: class widget { public: int m2; char m1; private: char m3; }; However, it can reorder the members so that m3 is before both m1 and m2 , as in: class widget { private: char m3; public: char m1; char padding ; int m2; }; None of the compilers that I have appear to rearrange members this aggressively. At least, I haven't been able to discover compiler options that will trigger such optimizations. If you have a compiler that will do this, please let me know which compiler(s) and compile option(s) you used to obtain this optimization. Endnotes: 1. Saks, Dan. " Classes are structure, and then some ," Embeddeddesignindia.com, March 2011. 2. Becker, Pete. Working Draft, Standard for Programming Language C++. ISO/IEC, February 2009.

For the most part, C code that defines and uses structures behaves the same when compiled and executed as C++. However, C++ generalizes structures into classes. A C++ class can have elements that a C structure cannot, such as access specifiers, member functions, static data members, and base classes. In my following blogs, I'll explain how some of these elements alter the physical layout of class objects. The C++ Standard says a lot about classes, but hardly anything about structures. C++ treats structures as just classes declared in a slightly different way. According to the C++ Standard, "A structure is a class defined with the struct ; its members and base classes ... are public by default." ii In a class defined with the keyword class , the members and bases are private by default. For example, in C++, the structure definition: struct widget { char m1; int m2; char m3; }; is actually equivalent to the class definition: class widget { public: char m1; int m2; char m3;} ; As a class, widget has the same size and alignment as it does as a structure. Each class member has the same size, allocation order, alignment and padding as it does in the structure. When compiled for a target machine in which each int occupies four bytes aligned to an address that's a multiple of four, the compiler will insert three bytes of padding after each of the char members, as if the class had been defined as: class widget { public: char m1; char padding_after_m1 ; int m2; char m3; char padding_after_m3 ; }; The keyword public is one of three possible access-specifiers, the others being private and protected . The access-specifiers themselves don't occupy any data storage. Non-virtual member functions don't occupy data storage either. (They do occupy code space.) Static data members do occupy data storage, but not in the objects of which they are members. Thus, adding either non-virtual member functions or static data members to a class doesn't alter the storage layout for objects of that class. For example, objects of a widget class defined as: class widget { public: widget(); // constructor ~widget(); // destructor char m1; int m2; char m3; static int k; // static data member }; have the same storage layout with or without these new members (the ones highlighted) . On the other hand, adding one or more virtual functions to a class that previously had none, as in: class widget { public: widget(); virtual ~widget(); // virtual destructor char m1; int m2; char m3; static int k;}; typically adds a hidden non-static data member of pointer type, called a vptr , thus increasing sizeof(widget) by the size of that pointer. The presence of the vptr has no impact on the size and alignment of any of the other data members, and typically no impact on the padding in the class. Adding a base class to a class that previously had none, as in: class widget: public gadget { public: widget(); virtual ~widget(); // virtual destructor char m1; int m2; char m3; static int k; }; effectively adds a hidden non-static data member of the base class type, called the base class sub-object , thus increasing sizeof(widget) by the size of a gadget plus any additional padding that may be needed. The C++ Standard says nothing about the placement of the base class sub-object and the vptr. Many compilers place the vptr at the beginning, followed by the base class sub-object and then the non-static data members. For example, the compiler might lay out the storage for objects of the derived widget class (just above) as if widget had been defined as: class widget { public: widget_vtable *vptr; gadget base_class_subobject; char m1; int m2; char m3; }; Others place the base class sub-object before the vptr. The compiler may insert padding as needed. If the gadget base class already has its own vptr, widget objects can use that vptr as their own, and the compiler can omit the allocation of a separate vptr in the widget itself. The classes in all of my examples thus far have only public members. C++ has additional rules governing the placement of members with different accessibility. Endnotes: 1. ISO/IEC Standard 14882:2003(E), Programming languages—C++.  

I once discussed Standard C's rules governing the alignment, padding and ordering of structure members. For the most part, C code that defines and uses structures behaves the same when compiled and executed as C++. However, C++ generalizes structures into classes. A C++ class can have elements that a C structure cannot, such as access specifiers, member functions, static data members, and base classes. In one of my blogs, I explained how some of these elements can alter the physical layout of class objects. 1 I'll soon expand my discussion of alignment, padding and member ordering to include access control. Access specifiers C++ class members can have different levels of accessibility:   - A public member of a class is accessible anywhere in the program where the class itself is visible and accessible. - A private member of a class is accessible only to members and friends of that class. - A protected member of a class is accessible only to members and friends of that class or to members and friends of classes derived from that class. For example, a class widget defined as: class widget { public: widget(); protected: ~widget(); private: char m1; int m2; char m3; static int k; }; has one public member function (a default constructor), one protected member function (a destructor), and four private data members (three non-static and one static). Each access-specifier can appear more than once, and in any order. For example, you could rewrite the previous definition for widget as: class widget { protected: ~widget(); private: char m1; int m2; private: char m3; static int k; public: widget(); }; Here the keyword private appears twice and the public member is at the end (rather than the beginning) of the class definition. These changes aren't likely to alter the size or alignment of widg et objects. Member allocation order Within a given C structure, the members have offsets that increase in the order in which they are declared. In C++, a structure is just a class in which the members (and base classes) are public by default. Thus, in a class with only public members, such as: class widget { public: widget(); ~widget(); char m1; int m2; char m3; static int k; }; compilers allocate storage within each widget object for the non-static data members m1 , m2 , and m3 in that order. As I explained bfore, the constructor, destructor and static data member k add no storage to each widget object. What about a class with private or protected members? The relevant words in the draft of the next C++ Standard differ somewhat from the words in the current (2003) C++ Standard. I believe the draft's words are a better description of current practice. The draft states, "Non-static data members of a ... class with the same access control are allocated so that later members have higher addresses within a class object." 2 Storage allocation for a class in which all non-static data members have the same access—all public, or all private, or all protected—behaves just like storage allocation in a C structure. For example, the storage layout for widget objects when widget is defined as: class widget { public: widget(); ~widget(); static int k; private: char m1; int m2; char m3; }; is the same as when widget is defined as: class widget { public: widget(); ~widget(); char m1; int m2; char m3; static int k; }; which is the same as when widget is defined as: struct widget { char m1; int m2; char m3; }; These different class definitions aren't functionally equivalent, but they yield objects with the same size, alignment and member arrangement. Freedom to rearrange things The draft Standard also states that "The order of allocation of non-static data members with different access control is unspecified." This means that, if it wishes, a compiler can allocate members with different accessibility to reduce or eliminate the need for padding. For example, suppose class widget is defined as: class widget { public: char m1; protected: int m2; private: char m3; }; When compiled for a target machine in which each int occupies four bytes aligned to an address that's a multiple of four, the compiler can allocate storage for the members in the order in which they're declared and insert padding as if the class were defined as: class widget { public: char m1; char padding_after_m1 ; protected: int m2; private: char m3; char padding_after_m3 ; }; This layout requires six bytes of padding. On the other hand, the compiler can reorder the members to reduce the need for padding bytes, as either: class widget { public: char m1; private: char m3; char padding ; protected: int m2; }; or as: class widget { protected: int m2; public: char m1; private: char m3; char padding ; }; Using either rearrangement eliminates four padding bytes and shrinks the size of each widget object by that much. A C++ compiler can reorder members with different access specifiers, but can't reorder members within the same access specifier. For example, given: class widget { public: char m1; int m2; private: char m3; }; the compiler can't reorder the members so that m2 is allocated before m1 , as in: class widget { public: int m2; char m1; private: char m3; }; However, it can reorder the members so that m3 is before both m1 and m2 , as in: class widget { private: char m3; public: char m1; char padding ; int m2; }; None of the compilers that I have appear to rearrange members this aggressively. At least, I haven't been able to discover compiler options that will trigger such optimizations. If you have a compiler that will do this, please let me know which compiler(s) and compile option(s) you used to obtain this optimization. Endnotes: 1. Saks, Dan. " Classes are structure, and then some ," Eetasia.com, March 2011. 2. Becker, Pete. Working Draft, Standard for Programming Language C++. ISO/IEC, February 2009.