[Compiler] Memory Allocation/Alignment of Objects and Virtual Functions

7 min readMay 24, 2023

Let’s talk about how the computer actually allocates memory for various types of variables and how it deals with function/virtual function calls!

Primitive Type Variables

First, let’s see primitive types, such as int, double, and char. Primitive types are pretty straightforward. Depending on the size of that data type, that variable is stored at that address.

Integer and Double

Integer and double are stored as binary numbers in memory according to the endianness. For example, suppose we have a 32-bit integer, int x = 4315123. Then, if we convert this number to Hex, then it’s 0041D7F3. Depending on the endianness, this number is stored a little differently.

Little-Endian

Little-endian stores the least significant byte at the smallest address. Thus, if the integer “x” is stored at address 0x1000, then F3(0041D7F3) is stored at 0x1000, D7(0041D7F3) is stored at 0x1001, 41(0041D7F3) is stored at 0x1002, and 00(0041D7F3) is stored at 0x1003. Here, assume that one address can hold 8 bits.

Big-Endian

On the other hand, Big-Endian stores the most significant byte at the smallest address. Thus, for the same “x,” 00(0041D7F3) is stored at 0x1000, 41(0041D7F3) is stored at 0x1001, D7(0041D7F3) is stored at 0x1002, and F3(0041D7F3) is stored at 0x1000.

Therefore, when we access int x, the computer will read 4 bytes(32bit) from the starting address, which is 0x1000, and combine the values according to endianness. Thus, if we print x, then it will give 4315123, but if we print &x, which is an address of the x, then it will give 0x1000.

Character and Boolean

Character and Boolean are stored the same way as Integer. However, in C++, they only consume 1 byte. For character, each character is converted to a corresponding number according to the ASCII table, and since those numbers can be represented with 1 byte, char only takes up 1 byte. For example, if we have a char letter = “a” and the letter is stored at 0x1000, then since “a” is 97 in the ASCII table, 0x61(in decimal 97) is stored at 0x1000.

Similarly, True and False are just 1 and 0, so they can also be represented with 1 byte. If we have, bool val = true, and “val” is stored at 0x1000, then 01 is stored at 0x1000.

An array of Primitive types

The array is just contiguous data. Thus, it is stored in the memory contiguously. If we have int x[4] = {10,11,12,13} and x[0](10) is stored at 0x1000, then x[1](11) is stored at 0x1004, x[2](12) is stored at 0x1008, and x[3](13) is stored at 0x1012 because each integer takes up 4 bytes and each address holds 1 byte(8 bits). Similarly, a char array is stored just like an integer array, but with an additional null character at the end (it is possible to manually create a char array without a null character, but print will go over the bound because it does not know the end).

String Constants

Interestingly, in C++, constant strings are stored in the .data section of the executable, just like static data.

Objects

Objects are pretty interesting because it is a compilation of multiple variables. However, there is nothing complicated about it. It just stores those variables just as an array does.

Simple Class Instance

A simple class instance, such as “MyClass test,” is stored like an array. In the order of variable declaration, those variables are stored in order. However, there are a few restrictions.

Starting address of the overall struct is aligned based on the largest field (divisible by the size of the largest field).
The size of an overall struct is a multiple of the largest field.
The address of a variable is aligned based on the size of the variable (starting address of each variable should be divided by the size of that variable)

Let’s look at the specific example,

Class MyClass {
  int x;
  double y;
  char c;
}
...
MyClass test;

Since double is the biggest variable inside of this class, starting address of all variables should be divided by 8. Suppose the test is stored at 0x1000. Since int is 4 bytes, x is stored at 0x1000 ~ 0x1003. Now, we want to store y at 0x1004, but since 1004 % 8 != 0, we cannot do this. Thus, there is a padding from 0x1004 ~ 0x1007. Then, we can store “y” at 0x1008 ~ 0x1015. Then, we store c at 0x1016. Since the overall size of the class instance should be divided by the size of the biggest primitive class member, we should add padding from 0x1017 ~ 0x1023. Thus, the overall size of the test is 24 bytes (0x1000 ~ 0x1023)

Due to this alignment, declaring class member variables in ascending or descending order of size can result in the minimum object size. Suppose we made MyClass like this,

Class MyClass {
  double y;
  int x;
  char c;
}

