Small String Optimization (SSO) in C++

Small String optimization SSO in C++

Introduction

Small string optimization (SSO) is a mechanism present in many programming languages and modern compilers. Its purpose is to reduce memory allocations on the heap. This optimization is particularly crucial in embedded environments and low-latency systems, where we must be vigilant about both our application’s memory consumption and code performance.

In the cppcon talk “The strange details of std::string at Facebook”, Nicholas Ormrod mentioned that std::string is the most frequently included file in the Facebook database, representing 18% of the CPU time spent in the STL.

Memory allocations are slow due to the numerous steps involved in the process of allocating memory on the heap. Typically, when working with strings, this memory is swiftly deallocated after usage, such as when printing text or assigning names to local (stack) objects.

The most frequently used string in C++ is the empty string. This string is generated when we perform default initialization on a string, and it ocuppies1 byte, which is the null terminator.

How does it works?

Before GCC 5.0, Small String Optimization (SSO) was not implemented. The std::string had a size of 8 bytes because both the size and the capacity were stored in positions -3 and -2 of the char* used to reference the std::string.

Source: Nicholas Ormrod

Before delving into how Small String Optimization (SSO) is implemented, it’s important to revisit how regular string objects are defined. Here’s a typical std::string implementation using modern C++:

struct string {
  std::unique_ptr<char[]> data; // data
  std::size_t size; // actual size
  std::size_t capacity; // total capacity of the buffer
}

With this implementation, we have a string class with a size of 24 bytes (on 64-bit architectures). If we compare this to the actual std::string in C++ found in the <string> header, we can observe that the C++ implementation has a size of 32 bytes. This size difference is attributable to Small String Optimization (SSO), which consumes some space within the struct. When SSO is applied, the implementation changes to something similar to this:

struct string_sso {
  std::size_t capacity;
  std::unique_ptr<char[]> data;
  std:size_t size;
  std::array<char, 16> sso_buffer;
}

The magic number 16 is determined by the compiler’s implementation and typically corresponds to 16 (15 characters + 1 null terminator).

This implementation has its advantages and disadvantages. If your string is shorter than 15 characters, it will be stored inside the std::array on the stack. However, if it exceeds 15 characters, your string will occupy 40 bytes in memory, with 24 bytes of that space going unused when SSO (capacity, size and data won’t be necessary until we reach 16 characters).

Note: std::array already has its own size that can be calculated in O(1).

The following implementation offers a more efficient way to utilize memory, paying only for what you actually use.

struct string_sso {
  std::size_t capacity;
  union {
    struct {
      std::unique_ptr<char[]> data;
      std:size_t size;
    } heap_buffer;
    std::array<char, sizeof(heap_buffer)> sso_buffer;
  };
}

In this new implementation, we utilize a static array (std::array) that eliminates the need for memory allocation on the heap. The critical element here is the sizeof(heap_buffer), which on a 64-bit architecture would be 16 bytes. This buffer accommodates 15 bytes for the string content and 1 byte for the null terminator for small strings. With this approach, the string size remains at 24 bytes, and the use of a union ensures that the same space is utilized whether the string size is larger or smaller than 16 bytes.

Personally, I prefer the second implementation, even though it lacks the flexibility to set a fixed size for every architecture or operating system, and it is tightly bound to data sizes. There are two potential reasons for using the first approach in compilers: either they consider it more efficient or they want to maintain compatibility with the existing Application Binary Interface (ABI).

Performance

The answer seems obvious, if our data structure is smaller and non allocated on the heap, our operations will be faster since it is faster to allocate and retrieve from the stack than from the heap. There are a lot of testing doing in the internet about that but I would like to add two of the most clear and well done that I found.

Source: https://cpp-optimizations.netlify.app/small_strings/
Source: HugoTeixeira in https://stackoverflow.com/a/51796541

Specially in the last one we can see clearly how in MacOS the SSO size is set to 23 characters, instead of 15 that is in Ubuntu

