Alignment, Collection Rules, and Signed Integers

Previous

Caching, File I/O

Next

Lecture 8: Signed Integers, Storage hierarchy, and Caching #

Signed number representation #

Why are we covering this?

Debugging computer systems often require you to look at memory dumps and understand what the contents of memory mean. Signed numbers have a non-obvious representation (they will appear as very large hexadecimal values), and learning how the computer interprets hexadecimal bytes as negative numbers will help you understand better what is in memory and whether that data is what you expect. Moreover, arithmetic on signed numbers can trigger undefined behavior in non-intuitive ways; this demonstrates an instance of undefined behavior unrelated to memory access!

Recall from prior lectures that our computers use a little endian number representation. This makes reading the values of pointers and integers from memory dumps (like those produced by our hexdump() function) more difficult, but it is how things work.

Using position notation on bytes allows us to represent unsigned numbers very well: the higher the byte’s position in the number, the greater its value. You may have wondered how we can represent negative, signed numbers in this system, however. The answer is a representation called two’s complement, which is what the x86-64 architecture (and most other architectures) use.

Two’s complement strikes most people as weird when they first encounter it, but there is an intuition for it. The best way to think about it is that adding 1 to -1 should produce 0. The representation of 1 in a 4-byte integer is 0x0000'0001 (N.B.: for clarity for humans, I’m using big endian notation here; on the machine, this will be laid out as 0x0100'0000). What number, when ad ded to this representation, yields 0?

The answer is 0xffff'ffff, the largest representable integer in 4 bytes. If we add 1 to it, we flip each bit from f to 0 and carry a one, which flips the next bit in turn. At the end, we have:

   0x0000'0001
 + 0xffff'ffff
--------------
 0x1'0000'0000 == 0x0000'0000 (mod 2^32)

The computer simply throws away the carried 1 at the top, since it’s outside the 4-byte width of the integer, and we end up with zero, since all arithmetic on fixed-size integers is modulo their size (here, 16⁴ = 2³²). You can see this in action in signed-int.c.

More generally, in two’s complement arithmetic, we always have -x + x = 0, so a negative number added to its positive complement yields zero. The principle that makes this possible is that -x corresponds to positive x, with all bits flipped (written ~x) and 1 added. In other words, -x = ~x + 1.

Signed numbers split their range in half, with half representing negative numbers and the other half representing 0 and positive numbers. For example, a signed char can represent numbers -128 to 127 inclusive (the positive range is one smaller because it also includes 0). The most significant bit acts as a sign bit, so all signed numbers whose top bit is set to 1 are negative. Consequently, the largest positive value of a signed char is 0x7f (binary 0111'1111), and the largest-magnitude negative value is 0x80 (binary 1000'0000), representing -128. The number -1 corresponds to 0xff (binary 1111'1111), so that adding 1 to it yields zero (modulo 2⁸).

Two’s complement representation has some nice properties for building hardware: for example, the processor can use the same circuits for addition and subtraction of signed and unsigned numbers. On the downside, however, two’s complement representation also has a nasty property: arithmetic overflow on signed numbers is undefined behavior.

Integer overflow #

Arithmetic overflow on signed integers is undefined behavior! To demonstrate this, let’s look at ubexplore.c. This program takes its first argument, converts it to an integer, and then adds 1 to it. It also calls a function called check_signed_increment, which uses an assertion to check that the result of adding 1 to x (the function’s argument) is indeed greater than x. Intuitively, this should always be true from a mathematical standpoint. But in two’s complement arithmetic, it’s not always true: consider what happens if I pass 0x7fff'ffff (the largest positive signed int) to the program. Adding 1 to this value turns it into 0x8000'0000, which is the smallest negative number representable in a signed integer! So the assertion should fail in that case.

With compiler optimizations turned off, this is indeed what happens. But since undefined behavior allows the compiler to do whatever it wants, the optimizer decides to just remove the assertion in the optimized version of the code! This is perfectly legal, because C compilers assume that programmers never write code that triggers undefined behavior, and certainly that programmers never rely on a specific behavior of code that is undefined behavior (it’s undefined, after all).

Perhaps confusingly, arithmetic overflow on unsigned numbers does not constitute undefined behavior. It still best avoided, of course :)

The good news is that there is a handy sanitizer tool that helps you detect undefined behavior such as arithmetic overflow on signed numbers. The tool is called UBSan, and you can add it to your program by passing the -fsanitize=undefined flag when you compile.

And just to mess with you and demonstrate that arithmetic overflow on signed integers produces confusing results not only with compiler optimizations enabled, let’s look at ubexplore2.c. This program runs a for loop to print the numbers between its first and second argument. ./ubexplore2.opt 0 10 prints numbers from 0 to 10 inclusive, and ./ubexplore2.opt 0x7ffffff0 0x7fffffff prints 16 numbers from 2,147,483,632 to 2,147,483,647 (the largest positive signed 4-byte integer we can represent). But ./ubexplore2.noopt 0x7ffffff0 0x7fffffff prints a lot more and appears to loop infinitely! It turns out that although the optimized behavior is correct for mathematical addition (which doesn’t have overflow), the unoptimized code is actually correct for computer arithmetic. When we look at the code carefully, we understand why: the loop increments i after the body executes, and 0x7fff’ffff overflows into 0x8000'0000 (= -1), so next time the loop condition is checked, -1 is indeed less than or equal to n2. But with optimizations enabled, the compiler increments i early and compares i + 1 < n2 rather than i <= n2 (a legal optimization if assuming that i + 1 > i always).

