优化思维【7】字符串拼接

论点

• 升级 C++ 版本或找个好库都能提升性能

定义

字符串拼接，除了典型的多个 std::string 拼接，还涉及到其它类型先转为字符串再拼接。

分析

实际上，其它类型“转为字符”还挺复杂的，不是简单写几行代码能搞定。凡是复杂的事情，就有很大优化空间。

当然，单纯多个 std::string 拼接，也有优化空间，这步可以先解决！假设变量 a、b、c 都是 std::string，先看两种做法：

a = a + b + c;  // method 1
a.append(b).append(c);  // method 2

这是在做 In-place 拼接，第二行才是正规的做法，而第一行在不同 C++ 版本下内部做法并不一样。古典 C++ 会产生更多的复制，当然稣已经完全无视 C++ 20 之前的版本，并不打算解释它们有多烂。在现代 C++ 下，第一行大致做了如下操作：

1. a + b 产生一个临时对象（设为 x）；
2. 把 c 追加到 x；
3. 把 x move 给 a。

注意到：里面新增了一个临时变量，因为 std::string 的实例还挺大的（大于 3 个机器字/指针），所以第二行是有优化效果的。

然而，由于在追加的过程中，可能需要扩容，追加两次，最多就可能扩容两次，所以实际上以上两种做法都不够极致，还应该先 reserve 足够内存：

a.reserve(a.size() + b.size() + c.size());
a.append(b).append(c);

有个大佬觉得这么写也太麻烦了，咱们应该发明一个高能的 concat 方法，它足够快，快到只有 AI 手动对特定场景进行优化才有可能打败它。没错，这个方法叫做——fastio::concat！

您可以先试试这里的各种拼接方法：https://github.com/cppfastio/fast_io/tree/master/benchmark/0009.concatstring

总之，fastio 最快。由于我们是先注意到 fastio 最快，所以下面的分析哪怕很简陋，也没关系了……

1. 可能是最慢的 std::ostringstream

std::ostringstream sst;
for (std::size_t i{}; i != 1000000; ++i) {
  sst.str("");
  sst << "hello" << test_i << test_s;
  re = sst.str();
}

这个方法本应是专门做“字符串拼接”，但实现得确实很慢。稣给优化了一下：

std::ostringstream sst;
for (std::size_t i{}; i != 1000000; ++i) {
  sst << "hello" << test_i << test_s;
  re = std::move(sst).str();
}

代码少了一行，而且少了一次复制。稍微快了一点点，但还是垫底的存在。

2. std::format

for (std::size_t i{}; i != 1000000; ++i) {
  re = std::format("hello{}{}", test_i, test_s);
}

使用 std::format 的问题在于 formatter 支持的语法还挺多，对它进行解析有一定损耗。

另外，std::format 刚出来时，稣拿它和 fmt::format 比较过，MSVC 上的实现比 fmt::format 明显慢很多。所以，换成 fmt::format 可能更快一些。

3. std::to_string + 拼接

for (std::size_t i{}; i != 1000000; ++i) {
  re = "hello" + std::to_string(test_i) + test_s;
}

std::to_string 可以说是一种特定场景的优化了，它比前面两种方法快是很自然的事。

3. fast_io::concat

毫无疑问的冠军。它之所以快，是因为在转换和拼接这两步都做到极致：一次性预计算总长度、只分配一次内存、无临时字符串、全内联、零冗余复制……问 AI 吧，稣冰冷的文风不合适夸。

对了，在稣的机器上，最快比最慢的差别是：10 倍以上。