FBString by Andrei Alexandrescu

In the CppCon 2016, Nicholas Ormrod mention in his talk “The strange details of std::string at Facebook”, the implementation done by Andrei Alexandrescu of FBString in order to implement a SSO prior to GCC 5.0.

In contrast to some SSO optimizations implemented by compilers, FBString offers an SSO buffer size of 23 characters, which is larger than the 15 characters provided by the vast majority of implementations. But why is this significant? As Nicholas mentioned in the talk, one of the most commonly used strings at Facebook consists of UUIDs with 20 characters. With the majority of compiler implementations, these strings exceed the maximum characters required to fit within the SSO buffer, leading to heap memory allocation. Aside from Facebook case, 15 characters are not enought space in order to parse some of the 64-bit integer values to strings (int64_t, uint64_t, long long)

You can find the FBString optimization here

This is accomplished through the implementation of a three-tiered storage strategy and by collaborating with the memory allocator. Specifically, FBString is designed to identify the use of jemalloc and work in conjunction with it to attain substantial enhancements in both speed and memory utilization.

FBString SSO uses the last byte to represent the spare capacity for the string (remaining caracters).

Source: Nicholas Ormrod

This is quite clever because 0 is equivalent to ‘\0’. Consequently, when the spare capacity is 0, our last character will be the null terminator.

Source: Nicholas Ormrod

With this implementation, we have 3 bits remaining within the 24 available bytes to use as flags. Here’s a quick summary table about how we store tha values based on the number of characters:

Character rangeStorage method
<= 23 charactersAllocated on the stack
24-255 charactersare stored in malloc-allocated memory and copied eagerly.
> 255 charactersare stored in malloc-allocated memory and copied lazily (copy on write).

Copy-on-write (COW) semantics were removed in C++11 due to multithreading problems, but Andrei’s implementation offers multithreading safety.

Nicholas claims that this new implementation resulted in a 1% performance improvement for Facebook, which may seem substantial for a mere std::string optimization. One of the reasons for this improvement is its high optimization for the cache. Although it generates more assembly instructions, it is more cache-friendly, making the implementation faster. It’s essential to consider whether our target platform has cache available when assessing the impact of this optimization.

Note: Clang and MSVC have a similar implementation.

String_view

std::string_view was introduced in C++17. The primary purpose of this data structure is to optimize operations involving read-only strings. As a result, the std::string_view interface closely resembles that of a constant std::string.

A std::string_view is exceptionally lightweight, consisting of just one pointer to data (8 bytes on 64-bit architectures) and the size (8 bytes on 64-bit architectures), for a total of 16 bytes of space. This property makes it extremely efficient to convert a std::string into a std::string_view using the std::basic_string_view(const CharT* s, size_type count) constructor. This operation is highly resource-efficient.

In contrast, transforming a null-terminated string (const char*) into a suitable data structure typically requires iterating through all the data to retrieve the size of the string. This process has a time complexity of O(n), which can be significant when dealing with very large null-terminated strings, although such situations are relatively rare.

It’s crucial to highlight that std::string_view instances are allocated on the stack, eliminating the need for memory heap allocations. This is made possible by their immutability and their role as a “view” of an existing string, rather than a separate data container.

It’s indeed a good practice to consider using std::string_view whenever you are working with data that effectively behaves like a const std::string& or a const char* without the need for a null terminator

Last but not least, std::string_view does not have a null terminator character!!!

References

  1. https://stackoverflow.com/a/10319672
  2. https://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring/51796541#51796541
  3. https://cpp-optimizations.netlify.app/small_strings/
  4. https://pvs-studio.com/en/blog/terms/6658/
  5. CppCon 2016: Nicholas Ormrod “The strange details of std::string at Facebook”: https://www.youtube.com/watch?v=kPR8h4-qZdk
  6. CppCon 2015: Marshall Clow “string_view”: https://www.youtube.com/watch?v=H9gAaNRoon4

