Learnings from Redis # 2 / Optimized String in C

Strings

In our previous post, we learnt about the usage of macros to eliminate repetitive usage of common logic, if you haven’t read it you can find it here.

C Programming Learnings from Redis # 1

Alright moving on to our next interesting topic which is about strings. As we know the functionality or the support around strings in C is very primitive and doesn’t scale well for a big project. In Redis, a library called Simple Dynamic Strings aka SDS is being used to overcome some of the difficulties around strings.

SDS provides dynamic memory allocated string in heap with the following structure.

+--------+-------------------------------+-----------+
| Header | Binary safe C alike string... | Null term |
+--------+-------------------------------+-----------+
         |
         `-> Pointer returned to the user. 

From the above structure we can see, the header exists before the actual string (char array) starts. In C, the header structure used to look like this in SDS v1:

struct sdshdr {
    int len;
    int free;
    char buf[];
};

If a new sds string of value Redisis created the memory view of it would look like this

                   +-------+------+----+
                   | 5 | 0 | Redis| \0 |
                   +-------+------+----+

All of the three fields will be aligned at the same place in the memory, when a new sds string is created a reference is returned to the start of char arraybuf.
I would like to highlight if it were a regular C string, in order to find the length of the string strlen method would be used and the cost of using it isO(N), N being the length of the string. However, while using sds a length of the string can be determined in O(1) . See how the magic works.

size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    return sh->len;
}

Inside the above method, as we can see we move back by sizeof(struct sdshdr) and retrieve the sdshdr and retrieve len from it. Beautiful, isn’t it ?

There are a lot’s of other benefits and antirez has talked about them in details in the project README file, go check it out.

antirez/sds

If you liked this idea and have other interesting library to share do post it in the comments. Have a good day!