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 not 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).
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 big. 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