字符串连接函数的执行时间出乎意料地差

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);
}

我使用 operator+= 以及 std::string class 的 operator+ 针对典型的内置 C++ 串联功能测试了 join 方法相当多的字符串。与普通 operator+= 或 operator+ 方法相比，我的方法如何以及为什么在时间执行方面产生较差的结果？

我正在使用以下 class 来测量时间：

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;
    }
}

我的结果是：

执行时间：11552 ns（join 方法）。
执行时间：3701 ns（operator+=() 方法）。
执行时间：5898 ns（operator+() 方法）。

我正在编译：g++ efficient_string_concatenation.cpp -std=c++11 -O3

Answer 1

请不要为此处理字符串。

使用字符串流，或像这样创建您自己的 StringBuilder：https://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

由于其智能分配管理而推荐的专业字符串构建器（有时它们支持字符串块列表，有时 - 增长预测）。分配是一项艰巨且非常耗时的操作。

Answer 2

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 次重新分配。

字符串连接函数的执行时间出乎意料地差

Unexpectedly poor execution time for string concatenation function

c++

string-concatenation

coding-efficiency

variadic-templates

c++11