GitHub - P-p-H-d/c-stl-comparison: Comparison of generic container C libraries (STL like)

Introduction

The goal of this project is to compare several generic container C libraries that provide some STL like capabilities of the C++ (container template) but are targeting classic C language.

The Standard Template Library STL was a software library for the C++ programming language that influenced many parts of the C++ Standard Library. It provided a set of container classes for C++ that can be used with any type. Now the parts of the C++ Standard Library directly influenced/inherited from this STL are what are commonly called "the STL".

So, a STL like library for the C is a C library providing several classic generic containers for the C language, like vector, list, sorted set, unordered_map, and so on.

To do this, the same simple programs are implemented by the libraries in the more straight-forward way possible, for different kind of containers and for different types. Then the API ergonomics of each programs can be compared each other according to the user taste.

A benchmark to compare their performance is included in the bench directory.

Objective characteristics of the libraries are directly compared in this file.

But first, let's see how we can implement generic code in C.

Implementing generic code in C

One of the main issue in the C language is how to write generic code, i.e. code that works the same for different kind of objects: you write once, and it works for several types. A kind of equivalent of the templates of the C++.

There are several ways of doing so:

voidp: Everything is a pointer to void.

Each object is handled through a pointer to void. The container store only pointers to these objects. Potentially, it may also register some callback functions to handle the contained objects for the needed specialized methods (copy, drop, ...). From a user point of view, this makes the code harder to use and to debug (as you don't have any help from the compiler) and type unsafe since a lot of cast is needed to handle it (so no formal proof of the code is usually possible). This also generally generate slower code (due to the multiple reduction, indirect callback, increase memory usage and cache miss) even if using link time optimization and full inline functions could reduce this a little (with inlining and LTO, some callback overhead can be reduced but it is really dependent on the compilers and will increase your compilation time). Properly used, it can yet be the most space efficient for the code, but can consume more for the data due to the obligation of using pointers (depending on your use case). This is however the easiest to design & code.

Pros:

• easy to develop,
• reduced code.

Cons:

• slow code,
• data memory usage,
• hard to debug for user,
• type unsafe.

Note: See synthesis for mixing macros with typed handles and void * elements and creating hybrid solutions.

macro: Everything is a macro

Macros are expanded in the user code and used to access structures in a generic way (using known named fields of a structure — typically size, capacity, etc.). The macro is fully always expanded in the user code. From a user point of view, this can create subtle bugs in the use of the library (as everything is done through macro expansion in the user defined code) and hard to understand warnings. This can be mitigated using proper macros expansion and type checking, but it increases the complexity of the solution. This can generates fully efficient code. From a library developer point of view, this can be quite limiting in what you can offer.

This technique can also enforce the type consistency by encoding the type in the macro name or by using typeof/_Generic internally to check for the right types.

A key macro pitfall is evaluating arguments multiple times, and a good library should prevent misuse of this if possible.

Pros:

• fast to develop,
• efficient code.

Cons:

• potentially type unsafe,
• error prone,
• macro Side-effect,
• can have cryptic error message if usage is incorrect
• can have incorrect code usage without any error message if usage is incorrect

Note: Not to be confused with Template macros.

OO-style object

The objects inherited from all the same base object. The base object has a virtual table that provides the callbacks to all the methods needed to handle such object. The generic code is a simple classic C code that handles only the base object: therefore it uses the provided callback in its vtable to handle the object for any operation. This is an alternative to everything is a void pointer.

Indirect calls are usually slower even if modern CPUs and branch prediction often make this cost modest (the overhead may still be negligible).

It can be a good fit for a specialized API with only custom types and custom algorithms that don't need a lot of speed.

Pros:

• reduce code size
• support different kind of objects in the same container

Cons:

• data memory usage
• slow code
• new operation requires rework of vtable
• complex development

Generic objects

Another alternative is encapsulating the methods in macros that detect the type of the argument passed as parameter using _Generics, before calling the associated method according to the given type.

The C standard mandates to have valid C expressions in all cases of the _Generic. This is not a problem for very simple use of _Generic (such as the examples provided in the standard to return a different function depending on the types). But more advanced uses cannot be implemented so simply: they need to generate complex expression. Therefore, such library usually uses a double _Generic switch to overcome this limitation (increasing the number of used _Generic a lot and making code more awkward). There is discussion to remove this limitation in future C standards.

The difficulty is how to add pure user types in this generic switch (possible, just awkward and it needs high C skill level to do it).

Using this technique means using a lot of _Generic in the code. Real examples of it show notable slower compilation. Maybe it is due to compiler naive implementation of _Generic?

It is usually not used alone but with other technics (like void pointer or container instantiations) in order to create an hybrid approach.

As they need to hide the _Generic in a macro, they are subject to the key macro pitfall in evaluating arguments multiple times (a good library should prevent misuse of this if possible).

Pros:

• uniform interface provided to the user.

Cons:

• macro Side-effect shall be protected,
• support of custom user types is difficult.
• potential slow compilation

Intrusive container

A known structure is put in an intrusive way in the type of all the objects you wan to handle. From a user point of view, he needs to modify its structure and has to perform all the allocation & deallocation code itself (which is good or bad depending on the context). This can generate efficient code (both in speed and size). From a library developer point of view, this is easy to design & code. You need internally a cast to go from a pointer to the known structure to the pointed object (a reverse of offsetof) that is generally type unsafe (except if mixed with the macro generating concept).

This is quite limited in what you can do: you usually don't want to move your objects so any container that has to move some objects is not a good fit (which means that you cannot use the most efficient container). Indeed You can move intrusive objects if you update or rebuild the intrusive links appropriately, but it will be awkward and impact performance.

Intrusive containers are a good fit when object lifetime is managed externally (e.g., kernel structures) as all allocations are usually let to the user. They are also a good fit when the same object can be within several containers.

Pros:

• reduce code size
• efficient code
• external object lifetime

Cons:

• data memory usage
• limited scope of the containers

Template header

Header files are included multiple times with different macro contexts (which act as arguments of the header) in order to generate different code for each type.

From a user point of view, this creates a new step before using the container: an instantiating stage that has to be done once per type and per compilation unit (The user is responsible to create only one instance of the container, which can be troublesome if the library doesn't handle proper prefix for its naming convention). This instantiating stage generates the functions handling the container with the correct type, ensuring type safety and control by the compiler.

This instantiating stage can generate only the external interface (extern declaration), the implementation or inline implementation in function of what the user requests (reducing code bloat for containers which are heavily used so that only one instance exists in the whole program).

The debug of the library is generally reasonable. It can generate fully specialized & efficient code. Incorrectly used, this can generate a lot of code bloat. Properly used, this can even create smaller code than the void pointer variant. The interface used to configure the library can be quite tiresome in case of a lot of specialized methods for configuring the used user type: it doesn't enable to chain the configuration from a container to another one easily.

The user code is a little bit more verbose as it uses specialized function names, and not generic ones.

Pros:

• specialized & efficient code
• type safe
• easy to use for user
• reasonable to develop and understand

Cons:

• Explicit instance needed
• can generate code bloat if incorrectly used
• can have cryptic error message at instantiation stage if incorrectly used
• method names are more verbose
• unnatural usage of headers.

Template macros

Macros are used to generate context-dependent C code enabling to generate code for different type. This is pretty much like the template headers solution but with added flexibility. From a user point of view, this creates a new step before using the container: an instantiating stage that has to be done once per type and per compilation unit (The user is responsible to create only one instance of the container, which can be troublesome if the library doesn't handle proper prefix for its naming convention).

This can generate fully specialized & efficient code with the correct type ensuring type safety and control by the compiler. Incorrectly used, this can generate a lot of code bloat. Properly used, this can even create smaller code than the void pointer variant.

This instantiating stage can generate only the external interface (extern declaration), the implementation or inline implementation in function of what the user requests (reducing code bloat for containers which are heavily used so that only one instance exists in the whole program).

From a library developer point of view, the library is harder to debug: everything being expanded in one line, you can't step in the library (there is however a solution to overcome this limitation by adding another stage to the compilation process: generating the preprocessed file (-E), cleaning it of the lines directives, and recompiling this file). But this should not impact the user if the library is properly maintained.

This can also generates cryptic error messages at user level if incorrectly used when creating an instance. You can however see the generated code by looking at the preprocessed file.

You can perform heavy context-dependent customization of the code (transforming the macro preprocessing step into its own language): you can generate a variable number of methods depending on the given arguments of your instantiation, which is not possible easily with any other methods. Also, Properly done, you can also chain the methods from a container to another one easily, enabling quick and easy expansion of the containers. Errors in user code are easy to read and natural. Code usage is a little bit more verbose as it uses specialized function names, and not generic ones.

Template macros are not subject to the key macro pitfall of evaluating arguments multiple times.

Note: not to be confused with usage of Macro for meta-programming. Template Macros are much closer to Template Headers.

Note: Some people reported "issue" of the template macros with their look due to the use of backslash at the end of the lines however it is due to their coding practices (you need to align backslash at the same column). Another one of the reported "issue" is the lack of support of syntax highlighting and autocomplete in macros but... it was more an issue in their used text editor.

Pros:

• specialized & efficient code
• type safe
• easy to use for user
• maximum flexibility in code generation

Cons:

• Explicit instance needed
• can generate code bloat if incorrectly used
• little harder to debug for the library developer
• can have cryptic error message at instantiation stage if incorrectly used
• method names are verbose

Synthesis

Even if a container is usually slow, it may be a good fit for your use case. There is no universal answer.

Some hybrid patterns of the previous solutions (e.g., _Generic + templates, opaque wrappers around void *) can also be chosen for a specific usage, in order to mitigate the Cons of both solution, increasing their added value.

For example, a common pattern is to define the public API using some types (e.g., struct my_vec *), but internally performs some cast to void * to use functions on void pointers. This gives better ergonomics and some type safety at the container level, even if element type is ultimately erased.

In practice, Template headers are often the best compromise between ease of development and what is possible with it. Template macros are a little bit harder to develop but increases the generation possibility. void pointer solutions are often the one that generate the smaller code but at the cost of performance and harder debug at user level.

C libraries Selection

The following C libraries have been selected as their aim is to provide generic containers to the C language:

• C-Macro-Collections
• COLLECTIONS-C
• CTL by glouw or by rurban
• M*LIB
• STC - Smart Template Container for C
• CC
• GLIB
• STB_DS
• KLIB

with C++ STL used as the reference baseline.

The used versions for the manual comparison are:

More specialized C libraries which provides only one kind of container are not included in this chapter. sglib is not included due to being abandoned.

Feature Comparison

Analysis

The following characteristics are compared. The C++ STL is also included as reference. For a container of such library that encapsulates a collection of objects of basic type, the following criterions are analyzed:

• What is the license?
• What is the supported C language? (C89, C99, C11 or C23, with or without extension)
• Is it a pure C program? (no need for external preprocessor)
• Is it Header only?
• How is implemented the Generic mechanism? By using (VP) void pointer, (M) macro, (OO) Object Oriented, (GO) Generic objects, (IF) intrusive field, (TH) template header, (TM) template macro
• Is it type safe (aka. using an incompatible type produces at least a compilation warning)?
• Does it support of integer/floats as basic type?
• Does it support of struct POD data as basic type?
• Does it support of array as basic type?
• Does it support of object like data (needing custom constructor, copy, destructor...) as basic type?
• Does it support of C++ class as basic type?
• Does it support of Assignment semantics? (container uses the C Assignment operators to set object in them)
• Does it support of copy semantics? (container creates a proper copy of the object data as per the object semantic: if there is pointer in the structure, it performs a proper copy of the pointed objects)
• Does it support of move semantics? (container steals the ownership of the object given as parameter as per the object semantic, rendering the original object in a destroyed or nearly destroyed state)
• Can the container and its basic type be defined fully separately in the source code? (spatial separation: the association of the methods of the basic type to the needed operators of the container library can be defined when the basic type is defined -ensuring spatial coherency of the basic type- and not only when the container is defined)
• Does it support of an adaptation layer? (a way to transform the interface of the provided method of the basic type to the expected interface of the operator of the container without writing explicitly a wrapper)
• Does it support of basic 'emplace'?
• Does it support of multiple, enhanced 'emplace' based on the initialized arguments?
• Does it support of iterator abstraction?
• Does it support of sort algorithm?
• Does it support of sort algorithm with custom comparison?
• Does it support of single definition for the whole program? (use of declaration only for all files except one that includes the container definition)
• Does it support of full abstraction of the container type? (user shall not have to use internal fields)
• Does it support of contract violation checks? (assertions on invalid inputs, on input contract violation or error reporting)
• Does it support of natural usage of array? (using of Array subscripting on the container)
• Is the basic type stored in the container, not a pointer to it?
• Does it need an explicit instantiation of the container with the basic type before its usage?
• Are the functions properly prefixed?
• How are the memory errors handled? (return code, exception, abort, none)
• Are destructors of objects on stack properly called on exception?
• Does it support custom memory functions?
• Does it support optional per-container context for custom memory functions?
• Does it support of forward declaration of container?
• Does it support of serialization? (JSON, XML, YAML)

Synthesis

• C11*: means C11 + typeof extension
• C99*: means C99 + typeof extension
• Y*: Yes with some limitations.
• N*: even it appears to be type safe, it is not and it is easy to misuse it.
• NA: the question has no meaning for this library.

If you see any mistakes in this report, or want to include another C library, or want to include another point of comparison, do not hesitate to open a pull request.

Ergonomic comparison

Rules

The test programs shall respect the following conditions:

• it shall use a basic type (int), a non POD type (the type mpz_t of the GMP library) and a string as the primary type of the container.
• if a dynamic string container exists in the container library, it shall be used instead of a C string,
• it shall not comment the code (the code is assumed to be clear on what it does by itself) except if there is some workaround,
• it shall not produce any compilation warnings,
• it shall execute properly,
• it shall not leak any memory,
• it shall abort on error,
• it shall link dynamically with the GMP library (https://gmplib.org/) if needed,
• it shall link statically with the container library if needed,
• the optional assertions shall be turned off.

A workaround is defined as a way to implement this program which is not natural for the library. This typically includes:

• create wrapper structure,
• create wrapper functions or macros,
• accessing internal fields of the containers (typically for using the qsort function).

For example, if a container library manual requests to define some macro for its use, then it won't be considered as a workaround. Workarounds are allowed but are counted separately.

Array tests

The program shall perform the following operations:

• declare a dynamic array of int (resp. mpz_t, a string),
• initialize this array with the small unsigned integers values 17, 42 and 9 (performing a conversion from unsigned integer to mpz_t for GMP) or the constant strings "Hello", "World" and "!" for strings,
• sort this array,
• iterate the array to print the values.

Associative array tests

The program shall perform the following operations:

• declare a non-ordered associative array from int (resp. mpz_t, a string) to int (resp. mpz_t, a string),
• initialize this array with the association of signed integers values 17 to 4585, 42 to 4856 and -9 to 1452 (performing a conversion from signed integer to mpz_t for GMP) or the strings "Hello" to "LIB", "Welcome" to "Program" and "Sincerely" to "Your map" for strings,
• search for the key "Hello" and display it if successful,
• iterate the associative array to print the values.

Execution

The different programs are available in this repository. To build them, you just need to have a working C11 compiler, a make tool, git, the GMP library, and the GLIB library.

Simply run "make" to perform clones of the C libraries and generate the different executables.

Conclusion

What can be objectively compared is the size of the programs:

As ergonomic is a personal judgement, no conclusion will be provided. You should open the different provided programs and make your own choice based on your own ergonomic criteria:

• Readability
• Debuggability
• Maintainability

However, we can still conclude that even the best C library in this domain is more verbose than the C++.

Performance Comparison

The bench directory contains a benchmark comparing the performance of different C libraries (including some C++ ones, like STL and BOOST as references).

Time and memory usage are provided for these tests and the best run out of 3 is kept to remove external interference, which is a compromise between execution time and reliability. Compiler flags are -O2 -march=native.

More specialized C libraries are added. The tested C libraries are:

• Bstrlib (for string)
• CC
• CCC
• CMC
• Collections C
• CTL
• GLIB
• KLIB
• liblfds (for thread communication)
• libsrt
• M*LIB
• Pottery
• Qlibc
• SDS (for string)
• STC
• TOMMY DS
• UT HASH (for hash table)
• VERSTABLE (for hash table)
• XXHASH (for hash function)

Rather than measuring the performance of each individual methods exported by the library on some dataset, it measures the time taken by some test programs implementing a defined algorithm using the methods of the containers for this (to provide more real world examples). Of course, it doesn't mean that these algorithms match with your use cases, so you should take them with a grain of salt.

Each dataset size is chosen so that the time using by the best library is around 1 second (which is a compromise between execution time and reliability of the test result).

For the hash tables, the load factor is let at the default defined by the library. Instead we measure and rank the memory consumption during the test, the ones using a low load factor being necessarily at a disadvantageous.

The performance programs are performed around the following functionalities:

• sequence container (array, list and deque) where two containers are growing at the same time (on 64 bits type),
• sorted set container,
• unordered map container (on unsigned 64 bits type, on 256 bits type and on string type) with a 50% found/un-found ratio,
• unordered set container (on 32 bits type) with a low found/un-found ratio,
• string concat,
• string replacement,
• sort algorithm,
• hash function,
• multithread communication queue container.

Exact program exact behaviors, code source and dataset size are provided in the bench directory for further analysis.

Conclusion

Results are available for i5-3210M and for AMD EPYC 7763 (the latter is generated by CI).

The results are archived in git so that you can look at the history of the different runs. Thanks to that, the best rank and worst rank of the 10 previous runs are extracted: this enables detecting external interference during the run when the ranking is not stable. For example, the sequence container bench is also dependent on the performance of the kernel to allocate pages, and the top 5 libraries are challenger for the first place depending on how the kernel serves them during the bench. Extracting the best/worst ranks enables to have a better view of the relative performance of the libraries.

The conclusion is that the best C libraries can be much faster than the STL. Such libraries are all based on template-header or template-macros paradigm. This is due to the over specification of the C++ standard which prevents the STL to achieve good performances in all cases. Even for C++, more specialized C++ libraries (like boost) are needed to achieve good performance.

Continuous Integration

This project includes all sources used for this comparison and provides continuous integration to:

• perform the run of the benchmark,
• automated validation
• regression detection