Оптимизация производительности для std :: string

Question

Когда я сделал тест производительности в своем приложении, я заметил разницу в следующем коде (Visual Studio 2010).

Медленнее версия

while(heavyloop) 
{ 
    if(path+node+"/" == curNode) 
    { 
     do something 
    } 
} 

Это вызовет дополнительный mallocs для результирующая строка будет генерироваться.

Для того, чтобы избежать этих mallocs, я изменил его следующим образом:

std::string buffer; 
buffer.reserve(500); // Big enough to hold all combinations without the need of malloc 

while(heavyloop) 
{ 
    buffer = path; 
    buffer += node; 
    buffer += "/"; 

    if(buffer == curNode) 
    { 
     do something 
    } 
} 

Хотя второй вариант выглядит немного более громоздкий по сравнению с первой версией, это по-прежнему читается достаточно. Однако мне было интересно, так ли эта оптимизация является надзором со стороны компилятора или если это всегда нужно делать вручную. Поскольку он меняет только порядок распределения, я бы ожидал, что компилятор также сможет понять это самостоятельно. С другой стороны, некоторые условия должны быть выполнены, чтобы действительно сделать его оптимизацией, которая не обязательно должна быть заполнена, но если условия не совпадают, код, по крайней мере, будет работать так же хорошо, как и первая версия. Являются ли новые версии Visual Studio лучшими в этом отношении?

Более полная версия, которая показывает разницу (ВПЧЭ):

std::string gen_random(std::string &oString, const int len) 
{ 
    static const char alphanum[] = 
     "" 
     "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
     "abcdefghijklmnopqrstuvwxyz"; 

    oString = ""; 

    for (int i = 0; i < len; ++i) 
    { 
     oString += alphanum[rand() % (sizeof(alphanum) - 1)]; 
    } 

    return oString; 
} 

int main(int argc, char *argv[]) 
{ 
    clock_t start = clock(); 
    std::string s = "/"; 
    size_t adds = 0; 
    size_t subs = 0; 
    size_t max_len = 0; 

    s.reserve(100000); 

    for(size_t i = 0; i < 1000000; i++) 
    { 
     std::string t1; 
     std::string t2; 
     if(rand() % 2) 
     { 
      // Slow version 
      //s += gen_random(t1, (rand() % 15)+3) + "/" + gen_random(t2, (rand() % 15)+3); 

      // Fast version 
      s += gen_random(t1, (rand() % 15)+3); 
      s += "/"; 
      s += gen_random(t2, (rand() % 15)+3); 
      adds++; 
     } 
     else 
     { 
      subs++; 
      size_t pos = s.find_last_of("/", s.length()-1); 
      if(pos != std::string::npos) 
       s.resize(pos); 

      if(s.length() == 0) 
       s = "/"; 
     } 

     if(max_len < s.length()) 
      max_len = s.length(); 
    } 
    std::cout << "Elapsed: " << clock() - start << std::endl; 
    std::cout << "Added: " << adds << std::endl; 
    std::cout << "Subtracted: " << subs << std::endl; 
    std::cout << "Max: " << max_len << std::endl; 

    return 0; 
} 

На моей системе я получаю около 1 второй разности между двумя (протестировано с НКОЙ на этот раз, но, кажется, не существует какие-либо заметное различие в Visual Studio есть):

Elapsed: 2669 
Added: 500339 
Subtracted: 499661 
Max: 47197 

Elapsed: 3417 
Added: 500339 
Subtracted: 499661 
Max: 47367 

Answer 1

Ваша медленная версия может быть переписана в виде

while(heavyloop) 
{ 
    std::string tempA = path + node; 
    std::string tempB = tempA + "/"; 

    if(tempB == curNode) 
    { 
     do something 
    } 
} 

Да, это не полный аналог, но делает временные объекты более заметными.

Просмотреть два временных объекта: tempA и tempB. Они созданы потому, что std::string::operator+ всегда генерирует новый объект std::string. Вот как проектируется std::string. Компилятор не сможет оптимизировать этот код.

Для решения этой проблемы существует методика в C++ под названием expression templates, но опять же она выполняется на уровне библиотеки.

Answer 2

путь + узел + "/" будет выделять строку переменных temp для сравнения с curNode, это реализация C++.

Answer 3

Для типов классов (например, std::string) не требуется, чтобы обычные отношения между оператором + и оператором += выполнялись так, как вы ожидаете. Разумеется, нет необходимости в том, чтобы a = a + b и a += b имели тот же эффект сети, так как operator=(), operator+() и operator+=() все могут быть реализованы индивидуально и не работают вместе в тандеме.

Как таковой, компилятор будет семантически неправильно, если он заменен

if(path+node+"/" == curNode) 

с

std::string buffer = path; 
buffer += node; 
buffer += "/"; 
if (buffer == curNode) 

Если есть некоторое ограничение в стандарте, например фиксированное соотношение между перегружена operator+() и перегружена operator+=(), то два фрагмента кода будут иметь тот же чистый эффект. Однако такого ограничения нет, поэтому компилятору не разрешено выполнять такие замены. Результатом будет изменение значения кода.