Немного о том, почему использование STL бывает неоптимальным

В этой небольшой заметке пойдет речь о том, как легко и просто можно убить производительность приложения с помощью библиотеки STL. Охватить всю библиотеку в рамках этого топика не возможно, поэтому будет рассмотрен только один компонент – контейнер std::string. В качестве примера будет показана цена инициализации std::string и, как следствие, продемонстрировано, к чему может привести неоптимальное использование библиотеки. Все нижесказанное особенно остро относится к области gamedev-а.


Итак, в качестве примера возьмем примитивную функцию вычисления хэш-значения строки. Приведу две реализации – одну в c-style, вторую – stl-style с использованием std::string. Ссылка на исходный код тестового примера.

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

* This source code was highlighted with Source Code Highlighter.

Прошу обратить внимание на то, что в функции фактически будут передаваться си-шные строки (const char*), таким образом, во втором случае будет происходить создание временного объекта std::string. Повторюсь, суть тестов – показать цену инициализации STL-строки.

Теперь замерим скорость выполнения функций, для достоверности результатов тестов сделаем циклы вычислений из 256*1024 проходов. Для каждой функции будет замерена производительность на разных размерах строки в 8, 16 и 32 байт (об этом будет подробнее описано чуть ниже).

1. #define ITERATION_COUNT 256*1024
2.  
3. // ...
4. for (int i = 0; i < ITERATION_COUNT; ++i)
5.     h1 = hash_c(str);
6.  
7. // ...
8. for (int i = 0; i < ITERATION_COUNT; ++i)
9.     h2 = hash_stl(str);

* This source code was highlighted with Source Code Highlighter.

Примечание: пример собирался компилятором от 2010 студии из командной строки, ключики компилятора приведены рядом.

1. cl /EHsc /O2 main.cpp
2.  
3. *************************************
4. string length: 8 bytes
5. const char*: 6.20 msec, hash: 312017024
6. std::string: 12.62 msec, hash: 312017024, 2.04x
7.  
8. total allocs: 0
9.  
10. *************************************
11. string length: 16 bytes
12. const char*: 11.78 msec, hash: 2657714432
13. std::string: 131.21 msec, hash: 2657714432, 11.14x
14.  
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
20.  
21. total allocs: 262144

* This source code was highlighted with Source Code Highlighter.

Здесь начинается самое интересное. По результатам тестов видно, что самая маленькая просадка в производительности составляет 2 раза, самая большая – 11 раз. При этом для строк с размером более 16 байт появляются дополнительные аллокации на heap-е. На 32-х байтных строках затраты на выделения памяти немного нивелируются на фоне вычислений и просадка составляет чуть меньше — почти в 2 раза ниже, чем на строках длиной 16 байт. Откуда появляются аллокации?

std::string имеет свой внутренний буфер для хранения строки, размер которого зависит от реализации STL. К примеру, в реализации STL из состава MS Visual Studio 2010 размер этого буфера равен 16 байт, о чем можно убедиться, заглянув в заголовочные файлы библиотеки (переменная _BUF_SIZE). При инициализации std::string происходит проверка на размер строки и в случае, если он меньше размера внутреннего буфера, строка сохраняется в этом буфере, иначе – происходит выделение памяти нужного размера на heap-е, и уже туда копируется строка. Как видим, при каждой инициализации std::string как минимум происходит копирование данных, а также дополнительные аллокации в случаях, если размер строки превышает размер внутреннего буфера std::string. Именно поэтому мы можем наблюдать падение производительности в релизной сборке вплоть до 11 раз в купе с аллокациями, которые приводят к фрагментации памяти. Последний момент является серьезной проблемой в мире консолей, где объем оперативной памяти жестко фиксирован и отсутствует виртуальная память.

Теперь, пожалуй, стоит привести результаты тестов в дебаг сборке.

1. cl /EHsc /MDd /RTC1 /ZI main.cpp
2.  
3. *************************************
4. string length: 8 bytes
5. const char*: 24.74 msec, hash: 312017024
6. std::string: 4260.18 msec, hash: 312017024, 172.23x
7.  
8. total allocs: 262144
9.  
10. *************************************
11. string length: 16 bytes
12. const char*: 34.87 msec, hash: 2657714432
13. std::string: 7697.69 msec, hash: 2657714432, 220.76x
14.  
15. total allocs: 524288
16.  
17. *************************************
18. string length: 32 bytes
19. const char*: 58.38 msec, hash: 3820028416
20. std::string: 14169.49 msec, hash: 3820028416, 242.70x
21.  
22. total allocs: 524288

* This source code was highlighted with Source Code Highlighter.

Отлично! Просадка производительности в эпичные 240 раз! Что и следовало ожидать. Конечно, в критических ситуациях можно изменить Debug Information Format c /ZI (edit & continue) на более быстрый /Zi, а также выключить различные проверки на срыв стека и неинициализированные переменные (/RTC1), и тем самым добиться более высокой производительности, но в таком случае пропадет весь смысл дебаг сборки.

Мораль. STL, без сомнения, инструмент удобный и мощный, однако нужно иметь представление о том, как он устроен и, из ходя из этого, тщательно выбирать места где его использование не приведет к печальным последствиям. И это относится не только к std::string, но и к другим компонентам. Поэтому, прежде чем использовать STL, нужно дважды думать про аллокации на heap-е, про фрагментацию памяти и про локальность данных.

Успехов в оптимизациях!