Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to write vector faster than STL, the content of the article is of high quality, so the editor will share it with you for reference. I hope you will have some understanding of the relevant knowledge after reading this article.

The self-developed version of vector is faster than std::vector in some scenarios. The main optimizations are:

There is some room for optimization for adding and deleting actions in std:: vector, because on the one hand, the memory is applied for release, on the other hand, the movement of T objects is relatively expensive, so there is some room for optimization for some scenarios. The key to optimization is to try to reduce the overhead of T object movement.

The test whether the flag can be optimized is a static bool value, which is mainly used to determine whether there is a pointer pointing to or relying on its own address inside the object T. The analysis result is obtained when the vector is created for the first time, and the Bool value is set. The detection code will not be executed when the same object is created later, so the detection overhead is minimal.

When it is detected that optimization processing is allowed, make the following performance optimizations:

1) avoid the optimization of T object movement:

The self-research library uses realloc to apply for memory expansion space, instead of using the conventional malloc way to apply for memory, so there is no need to copy data when expanding, which greatly improves the performance. the actual performance improvement multiple of this piece depends on how many times you can successfully apply for extended memory at the original address, as long as you can successfully expand the space at the original address, there is no need to move T objects, which greatly saves overhead.

2) reduce the overhead of creating and destructing T objects:

There are many internal implementations of functions such as erase () / insert () that need to move objects, which can be optimized in memmove / memcpy / memset mode, which can greatly improve performance (reducing the overhead of object creation and deconstruction)

3) there may be compatibility problems in the optimization of std::string:

At present, the first content of the default empty string in the std:: string version of gcc is the pointer to itself. In this case, moving T objects can only deal with T in the traditional std:: move way, which cannot be optimized. The performance is basically the same as the implementation of std library, with an error of 1%. Subject to T object is std::string, the code in this case is also optimized, I am afraid there will be compatibility problems.

Memory optimization: when it is detected that optimization processing is allowed, because the T object moves very fast, it can increase the number of T object movement, reduce space waste, and save half of the space. The overall performance is still twice as fast as std::vector.

1) when it is detected that optimization processing is allowed, change the expansion multiple of vector from the default 2x growth of gcc to 1.5x growth (that is, 8L12, 16jin24, 32, 48pc64.), in many cases, you can save half of the space. otherwise, the default 2x growth is used to provide the same performance as the std library.

2) modify the number of starting space: gcc default data start space size is 1, self-developed version default data start space size is 8, so as to waste a little space, to reduce the number of memory expansion, improve a little performance.

On how to write faster than STL vector to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.