“y” is stored at 0x1000 ~ 0x1007. Then, “x” is stored at 0x1008 ~ 0x1011. Since “x” is 4 bytes and 0x1008 % 4 == 0, there is no problem. Then “c” is stored at 0x1012. Then, add padding from 0x1013 ~ 0x1015 because the overall size should be divided by 8. Now, the test variable has only 16 bytes from 0x1000 to 0x1015.

How about Methods?

We talked about member variables, but how about member functions? How does the compiler call the correct member function when we do something like, test.callMember()? How does the compiler locate the correct function definition?

Class definitions are stored in the code section. This makes sense because the class definition is basically just a code. We do not store this definition inside of each instance, because definitions are identical across all instances. Since class definitions are stored in the code section, when we call member functions, all we do is jumping to that code section. Again, calling the function at a low level is jumping to the address where that function is defined. For example, suppose we have,

class Rabbit{
  string name;
  void eat() {...}
}
...
Rabbit rb;
rb.eat();

And in assembly,

       _Rabbit.eat:
0x2000   subu $sp, $sp, 8 # examples... 
0x2004   sw $fp, 8($sp) 
0x2008   sw $ra, 4($sp) 
         ...

So, when we call rb.eat(), we basically jump to 0x2000 and pass the “rb” variable, just as Python pass “self” in their methods.

Inheritance

When we call methods, we just jump to the function definition. The reason we were able to do this was that we know the class name and function name. However, sometimes, the function we want to call does not exactly match the class name. When we are using polymorphism, we use virtual functions. In this case, we have a variable of the parent’s class pointer, but we actually want to run a child’s overridden function. Ex) Parent* par = new child, par.callOverridedFunction();

How can we do this? Since the type of the pointer is “Parent,” we cannot just locate the function using the type name. Also, calling a virtual function is a dynamic process, we cannot decide the name of the child class that has the function we want to run in compile time.

Virtual Table Pointer

To solve this problem, we use a Virtual Table Pointer. A virtual table is a table that contains pointers to the function definitions (each pointer stores the address of the corresponding function definition). Since it is a pointer, we can change the function definition dynamically by changing the value of the pointer, which is the address of the function definition. Then, each object stores a pointer to this virtual table and uses the virtual table to call the correct function. It is pretty confusing, so let’s look at the example and diagram.

class Animal{
  public:
    void walk(){}
    virtual void bark(){
      cout << "hello";
    }
};

class Dog : Animal{
  public:
    int weight;
    int height;
    void eat(){}
    void bark(){
      cout << "woff woff";
    }
    virtual void run(){
      cout << "running";
    }
};

class Corgi : Dog{
  public:
    string name;
    void sleep(){}
    void bark(){
      cout << "hi im corgi!";
    }
}
...
Animal* justDog = new Dog;
Animal* corgi = new Corgi;

justDog.bark(); // woff woff
corgi.bark(); // hi im corgi!

Diagram of the pointer, virtual tables, and code.

Just like the above diagram, the virtual table is just an array of pointers, storing the address of the actual definition of the function. For example, walk() : 0x1000, and at 0x1000: definition of walk(). The computer calls the function by accessing the function in the virtual table by the offset like we are accessing an array. For example, if we call Dog.bark(), it jumps to, *(vtable pointer + 8), which equals to *(*justDog + 8). Reference is a bit complicated, but let’s see an example.

Suppose values are stored like this,

0x1000: justDog, 0x1234: new Dog(), 0x2345: Dog’s virtual table, 0x3456: _Dog.bark’s definition. Then, since the virtual table pointer is stored in the “new Dog”, 0x1234 holds the address of the Dog’s virtual table, which is 0x2345.

Now, since justDog’s value is 0x1234 (address of new Dog), *justDog = *(0x1234) = data that 0x1234 holds = 0x2345 = Dog’s vtable.

Since bark() is two elements away from the starting point of the vtable, we should access it with offset 8. Thus, *(*justDog + 8) = *(0x2345 + 8) = data that 0x2345 + 8 holds = 0x3456 = address of _Dog.bark’s definition. As a result, we can jump to _Dog.bark() using *(*justDog + 8).

(remark: function’s definitions are located in the table in the order of declaration. The above diagram has a minor error in terms of that)

Objects with virtual pointer

Since objects need a virtual pointer to locate the correct function, their size is different from canonical class instances. Each object allocates additional spaces for the virtual pointer in addition to class member variables, so the size is class size + 8 (size of a pointer). For example, from the above diagram, new Dog() contains a virtual table pointer, height, and weight.

This was a quick overview of how variables are stored and how the compiler deals with polymorphism!