Geekly Articles each Day
📜 ⬆️ ⬇️

A little bit about why using STL can be suboptimal

In this small note we will talk about how you can easily and easily kill application performance with the help of the STL library. It is not possible to cover the entire library within this topic, therefore only one component will be considered - the container std :: string. As an example, the initialization price of std :: string will be shown and, as a result, it will be demonstrated what the non-optimal use of the library may lead to. All of the following is particularly acute in the gamedev area.


So, as an example, take the primitive function to calculate the hash value of a string. I will give two implementations - one in the c-style, the second - stl-style using std :: string. Link to the source code of the test case.

uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  1. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  2. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  3. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  4. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  5. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  6. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  7. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  9. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  10. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  11. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  12. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  13. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
  14. uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .
uint32 hash_c( const char * str) { uint32 h = 0; const int len = strlen(str); for ( int i = 0; i < len; ++i) h = 31*h + str[i]; return h; } uint32 hash_stl( const std:: string & str) { uint32 h = 0; for (std:: string ::const_iterator it = str.begin(); it != str.end(); ++it) h = 31*h + + *it; return h; } * This source code was highlighted with Source Code Highlighter .

')
I ask you to pay attention to the fact that s-shnye strings (const char *) will actually be passed to the function, so in the second case, a temporary object std :: string will be created. Again, the essence of the tests is to show the initialization price of the STL string.

Now we will measure the speed of the functions, for the reliability of the test results we will make the calculation cycles of 256 * 1024 passes. For each function, the performance will be measured at different line sizes of 8, 16 and 32 bytes (this will be described in more detail below).

  1. #define ITERATION_COUNT 256 * 1024
  3. // ...
  4. for ( int i = 0; i <ITERATION_COUNT; ++ i)
  5. h1 = hash_c (str);
  7. // ...
  8. for ( int i = 0; i <ITERATION_COUNT; ++ i)
  9. h2 = hash_stl (str);
* This source code was highlighted with Source Code Highlighter .


Note: the example was collected by the compiler from the 2010 studio from the command line, the keys of the compiler are given nearby.

  1. cl / EHsc / O2 main.cpp
  3. **************************************
  4. string length: 8 bytes
  5. const char *: 6.20 msec, hash: 312017024
  6. std :: string : 12.62 msec, hash: 312017024, 2.04x
  8. total allocs: 0
  10. **************************************
  11. string length: 16 bytes
  12. const char *: 11.78 msec, hash: 2657714432
  13. std :: string : 131.21 msec, hash: 2657714432, 11.14x
  15. total allocs: 262144
  16. **************************************
  17. string length: 32 bytes
  18. const char *: 23.20 msec, hash: 3820028416
  19. std :: string : 144.64 msec, hash: 3820028416, 6.24x
  21. total allocs: 262144
* This source code was highlighted with Source Code Highlighter .


This is where the fun begins. The test results show that the smallest performance drawdown is 2 times, the largest - 11 times. In this case, for rows with a size of more than 16 bytes, additional allocations on heap appear. On 32-byte lines, memory allocation costs are slightly leveled against the background of calculations and the drawdown is slightly less - almost 2 times lower than on lines with a length of 16 bytes. Where do allocations come from?

std :: string has its own internal buffer for storing a string, the size of which depends on the implementation of STL. For example, in the implementation of STL from MS Visual Studio 2010, the size of this buffer is 16 bytes, as can be seen by looking at the library header files (_BUF_SIZE variable). When std :: string is initialized, a check for the size of the string occurs and if it is smaller than the internal buffer size, the string is saved in this buffer, otherwise, the memory is allocated to the desired size on the heap, and the string is already copied there. As you can see, every time std :: string is initialized, at least data is copied, as well as additional allocations in cases where the size of the string exceeds the size of the internal std :: string buffer. That is why we can observe a drop in performance in the release assembly up to 11 times, coupled with allocations, which lead to memory fragmentation. The last point is a serious problem in the world of consoles, where the amount of RAM is fixed and there is no virtual memory.

Now, perhaps, it is worthwhile to bring the test results in the debug build.

  1. cl / EHsc / MDd / RTC1 / ZI main.cpp
  3. **************************************
  4. string length: 8 bytes
  5. const char *: 24.74 msec, hash: 312017024
  6. std :: string : 4260.18 msec, hash: 312017024, 172.23x
  8. total allocs: 262144
  10. **************************************
  11. string length: 16 bytes
  12. const char *: 34.87 msec, hash: 2657714432
  13. std :: string : 7697.69 msec, hash: 2657714432, 220.76x
  15. total allocs: 524288
  17. **************************************
  18. string length: 32 bytes
  19. const char *: 58.38 msec, hash: 3820028416
  20. std :: string : 14169.49 msec, hash: 3820028416, 242.70x
  22. total allocs: 524288
* This source code was highlighted with Source Code Highlighter .


Fine! Sink performance in epic 240 times! What should be expected. Of course, in critical situations, you can change Debug Information Format c / ZI (edit & continue) to a faster / Zi, as well as turn off various stack stall checks and uninitialized variables (/ RTC1), and thereby achieve higher performance, but in In this case, the whole point of the assembly is lost.

Morality. STL, without a doubt, is a convenient and powerful tool, but you need to have an idea of ​​how it works and, from this, carefully choose the places where its use will not lead to sad consequences. And this applies not only to std :: string, but also to other components. Therefore, before using STL, you need to think twice about allocation on heap, about memory fragmentation and about data locality.

Successes in optimizations!

Source: https://habr.com/ru/post/131598/

More articles:


All Articles