DISCOVERY

September 24th, 2022

Understanding Data Alignment in Go

Go

C++

C

System Programming

Data alignment in operating systems is something I’ve been aware of throughout my young career, mostly thanks to my love for reading software engineering books. However, it’s not a concept that I’ve explored in depth. In this article, I’ll discuss the basics of data alignment and how it applies to programming languages like Go.

Data alignment feels like an intimidating topic since alignments differ depending on machine architectures and operating systems. However, data alignment is conceptually equivalent across these different architectures. High-level programming languages like Go abstract away much of the complexity as well, making data alignment something an application engineer rarely needs to worry about.

Data Alignment

Data alignment refers to how data is arranged in computer memory. Computer memory is a device used to store data for immediate use. Computer memory most likely refers to main memory, which in modern computers is Random Access Memory (RAM)1. CPUs perform optimally when data in memory is properly aligned2,3. In fact, many processors have requirements that force data in memory to be properly aligned, or so-called naturally aligned4.

For example, in a processor with a 32-bit architecture (a CPU with a 4 byte word size), data is naturally aligned if it exists at a location in memory that is a multiple of 325,6. For example, if an integer is stored at the 96th bit in memory within a 32-bit architecture, it is properly aligned because 96 / 32 == 3. Similarly, in a processor with a 64-bit architecture (a CPU with an 8 byte word size), data is naturally aligned if it exists at a location in memory that is a multiple of 64.

Naturally Aligned

Data is considered naturally aligned when it is stored at a memory address that is a multiple of its size. With regards to processors, word size is used to determine natural data alignment. However, in regards to programming language variables, the size of a data type is often used to determine the alignment of data. For example, in Go, a 16-bit integer (of type int16) should be aligned in memory at a location that is a multiple of 16 to be naturally aligned.

In languages with manual memory management, for example, C and C++, functions to allocate memory such as malloc() and calloc() are guaranteed to properly align the memory space that they return4. Manual memory management is when memory needs to be explicitly managed by a programmer throughout its lifecycle, from creation to garbage collection7. Since Go is a programming language with automatic memory management (it automatically allocates memory using new() or make() and automatically garbage collects unused memory), instances where data alignment is top of mind for engineers are infrequent.

Go has three functions for finding the size and alignment of data: unsafe.Sizeof(), unsafe.Alignof(), and unsafe.Offsetof(). unsafe.Sizeof() returns the size of a variable's data type and unsafe.Alignof() returns the proper alignment of a variable’s data type. unsafe.Offsetof() is used specifically for struct fields to determine the offset of a field's memory location within a struct.

The value returned by unsafe.Sizeof() can be machine dependent. For types such as booleans, the return value is always 1, representing one byte8. However, for other data types, such as integers, strings, arrays, etc., the return value is dependent on the word size of a computer's CPU architecture.

// Bool // Return value: 1 unsafe.Sizeof(false) // int (on a 64-bit processor) // Return value: 8 unsafe.Sizeof(1) // string (on a 64-bit processor) // Return value: 16 unsafe.Sizeof("Andy") // []T (array) (on a 64-bit processor) // Return value: 24 unsafe.Sizeof([]string{})

On a 64-bit architecture, the word size is 8 bytes. That means that integers, strings, and arrays have sizes of 1 word, 2 words, and 3 words, respectively. Sizes represent the fixed size of a data type, so the return value of unsafe.Sizeof() is consistent no matter how long a string is or how many elements an array contains. For basic types like bool and int, unsafe.Alignof() returns the same value as unsafe.Sizeof(). For more complex types like string and []T, unsafe.Alignof() returns the CPU word size in bytes.

// Bool // Return value: 1 unsafe.Alignof(false) // int (on a 64-bit processor) // Return value: 8 unsafe.Alignof(1) // string (on a 64-bit processor) // Return value: 8 unsafe.Alignof("Andy") // []T (array) (on a 64-bit processor) // Return value: 8 unsafe.Alignof([]string{})

unsafe.Alignof() returns the necessary data alignment for its argument’s type. Therefore, it makes sense that larger types return the word size of the computer processor, which is equal to the natural alignment in memory.

Things get a bit more interesting for data types whose size is less than the word size of a computer’s architecture. Data types such as bool, whose size is one byte, still must be naturally aligned in memory (its location in memory must be a multiple of the word size, such as 8-bytes on a 64-bit architecture). To achieve this, padding is added after the data type in memory to keep it aligned9. In the case of bool on a 64-bit machine, one byte is used to store the data and the next seven bytes are padding.

If a boolean actually takes up a full word size in memory, why do unsafe.Sizeof() and unsafe.Alignof() return 1? The answer is because within a struct, it is possible to "pack" data such that multiple pieces of data are stored within a single word size worth of memory10. Data packing is commonly used to save space in a data structure. The side effect of data structure packing is the order in which struct fields are defined can alter the amount of memory a struct requires.

Let’s look at an example. The following two structs appear to be equivalent, since they have the same fields defined in a different order.

type Sample1 struct { a bool b bool c float64 } type Sample2 struct { a bool c float64 b bool }

However, calling unsafe.Sizeof() on these structs reveals their sizes are different in memory.

