EBO (Empty Base Optimization) in STL Design

Table of Contents

EBO (Empty Base Optimization) in STL Design

0. Introduction

EBO, short for Empty Base Optimization, is a technique used to optimize the memory layout of classes in C++.

In this section, we'll start from empty classes, delve into the internals of the STL, conduct tests, implement our own EBO, compare performances, and conclude.

1. Empty Class

Let's define an empty class: a class with no member variables, no inheritance, and no data elements.

class Empty {
public:
    void print() {
        std::cout << "I am Empty class" << std::endl;
    }
};

Since it's empty, what would be its sizeof?

std::cout << sizeof(Empty) << std::endl; //1

The result is 1. Why isn't it 0 since it's empty?

Because an empty class can still be instantiated, and each instance needs a unique address in memory. To achieve this, compilers often implicitly add a byte to an empty class, ensuring each instance has a unique address in memory. Hence, the size is 1.

Following this explanation, you might wonder: why should the addresses of two different objects be different?

Consider the following example:

class Empty {
public:
    void print() {
        std::cout << "I am Empty class" << std::endl;
    }
};
template <typename T>
bool isSame(T const & t1, T const & t2) {
    return &t1 == &t2;
}

Let's test it:

int main() {
    Empty a, b;
    assert(!isSame(a, b));  // Compiles successfully, addresses of a and b are different

    Empty *p = new Empty;
    Empty *q = new Empty;
    assert(!isSame(p, q)); // Compiles successfully, addresses of p and q are different
    return 0;
}

The test shows that the addresses of two different objects are indeed different. Now, consider this scenario:

Empty a, b;
// If a and b had the same address, having two objects at the same address would mean that when using pointers to reference them, we couldn't distinguish between the two objects.
Empty *p1 = &a;
p1->print();

In this case, if a and b had the same address, having two objects at the same address would mean that when using pointers to reference them, we couldn't distinguish between the two objects. Hence, the addresses of two different objects are different.

2. Empty Base Class Optimization

Now let's compare the following two approaches. The first one includes another class as a member in a class and then accesses the functionality of the included class through it.

class NotEbo {
    int i;
    Empty e;
    // do other things
};

The second one directly inherits from a base class to acquire its member functions and other functionalities.

class Ebo: public Empty {
    int i;
    // do other things
};

Next, let's perform a test:

std::cout << sizeof(NotEbo) << std::endl;
std::cout << sizeof(Ebo) << std::endl;

Output:

8 
4

In the first case, due to byte alignment, the size is extended to the nearest multiple of 4, making it 8 bytes.

Comparing these two, we observe that the second approach, inheriting to acquire functionalities of the base class without generating additional size, is called EBO (Empty Base Optimization).

Now, let's revisit the STL source code to see its application!

3. EBO World in the STL

Whether it's deque, rb_tree, list, or other containers, memory management is essential. These containers include respective memory management and inherit from the following classes through _xx_impl:

std::allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::__mt_alloc<_Tp>
__gnu_cxx::__pool_alloc<_Tp>
__gnu_cxx::malloc_allocator<_Tp>

What does this have to do with our EBO?

In fact, the base classes listed above for memory management are instances of EBO (Empty Base Optimization).

In each container, these are used by invoking rebind<_Tp>::other for each memory management.

For instance, in the source code structure of a red-black tree:

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
        rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
struct _Rb_tree_impl : public _Node_allocator
{
// do somethings
};

Now let's examine the source code structures of the memory management classes listed above. Let's take allocator as an example:

template<typename _Tp>
class allocator: public __allocator_base<_Tp>
{
	 template<typename _Tp1>
     struct rebind { typedef allocator<_Tp1> other; };
};

See that? Through rebind<_Tp>::other, it obtains the memory allocator passed in, which are the ones listed earlier.

std::allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::__mt_alloc<_Tp>
__gnu_cxx::__pool_alloc<_Tp>
__gnu_cxx::malloc_allocator<_Tp>

Understanding this, let's run some tests:

void print() {
    cout << sizeof(std::allocator<int>) << " " << sizeof(std::allocator<int>::rebind<int>::other) << endl;
    cout << sizeof(__gnu_cxx::bitmap_allocator<int>) << " " << sizeof(__gnu_cxx::bitmap_allocator<int>::rebind<int>::other) << endl;
    cout << sizeof(__gnu_cxx::new_allocator<int>) << " " << sizeof(__gnu_cxx::new_allocator<int>::rebind<int>::other) << endl;
    cout << sizeof(__gnu_cxx::__mt_alloc<int>) << " " << sizeof(__gnu_cxx::__mt_alloc<int>::rebind<int>::other) << endl;
    cout << sizeof(__gnu_cxx::__pool_alloc<int>) << " " << sizeof(__gnu_cxx::__pool_alloc<int>::rebind<int>::other) << endl;
    cout << sizeof(__gnu_cxx::malloc_allocator<int>) << " " << sizeof(__gnu_cxx::malloc_allocator<int>::rebind<int>::other) << endl;
}

Let's test if these sizeof values are 1. After testing, the output is as follows:

This indicates that the implementation of memory management utilizes inheritance

to minimize the size of containers, achieving optimization goals.

4. Implementing a Simple Memory Allocation and Deallocation Using EBO

First, let's define a class with sizeof(class) = 1, similar to STL, using allocate and deallocate for memory management.

class MyAllocator {
public:
    void *allocate(std::size_t size) {
        return std::malloc(size);
    }

    void deallocate(void *ptr) {
        std::free(ptr);
    }
};

For the first approach to memory management: embedding a memory management class:

template<class T, class Allocator>
class MyContainerNotEBO {
    T *data_ = nullptr;
    std::size_t capacity_;
    Allocator allocator_;   // Embedding a MyAllocator
public:
    MyContainerNotEBO(std::size_t capacity)
            : capacity_(capacity), allocator_(), data_(nullptr) {
        std::cout << "alloc malloc" << std::endl;
        data_ = reinterpret_cast<T *>(allocator_.allocate(capacity * sizeof(T))); // Memory allocation
    }

    ~MyContainerNotEBO() {
        std::cout << "MyContainerNotEBO free malloc" << std::endl;
        allocator_.deallocate(data_);
    }
};

For the second approach: using EBO to inherit memory management functionality:

template<class T, class Allocator>
class MyContainerEBO
        : public Allocator {    // Inheriting an EBO
    T *data_ = nullptr;
    std::size_t capacity_;
public:
    MyContainerEBO(std::size_t capacity)
            : capacity_(capacity), data_(nullptr) {
        std::cout << "alloc malloc" << std::endl;
        data_ = reinterpret_cast<T *>(this->allocate(capacity * sizeof(T)));
    }

    ~MyContainerEBO() {
        std::cout << "MyContainerEBO free malloc" << std::endl;
        this->deallocate(data_);
    }
};

Let's begin testing:

int main() {
    MyContainerNotEBO<int, MyAllocator> notEbo = MyContainerNotEBO<int, MyAllocator>(0);
    std::cout << "Using Not EBO Test sizeof is " << sizeof(notEbo) << std::endl;
    MyContainerEBO<int, MyAllocator> ebo = MyContainerEBO<int, MyAllocator>(0);
    std::cout << "Using EBO Test sizeof is " << sizeof(ebo) << std::endl;

    return 0;
}

Test results:

alloc malloc
Using Not EBO Test sizeof is 24
alloc malloc
Using EBO Test sizeof is 16
MyContainerEBO free malloc
MyContainerNotEBO free malloc

We observe that the design using EBO is significantly better than embedding. With this, we conclude this section.