Самый оптимизированный способ конкатенации в строках

Question

Мы всегда сталкивались с ситуацией на ежедневной основе, в которой мы должны выполнять утомительное и очень много операций с цепочками в нашем коде. Мы все знаем, что струнные манипуляции - дорогостоящие операции. Я хотел бы знать, какая из них самая дешевая среди доступных версий.

Наиболее распространенными операциями являются конкатенация (это то, что мы можем контролировать в некоторой степени). Каков наилучший способ объединить std :: strings в C++ и различные обходные пути для ускорения конкатенации?

Я имею в виду,

std::string l_czTempStr; 

1).l_czTempStr = "Test data1" + "Test data2" + "Test data3"; 

2). l_czTempStr = "Test data1"; 
    l_czTempStr += "Test data2"; 
    l_czTempStr += "Test data3"; 

3). using << operator 

4). using append() 

Кроме того, мы получаем какие-либо преимущества использования CString над станд :: строка?

Answer 1

Вот небольшой набор тестов:

#include <iostream> 
#include <string> 
#include <chrono> 
#include <sstream> 

int main() 
{ 
    typedef std::chrono::high_resolution_clock clock; 
    typedef std::chrono::duration<float, std::milli> mil; 
    std::string l_czTempStr; 
    std::string s1="Test data1"; 
    auto t0 = clock::now(); 
    #if VER==1 
    for (int i = 0; i < 100000; ++i) 
    { 
     l_czTempStr = s1 + "Test data2" + "Test data3"; 
    } 
    #elif VER==2 
    for (int i = 0; i < 100000; ++i) 
    { 
     l_czTempStr = "Test data1"; 
     l_czTempStr += "Test data2"; 
     l_czTempStr += "Test data3"; 
    } 
    #elif VER==3 
    for (int i = 0; i < 100000; ++i) 
    { 
     l_czTempStr = "Test data1"; 
     l_czTempStr.append("Test data2"); 
     l_czTempStr.append("Test data3"); 
    } 
    #elif VER==4 
    for (int i = 0; i < 100000; ++i) 
    { 
     std::ostringstream oss; 
     oss << "Test data1"; 
     oss << "Test data2"; 
     oss << "Test data3"; 
     l_czTempStr = oss.str(); 
    } 
    #endif 
    auto t1 = clock::now(); 
    std::cout << l_czTempStr << '\n'; 
    std::cout << mil(t1-t0).count() << "ms\n"; 
} 

На coliru:

Compile со следующим:

лязг ++ -std = C++ 11 -O3 -DVER = 1 -Wall -пейский -pthread main.cpp

21.6463ms

-DVER = 2

6.61773ms

-DVER = 3

6.7855ms

-DVER = 4

102.015ms

Похоже 2), += является победителем.

(также составление и без -pthread, кажется, влияет на тайминги)

Answer 2

наихудший возможный сценарий использует обычный старый strcat (или sprintf), так как strcat принимает строку C, и что должно быть «подсчитаны» чтобы найти конец. Для длинных строк это настоящий человек. Строки стиля C++ намного лучше, и проблемы с производительностью, скорее всего, будут связаны с распределением памяти, а не с подсчетом длин. Но опять же, строка растет геометрически (удваивается каждый раз, когда она должна расти), так что это не так страшно.

Я очень подозреваю, что все вышеперечисленные методы заканчиваются тем же или, по крайней мере, очень похожими характеристиками. Во всяком случае, я ожидал бы, что stringstream будет медленнее, из-за накладных расходов на поддержку форматирования, но я также подозреваю, что это маргинально.

Как это похоже на «веселье», я вернусь с эталоном ...

Edit:

Обратите внимание, что эти результаты применимы к моей машине, работает x86-64 Linux, составленное с г ++ 4.6.3. Другие версии ОС, компиляторов и реализаций библиотек выполнения C++ могут отличаться. Если производительность важна для вашего приложения, то сравните систему (ы), которая имеет для вас решающее значение, используя используемые вами компиляторы (компиляторы).

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

#include <iostream> 
#include <iomanip> 
#include <string> 
#include <sstream> 
#include <cstring> 

using namespace std; 

static __inline__ unsigned long long rdtsc(void) 
{ 
    unsigned hi, lo; 
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); 
    return ((unsigned long long)lo)|(((unsigned long long)hi)<<32); 
} 

string build_string_1(const string &a, const string &b, const string &c) 
{ 
    string out = a + b + c; 
    return out; 
} 

string build_string_1a(const string &a, const string &b, const string &c) 
{ 
    string out; 
    out.resize(a.length()*3); 
    out = a + b + c; 
    return out; 
} 

