C++ 20: A Formidable Armada – My honest First Impression

I have just started with C++20. In one word, I am flabbergasted!

Though, I had just a glance, that was indeed an awe-inspiring session!

One can never complete learning C++, as they keep on adding new features every 3 years or so, with a new standard. I was sceptical about this at first. But, looking at the way they have improvised the language with C++20, I am forced to turn back on that pre-conception of mine. I refuse to use the word “prejudice thought” here. Please cut me some slack here. It will take time to welcome all these additions just like that. Let it take some time to bake-in and ready. I am pro-C++ 20 now! It seems like improvisation is a necessity of the modern programming language and problems that it tries to solve.

Now, let me mention some of the core C++20 features which is worth mentioning.

According to C++ 20 experts, the 4 core features includes concepts, co-routines, ranges, and modules.

They are looking forward to avoid header files through modules, minimalistic thread like yielding functions called coroutines, language support for “parameterized types” pre-requisites through concepts in templates etc. Concepts are more readable and intuitive than previous static_assert<>, that’s my opinion. Kindly excuse!

Python enthusiasts, just have a look at what C++20 has in its offerings.

They have literally made C++ more Pythonic. I don’t mean the way experts, a.k.a. Pythonistas, write Python code. Here, by “pythonic”, I am simply referring to the way, how C++ 20 is filled with features which could be found in Python already, and in abundance. Introducing view::filter, transform, pipelines!!! As an intermediate python programmer, I know that python has map() and filter() for the same purpose. Also, python’s yield feature. which is a kind of temporary suspension/or partial return from a function, is now realized in C++ 20 using coroutines. This is just another beautiful example, where we can see a very popular programming language such as python influencing another popular language such as C++. In olden days I have seen the way C++ influenced C and Java and even vice versa. But C++ becoming more python like? Well, that’s another story!!!!

Most of them are expecting “generators” in the next C++ standard!!! Python has generators from the beginning. Now they have added experimental generators in Microsoft Visual C++. (Reference: C++20: An (Almost) Complete Overview – Marc Gregoire – CppCon 2020)

To conclude, for the sake of, well, concluding, C++ is way too powerful now and quite elegant. I came to know that, the only compiler that support C++ 20 one hundred percent is Microsoft C++ compiler. Well done, Microsoft! Not sure on GCC. I heard version 10 supports C++20. Don’t know up to what extend??? But I’m pretty sure that it’s just a work in progress and is just a matter of time that we will see GCC and clang with full C++ 20 support!

Just for a quick reference: Please go through video titled: C++20: An (Almost) Complete Overview – Marc Gregoire – CppCon 2020.

Link: https://youtu.be/FRkJCvHWdwQ

Chapter 23 : Implementing A Custom Heap

Key-Words: Custom Heap, Allocating memory from heap, Releasing memory back to heap, Singleton Heap, Custom free storeOverloading new and delete

Topics at a glance:

  • How to implement a custom heap in C++
  • How to overload new and delete to make use of custom heap

In previous chapters we have seen how to implement custom Array class with iterator support, custom unique and shared pointers, custom queues etc. In this chapter, we will implement a custom heap. Heaps are used for dynamically allocating memory regions in course of a program execution. The program releases the memory back to heap once it is done with the usage of the memory. Heaps are usually implemented by the underlying platform usually an OS. C++ abstracts the entire heap management using an entity called the free store along with operators new and delete. But in certain cases, say, a small embedded system with a bare minimal operating system or say, just a bare metal platform where there is no operating system, one cannot use the C++’s default new and delete as there is no heap defined. In such cases when one has to mimic C++’s free store facilities such as new and delete, it is imperative to define your own custom heap. Let us see how to define a custom heap.

Custom Heap

The core logic here is to define a memory region either in BSS or an area in RAM defined in a linker script. This region is our heap memory. Then, we have to define operations for allocating memory from this region and de-allocating (releasing) memory back to this region. Also, to keep track of the memory blocks that are in use and blocks that are free, we will have to define a memory information structure that bears information such as whether a block is free or not, the size of the current block and a pointer to the next block. This resembles a singly-linked list, of course. The only difference being that these memory information blocks are allocated in the custom defined heap memory itself.

Allocating memory from heap

When allocating a new memory, the alloc() function iteratively goes through these memory block info structures and find a free block with adequate size. When the required size is less than the capacity of the block, an additional logic runs to allocate a free memory block at the end of this newly allocated block, as there will be remaining size left after this newly allocated memory block. This logic has to consider two cases mentioned below.

Case 1: Where there is already another block of memory present after this free block. This is analogous to a linked list implementation where one tries to insert one node between two nodes.

Case 2: There is no memory present after this free block. This is like adding a new node in a linked list at the very end.

Releasing memory back to heap

When deallocating memory simply mark the block as free. There is an improvement that could be done here. That is to merge this block with consecutive free memory block. This is not yet implemented in the current version.

Singleton Heap