Custom conversions in C++

Introduction

In some languages it is common to have conversions between different types such as converting an integer to a floating point, for example. There are two types of conversions in programming; implicit conversions and explicit conversions.

Explicit conversions

An explicit conversions, as the name suggest, it is when the programmer have to explicitly specify what conversion has to be done. This way the code may look more messy but the programmer has the control of the code in all time.

C++
void floatToInt(int x) {
    std::cout << x; // prints 42
}

int main() {
    float x = 42.51231;
    floatToInt(static_cast<int>(x));
}

Implicit conversions

Implicit conversions are a powerfull tool that some languages provide usually to make the code easier to read and more agile when coding. Implicit conversions as the name suggest are done behind the scenes, wich means that the language itself knows that one type has to be converted to another type. In the code snippet below we can see an example:

C++
void floatToInt(int x) {
    std::cout << x; // prints 42
}

int main() {
    float x = 42.51231;
    floatToInt(x);
}

In this case, we can see how easily is to lose information in some data types if you rely in implicit conversion too much. This is te reason some modern languages like Rust doesn’t allow implicit conversions.

“explicit” specifier

explicit specifier is a keyword that C++ provides and can be used in constructors and conversion functions to avoid undisered implicit conversions.

C++
struct X {
    X(int) {}
    operator std::string() const { return std::string();}
};

struct Y {
    explicit Y(int) {}
    explicit operator std::string() const {return std::string();}
};
 
int main() {
    X x1 = 10;
    X x2(10);
    X x3 = {10};
    std::string s1 = x1;
    std::string s2 = static_cast<std::string>(x1);

    Y y1 = 10; // Error: cannot convert int to Y
    Y y2(10);
    Y y3 = {10}; // Error: cannot convert initializer-list to Y
    std::string s3 = y2; // Error: Implicit conversion not implemented.
    std::string s4 = static_cast<std::string>(y2);
}

In an effort for C++ to prevent issues with implicit conversion we have the ‘uniform initialization’ or ‘braced initialization’ in C++ 11 with the operator{}. This operator forze us to expecify the exact type our constructor is expecting.

C++
struct Z {
    Z(int, bool) {}
};

int main() {
    int x1(10.5); // Implicit conversion from double to int -> 10
    int x2{10.5}; // Error: narrowing conversion from double to int.
    
    Z z1(10.5, -1);
    Z z2{10, -1}; // Error: narrowing conversion int to bool.
    Z z3{10, false};
}

Explicit functions

But since ‘braced initialization’ only applies when constructing a type or an object, if we want a specific function to only accept the type we are indicating, the solution is a little bit more tricky.

1. Deleting function overloads
C++
struct Z {
    Z() = default;
    void Foo(int) {}
    void Foo(float) = delete;
    void Foo(bool) = delete;
};

int main() {
    Z z1;
    z1.Foo(1);
    z1.Foo(1.5); // Error: use of deleted function
    z1.Foo(true); // Error: use of deleted function
}

We can use generic parametrization to ensure that only functions we declare are going to be called.

C++
struct Z {
    Z() = default;
    void Foo(int) {}
    
    template<typename T>
    void Foo(T) = delete;
};

int main() {
    Z z1;
    z1.Foo(1);
    z1.Foo(true); // Error: use of deleted function
    z1.Foo(1.5); // Error: use of deleted function
    z1.Foo('a'); // Error: use of deleted function
}
2. Concepts

In C++ 20 concepts were added and it is the proper way to address this problem. Let’s see an example:

C++
template<typename T> 
    requires std::same_as<T, int>
void Foo(T) {}

But we can do it in a shorter way using auto.

C++
concept is_integer = std::same_as<T, int>;

void Foo(is_integer auto) {}

User defined conversions in C++

