The performance of dynamic strings implementations
Let’s say you want to create a nice string abstract data type to use in your C code. You can end with a structure like this:
- the buflen field keeps track of the length of the allocated buffer;
- the len field keeps track of the length of the string, so that you can know the string length in constant time;
- the buf field keeps track of the memory address where the string is allocated. This field will be changed when you reallocate the string when the buffer is full.
It sound nice and you can also have manipulation functions that reallocate the string when necessary. They will be really useful! Let’s try:
This is nice indeed! But is really not that efficient from a memory point of view. In your heap you will have:
- The string descriptor (12 byte on a 32-bit architecture)
- The string contents (variable length)
Your implementation of the holy tuple
free must keep track of the string descriptor and of the strings contents, which can be (and will be) non-contiguous in memory.
You can do really better allocating the string descriptor directly before the string contents and having
mstring_new return the address of the string contents instead of the string descriptor. Your strings will be C-compatible and more efficient.
Let’s try again:
But now your
fstring_append function can’t simply change the
buf field when a buffer reallocation is needed. You must to reallocate the entire string, descriptor included.
So your code will change like this:
You may say that this is premature optimization but wait! You saved:
- one malloc
- one free
and now the string descriptor is also attached to the string, and your cache will be happy. Really more efficient. In my tests this string implementation is two times more efficient that the previous.