Caching and the Storage Hierarchy #

We are now switching gears to talk about one of the most important performance-improving concepts in computer systems. This concept is the idea of cache memory.

Why are we covering this?

Caching is an immensely important concept to optimize performance of a computer system. As a software engineer in industry, or as a researcher, you will probably find yourself in countless situations where “add a cache” is the answer to a performance problem. Understanding the idea behind caches, as well as when a cache works well, is important to being able to build high-performance applications.

We will look at specific examples of caches, but a generic definition is the following: a cache is a small amount of fast storage used to speed up access to larger, slower storage.

One reasonable question is what we actually mean by “fast storage” and “slow storage”, and why need both. Couldn’t we just put all of the data on our computer into fast storage?

To answer this question, it helps to look at what different kinds of storage cost and how this cost has changed over time.

The Storage Hierarchy #

When we learn about computer science concepts, we often talk about “cost”: the time cost and space cost of algorithms, memory efficiency, and storage space. These costs fundamentally shape the kinds of solutions we build. But financial costs also shape the systems we build, and the costs of the storage technologies we rely on have changed dramatically, as have their capacities and speeds.

The table below gives the price per megabyte of different storage technology, in price per megabyte (2010 dollars), up to 2019. (Note that flash/SSD storage did not exist until the early 2000s, when the technology became available.)

(Prices due to John C. McCallum, and inflation data from here. $1.00 in 1955 had “the same purchasing power” as $9.62 in 2019 dollars.)

Computer technology is amazing – not just for what it can do, but also for just how tremendously its cost has dropped over the course of just a few decades. The space required to store a modern smartphone photo (3 MB) on a harddisk would have costs tens of thousands of dollars in the 1950s, but now costs a fraction of a cent.

But one fundamental truth has remained the case across all these numbers: primary memory (DRAM) has always been substantially more expensive than long-term disk storage. This becomes even more evident if we normalize all numbers in the table to the cost of 1 MB of harddisk space in 2019, as the second table below does.

As a consequence of this price differential, computers have always had more persistent disk space than primary memory. Harddisks and flash/SSD storage are persistent (i.e., they survive power failiures), while DRAM memory is volatile (i.e., its contents are lost when the computer loses power), but harddisk and flash/SSD are also much slower to access than memory.

In particular, when thinking about storage performance, we care about the latency to access data in storage. The latency denotes the time it takes until data retrieved is available if read, or until it is on the storage medium if written. A longer latency is worse, and a smaller latency better, as a smaller latency means that the computer can complete operations sooner.

Another important storage performance metric is throughput (or “bandwidth”), which is the number of operations completed per time unit. Throughput is often, though not always, the inverse of latency. An ideal storage medium would habe low latency and high throughput, as it takes very little time to complete a request, and many units of data can be transferred per second.

In reality, though, latency generally grows, and throughput drops, as storage media are further and further away from the processor. This is partly due to the storage technologies employed (some, like spinning harddisks, are cheap to manufacture, but slow), and partly due to the inevitable physics of sending information across longer and longer wires.

The table below shows the typical capacity, latency, and throughput achievable with the different storage technologies available in our computers.

This notion of larger, cheaper, and slower storage further away from the processor, and smaller, faster, and more expensive storage closer to it is referred to as the storage hierarchy, as it’s possibly to neatly rank storage according to these criteria. The storage hierarchy is often depicted as a pyramid, where wider (and lower) entries correspond to larger and slower forms of storage.

This picture includes processor caches, which are small regions of fast (SRAM) memory that are on the processor chip itself. The storage hierarchy shows the processor caches divided into multiple levels, with the L1 cache (sometimes pronounced “level-one cache”) closer to the processor than the L2, L3, and L4 caches. This reflects how processor caches are actually laid out, but we often think of a processor cache as a single unit.

Different computers have different sizes and access costs for these hierarchy levels; the ones in the table above are typical. Here are some more, based on Malte’s MacBook Air from ca. 2013: a few hundred bytes of of registers; ~5 MB of processor cache; 8 GB primary memory; 256 GB SSD. The processor cache divides into three levels: 128 KB of total L1 cache, divided into four 32 KB components; each L1 cache is accessed only by a single processor core (which makes it faster, as cores don’t need to coordinate). There are 256 KB of L2 cache, and there are 4 MB of L3 cache shared by all cores.

Each layer in the storage hierarchy acts as a cache for the following layer.

Finally, consider how the concept of caching abounds in everyday life, too. Imagine how life would differ without, say, fast access to food storage – if every time you felt hungry, you had to walk to a farm and eat a carrot you pulled out of the dirt. Your whole day would be occupied with finding and eating food! (Indeed, this is what some animals spend most of their time doing.) Instead, your refrigerator (or your dorm’s refrigerator) acts as a cache for your neighborhood grocery store, and that grocery store acts as a cache for all the food producers worldwide.

Summary #

Today, we learned some handy rules about collections and their memory representation and review how these rules they interact with alignment, particularly within structs. We saw that changing the order in which members are declared in a struct can significantly affect its size, meaning that alignment matters for writing efficient systems code.