C++ is one of those languages that give us tools to play with almos every aspect of an implementation. Usually, programming languages with type conversions have some conversiones already defined by the standard. In this case, C++ allow us to define our owns conversions. In the next code snippet we can see an explicit and implicit conversion between two custom types. Both structs recieve 2 std::strings& and 1 int and implement custom casting to std::string.

C++
struct FullNameExplicit {
    explicit FullNameExplicit(const std::string& name, const std::string& second_name, int age) :
    name(name),
    second_name(second_name),
    age(age) {}

    explicit operator std::string() const {
        return name + ' ' + second_name + " has " + std::to_string(age) + '\n';
    }

    std::string name;
    std::string second_name;
    int age;
};

struct FullNameImplicit {
    FullNameImplicit(const std::string& name, const std::string& second_name, int age) :
    name(name),
    second_name(second_name),
    age(age) {}

    operator std::string() const {
        return name + ' ' + second_name + " has " + std::to_string(age) + '\n';
    }

    std::string name;
    std::string second_name;
    int age;
};

void Foo(const std::string person) {
    std::cout << person;
}

int main() {
    FullNameExplicit fne("Ruben", "Rubio", 24);
    Foo(fne); // Error: implicit conversion not defined.
    Foo(static_cast<std::string>(fne));
    
    FullNameImplicit fni("Ruben", "Rubio", 24);
    Foo(fni);
    Foo(static_cast<std::string>(fni));
}

Conclusion

In my humild opinion, I think we should avoid implicit conversion as much as possible. Particularly, when working with other people involved in the code they may not be aware of the implicit conversions you are using and this can tend to get lost easily in a large project.

References

  1. https://en.cppreference.com/w/cpp/language/cast_operator
  2. https://en.cppreference.com/w/cpp/language/explicit
  3. https://stackoverflow.com/questions/121162/what-does-the-explicit-keyword-mean

ADL (Argument-dependent lookup) explained

ADL also known as argument-dependent lookup or Koenig lookup (even thought he said that he have not discovered it), is a very old and unfamiliar C++ feature.

ADL work is to set a couple of rules to lookup for functions based on their namespaces parameters provided, e.g:

C++
int main() {
    std::vector<int> v;
    
    auto it = std::begin(v); // Common std::begin function.
    auto itAdl = begin(v); // Also calling std::begin because 'v' is in the std namespace.
}

This is a common piece of code in C++ that everyone has written without knowing why exactly works. In this case both ways are equivalent because they are calling std::begin. The first one is called directly and the second one is found thanks to ADL set of rules.

This is very powerfull specially when working with operators like the example below:

C++
int main() {
    const std::string& out = std::string("Hello") + "world";
    std::cout << out;
}

There is neither a + or << global operator but thanks to ADL it is smart enought to look for them in their relative namespaces. Let’s take a look what are the real code generated by the compiler using https://cppinsights.io/

C++
int main() {
  const std::basic_string<char, std::char_traits<char>, std::allocator<char> > & out = std::operator+(std::basic_string<char, std::char_traits<char>, std::allocator<char> >(std::basic_string<char, std::char_traits<char>, std::allocator<char> >("Hello", std::allocator<char>())), "world");
  std::operator<<(std::cout, out);
}

Both operators have been converted to std::operator calls.

Another very cool feature is to prioritize our own function calls when overriding some std implementations:

C++
template<typename T>
int accumulate(T begin, T end, int sum) {
    return 42;
}

int main() {
    std::vector<int> values{10,30,10};
    int sum{0};
    accumulate(values.begin(), values.end(), sum); // Returns 42.
}

In this case if our own accumulate implementation have not been provided, std::accumulate would be called instead.

Obviously we can take advantage of this an use it in our own code. Even thougt I personally think it is a better practice to always specify the namespace on our functions and objects, it could be a very powerfull solution if at some time we want to change a large piece of code just by swapping namespaces.

C++
namespace ns1 {
    struct X{};
    void g(const X x) {}
    void f(const X x) {}
}

namespace ns2 {
    struct X{};
    void g(const X x) {}
    void f(const X x) {}
}

