I would like to present a very cool technique, widely used in C libraries, yet almost completely forgotten in C++.
We have a String class. It is a reference-counted, immutable string. Typical data structures in C++ would look like:
struct string { string_data * data; }; struct string_data { int refcount; int length; char * data; };
So, string is merely a reference to actual string_data. Creating new string objects (string foo = "hello world") looks like:
- string_constructor(const char *)
- allocate string_data
- string_data_constructor(const char *)
- allocate char[]
- copy data, set all other members
In memory, it would actually look like:
So, we have one stack allocation, two dynamic allocations and our data is in three different places in memory. But in C++ terms it seems impossible to improve it. However, we can go C way and change string_data definition:
struct string_data { int refcount; int length; char data[1]; };
Array of one character? I must be crazy, right?
Most C++ courses are not very precise about pointers and arrays. Especially, what is the difference of following instructions?
const char * string1 = "hello world"; const char string2[] = "hello, C++!";
And what is the difference of those?
int foo(const char *) { printf("*\n"); } int foo(const char[]) { printf("[]\n"); }
Unfortunately, in C++ world where really various things can be static, answers are different. In first case, string1 and string2 are something else. In second case, there is no difference — actually, that code won’t compile due to non-unique overload.
Maybe little investigation? Let’s print some data:
printf("%p %p %s\n", string1, &string1, string1); printf("%p %p %s\n", string2, &string2, string2);
What we do is printing expression as a pointer, address of this expression as a second pointer and null-terminated string pointed by expression. Results:
0x08048650 0xbfddbfa4 hello world 0xbfddbf98 0xbfddbf98 hello, C++!
Now you see magic behind it. 0xbf…… are stack addresses while 0×08048650 comes from somewhere else (likely from static, read-only data section). So, while pointer types hold address inside, arrays points to themselves. And we can abuse it!
“Typical” C++ allocation of string_data would look like this:
string_data * foo = new string_data;
It would allocate sizeof(string_data) bytes (9 + padding, probably 12). But in fact, we can allocate as much as we want! For example:
string_data * q = (string_data*)malloc(2 * sizeof(int) + 12); new (q) string_data;
In this case — 2 ints and 12 bytes of string data. After successful allocation we need to manually invoke constructor, using placement new. Similarly, regular delete q won’t work — following code will:
q->~string_data(); free(q);
Of course if data type is simple (built-in datatypes, relaxed POD, whatever) there is no need to call constructor and destructor (although those calls probably would be simply optimized away). And malloc/free can be replaced with custom allocation routines.
And after such allocation, we can use data like it was not a char[1] array but rather a char[as much as we have allocated] array! How does memory look like with this data structure?
And there are numerous benefits of such approach:
- one dynamic allocation less
- data is less scattered in memory
- we saved some memory (how much? size of the pointer + size of allocation metadata)
In the next part, I’ll show how we can save even more allocations/memory.
(from #altdevblogaday)