string build_string_2(const string &a, const string &b, const string &c) 
{ 
    string out = a; 
    out += b; 
    out += c; 
    return out; 
} 

string build_string_3(const string &a, const string &b, const string &c) 
{ 
    string out; 
    out = a; 
    out.append(b); 
    out.append(c); 
    return out; 
} 


string build_string_4(const string &a, const string &b, const string &c) 
{ 
    stringstream ss; 

    ss << a << b << c; 
    return ss.str(); 
} 


char *build_string_5(const char *a, const char *b, const char *c) 
{ 
    char* out = new char[strlen(a) * 3+1]; 
    strcpy(out, a); 
    strcat(out, b); 
    strcat(out, c); 
    return out; 
} 



template<typename T> 
size_t len(T s) 
{ 
    return s.length(); 
} 

template<> 
size_t len(char *s) 
{ 
    return strlen(s); 
} 

template<> 
size_t len(const char *s) 
{ 
    return strlen(s); 
} 



void result(const char *name, unsigned long long t, const string& out) 
{ 
    cout << left << setw(22) << name << " time:" << right << setw(10) << t; 
    cout << " (per character: " 
     << fixed << right << setw(8) << setprecision(2) << (double)t/len(out) << ")" << endl; 
} 

template<typename T> 
void benchmark(const char name[], T (Func)(const T& a, const T& b, const T& c), const char *strings[]) 
{ 
    unsigned long long t; 

    const T s1 = strings[0]; 
    const T s2 = strings[1]; 
    const T s3 = strings[2]; 
    t = rdtsc(); 
    T out = Func(s1, s2, s3); 
    t = rdtsc() - t; 

    if (len(out) != len(s1) + len(s2) + len(s3)) 
    { 
     cout << "Error: out is different length from inputs" << endl; 
     cout << "Got `" << out << "` from `" << s1 << "` + `" << s2 << "` + `" << s3 << "`"; 
    } 
    result(name, t, out); 
} 


void benchmark(const char name[], char* (Func)(const char* a, const char* b, const char* c), 
       const char *strings[]) 
{ 
    unsigned long long t; 

    const char* s1 = strings[0]; 
    const char* s2 = strings[1]; 
    const char* s3 = strings[2]; 
    t = rdtsc(); 
    char *out = Func(s1, s2, s3); 
    t = rdtsc() - t; 

    if (len(out) != len(s1) + len(s2) + len(s3)) 
    { 
     cout << "Error: out is different length from inputs" << endl; 
     cout << "Got `" << out << "` from `" << s1 << "` + `" << s2 << "` + `" << s3 << "`"; 
    } 
    result(name, t, out); 
    delete [] out; 
} 


#define BM(func, size) benchmark(#func " " #size, func, strings ## _ ## size) 


#define BM_LOT(size) BM(build_string_1, size); \ 
    BM(build_string_1a, size); \ 
    BM(build_string_2, size); \ 
    BM(build_string_3, size); \ 
    BM(build_string_4, size); \ 
    BM(build_string_5, size); 

int main() 
{ 
    const char *strings_small[] = { "Abc", "Def", "Ghi" }; 
    const char *strings_medium[] = { "abcdefghijklmnopqrstuvwxyz", 
            "defghijklmnopqrstuvwxyzabc", 
            "ghijklmnopqrstuvwxyzabcdef" }; 
    const char *strings_large[] = 
     { "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" 
      "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz", 

      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 

      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
      "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc", 

      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
      "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" 
     }; 

    for(int i = 0; i < 5; i++) 
    { 
     BM_LOT(small); 
     BM_LOT(medium); 
     BM_LOT(large); 
     cout << "---------------------------------------------" << endl; 
    } 
} 

Вот некоторые репрезентативные результаты:

build_string_1 small time:  4075 (per character: 452.78) 
build_string_1a small time:  5384 (per character: 598.22) 
build_string_2 small time:  2669 (per character: 296.56) 
build_string_3 small time:  2427 (per character: 269.67) 
build_string_4 small time:  19380 (per character: 2153.33) 
build_string_5 small time:  6299 (per character: 699.89) 
build_string_1 medium time:  3983 (per character: 51.06) 
build_string_1a medium time:  6970 (per character: 89.36) 
build_string_2 medium time:  4072 (per character: 52.21) 
build_string_3 medium time:  4000 (per character: 51.28) 
build_string_4 medium time:  19614 (per character: 251.46) 
build_string_5 medium time:  6304 (per character: 80.82) 
build_string_1 large time:  8491 (per character:  3.63) 
build_string_1a large time:  9563 (per character:  4.09) 
build_string_2 large time:  6154 (per character:  2.63) 
build_string_3 large time:  5992 (per character:  2.56) 
build_string_4 large time:  32450 (per character: 13.87) 
build_string_5 large time:  15768 (per character:  6.74) 

