How much space does an unsigned 8-bit integer occupy in C and Haskell?
Neither the C99 standard nor the Haskell2010 standard specifies such low-level details, so the answer could in theory be anything. To have something to work with, let’s make the following assumptions:
- architecture: x86-64
- ABI/calling conventions: System V
- C compiler: GCC 6.3
- Haskell compiler: GHC 8.0
In C, the unsigned 8-bit integer type is called
uint8_t. It is defined in the header
stdint.h. Its width is guaranteed to be exactly 8 bits; thus, its size is 1 byte.
But how much space does it really occupy? That depends on two factors
- whether it is a function argument or return value, or a (local or global) variable
- whether it is part of an array or struct
Function arguments and return values
According to the AMD64 System V ABI, the first 6 integer arguments are passed via registers and the rest are passed on the stack. If a function returns a single integer value, it is passed back in a register. Since the integer registers are 64-bit wide, when a
uint8_t value is passed in a register, it effectively occupies 8 bytes.
To illustrate, consider this function:
GCC generates the following code:
The two arguments are passed in the 64-bit registers
%rdi. Although the result is written to a 32-bit register
%eax, it is part of the 64-bit register
%rax, and the other 32 bit of that register cannot be reused easily while
%eax is occupied.
What about the arguments passed through the stack? The ABI dictates that their sizes, too, are rounded up to 8 bytes. This allows to preserve stack alignment without complicating the calling conventions.
We see that the
g argument is 8 bytes below the stack boundary,
(%rsp). These whole 8 bytes are dedicated to our tiny int.
uint8_t’s are part of a struct or similar, they occupy one byte each. Curiously, if the struct is 16 bytes or smaller, the
uint8_t’s will be packed into registers!
Both bytes are passed inside
%edi, and the intermediate 1-byte
%ah register is used to take them apart.
Local and global variables
Like function arguments, local variables can reside in registers or on the stack. But unlike function arguments, local variables are not constrained by calling conventions; the compiler can do whatever it wants.
When an 8-bit local variable is stored in a register, it effectively occupies the whole 64-bit register, as there is only one 8-bit “subregister” per general-purpose register (unlike in x86).
What happens to the local
uint8_t variables stored on the stack? We can compile this test program to find out:
volatile keyword is needed to force the compiler to store the local variable
c on the stack rather than in a register. As we see,
c is stored at
-0x1(%rsp), so 1 byte is enough here. This is because there is no alignment requirement for 8-bit integers. The same is true for global variables.
In Haskell, the unsigned 8-bit integer type is called
Word8. Its canonical module according to the standard is
Data.Word, but in GHC, it is originally defined in
GHC.Word and then re-exported from
Word8 is a boxed type. The space occupied by every boxed type in Haskell consists of two parts: the header and the payload. Here is a helpful picture from the GHC wiki:
Note that stuff on the bottom of the picture — the info table and the entry code — is read-only static data shared among all instances of the given type and even across multiple copies of the same program, so we don’t count it towards the space occupied by a value.
The header is a structure that (on x86-64) normally consists of 8 bytes — a pointer to the entry code for the object.
The value of our byte is stored in the payload. But how exactly? Let’s look at the definition of
Word# is an unboxed machine-word-sized unsigned integer, i.e. a 64-bit integer for x86-64.
In total, a
Word8 lying around occupies 16 bytes. When computing with
Word8’s inside some kind of inner loop, they will normally be unboxed into
Word#’s and passed around in 8-byte registers or in 8-byte cells on the (Haskell) stack — more or less like in C.
Thus, during computation, Haskell is not that different from C. But what about storage? Can multiple
Word8’s be packed together densely?
Say, we need a structure,
TwoBytes, consisting of two
Word8’s. We intend to use it as a key and/or element type in a large dictionary, so we’d like to keep it as compact as possible. (Note that
Data.Map already adds a 48 bytes overhead per key/value.)
If we declare
TwoBytes in the most naive way
the structure will occupy 56 bytes!
TwoBytes would consist of a header (8 bytes) and a payload consisting of two pointers (8 bytes each), each pointing to a
Word8 (16 bytes each).
A more efficient way to declare
This makes the fields strict and unpacked, so that the two bytes are stored directly in
TwoBytes’s payload. This occupies 24 bytes — “only” 12 bytes per
Word8. Compared to a single
Word8, we see some economy, but it only amortizes the header. No matter how many
Word8’s we put together, the size won’t get below 8 bytes per
To pack bytes together, we can use an unboxed vector:
To see how much memory this structure occupies, we need to see the definition of
Vector and the underlying ByteArray:
The runtime representation of
ByteArray# is a pointer to the
StgArrBytes structure defined in
The space required for a
ByteArray# is 8 bytes for the header, 8 bytes for the length, and the payload, rounded up to whole words (see
rts/PrimOps.cmm) — so 8 bytes in our case, 24 in total.
The size of
Vector, therefore, is 8 bytes for the header, 16 bytes for the offset and length (needed to provide O(1) slicing for vectors), 8 bytes for the pointer to the
ByteArray#, and 24 bytes for
ByteArray# itself; total of 56 bytes.
This is the opposite of the previous definition in that the representation is asymptotically efficient, requiring 1 byte per
Word8, but the upfront cost makes it absolutely impractical for
Even if we cut out the middleman and used
… it would only get us to 40 bytes.
The most frugal approach for the case of two bytes is to define
(16 bytes) and do packing/unpacking by hand. This is a rare case where a Haskell programmer needs to write code that a C compiler would generate (recall two bytes packed into
%edi) and not the other way around.
If GHC provided a
Word8# unboxed type, we could use the earlier defined
which would still occupy 16 bytes but be more conventient to work with than a single
Word. But that’d require a major change to the compiler, and it’s probably not worth the hassle.
In both C and Haskell, a byte-sized integer occupies 8 bytes when it is actively worked upon (i.e. kept in a register) and 1 byte when many of them are stored in an array/vector.
However, when storing single
Word8’s or small structures like
TwoBytes, Haskell is not as memory-efficient. Primarily this is because idiomatic Haskell relies heavily on pointers and everything is word-aligned.