C++ Benchmark - std::list VS boost::intrusive::list
Recently, we saw that the std::list performance was not really good when it comes to searching it or iterating through it.In this post, we will see an alternative to the std::list: the boost::intrusive::list from the Boost C++ libraries. It is not a well known library but it can be useful in some specific cases. I will focus on how this implementation performs compared to an std::list.
An intrusive list does not store copies of the object but the objects itself. Because it stores the objects, it is necessary to add information to the object data structure directly to link them together, that is why it is called an intrusive list. This has a big advantage, the list does not have to allocate any memory at all to insert objects. In a std::list if you insert an object, a node object will be created containing a copy of the object, but not in an intrusive list where only the pointers to the next and to the previous element of the inserted object are updated. Another advantage is that if you have a reference to an object you can directly obtain an iterator to this object in O(1), an operation that would be in O(n) with a std::list. Iteration is faster because it needs less memory accesses.
On the other hand, an intrusive list has also several drawbacks. First of all, it is intrusive. It means that you have to change the definition of the type that is stored inside the intrusive list. Then, and it be very complicated, it is up to the developer to manage the life time of the objects. It means that it is up to you to allocate and deallocate memory for each objects that you want to put in your collection. For instance, if you store an object into an intrusive list and later delete this object without removing it from the list, you will have broken you list. It is also less safe because the container can be modified from outside simply by modifying the pointers directly inside the objects.
This article is not a tutorial for Boost intrusive collections, I will just focus on the performance aspect, if you want to learn how to use them, you can consult the official documentation.
A boost::intrusive::list can be configured in three mode:
- Normal mode: No special features
- Safe mode: The hook is initialized to a default safe state and the container check this state before inserting a value. The state of a removed node is also updated correctly. It can be used to detect programming errors. It implies a small performance overhead. This is the default mode.
- Auto unlink mode: When an object gets destructed it is automatically removed from the container. This mode has also the properties of the safe mode.
The mode is chosen at constant time by configuring the hook of the data type. In this article, all three mode will be tested. Here are the four types that will be tested:
- list : std::list
- normal_ilist : boost::intrusive::list in normal mode
- safe_ilist : boost::intrusive::list in safe mode
- auto_unlink_ilist : boost::intrusive::list in auto unlink mode
The data types are varying in size, they hold an array of longs and the size of the array varies to change the size of the data type. In each graph, the size of the data type is indicated. It is the size of the normal data type. The intrusive data types are always 16 bytes bigger than the normal data types.
In the graphs and in the text, n is used to refer to the number of elements of the collection.
All the tests performed have been performed on an Intel Core i7 Q 820 @ 1.73GHz. The code has been compiled in 64 bits with GCC 4.7.2 with the given options: -std=c++11 -O2 -fomit-frame-pointer -march=native
For each graph, the vertical axis represent the amount of time necessary to perform the operations, so the lower values are the better. The horizontal axis is always the number of elements of the collection. For some graph, the logarithmic scale could be clearer, a button is available after each graph to change the vertical scale to a logarithmic scale.
So let's see these data structures in practice.
Fill list
The first test that is performed is how long does it take to fill each data structure. For the std::list, each value is entered directly. For the intrusive list variations, the data are entered into a vector and then pushed back to the intrusive list.
So, let's test them:
We can see that filling a list is about thrice slower than an intrusive version. This is quite logical because there are much less memory allocations in the case of the intrusive lists. The differences between the different intrusive versions are not very big. The normal version is the fastest, then the auto unlink and finally the safe version is the slowest.
If we increase the size of the data type a bit:
The results remains more or less the same, but this time there is less difference between list and intrusive list.
This time, the results are really different. The intrusive versions are twenty times faster than a standard list. This comes from dynamic allocations of large blocks that is very expensive. In the case of intrusive list, there are no memory allocations, just modifications of pointers, so it it is normal that for big blocks the difference is higher.
We can see that for push_back operations, the intrusive are clearly faster. For small data types, they can be up to three times faster. The difference can be much higher with very big data types. There are no big differences between the different versions of the intrusive lists. The normal mode is about 10% faster than the safe mode.
Destruction of list
The second test is about the time necessary to destruct a collection. For a list, the list is simply allocated on the heap and destructed with delete operator. For an intrusive list, both the vector and the list are allocated on the heap. The time is computed to delete both the vector and the intrusive list.
Let's take a look at the results:
The impressive result is that the normal mode is almost free. It is normal because the destructor of the objects does not do anything. Neither the list does anything about the state of the object after it has been removed. The other two intrusive versions performs the same and twice faster than a list.
Let's increase a bit the size:
This time, the std::list version is getting closer to the auto unlink and safe versions. The auto unlink version is a bit slower than the safe version. The normal mode is still free.
Increasing it a bit again:
We can see that the list is a small bit faster than the other two versions.
If we push the memory to its limit:
This time, the list is again slower. I'm not sure of why this happens, but it is certainly because of the memory allocator that has two allocate too many big blocks, which tends to be more costly than many small.
For the destruction, the normal mode proved its high strength, being totally free to destroy. The safe and auto unlink modes are proving much more expensive during destruction, but still quite a bit faster than a standard list.
It is also necessary to keep in mind that the destruction is generally not a common operation and is about 4 times faster than insertion. In practice, neither push_back nor destruction are critical in choosing a data structure.
Linear Search in a list
The next operation that will benchmark is the linear search. The container is filled with all the numbers in [0, n] and shuffled. Then, each number in [0, n] is searched in the container with std::find that performs a simple linear search.
How do the different data structures perform:
As expected, the intrusive list versions are faster than the standard list. The margin is about 40%. The intrusive versions have a better locality than the standard list because there is one less indirection.
Increasing the data type size:
The margin has decreased a bit to about 15%. As the data object does not fit in cache we have higher cache misses rate.
If we increase it to the maximum:
Again, the margin decreased, to 3%.
For linear searching, the intrusive versions are clearly faster, however, not by a high advantage and this advantage tends to get lower with bigger data types. I would really have expected a more interesting result here. We will see with the next results if it gets better.
Iteration over a list
This time, we will test the iteration over a whole collection. The iterate is done with the C++11 foreach loop (taking a reference) and the data is used to increment a counter (to make sure the loop is not optimized away.
Let's start with our small data type:
The standard list is indeed slower than the other versions (by about 20%). Which is expected due to their better data locality. However, the results are not very stable (probably too fast, many things can intervene). I was expecting better results.
Let's go with a higher data type:
This time, the results look better, but there are less difference between the standard list and the intrusive versions. The intrusive versions are faster by about 10%.
If we take a bigger data type:
This time, there is no more difference between the different versions.
Just like the results for linear search, the intrusive versions are faster but the difference is not huge. For very small data type, there is a gain of about 15 to 20 percent, but on very big data types, there is no more increase in performance. Again, I would have expected better results for the intrusive versions.
Write to elements of the list
This test is almost the same as the previous one, but this time each element of the collection is modified by incrementing one of its field.
Let's see if the results are different this time.
The results are more stable than before. We can see that the normal mode is leading the results by a bit less than 30%. Just like for iteration, there no real difference between the different modes.
Let's increase the data size by a bit:
The results are the same, still 30% better for the intrusive version.
Bigger data type again:
This time, the intrusive version is not faster anymore than the standard list.
We have seen that when write is made to the data, intrusive list are better than list. The margin is higher than when doing only iteration.
Reverse the list
Let's test something more useful with a reverse operation. The reverse member function is used to reverse all the containers.
Let's see how they perform:
The intrusive versions are about 25% faster than standard list. Even if reversal does not need to access the values, the pointers of the intrusive lists have a better locality than the one of a list that can be dispersed through memory.
The performance improved a bit, to 30% improvement for an intrusive list.
Let's see if this continue:
It did, the intrusive list is more than 40% faster than the standard list !
What happens a bigger one:
The lines have been interchanged! This time the standard list is about 25% faster than the intrusive versions. This time, the better locality of the intrusive versions is not a gain but a loss.
It is logical that the margin decrease with very big objects during reversal. Indeed, each element is very close one to another, but the pairs of pointers are separated by the size of the data type. The bigger the data type, the higher distance between the pointers and so the worse spatial locality for the pointers. However, I do not explain why there is this big difference...
The performance of intrusive list are clearly interesting for reversing collection of small data types. However, it seems that for high data types, the standard list is faster.
Sort the list
Let's continue with an even more interesting operation, sorting the list. All the versions are sorted with the sort member function.
The intrusive versions are really interesting, being twice faster than a standard list.
Let's see with a see a higher data type:
The difference is decreasing to about 20%.
Increasing it again:
It decreased again to 18%.
For sort operations, the intrusive versions are clearly interesting, especially for small data types.
Random insert into the list
The last operation that we will test is the random insert. I have to say that this test is not fair. Indeed, in an intrusive list, from an object we can directly get an iterator and insert at a random position. For a standard list, we have to find the iterator by linear search. I think that it is still important because it is one of the advantages of an intrusive container.
It is very clear that the performance are much better but it is logical because we are comparing something in O(1) versus something in O(n).
Conclusion
In conclusion, intrusive lists are almost always faster than a standard list. However, on my computer and with GCC, the difference is not always very important. It can brings about 20%-30% on some workloads but most likely around 15%. Even if not negligible, it is not a huge improvement. I would have thought that intrusive lists were faster by an higher margin. On some operations like sort, it is clearly more interesting. It has a better data locality than standard list.
It is also more interesting to fill the collection, because no memory allocation is involved. But of course, you need to take care of memory allocation by yourself, for example in a vector like here or by dynamically allocating the objects one after one. This has also a cost that is not counted in the benchmark.
If you really have to use a linked list and performance is critical, I advice you to use Boost intrusive list. If performance is not really critical, it is not perhaps not interesting because of the increased complexity.
There are situations when only intrusive lists can work. If you want the same object to be present in two different list, you can use boost intrusive list with several member hooks, which is not possible with standard list because only a copy is stored, not the object itself. The same is true for objects that are non-copyable, only intrusive list can handle them. And finally, with intrusive lists you can directly get an iterator to an object in O(1) if you have a reference to an object. For a standard list, you have to iterate through the list to find the object. Sometimes, it can be very useful.
If you are interested, the Boost documentation provides also a performance benchmark for intrusive list, but it is very old (GCC 4.1.2). It is interesting to see that the results are better for intrusive lists than on my benchmark. I do not know if it comes from the processor, the memory or from the compiler.
I hope you found this benchmark interesting. If you have questions, comments, ideas or whatever to say about this benchmark, don't hesitate to comment. I would be glad to answer you :) The same if you find errors in this article. If you have different results, don't hesitate to comment as well.
The code source of the benchmark is available online: https://github.com/wichtounet/articles/blob/master/src/intrusive_list/bench.cpp
Comments
Comments powered by Disqus