In C++ implementation, I have defined one Heap class with all the above-mentioned functionalities implemented. One important thing with this implementation is that we cannot have multiple instances of this Heap class. So, the obvious choice here is to make this class a singleton class with a private constructor and a static member function to return the singleton instance of Heap class. But there is a small problem with singleton.

We know that for singleton, get_heap_instance method has to return an instance’s pointer. Constructor of Heap class is made private so that no one outside can instantiate Heap objects directly without get_heap_instance member function. The trick here is to define custom new function for Heap class that will actually allocates this Heap object from a pre-defined memory, either from BSS or from a location defined through linker script.

Custom free store

Now, we have a Heap class, the next step is to define custom new and delete operators for classes for which we want to instantiate objects from this custom heap. For demonstrating this I have defined one class A{}, that defined custom new and custom delete that will use Heap’s alloc and de-alloc functions. Let us see the implementation of our Custom Heap class.

heap.h file:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#ifndef HEAP_H
#define HEAP_H

class Heap
{
private:
	struct mem_info_t
	{
		struct mem_info_t *next;
		size_t size;
		bool is_free;
	};
	
	mem_info_t *root;
	char *heap_end;
private:
	Heap();
	static void* operator new(size_t size);
public:
	~Heap();
	void clear_heap_memory();	
	void* alloc_memory(size_t size);
	bool dealloc_memory(void *this_mem);
	void heap_dump();
	static Heap* get_heap_instance(void);
	
};


#endif /*HEAP_H*/

heap.cpp file

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <iomanip>
#include "heap.h"

using namespace std;

static const size_t max_heap_size = (10 * 1024); // 10 KB

static char heap_memory[max_heap_size];

static char heap_object[sizeof(Heap)];


Heap::Heap()
{
	clear_heap_memory();
	
	// set up the root node mem info structure 
	root = reinterpret_cast<mem_info_t*>(&heap_memory[0]);
	root->next = nullptr;
	root->size = max_heap_size;
	root->is_free = true;	
	
	heap_end = &heap_memory[max_heap_size-1];
	
	cout << "heap initialized" << endl;
}

Heap::~Heap()
{
	clear_heap_memory();
	cout << "Heap destroyed" << endl;
}

void Heap::clear_heap_memory()
{
	for (auto &byte : heap_memory)
	{
		byte = static_cast<char>(0);
	}
	
	return;
}

void* Heap::alloc_memory(size_t size)
{
	char *mem = nullptr;
	mem_info_t *block_info = root;
	// first check whether any free blocks are there 
	do
	{
		// check for free blocks and see whether the size is adequate 
		if( (block_info->is_free == true) && (block_info->size >= size) )
		{
			// found a node 
			// 1. allocate memory block 
			mem = reinterpret_cast<char*>(block_info + 1);
			// 2. update this block information 
			block_info->size = size;
			block_info->is_free = false;
			
			// 3. update mem_info for next block 
			if(block_info->next != nullptr)
			{
				mem_info_t *temp_next = reinterpret_cast<mem_info_t*>(block_info->next);
				// check of enough space is there to accommodate a new empty block in between
				size_t rem_size = size_t( ((size_t)temp_next) - ((size_t)(mem + size)) + ((size_t)1) );
				
				if (rem_size > sizeof(mem_info_t))
				{
					mem_info_t *temp_new = reinterpret_cast<mem_info_t*>(mem + size);
					temp_new->next = temp_next;
					temp_new->is_free = true;
					temp_new->size = rem_size - sizeof(mem_info_t);
					block_info->next = temp_new;
				}
				// else no block can be allocated here 					
			}
			// there is no more block allocated here 
			// check if a new block can be allocated here 
			else if( size_t(mem) + size < size_t(heap_end) )
			{
				
				size_t rem_size = size_t(heap_end) - ( size_t(mem) + size) + size_t(1);
				
				if (rem_size > sizeof(mem_info_t))
				{
					mem_info_t *temp_new = reinterpret_cast<mem_info_t*>(mem + size);
					temp_new->next = nullptr;
					temp_new->is_free = true;
					temp_new->size = rem_size - sizeof(mem_info_t);
					block_info->next = temp_new;
				}
				
			}
			
			break; // exit while loop 
		}
		
		block_info = block_info->next;
		
	}while(block_info != nullptr);
	
	return reinterpret_cast<void*>(mem);
}

bool Heap::dealloc_memory(void *this_mem)
{
	char *mem = reinterpret_cast<char*>(this_mem);
	bool status = false;
	if( (unsigned int)(mem) < (unsigned int)(heap_memory))
	{
		cout << "Invalid memory" << endl;
		return status;
	}
	
	mem_info_t *block_info = root;
	mem_info_t *required_mem_block = reinterpret_cast<mem_info_t*>(mem) - 1;
	
	do
	{
		if(block_info == required_mem_block)
		{
			cout << "found the memory to be deallocated at " << hex << (unsigned int)required_mem_block << endl;
			block_info->is_free = true;
			// clear the memory
			for(int c = 0; c < block_info->size; ++c)
			{
				mem = char(0);
			}
			status = true;
			break; //exit while loop 
		}
		
		block_info = block_info->next;			
		
	}while(block_info != nullptr);
	
	// TODO : To merge with consecutive free blocks 
	
}

