s we all know, premature optimization is considered evil as it often entails eventually useless design complications and portability compromises. However, this doesn’t mean that healthy programming habits should be completely ignored, especially when they are free of charge. This month’s solution shows you an effective and simple technique that will help optimize the layout of your data structures (classes, structs, and unions) without sacrificing performance or incurring any design compromises. This technique is particularly useful in applications that manipulate a large number of objects, for example databases, CAD tools, directory services, graphical editors, and financial systems. It is also useful in memory-challenged environments such as embedded systems and mobile devices.

How to pack data members optimally so that memory isn’t wasted and speed isn’t lost?

Organize data members in a way that minimizes the amount of padding bytes inserted between them.

At Sixes and Sevens
Suppose you’re writing a pay-per-program app that accepts users’ requests to listen to a certain radio program. Each request is represented as a struct that contains the following data members:

struct Broadcast{ char timezone; // 'Z' for Zulu, etc. int frequency; //88000000 for 88FM short timeofday; //e.g., 1530};

On a typical 32-bit system, the individual sizes of these members are:

sizeof(timezone)==1;sizeof(frequency)==4;sizeof(timeofday)==2;--------------------Total:            7

Many programmers don’t know that size of Broadcast isn’t necessarily equivalent to the sum of these values. In other words,

sizeof (Broadcast);

Is often larger than:

sizeof(timezone)+sizeof(frequency)+sizeof(timeofday)

There are two reasons for this. First, compilers usually round up a data structure’s size to make it divisible by 2, 4, or 8?depending on the hardware’s memory alignment requirements. Secondly, compilers insert padding bytes between data members to ensure that each member’s address is properly aligned. The problem is that when members are declared in a random order, the compiler may need to insert more padding bytes between them, thereby inflating the data structure’s size. This is why in C++ Builder, for example, struct Broadcast occupies 12 bytes rather than 8. Your compiler is likely to produce a similar result (try it!). Clearly, space is wasted here. This waste is particularly noticeable when you create a large array of Broadcast objects.

Brute Force Downsizing
It’s tempting to play with your compiler’s settings to force a more stringent alignment policy. You can either use a #pragma directive for this purpose or modify the appropriate command line option. In C++ Builder, you do it like this: go to Project?>Options… In the Advanced Compiler tab, change the Data Alignment value to Byte or Word (as seen in Figure 1).

Figure 1. The image shows C++ Builder’s data alignment setting.

This will cause the size of Broadcast to shrink to 7 or 8 bytes, respectively. It’s too early to celebrate, though. Forcing a struct to align on a byte boundary severely compromises portability; some compilers and operating systems won’t run such code. Even if your platform tolerates this and you’re not aiming at cross-platform development, this workaround is still problematic because you have to make sure that all source file and headers are compiled with the same configuration. Failing to do so will cause incompatible binary layout among different .obj files leading to unpredictable behavior at runtime. Even if you recompile and re-link your entire project with this setting, your program might exhibit a speed penalty. Sounds bad, doesn’t it? What if I told you that you can optimize members’ layout without resorting to compiler-dependent hacks and more importantly?without sacrificing speed?

Member Reordering
When a data structure contains members whose total size is odd, it’s best to let the compiler round the size up. In the case of Broadcast, letting the compiler round its size from 7 to 8 bytes is acceptable. However, because of the random order in which data members are declared, the size of Broadcast is further augmented to 12. This isn’t acceptable. It’s this leap from 8 to 12 bytes that you wish to avert. To help the compiler out, ensure that members whose size is smaller than the default alignment unit (4 bytes in this example, or sizeof(int) in general) are adjacent. This is like laying out Lego bricks: instead of using one large brick, place two small bricks together. Let’s look at the current inefficient memory layout of Broadcast’s members:

• timezone: occupies one byte for itself and three additional padding bytes
• frequency: occupies four bytes for itself
• timeofday: occupies two bytes for itself, two for padding

The three padding bytes inserted after timezone are large enough to accommodate timeofday. Reorganizing Broadcast like this:

struct Broadcast{ char timezone; //hasn't moved short timeofday; //originally was #3 int frequency; //originally was # 2};

reduces its size to 8 bytes! The members are now aligned as follows:

• timezone: occupies one byte for itself and one padding byte
• timeofday: occupies two bytes for itself
• frequency: occupies four bytes for itself

In terms of alignment, the compiler treats timezone and timeofday as a single member that occupies four bytes (including one padding byte). Notice that this size reduction is achieved without compromising design or tampering with the compiler’s setting. Of course, this technique is applicable to all data structures, including classes and unions. The more data members a data structure has, the more space you can save by reordering them. Consider the following class:

class Page{private:  bool swappable; //1 byte + 3 for padding void * address; //4 bytes short page_size; //2 bytes + 2 for padding int bytesused; //4 bytes bool readonly; //1 byte + 3for padding//..member functions};

The result of summing each member’s size is 12 bytes. However, sizeof(Page) is actually 20, which means that 8 bytes, or almost half of this class’s size, are wasted as padding bytes. Now, try to group members that occupy less than 4 bytes together:

class OptimizedPage{private://the following 3 members make exactly one alignment unit bool swappable; //1 byte bool readonly; //1 byte short page_size; //2 bytes//each of the following 2 fits into one alignment unit void * address; //4 bytes int bytesused; //4 bytes};

This way, no padding bytes are required because the first three members fit exactly into an alignment unit. As a result, sizeof(OptimizedPage) is now reduced to 12.

Sizing Up
Code optimization usually boils down to rewriting heavily-used functions and poking into the generated assembly code. However, the member reordering technique shown here is one of the few optimizations that are simple and hassle-free. In memory-challenged systems, it should become a natural programming habit that will pay off very quickly. Even in desktop applications and server processes, it can be useful.