же код, выполняющиеся как 32-бит:

build_string_1 small time:  4289 (per character: 476.56) 
build_string_1a small time:  5967 (per character: 663.00) 
build_string_2 small time:  3329 (per character: 369.89) 
build_string_3 small time:  3047 (per character: 338.56) 
build_string_4 small time:  22018 (per character: 2446.44) 
build_string_5 small time:  3026 (per character: 336.22) 
build_string_1 medium time:  4089 (per character: 52.42) 
build_string_1a medium time:  8075 (per character: 103.53) 
build_string_2 medium time:  4569 (per character: 58.58) 
build_string_3 medium time:  4326 (per character: 55.46) 
build_string_4 medium time:  22751 (per character: 291.68) 
build_string_5 medium time:  2252 (per character: 28.87) 
build_string_1 large time:  8695 (per character:  3.72) 
build_string_1a large time:  12818 (per character:  5.48) 
build_string_2 large time:  8202 (per character:  3.51) 
build_string_3 large time:  8351 (per character:  3.57) 
build_string_4 large time:  38250 (per character: 16.35) 
build_string_5 large time:  8143 (per character:  3.48) 

Исходя из этого, можно сделать вывод:

1. Лучшим вариантом является добавление бит за раз (out.append() или out +=), при этом «цепной» подход подходит близко.

2. Предварительная выделение строки не помогает.

3. Использование stringstream - довольно плохая идея (между 2-4x медленнее).

4. char * использует new char[]. Использование локальной переменной в вызывающей функции делает ее самой быстрой, но слегка несправедливо ее сравнивает.

5. В сочетании короткой строки имеется довольно много накладных расходов. Простое копирование данных должно составлять не более одного цикла на каждый байт [если данные не помещаются в кеш].

edit2

Added, согласно комментариям:

string build_string_1b(const string &a, const string &b, const string &c) 
{ 
    return a + b + c; 
} 

и

string build_string_2a(const string &a, const string &b, const string &c) 
{ 
    string out; 
    out.reserve(a.length() * 3); 
    out += a; 
    out += b; 
    out += c; 
    return out; 
} 

который дает следующие результаты:

build_string_1 small time:  3845 (per character: 427.22) 
build_string_1b small time:  3165 (per character: 351.67) 
build_string_2 small time:  3176 (per character: 352.89) 
build_string_2a small time:  1904 (per character: 211.56) 

build_string_1 large time:  9056 (per character:  3.87) 
build_string_1b large time:  6414 (per character:  2.74) 
build_string_2 large time:  6417 (per character:  2.74) 
build_string_2a large time:  4179 (per character:  1.79) 

(32-разрядный запуск, но 64-бит показывает очень похожие результаты).

Answer 3

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

append и += должны делать то же самое.

+ концептуально менее эффективен, поскольку вы создаете и уничтожаете временные рамки.Ваш компилятор может или не может оптимизировать это так быстро, как добавлять.

Вызов reserve с общим размером может уменьшить количество необходимых распределений памяти - они, вероятно, будут самым большим узким местом.

<< (предположительно на stringstream) может быть или не быть быстрее; вам нужно будет это измерить. Это полезно, если вам нужно форматировать нестрочные типы, но, вероятно, не будет особенно лучше или хуже при работе со строками.

CString имеет тот недостаток, что он не переносится, и что такой хакер Unix, как я, не может сказать вам, какие его преимущества могут или не могут быть.

Answer 4

В дополнение к другим ответам ...

Я сделал обширные тесты по этой проблеме некоторое время назад, и пришли к выводу, что наиболее эффективным решением (НКУ 4,7 & 4,8 на Linux x86/x64/ARM) в все прецеденты сначала reserve() в строке результата с достаточным пространством для хранения всех конкатенированных строк, а затем только append() их (или используйте operator +=(), что не имеет значения).

К сожалению, кажется, я удалил этот тест, поэтому у вас есть только мое слово (но вы можете легко адаптировать тест Матса Петерсона, чтобы убедиться в этом сами, если моего слова недостаточно).

В двух словах:

const string space = " "; 
string result; 
result.reserve(5 + space.size() + 5); 
result += "hello"; 
result += space; 
result += "world"; 

В зависимости от конкретного случая использования (количество, типы и размеры сцепленных строк), иногда этот метод на сегодняшний день является наиболее эффективным, а иногда он находится на одном уровне с другими методами, но это никогда не бывает хуже.

---