int main() {
    ns1::X x;
    g(x); // ns1::g(ns1::X) is called.
    f(x); // ns1::f(ns1::X) is called.
}

In this particular example if we change the namespace in the object declaration, all the function calls would also change.

References

  1. https://en.cppreference.com/w/cpp/language/adl
  2. https://www.drdobbs.com/cpp/a-personal-note-about-argument-dependent/232901443
  3. https://www.youtube.com/watch?v=agS-h_eaLj8&ab_channel=C%E1%90%A9%E1%90%A9WeeklyWithJasonTurner
  4. https://stackoverflow.com/questions/8111677/what-is-argument-dependent-lookup-aka-adl-or-koenig-lookup

return false vs return true

Introduction

You might think that this is a stupid debate, and maybe you are right but let me take a moment to explain to you if we should care whether to return true or false.

True and false are the basis in computer programming and traditional logic. The binary system is used based on this only two possibilities, the value is either one or zero.

To understand if returning true or false has an impact in our code performance we have to talk about how computers work in a very low level, in specific I’m going to talk a bit about x86-64 assembly and different C++ compilers.

Benchmarking

Once we compile our code in C++ the compilers convert the code into assembly code. In assembly we usually talk about number of instructions instead of number of lines. And even different instructions can take different number of cycles to be processed in our CPU. Okey, let’s see how return true and return false is compiled into assembly code using GCC 11.2 and Clang 12.0.1. Both without any optimizations on.

Clang 12.0.1 -O0
C++
/*
    push    rbp 
    mov     rbp, rsp
    xor     eax, eax
    and     al, 1
    movzx   eax, al
    pop     rbp
    ret
*/
bool ReturnFalse() {
    return false;
}

/*
    push    rbp
    mov     rbp, rsp
    mov     al, 1
    and     al, 1
    movzx   eax, al
    pop     rbp
    ret
*/
bool ReturnTrue(){
    return true;
}
GCC 11.2 -O0
C++
/*
    push    rbp
    mov     rbp, rsp
    mov     eax, 0
    pop     rbp
    ret
*/
bool ReturnFalse() {
    return false;
}

/*
    push    rbp
    mov     rbp, rsp
    mov     eax, 1
    pop     rbp
    ret
*/
bool ReturnTrue(){
    return true;
}

As we can see Clang takes 4 more instructions than GCC to do the same piece of code. Now let’s take a look what happens when we turn optimizations on (-O3) in both compilers.

Clang 12.0.1 -O3
C++
/*
    xor     eax, eax
    ret
*/
bool ReturnFalse() {
    return false;
}

/*
    mov     al, 1
    ret
*/
bool ReturnTrue(){
    return true;
}
GCC 11.2 -O3
C++
/*
    xor     eax, eax
    ret
*/
bool ReturnFalse() {
    return false;
}

/*
    mov     eax, 1
    ret
*/
bool ReturnTrue(){
    return true;
}

Now both compilers are able to perform both tasks in only 2 instructions. But as I mention before all instructions are not the same, let’s take a moment to analize this in machine code.

The instruction mov definitions is: “Copies the second operand (source operand) to the first operand (destination operand)”. Wich means that we are copying the right value to the left register. And its translation to machine code is:

ShellScript
mov eax, 1 # b8 01 00 00 00
ShellScript
mov al, 1  # b0 01

Why are the machine code different if both instructions perform the same operation? This is because copying a value into a register depends on the register. In this case eax is a 32 bits register meanwhile al is an 8 bit subset of eax register.

x86-64 register explanation by: https://www.tutorialspoint.com/assembly_programming/assembly_registers.htm

On the other hand, the xor definition says: “Performs a bitwise exclusive OR (XOR) operation on the destination (first) and source (second) operands and stores the result in the destination operand location“. A classic XOR logic operation which has the advantage that if done with the register itself it will always become 0. The CPU is extremely optimized to perform this kind of bitwise operations.

