Tips for Geeks. Часть 2

Оптимизация строковых операций - чуть ли не первое, что делает среднестатистический гик-оптимизатор. Эти оптимизации и собственные классы идут по популярности сразу после собственных коллекций. Впрочем, и программисты со стажем зачастую не прочь побаловаться со стрингами :)

В этой статье я рассмотрю довольно распостраненный случай - множественную конкатенацию константных строк в С++.

Представим, что нам надо составлять длинную строку из некого количества маленьких константных строк. К примеру, это могут быть опции, дефайны, запросы и пр.

Для примера пусть это будет выглядеть так:

void initString(int i, string & str)
{
    str.clear();
    str += "SOME_TEST_DATA";
    if (i % 2)
        str += ",DATA_MOD_02";
    if (i % 3)
        str += ",DATA_MOD_03";
    if (i % 5)
        str += ",DATA_MOD_05";
    if (i % 7)
        str += ",DATA_MOD_07";
    if (i % 11)
        str += ",DATA_MOD_11";
    if (i % 13)
        str += ",DATA_MOD_13";
    if (i % 15)
        str += ",MOD_15_EXTRA_DATA";
    if (i % 16)
        str += ",MOD_16_EXTRA_DATA";
    if (i % 21)
        str += ",MOD_21_EXTRA_DATA";
    if (i % 24)
        str += ",MOD_24_EXTRA_DATA";
    if (i % 25)
        str += ",MOD_25_EXTRA_DATA";
}

Операцию эту выполним в цикле, увеличивая i от 0 до 1000000:

string paramString;
paramString.reserve(1000);
int result = 0;
for(int i=0; i<1000000;i++)
{
    initString(i, paramString);
    result += paramString.size();
}

Сюда же добавим измерения скорости выполнения. Сразу предупрежу, что результаты заметно зависят от компилятора, процессора и системы в целом. Интересны они лишь для сравнения разных подходов.
С использованием std::string на Athlon 4200 и MS VC++ 2008 мы получаем ~600мс времени выполнения. Много это или мало? Как по мне, для миллиона итераций этого вполне достаточно. Но серия статей не зря называется Tips for Geeks :)

Что происходит, когда к переменной str добавляется "SOME_TEST_DATA"? Если места в буфере достаточно, то произойдет всего три действия: измерение длины добавляемой строки, копирование данных и смещение индекса в переменной str. Мы не сможем оптимизировать копирование и изменение индекса, но так ли нужно в этом случае измерение длин строк (т.е. перебор всех их символов в поисках '\0')? Ведь длину константной строки компилятор знает еще на этапе компиляции.

Для экспериментов сделаем собственный класс custom_string:

class custom_string
{
 char * m_data;
 int m_allocated;
 int m_size;
public:

 void reserve(int size)
 {
 ...
 }

 custom_string & operator += (const char * str)
 {  
  int size = strlen(str);
  reserve(size);
  memcpy(m_data + m_size, str, size + 1);
  m_size += size;
  return *this;
 }
};

Метод reserve проверяет, достаточно ли места в буфере и выделяет новый при необходимости. Код этого метода, как и конструктор с деструктором я опустил, чтобы они не отвлекали от основной задачи.

Наш тест с таким классом выполняется за те же самые ~600мс, как и с std::string. Есть как минимум два метода "подстегнуть" его работу.
Первый метод очень прост, но может отказаться работать при каких-либо дополнительных условиях, параметрах компиляции и пр. Он состоит в том, чтобы сделать код оператора более привлекательным для инлайнинга. Сделаем так:

 void append(const char * str, int size)
 {
  reserve(size);
  memcpy(m_data + m_size, str, size + 1);
  m_size += size;
 }

 custom_string & operator += (const char * str)
 {  
  append(str, strlen(str));
  return *this;
 }

Не смотря на то, что визуально код почти не изменился, время выполнения его на моем компьютере теперь составляет ~100мс. Я не смотрел в генерируемый ассемблерный код и не изучал причины, но первое, что приходит в голову - оператор += инлайнится, его вызовы заменяются на вызовы append, и расчет длины строки происходит именно на этапе компиляции. Так это или нет, не суть важно, потому что стабильность такой реализации под вопросом - оптимизация как появилась, так может и пропасть для Unicode строк, при сборке под другую ОС и пр., вне зависимости от бубнов __forceinline и нашего желания.

Более универсальный метод основывается на том, что константная строка в С++ может быть представлена в виде массива символов фиксированной длины. Такая запись вполне валидна:

 const char something [] = "something";

Для этого трюка мы используем темплейты:

 template<int N>
 custom_string & operator += (const char (&str)[N])
 {
  reserve(N - 1);
  memcpy(m_data + m_size, str, N);
  m_size += N - 1;
  return *this;
 }

В переменную N компилятор положит длину массива символов, включая и trailing zero.
Тест с таким методом выполняется на моем компьютере примерно за 140мс, что лежит в пределах статистической погрешности от предыдущего метода, но гарантированно будет работать, т.к. соответствует стандарту C++. Единственный недостаток в том, что для каждой длины строки будет создана новая копия метода конкатенации.

Можно ли таким образом "улучшить" std::string? Мои эксперименты показали, что прирост получается не существенный, порядка 50мс на исходном тесте. Такой трюк лучше использовать в собственных строковых классах, а по-честному лучше не использовать вообще (как и самописные классы для примитивов). Не стоит забывать, что сложение миллионов строк - экстраординарная ситуация, которая если и возникает, то редко бывает настолько критичной по времени. Использование же собственных строк, а тем более методов с необычными конструкциями заметно понижает читабельность кода, а значит и возможность его поддержки как автором, так и сторонними специалистами.