Please consider a donation to the Higher Intellect project. See https://preterhuman.net/donate.php or the Donate to Higher Intellect page for more info. |
Chiropractic for Your Misaligned Data
by Kevin Looney and Craig Anderson
Misalignment occurs when a program accesses data in a way that's not in sync with the processor's internal paths. This can slow down performance a little or a lot, depending on the CPU architecture. But finding these areas in code can be very difficult. We'll demonstrate the cause and cost of alignment problems and then show you a couple of tools you can use to detect them in your programs.
Sometimes Macintosh application performance is limited by architectural factors that can't be remedied, like the raw speed of the I/O or memory subsystem. But the programmer does have control over some factors that affect the speed of the memory subsystem and thus application performance -- such as how data is aligned and accessed within memory. By default, most compilers will do the appropriate alignment for PowerPC code. However, alignment options offered for backward compatibility with the 680x0 architecture can cause significant overhead.
Misalignment is a difficult performance problem to detect. Traditional debugging and performance tools typically don't help you find misaligned accesses. On top of this, misalignment problems manifest themselves differently on different CPU architectures.
In this article, we'll define misalignment, describe how it's caused, discuss the overhead penalties for accessing misaligned data on various microprocessors, and introduce some tools designed to aid in the detection of misaligned accesses in code. These tools accompany the article on this issue's CD and develop's Web site. Armed with these tools and what you learn in this article, you can perform chiropractic adjustments on your programs to solve their data alignment problems.
WHAT IS MISALIGNMENT AND WHY SHOULD I CARE?
A piece of data is properly aligned when it resides at a memory address that a processor can access efficiently. If it doesn't reside at such an address, it's said to be misaligned. In the PowerPC architecture, 32-bit and 64-bit floating-point numbers are misaligned when they reside at addresses not divisible by 4. Misalignment exceptions are taken based on the specific microprocessor.
Whether a data item is aligned depends not only on its address and the processor that's performing the access, but also on the size of the item. In general, data of size s is aligned if the least significant n bits of its address are 0, where n = log2(s). Hence, 1-byte items are always aligned, while 2-byte items are aligned on even addresses and 4-byte items are aligned if the address is evenly divisible by 4. This alignment policy is often called natural alignment and is the recommended data alignment for code to run well on all current and future PowerPC processors.
Accessing misaligned data can be quite costly, depending on the microprocessor your program is running on. We'll demonstrate just how costly in a minute, but in general, misaligned memory accesses take from 2 to 80 times longer than aligned accesses on 603, 604, and future PowerPC microprocessors. A misaligned access can require more time to perform for two reasons:
- It may require two requests to the memory system instead of just one.
- It may cause the processor to take an unaligned access exception, a costly penalty.
WHAT CAUSES MISALIGNMENT?
Misaligned accesses can involve variables located on the stack or on the heap. The type of compiler and the compiler settings that you use will determine whether misaligned accesses occur. Improper structure placement and incorrect pointer arithmetic can also cause misaligned accesses. These problems can be found with the tools and techniques described below, but this article generally focuses on alignment problems that aren't caused by programmatic errors.
Most compilers for the Macintosh allow you to choose among various alignment options. Some compilers default to 2-byte alignment so that data alignment in PowerPC code mimics alignment on the 680x0 processor. While using this option means that structures written to disk in binary format can be accessed easily by both architectures, it also permits alignment problems in the PowerPC architecture. Both improper structure padding and misaligned stack parameters can result in misaligned accesses.
IMPROPER STRUCTURE PADDING
When a float field occurs in a structure, improper padding by the compiler will cause the float field to be misaligned. The example in Listing 1 uses MPW's
alignment pragmas to illustrate this.
Listing 1. An example of a poorly aligned structure
#pragma options align=mac68k typedef struct sPoorlyAlignedStruct { char fCharField; float fFloatField; char fSecondCharField; } sPoorlyAlignedStruct; sPoorlyAlignedStruct gPoorlyAlignedStruct; #pragma options align=reset
In this example, a compiler that did no padding would align fFloatField on an offset of one byte from the structure's base address. Since compilers (and memory allocators) usually align the base of a structure on a boundary of at least four bytes (and multiples of four bytes), every access to fFloatField will cause a misalignment error. Also, fFloatField will be misaligned in statically or dynamically allocated arrays, since the lengths of structures are padded so that each structure that's an array element starts on a 4-byte aligned address.
A compiler with a 2-byte padding setting would align fFloatField on an even address, but this would still cause misalignment when that address isn't divisible by 4. Compilers using the mac68k pragma (as shown in Listing 1) cause 2-byte alignment, putting fFloatField on an even but often misaligned address for PowerPC processors.
A compiler with a 4-byte padding setting would always align the field properly.
MISALIGNED STACK PARAMETERS
Besides affecting the alignment of data in a structure, compiler settings can affect the way data structures are placed on the stack. Consider this function declaration:
void FunctionFoo (sPoorlyAlignedStruct firstParam, float floatParam)
In this example, the parameters are placed on the stack (even though PowerPC compilers use registers if possible). A compiler using a 680x0 2-byte padding option may align firstParam.fFloatField on an even address, but if the address isn't divisible by 4 this will cause a misalignment every time that parameter field is accessed within FunctionFoo. It won't, however, change the alignment
of other parameters on the stack.
On the PowerPC processor, nonstructure parameters are usually placed in registers. There are no alignment problems when accessing registers.
THE COST OF MISALIGNMENTS
To demonstrate the cost of misalignments, we've written the code in Listing 2, which generates both aligned and misaligned accesses in the course of a million iterations. It accesses a byte array in different ways -- data writes of integers, floats, and doubles -- and at different offsets. In a portion of the code not shown, accesses are confined to within a single page of memory, and interrupts are turned off. Running this code enabled us to calculate the difference in performance between aligned and misaligned accesses. This code (with slight modifications for the various compilers) was compiled with the
Symantec, MrC, and Metrowerks compilers. All compilers behaved similarly.
Listing 2. Generating accesses for comparison of access time
#define kNumAccessesPerCycle 200 #define kNumCycles 5000 // Number of total accesses = kNumAccessesPerCycle * kNumCycles // 1000000 = 200 * 5000 #define kTableSize 1608 // Table size needed for 200 separate aligned // accesses on the largest data type (doubles) typedef enum ECType { eLong, eFloat, eDouble }; void main(void) { double AlignedTimeFloat = AlignLoop(0, eFloat); double Misaligned1TimeFloat = AlignLoop(1, eFloat); double Overhead1Float = (((Misaligned1TimeFloat - AlignedTimeFloat) * 100) / AlignedTimeFloat); double avgOverhead1Float = (Misaligned1TimeFloat - AlignedTimeFloat) / kNumTotalAccesses; ... } // The function AlignLoop measures the time of a loop of "writes" to a // byte array. The writes are either aligned or misaligned, based on the // offset parameter, which should be between 0 and 7. The type should be // eLong, eFloat, or eDouble. double AlignLoop(short offset, ECType type) { UnsignedWide startTime, stopTime; double start, stop; char bytetable[kTableSize]; long j, k; // Get starting timestamp. Microseconds(&startTime); switch (type) { case eLong: { long *longPtr = (long *) &bytetable[offset]; for (j = 0; j < kNumCycles; j++) for (k = 0; k < kNumAccessesPerCycle; k++) longPtr[k] = 1; } break; case eFloat: { float *floatPtr = (float *) &bytetable[offset]; for (j = 0; j < kNumCycles; j++) for (k = 0; k < kNumAccessesPerCycle; k++) floatPtr[k] = 1.0; } break; case eDouble: { double *doublePtr = (double *) &bytetable[offset]; for (j = 0; j < kNumCycles; j++) for (k = 0; k < kNumAccessesPerCycle; k++) doublePtr[k] = 1.0; } break; } // Get ending timestamp. Microseconds(&stopTime); // Move the values to doubles. start = (((double) ULONG_MAX + 1) * startTime.hi) + startTime.lo; stop = (((double) ULONG_MAX + 1) * stopTime.hi) + stopTime.lo; return stop - start; }
Table 1 shows the results. Overhead is calculated as the percentage difference between the time required for aligned and misaligned accesses. Our experiments showed that misaligned accesses at different offsets seemed to pay the same penalty (excluding cases where the two accesses required to retrieve the data straddle a memory page boundary, which is every 4K of memory).
Table 1. Misalignment overhead for basic data types, native PowerPC code
CPU and data | Aligned total access time (usec) | Misaligned total access time (usec) | Overhead |
PowerPC 601 integers | 113439 | 119573 | 5.4% |
PowerPC 601 floats | 63234 | 94505 | 50.0% |
PowerPC 601 doubles | 63251 | 113306 | 79.1% |
PowerPC 604 integers | 687 | 695 | 1.1% |
PowerPC 604 floats | 261 | 23753 | 9009.0% |
PowerPC 604 doubles | 262 | 22546 | 8509.5% |
Note: Tests were run at 80 MHz on the PowerPC 601 and 132 MHz on the PowerPC
604.
Misaligned integer accesses result in a relatively small penalty for PowerPC 601, 603, and 604 CPUs. However, there's no guarantee that future microprocessors will provide hardware support for integer misalignment. Floating-point misalignments are severely penalized by the 604 implementation. In fact, while a misaligned access takes 1.5 times as long as an aligned access on the 601, it takes more than 80 times as long as an aligned access on the 604. The 601 pays a penalty only when an access crosses a page boundary (this will be verified later). Misaligned accesses to doubles on a 601 result in nearly double the overhead of misaligned accesses to floats. On the 604, however, doubles and floats suffer nearly the same overhead penalty. Misaligned accesses for doubles occur on any address not divisible by 8 on the 601, and any address not divisible by 4 on the 604. It's important to note that all memory accesses (aligned and misaligned) result in some timing penalty.
When we ran these experiments as emulated code (compiled for 680x0), float and double accesses showed no significant overhead (less than 8%). The 68040LC emulator doesn't do PowerPC floating-point loads/stores when processing floating-point data; it avoids alignment exceptions by doing integer emulation of a floating-point unit and loading and storing data 16 bits at a time.
Our code paints a worst-case scenario; worst case or not, the results indicate that there's plenty of motivation to avoid misaligned accesses in native PowerPC code. Perhaps the biggest problem facing the programmer, however, is the detection of these problems in application code. We'll look now at two tools that are useful for detecting and pinpointing alignment problems.
TOOLS FOR DETECTING MISALIGNMENTS
Apple's Performance Evaluation Group has developed two tools for detecting misalignments that cause exceptions:
- PPCInfoSampler, a tool to detect high levels of misalignment exceptions over general application workloads
- the Misalignment Instrument Library (MIL), a set of functions useful for profiling misalignments in specific regions of code
PPCInfoSampler is useful for determining whether your code has misalignment problems. If misaligned accesses are detected, the MIL can be used to pinpoint which parts of your code are causing the misalignments. We'll describe each tool in greater
detail before discussing how to correct misalignments that you identify.
PPCINFOSAMPLER
PPCInfoSampler is a control panel that when activated records information about the PowerPC exception services and emulator at 100-millisecond intervals. The information recorded includes counts of mode switches, interrupts, misalignment exceptions, and page faults. See Table 2 for a list of PPCInfoSampler output categories. The output saved from PPCInfoSampler is in tab-delimited format and
is best viewed from a spreadsheet program.
Table 2. PPCInfoSampler output categories
Output category | Explanation |
Time Delta (millis) | Elapsed milliseconds since last sample of "exception services" registers |
Microseconds time | Microseconds (calculated from timebase) since PPCInfoSampler was enabled |
Timebase Ticks | A reading of the 64-bit timebase register |
MixedMode switches | Number of mode switches into PowerPC code |
Data Page Faults | Number of page faults |
ExternalIntCount | Number of external processor interrupts |
MisalignmentCount | Number of misaligned accesses that caused an exception |
FPUReloadCount | Number of reloads of the FPU register state |
DecrementerIntCount | Number of interrupts caused by the PowerPC decrementer register |
EmulatedUnimpInstCount | Number of instructions that are emulated in exception services |
Timebase Ticks 68k | Number of timebase ticks spent in 680x0 code |
Timebase Ticks PPC | Number of timebase ticks spent in PowerPC code |
Level n Int Ticks | Number of timebase ticks that expired per interrupt level |
Level n interrupts | Number of interrupts that occurred at each interrupt level |
Note: With the exception of microseconds time, each measurement is per sample
and isn't cumulative with the next interval.
To use PPCInfoSampler, you must first drop it into your Control Panels folder and reboot. The tool installs code in the system heap that waits for an action to occur. There are two ways to activate the sampling mechanism:
- You can use the keyboard shortcut Command-Option-Z to start the sampler instantly at any time. When you start the sampler, an 8-pixel line will flash in the upper left corner of your main screen. It will continue to flash for each sample that's recorded. To stop the sampler, use the keyboard shortcut again.
- You can use the control panel interface, as shown in Figure 1, to start, stop, and save a sample.
Figure 1. PPCInfoSampler control panel interface
For our purposes, let's focus on the number of misalignment exceptions. To determine in general whether you have misalignment problems in your application, think of the operations or "workloads" (such as saving to disk) that force your application to access many data structures. Run PPCInfoSampler during these workloads to determine whether any misalignments are occurring. Any misalignment count greater than 0 should be investigated and, if possible, corrected.
Table 3 shows an example of a misalignment count generated by PPCInfoSampler. The program that was being executed during this count displayed bursty misalignment characteristics. That is, during some 100-millisecond intervals no misalignments were happening; during other intervals, large numbers were happening.
Table 3. Sample output from PPCInfoSampler
Milliseconds | Misalignment count |
100 | 0 |
100 | 0 |
100 | 11652 |
100 | 43694 |
100 | 42931 |
100 | 43695 |
100 | 43679 |
100 | 43705 |
100 | 42942 |
100 | 31213 |
100 | 0 |
100 | 0 |
100 | 0 |
100 | 14510 |
100 | 44135 |
100 | 44667 |
100 | 44470 |
100 | 44347 |
100 | 44323 |
100 | 44303 |
100 | 6416 |
100 | 0 |
100 | 0 |
THE MISALIGNMENT INSTRUMENT LIBRARY
Where PPCInfoSampler allows you to detect misalignment activity in broad 100-millisecond intervals, the Misalignment Instrument Library (MIL) allows you to then make educated guesses about where to further instrument your code to pinpoint where the misalignment is happening. The MIL consists of two routines:
void initMisalignRegs(void); // Initializes our misalignment // counter (do this only once) unsigned long getMisalignments(void); // Returns the total number of // misalignment exceptions since // the initMisalignRegs call
With these calls to the MIL, you can profile strategic portions of your source for the application's workloads. Iteratively narrow the focus of your profile by moving the instrumentation in the code until you can determine where the
misaligned accesses are and the structures that they're associated with.
Listing 3 is a sample of application code instrumented with the MIL calls. In this sample, we use the MIL to display the different floating-point exception-handling properties of the 601 and 604 CPUs.
Listing 3. Sample application code using the MIL
#define kNumAccessesPerCycle 200 #define kNumCycles 5000 #define kTableSize 804 // Table size needed for 200 separate aligned // accesses on the largest data type (floats) unsigned long gNumberOfMisalignments = 0; // Misalignments forced by // program unsigned long gReportedMisalignments = 0; // Misalignments reported // by exception services void main(void) { float MisalignedTime = misalignLoop(false); printf(">*> Forced number of misalignments: %d\n", gNumberOfMisalignments); printf(">*> Reported number of misalignments: %d\n", gReportedMisalignments); } // The function misalignLoop measures the time of a loop of "writes" to // a byte array. The writes are either aligned or misaligned, based on // the align parameter. double misalignLoop(boolean align) { UnsignedWide startTime, stopTime; float start, stop; short alignIndex = (align)?0:1; // · MIL instrumentation code: initialize misalignment counter. initMisalignRegs(); // Get starting timestamp. Microseconds(&startTime); for (long j = 0; j < kNumCycles; j++) { char bytetable[kTableSize]; float *floatPtr = (float *) &bytetable[alignIndex]; for (long k = 0; k < kNumAccessesPerCycle; k++) { gNumberOfMisalignments++; floatPtr[k] = 1; } } // Get ending timestamp. Microseconds(&stopTime); // · MIL instrumentation code: get number of misalignments. gReportedMisalignments = getMisalignments(); // Move the values to doubles. start = (((double) ULONG_MAX + 1) * startTime.hi) + startTime.lo; stop = (((double) ULONG_MAX + 1) * stopTime.hi) + stopTime.lo; return stop - start; }
The results of running this code are shown in Table 4. There's a large discrepancy between the number of misalignments generated and the number reported by the MIL on the 601. The 601 architecture internally fixes float and double misalignments in hardware. However, the 601 can't fix misalignments across page boundaries, so it takes a misalignment exception. Thus, only those page boundary cases are reported. The 603/604 architecture doesn't handle misalignments in hardware, and it takes an exception in all cases.
Table 4. Number of misalignments generated and reported
CPU | Number of misalignments | Reported number of misalignments |
PowerPC 601 | 1000000 | 120 |
PowerPC 604 | 1000000 | 1000000 |
NOW FOR THE CHIROPRACTIC ADJUSTMENTS
You've determined with the help of PPCInfoSampler that you have misalignment problems in your application. You've used the MIL to determine where the misaligned accesses are and the structures that they're associated with. Now
it's time to think about these structures.
Is there a reason why they can't be naturally aligned (as we described early in the article)? If there are structures in the parameter block passed to a Toolbox call, fields within these structures may not naturally align, but this is something the programmer can't do much about until the system provides an alternate API. Perhaps there are binary data files created and accessed from 680x0 legacy code. Is it really necessary to still be supporting data files formatted to 2-byte alignment? Can you provide a version mechanism for your data files, such that newer versions write and read to natural PowerPC alignment? Ask these questions, and naturally align structures as much as possible.
You can ensure proper structure alignment by ordering the fields in your structures by hand, from largest to smallest, instead of relying on a compiler to pad the fields. This will require you to do more work but will remove reliance on any particular padding strategy.
Another possible scenario is the case where data files are shared across multiple platforms. Alignment strategies on Intel and other x86 processors aren't the same as on PowerPC processors. There are two possible approaches to this scenario, given an application on Windows and one on the Mac OS that share the same data files:
- Try compiling structures on the Windows application with 4-byte alignment, according to PowerPC natural alignment. This is a "least common denominator" approach.
- If rebuilding a Windows application isn't a viable option, load the data from disk and convert the data structures to an aligned structure that's used internally. The performance tradeoff depends on how often the misaligned structure is used.
IT'S THAT SIMPLE
Misaligned memory accesses can take a real toll on your application's performance, requiring from 2 to 80 times longer than aligned accesses on newer PowerPC CPUs. If you do what we've described in this article, you can detect and pinpoint misalignments and fix them so that your code will run efficiently now and on future processors (which won't include hardware to fix misaligned accesses for any misaligned data type) and won't be penalized by the lack of hardware support in future implementations of PowerPC architecture. Isn't it worth a few simple adjustments now to know that your code's future is secure?