Навигация
Главная »  Visual Studio 

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


Источник: habrahabrru
В этой небольшой заметке пойдет речь о том, как легко и просто можно убить производительность приложения с помощью библиотеки 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-е, про фрагментацию памяти и про локальность данных.

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



 

 Вышли релиз-кандидаты Visual Studio 2012, .NET Framework 4.5 и Windows Server 2012.
 Обработка Segmentation Fault в C++.
 Итоги конференции TechEd Russia 2011.


Главная »  Visual Studio 

© 2017 Team.Furia.Ru.
Частичное копирование материалов разрешено.