В этой небольшой заметке пойдет речь о том, как легко и просто можно убить производительность приложения с помощью библиотеки STL. Охватить всю библиотеку в рамках этого топика не возможно, поэтому будет рассмотрен только один компонент - контейнер std::string. В качестве примера будет показана цена инициализации std::string и, как следствие, продемонстрировано, к чему может привести неоптимальное использование библиотеки. Все нижесказанное особенно остро относится к области gamedev-а.
Итак, в качестве примера возьмем примитивную функцию вычисления хэш-значения строки. Приведу две реализации - одну в c-style, вторую - stl-style с использованием std::string. Ссылка на исходный код тестового примера.
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.
Прошу обратить внимание на то, что в функции фактически будут передаваться си-шные строки (const char*), таким образом, во втором случае будет происходить создание временного объекта std::string. Повторюсь, суть тестов - показать цену инициализации STL-строки.
Теперь замерим скорость выполнения функций, для достоверности результатов тестов сделаем циклы вычислений из 256*1024 проходов. Для каждой функции будет замерена производительность на разных размерах строки в 8, 16 и 32 байт (об этом будет подробнее описано чуть ниже).
#define ITERATION_COUNT 256*1024
// ...
for (int i = 0; i < ITERATION_COUNT; ++i)
h1 = hash_c(str);
// ...
for (int i = 0; i < ITERATION_COUNT; ++i)
h2 = hash_stl(str);
* This source code was highlighted with Source Code Highlighter.
Примечание: пример собирался компилятором от 2010 студии из командной строки, ключики компилятора приведены рядом.
cl /EHsc /O2 main.cpp
*************************************
string length: 8 bytes
const char*: 6.20 msec, hash: 312017024
std::string: 12.62 msec, hash: 312017024, 2.04x
total allocs: 0
*************************************
string length: 16 bytes
const char*: 11.78 msec, hash: 2657714432
std::string: 131.21 msec, hash: 2657714432, 11.14x
total allocs: 262144
*************************************
string length: 32 bytes
const char*: 23.20 msec, hash: 3820028416
std::string: 144.64 msec, hash: 3820028416, 6.24x
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 раз в купе с аллокациями, которые приводят к фрагментации памяти. Последний момент является серьезной проблемой в мире консолей, где объем оперативной памяти жестко фиксирован и отсутствует виртуальная память.
Теперь, пожалуй, стоит привести результаты тестов в дебаг сборке.
cl /EHsc /MDd /RTC1 /ZI main.cpp
*************************************
string length: 8 bytes
const char*: 24.74 msec, hash: 312017024
std::string: 4260.18 msec, hash: 312017024, 172.23x
total allocs: 262144
*************************************
string length: 16 bytes
const char*: 34.87 msec, hash: 2657714432
std::string: 7697.69 msec, hash: 2657714432, 220.76x
total allocs: 524288
*************************************
string length: 32 bytes
const char*: 58.38 msec, hash: 3820028416
std::string: 14169.49 msec, hash: 3820028416, 242.70x
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-е, про фрагментацию памяти и про локальность данных.
Успехов в оптимизациях!