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:

  1. string_constructor(const char *)
  2. allocate string_data
  3. string_data_constructor(const char *)
  4. allocate char[]
  5. 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 (but probably only on my personal blog, so subscribe if you’re interested).