Проблема заключается в том, что это действительно больно, чтобы вычислить общий необходимый размер заранее, особенно при смешивании строковых литералов и std::string (в приведенном выше примере достаточно ясно по этому вопросу, я считаю). Ремонтопригодность такого кода абсолютно ужасна, как только вы модифицируете один из литералов или добавляете еще одну строку, которая будет конкатенирована.

Один из подходов заключается в использовании sizeof для вычисления размера литералов, но ИМХО это создает столько путаницы, чем решает, ремонтопригодность все еще страшно:

#define STR_HELLO "hello" 
#define STR_WORLD "world" 

const string space = " "; 
string result; 
result.reserve(sizeof(STR_HELLO)-1 + space.size() + sizeof(STR_WORLD)-1); 
result += STR_HELLO; 
result += space; 
result += STR_WORLD; 

работоспособное решение (C++ 11, variadic templates)

Я, наконец, решил использовать набор вариативных шаблонов, которые эффективно занимаются вычислением размеров строк (например, размер строковых литералов определяется во время компиляции), reserve() по мере необходимости, а затем объединяет все ,

Вот она, надеюсь, что это полезно:

namespace detail { 

    template<typename> 
    struct string_size_impl; 

    template<size_t N> 
    struct string_size_impl<const char[N]> { 
    static constexpr size_t size(const char (&) [N]) { return N - 1; } 
    }; 

    template<size_t N> 
    struct string_size_impl<char[N]> { 
    static size_t size(char (&s) [N]) { return N ? strlen(s) : 0; } 
    }; 

    template<> 
    struct string_size_impl<const char*> { 
    static size_t size(const char* s) { return s ? strlen(s) : 0; } 
    }; 

    template<> 
    struct string_size_impl<char*> { 
    static size_t size(char* s) { return s ? strlen(s) : 0; } 
    }; 

    template<> 
    struct string_size_impl<std::string> { 
    static size_t size(const std::string& s) { return s.size(); } 
    }; 

    template<typename String> size_t string_size(String&& s) { 
    using noref_t = typename std::remove_reference<String>::type; 
    using string_t = typename std::conditional<std::is_array<noref_t>::value, 
               noref_t, 
               typename std::remove_cv<noref_t>::type 
               >::type; 
    return string_size_impl<string_t>::size(s); 
    } 

    template<typename...> 
    struct concatenate_impl; 

    template<typename String> 
    struct concatenate_impl<String> { 
    static size_t size(String&& s) { return string_size(s); } 
    static void concatenate(std::string& result, String&& s) { result += s; } 
    }; 

    template<typename String, typename... Rest> 
    struct concatenate_impl<String, Rest...> { 
    static size_t size(String&& s, Rest&&... rest) { 
     return string_size(s) 
      + concatenate_impl<Rest...>::size(std::forward<Rest>(rest)...); 
    } 
    static void concatenate(std::string& result, String&& s, Rest&&... rest) { 
     result += s; 
     concatenate_impl<Rest...>::concatenate(result, std::forward<Rest>(rest)...); 
    } 
    }; 

} // namespace detail 

template<typename... Strings> 
std::string concatenate(Strings&&... strings) { 
    std::string result; 
    result.reserve(detail::concatenate_impl<Strings...>::size(std::forward<Strings>(strings)...)); 
    detail::concatenate_impl<Strings...>::concatenate(result, std::forward<Strings>(strings)...); 
    return result; 
} 

Единственная интересная часть, насколько общедоступный интерфейс касается, это последний template<typename... Strings> std::string concatenate(Strings&&... strings) шаблон.Использование просто:

int main() { 
    const string space = " "; 
    std::string result = concatenate("hello", space, "world"); 
    std::cout << result << std::endl; 
} 

С оптимизациями включены, любой приличный компилятор должен иметь возможность расширить concatenate вызов на тот же код, как мой первый пример, когда я вручную написал все. Что касается GCC 4.7 & 4.8, сгенерированный код в значительной степени идентичен, а также производительность.

Answer 5

Есть несколько важных параметров, которые могут повлиять на решение «наиболее оптимизированного пути». Некоторые из них: размер строки/содержимого, количество операций, оптимизация компилятора и т. Д.

В большинстве случаев string::operator+= работает лучше всего. Однако иногда, на некоторых компиляторах, также наблюдается, что ostringstream::operator<< работает лучше всего [например, MingW g ++ 3.2.3, 1,8 ГГц однопроцессорный компьютер Dell]. Когда возникает контекст компилятора, то это главным образом оптимизация в компиляторе, которая повлияет. Также следует отметить, что stringstreams являются сложными объектами по сравнению с простыми строками и, следовательно, добавляются к накладным расходам.

Дополнительная информация - discussion, article.