(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

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

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



 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Embarcadero » [2]
Написать редактору 
 Рекомендовать » Дата публикации: 01.11.2011 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Enterprise Connectors (1 Year term)
Delphi Professional Named User
Allround Automation PL/SQL Developer - 5 user license
ReSharper Ultimate - Commercial annual subscription
erwin Data Modeler Standard Edition r9.7 - Product plus 1 Year Enterprise Maintenance Commercial
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Программирование в AutoCAD
СУБД Oracle "с нуля"
Краткие описания программ и ссылки на них
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Требуется Краснодар: Java -разрабочик (2)
Обязанности: Разработка корпоративных backend-приложений для автоматизации розничных продаж...
 
Рабочее зеркало БК Мостбет - как найти? (3)
Узнайте обо всех особенностях по поиску рабочего зеркала БК Мостбет из нашей статьи...
 
Ставки на спорт (7)
Добрый вечер! Давно хочу попробовать зарабатывать на ставках. Что посоветуете? Стоит пробовать?
 
Поиск рабочих зеркал МарафонБет (2)
На сегодняшний день, просторы интернета позволяют нам легко найти зеркало на Марафон для входа в...
 
Слот Биг Бэнг (5)
Большой взрыв как правящая теория сотворения мира. Теперь вы можете поиграть слот Big Bang в...
 
 
 



    
rambler's top100 Rambler's Top100