XOR gate output by: https://sites.google.com/a/cecytebc.edu.mx/audg_2014-ii_tics/mecatronica/2bmt-digitales

Conclusion

Returning 0 (false) seems to be better than returning 1 (true) but the difference it is almost indistinguishable. Even thought it is always a good practice to analize your problem and try to optimize it as much as you can, e.g: You can not always return false instead of true, what you can is to study the percentage of times your result will be true or false. This is a common practice when developing in assembly code specially when you have to deal with some if-else and you really want to just ride of the evaluations as fast as possible.

References

  1. https://randomascii.wordpress.com/2012/12/29/the-surprising-subtleties-of-zeroing-a-register/
  2. https://qastack.mx/programming/33666617/what-is-the-best-way-to-set-a-register-to-zero-in-x86-assembly-xor-mov-or-and
  3. https://godbolt.org/z/reTEPE3En

What happens with std::vector<bool>?

If you know a bit of modern C++ you will have use the std::vector<T> container a lot of times without even wondering what type you specify to instantiate the container. This is fine for every case except for on specific one, std::vector<bool>.

If you go to the std::vector specification you will find that there is only one specification which is std::vector<bool>. That’s because the bool type specification is implemented outside the standard std::vector<T> container. The reason for this could be pretty obvious and logic for you but it could also be a headache for others who try to use it.

As you may know one bool has the size of 1 byte in the C++ standard. This may make us think why we should use 8 bits when we can know if a bool is true or false just with 1 bit of information, if it’s either 1 = true or 0 = false. Well, that’s exactly what the C++ commitee thought back in the days and decided to use only 1 bit to represent the value in the container, in this way the can store up to 8 values just in 1 byte of memory which means 8 more values than using a standard boolean.

And with that decision is when the problems come. As you may know, a reference is just a memory adress to the beginning of a specific data, which means that you can point to the start of something and increase this position byte by byte.

C++
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vector_int{1, 2};
    
    std::cout << &vector_int[0]; // 0x1e06eb0
    std::cout << &vector_int[1]; // 0x1e06eb4
}

As you can see the offset between the first and the second integer is 4 bytes because that is the size of an int in C++ standard. Now lets try the same with std::vector<bool>.

C++
#include <vector>
#include <iostream>

int main() {
    std::vector<bool> vector_bool{true, false};
    
    std::cout << &vector_bool[0]; // error: taking address of rvalue.
}

The error the compiler give us can be easily understandable by checking out std::vector<bool> specification.

  • Exposes class std::vector<bool>::reference as a method of accessing individual bits. In particular, objects of this class are returned by operator[] by value.

And for the same reason you can’t take values by reference using base-ranged loops which are implemented based on begin() and end().

C++
#include <vector>
#include <iostream>

int main() {
    std::vector<bool> vector_bool{false, true};
    std::vector<int> vector_int{1, 2, 3};

    for (int& i : vector_int) {
        // OK.
    }

    for (bool& b : vector_bool) {
        // error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
    }
   
}

Finally, to show the final evidence about the difference between std::vector<T> and std::vector<bool> we can see their sizes in bytes.

C++
int main() {
    std::cout << sizeof(std::vector<int>);   // 24 bytes.
    std::cout << sizeof(std::vector<bool>);  // 40 bytes.
}

Spark Engine

Spark engine logo

Spark Engine is a graphic engine made from scratch using C++ 17 and OpenGL. Spark Engine has the ability to render 3D and 2D objects and its main object is to be used for videogames and graphics shows.

Among all its features we can mention the ability to render dynamic lighting, shadows, and a full integrated particle system. It is also capable to generate and render custom vegetation on an optimized way. Its frustum feature bring the user the posibility to only render what the user is seeing to improve the performance.

The engine can be used in Windows or Linux as a dynamic library for C++. The source code can be found in the open github repository.

Spark Engine in game render from Beast Brawl.