void Heap::heap_dump()
{
	int i;
	cout << "\nHeap dump" << endl;
	
	for(auto byte: heap_memory)
	{
		cout << "Byte " << dec << i << " : " << hex << "0x" << (0xFF & (unsigned int)byte) << endl;
	}
	
	cout << endl;
}


static void* Heap::operator new(size_t size)
{
	// size is unused 
	return reinterpret_cast<void*>(heap_object);
}

Heap* Heap::get_heap_instance()
{
	static bool is_init = false;
	static Heap *heap = nullptr;
	
	if(is_init == false)
	{
		heap = new Heap();
		is_init = true;
	}
	
	return heap;
}

Now, let us test this heap.

heap_test.cpp file

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include "heap.h"

using namespace std;

class A
{
private:
	int a_;
public:
	explicit A(int a = 0):a_{a}
	{
		cout << "A created with : " << dec << a_ << endl;
	}
	
	~A()
	{
		cout << "A destroyed" << endl;
	}
	
	static void* operator new(size_t size)
	{
		cout << "Custom new size " << size << endl;
		Heap* heap = Heap::get_heap_instance();
		void *mem_new = heap->alloc_memory(size);
		return mem_new;
	}
		
	static void operator delete(void *mem)
	{
		cout << "Custom delete" << endl;
		Heap* heap = Heap::get_heap_instance();
		heap->dealloc_memory(mem);
		
		return;
	}
};


int main()
{
	char *mem1, *mem2, *mem3, *mem4, *mem5;
	
	Heap* heap = Heap::get_heap_instance();
	
	mem1 = reinterpret_cast<char*>(heap->alloc_memory(200));
	
	if(mem1 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem1 << endl;
		for(int c = 0; c < 200; ++c )
		{
			mem1 = (char)(c);
		}
		
		mem2 = reinterpret_cast<char*>(heap->alloc_memory(100));
		
		if(mem2 != nullptr)
		{
			cout << "second memory allocated at " << hex << (unsigned int)mem2 << endl;
			for(int c = 0; c < 100; ++c )
			{
				mem2 = (char)(c);
			}
		}
		else
		{
			cout << "memory not allocated" << endl;
		}
		
		mem3 = reinterpret_cast<char*>(heap->alloc_memory(300));
		
		if(mem3 != nullptr)
		{
			cout << "second memory allocated at " << hex << (unsigned int)mem3 << endl;
			for(int c = 0; c < 100; ++c )
			{
				mem3 = (char)(c);
			}
		}
		else
		{
			cout << "memory not allocated" << endl;
		}
		
	}
	
	// heap dump 
	//Heap::heap_dump();
	
	if(true == heap->dealloc_memory(mem2))
	{
		cout << "mem2 freed" << endl;
	}
	else
	{
		cout << "mem2 not freed" << endl;
	}
	
	// allocate a new memory 
	
	mem4 = reinterpret_cast<char*>(heap->alloc_memory(30));
	
	if(mem4 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem4 << endl;
	}
	
	mem5 = reinterpret_cast<char*>(heap->alloc_memory(30));
	
	if(mem5 != nullptr)
	{
		cout << "memory allocated at " << hex << (unsigned int)mem5 << endl;
	}
	
	{
		A *a1 = new A(5);
		delete a1;
		
		A a2(10);
	}
	
	
	cout << "main ends" << endl;
	
	return 0;	
	
}

How to compile this using g++:

Invoke the command:

g++ -std=c++14 -I. -o heap_test.exe heap.cpp heap_test.cpp

Result:

heap initialized
memory allocated at 40704c
second memory allocated at 407120
second memory allocated at 407190
found the memory to be deallocated at 407114
mem2 freed
memory allocated at 407120
memory allocated at 40714a
Custom new size 4
A created with : 5
A destroyed
Custom delete
found the memory to be deallocated at 407168
A created with : 10
A destroyed
main ends

Of course there are further improvements as I have already pointed out above. I leave that to you.

Enjoyed the chapter? Let me know in the comments below. Thanks 🙂

Part 4 : Design Patterns With Modern C++

Chapter 12 : Series On Design Patterns – Factory Method

Chapter 13 : Series On Design Patterns – Command Pattern

Chapter 14 : Series On Design Patterns – Observer Pattern

Chapter 15 : Series On Design Patterns – Composite Pattern

Chapter 16 : Series On Design Patterns – Decorator Pattern

Chapter 17 : Series On Design Patterns – Strategy Pattern

Chapter 18 : Series On Design Patterns – Singleton Pattern

Chapter 19 : Series On Design Patterns – State Pattern

Chapter 20 : Series On Design Patterns – Bridge Pattern