one := Sample1{a: true, b: true, c: 1.0} two := Sample2{a: true, b: true, c: 1.0} // Return value (on a 64-bit processor): 16 unsafe.Sizeof(one) // Return value (on a 64-bit processor): 24 unsafe.Sizeof(two)

While Sample1 creates a struct the size of two words (16 bytes), Sample2 creates a struct the size of three words (24 bytes). This is the result of extra padding needed in Sample2 due to the field order in the struct definition.

The first two fields in Sample1, a and b, are type bool. Since the size and alignment of bool is one, both a and b can be packed together into a single word in memory. This means the first eight bytes of memory for a struct of type Sample1 consists of a and b in the first two bytes followed by six bytes of padding. The third field in Sample1, c, is a float64, which takes up a full eight bytes on a 64-bit machine. In total, the struct takes up 16 bytes (2 words).

Next, let's take the case of Sample2. The first field in Sample2, a, is a bool that is placed in the first byte of memory for the struct. Since the second field is c, a float64 that takes up a full eight bytes, seven bytes of padding are added after a. The third field is b, which takes up one byte followed by another seven bytes of padding. In total, the struct takes up 24 bytes (3 words).

Luckily for application engineers, outside of field packing in structs, data alignment in memory is not a concern that arises when writing Go programs. The code examples I showed above can be viewed in more detail in my go-programming repository, specifically within sizeof_test.go and alignment_offset_test.go.

As I mentioned previously, C and C++ are programming languages with manual memory management, and standard library functions such as malloc() and calloc() are guaranteed to properly align allocated memory. Similar to Go, structs are a common instance where data alignment impacts application code. The struct example I showed in Go with two structs, Sample1 and Sample2, is implemented in C and C++ below.

#include <stdbool.h> #include <assert.h> #include <stdio.h> struct Sample1 { bool a; bool b; double c; }; struct Sample2 { bool a; double c; bool b; }; int main() { struct Sample1 first = {true, false, 1.0}; struct Sample2 second = {true, 1.0, false}; // Return value (on a 64-bit processor): 16 sizeof(first); // Return value (on a 64-bit processor): 24 sizeof(second); }
#include <cassert> #include <iostream> using namespace std; struct Sample1 { bool a; bool b; double c; }; struct Sample2 { bool a; double c; bool b; }; int main() { auto first = Sample1{true, false, 1.0}; auto second = Sample2{true, 1.0, false}; // Return value (on a 64-bit processor): 16 sizeof(first); // Return value (on a 64-bit processor): 24 sizeof(second); }

Just like Go, an instance of Sample1 takes up two word sizes of memory while Sample2 takes up three word sizes of memory. These code samples are available in my cpp-c-programming repository, within data_alignment.c and data_alignment.cpp files, respectively.

While writing system programs, specifically in Linux, an engineer has a bit more control over how allocated memory is aligned. POSIX defines a function posix_memalign() which allocates memory and aligns it at a multiple of its second argument11,12. The first argument of posix_memalign() is a pointer that will point to the allocated memory and the third (and final) argument is the number of bytes to allocate in memory. The example below allocates 1024 bytes of memory and aligns it at a multiple of eight. It frees the newly allocated memory before using it by invoking free(buf).

char *buf; // Allocate 1024 bytes of memory aligned at a multiple of 8. int ret = posix_memalign(&buf, 8, 1024); if (ret) { perror("posix_memalign"); return -1; } free(buf);

Although I aligned the allocated memory on the 64-bit architecture page size (8 bytes) above, any value that is a multiple of two and a multiple of sizeof(void *) can be used. On a 64-bit architecture, sizeof(void *) likely returns 8 (the page size). The full code example is available in an alignment.c file and is based on my reading of Linux System Programming by Robert Love.

Although data alignment may not be top of mind for application engineers, it is important to understand how it works and its impact on high-level programming languages. In general, knowing low-level operating system functionality helps engineers write better programs in high-level languages, just as knowing data structures and algorithms helps write faster and less memory intensive code. All the code discussed in this article is available in my go-programming, system-programming-prototypes, and cpp-c-programming repositories.

[1] "Computer memory", https://en.wikipedia.org/wiki/Computer_memory

[2] "Data structure alignment", https://en.wikipedia.org/wiki/Data_structure_alignment

[3] Alan A. A. Donovan & Brian W. Kernighan, The Go Programming Language (New York, NY: Addison-Wesley, 2016), 354

[4] Robert Love, Linux System Programming, 2nd ed (Sebastopol, CA: O'Reilly, 2013), 303

[5] "Words in Computer Architecture", https://learn.saylor.org/mod/page/view.php?id=18960

[6] "Data Alignment", http://books.gigatux.nl/mirror/kerneldevelopment/0672327201/ch19lev1sec3.html

[7] "Manual memory management", https://en.wikipedia.org/wiki/Manual_memory_management

[8] Donovan., 355

[9] "Why does a bool appear to take up as much memory as an int? C++", https://stackoverflow.com/a/20116948

[10] "Data structure alignment: Data structure padding", https://en.wikipedia.org/wiki/Data_structure_alignment#Data_structure_padding

[11] Love., 304

[12] "posix_memalign(3) — Linux manual page", https://man7.org/linux/man-pages/man3/posix_memalign.3.html