字符串連接函數的執行時間意外很差

Question

我編寫了以下字符串連接函數（join）以減少分配數量和構建最終字符串所花費的時間。我也想寫一個易於使用的附加功能（如果可能的話，單線程）。

size_t str_size(const char *str) { 
    return std::strlen(str); 
} 

size_t str_size(const std::string &str) { 
    return str.size(); 
} 

template <typename T> 
size_t accumulated_size(const T& last) { 
    return str_size(last); 
} 

template <typename T, typename... Args> 
size_t accumulated_size(const T& first, const Args& ...args) { 
    return str_size(first) + accumulated_size(args...); 
} 

template <typename T> 
void append(std::string& final_string, const T &last) { 
    final_string += last; 
} 

template <typename T, typename... Args> 
void append(std::string& final_string, const T& first, const Args& ...args) { 
    final_string += first; 
    append(final_string, args...); 
} 

template <typename T, typename... Args> 
std::string join(const T& first, const Args& ...args) { 
    std::string final_string; 

    final_string.reserve(accumulated_size(first, args...)); 
    append(final_string, first, args...); 

    return std::move(final_string); 
} 

我測試針對典型內置C++級聯功能join方法使用operator+=以及還有std::string類的一個相當大的量的字符串的operator+。與普通的operator+=或operator+方法相比，我的方法在時間執行方面如何以及爲什麼會產生較差的結果？

我使用下面的類來測量時間：

class timer { 
public: 
    timer() { 
     start_ = std::chrono::high_resolution_clock::now(); 
    } 

    ~timer() { 
     end_ = std::chrono::high_resolution_clock::now(); 
     std::cout << "Execution time: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_ - start_).count() << " ns." << std::endl; 
    } 

private: 
    std::chrono::time_point<std::chrono::high_resolution_clock> start_; 
    std::chrono::time_point<std::chrono::high_resolution_clock> end_; 
}; 

我比較方式如下：

#define TEST_DATA "Lorem", "ipsum", "dolor", "sit", "ame", "consectetuer", "adipiscing", "eli", "Aenean",\ 
        "commodo", "ligula", "eget", "dolo", "Aenean", "mass", "Cum", "sociis", "natoque",\ 
        "penatibus", "et", "magnis", "dis", "parturient", "monte", "nascetur", "ridiculus",\ 
        "mu", "Donec", "quam", "feli", ", ultricies", "ne", "pellentesque", "e", "pretium",\ 
        "qui", "se", "Nulla", "consequat", "massa", "quis", "eni", "Donec", "pede", "just",\ 
        "fringilla", "ve", "aliquet", "ne", "vulputate", "ege", "arc", "In", "enim", "just",\ 
        "rhoncus", "u", "imperdiet", "", "venenatis", "vita", "just", "Nullam", "ictum",\ 
        "felis", "eu", "pede", "mollis", "pretiu", "Integer", "tincidunt" 

#define TEST_DATA_2 std::string("Lorem") + "ipsum"+ "dolor"+ "sit"+ "ame"+ "consectetuer"+ "adipiscing"+ "eli"+ "Aenean"+\ 
        "commodo"+ "ligula"+ "eget"+ "dolo"+ "Aenean"+ "mass"+ "Cum"+ "sociis"+ "natoque"+\ 
        "penatibus"+ "et"+ "magnis"+ "dis"+ "parturient"+ "monte"+ "nascetur"+ "ridiculus"+\ 
        "mu"+ "Donec"+ "quam"+ "feli"+ ", ultricies"+ "ne"+ "pellentesque"+ "e"+ "pretium"+\ 
        "qui"+ "se"+ "Nulla"+ "consequat"+ "massa"+ "quis"+ "eni"+ "Donec"+ "pede"+ "just"+\ 
        "fringilla"+ "ve"+ "aliquet"+ "ne"+ "vulputate"+ "ege"+ "arc"+ "In"+ "enim"+ "just"+\ 
        "rhoncus"+ "u"+ "imperdiet"+ ""+ "venenatis"+ "vita"+ "just"+ "Nullam"+ "ictum"+\ 
        "felis"+ "eu"+ "pede"+ "mollis"+ "pretiu"+ "Integer"+ "tincidunt" 

int main() { 
    std::string string_builder_result; 
    std::string normal_approach_result_1; 
    std::string normal_approach_result_2; 

    { 
     timer t; 
     string_builder_result = join(TEST_DATA); 
    } 

    std::vector<std::string> vec { TEST_DATA }; 
    { 
     timer t; 
     for (const auto & x : vec) { 
      normal_approach_result_1 += x; 
     } 
    } 

    { 
     timer t; 
     normal_approach_result_2 = TEST_DATA_2; 
    } 
} 

我的結果是：

• 執行時間：11552ns（join方法）。
• 執行時間：3701納秒（operator+=()方法）。
• 執行時間：5898 ns（operator+()方法）。

我與編譯：g++ efficient_string_concatenation.cpp -std=c++11 -O3

Answer 1

operator+有一個右參考左手邊std::string。你寫的+=代碼並不比+長鏈更好。

其+可以使用指數重新分配，大約從10左右開始。在1.5的增長因素，這是約9分配和重新分配。

遞歸可能會導致混淆或放慢速度。你可以解決這個問題：

template <typename... Args> 
void append(std::string& final_string, const Args&... args) { 
    using unused=int[]; 
    (void)unused{0,(void(
    final_string += args 
),0)...}; 
} 

這消除了遞歸，同樣：

template <typename... Args> 
size_t accumulated_size(const Args& ...args) { 
    size_t r = 0; 
    using unused=int[]; 
    (void)unused{0,(void(
    r += str_size(args) 
),0)...}; 
    return r; 
} 

，但是，它可能不值得一遊，很多字符串來計算它們的長度，以節省8和再分配。

Answer 2

請不要與該字符串處理。

使用字符串流，或者創建自己的StringBuilder像這樣的：推薦這種智能分配管理https://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

專業字符串生成器（有時他們支持串塊，有時名單 - 增長的預測）。分配是困難且非常耗時的操作。