C++ STL 容器用作简单缓冲区时速度很慢（我做了一个基准测试）？
C++ STL containers are slow when used as simple buffers (I did a benchmark)?
我一直认为 C++ 代码在效率方面通常与 C 代码不相上下，甚至更好（例如：std::sort 由于比较器内联而优于 qsort）。人们还普遍认为，如果需要动态内存缓冲区，std::vector 将是合理的首选。
最近我实施了一个基准测试来获取硬数据并得到了令人惊讶的结果。基本上在紧密循环中附加到向量（或字符串）是相对较慢。
有没有办法让它更快，请赐教！
有关基准测试的详细信息，请参见下文。
当然，一种选择是使用自定义容器。出于显而易见的原因（代码的一致性加上在同一事物的不兼容表示之间进行转换的开销，比如 std::string 和 custom_string），我非常想尽可能避免这条路线。
关于benchmark。
有输入缓冲区和输出缓冲区。如果输入字节通过验证，它会按原样传输到输出，否则它会被编码并传输生成的 3 个字节（这里是某种转义）。正在实施的算法是 UTF-8 验证。
基本上是code:
// Templated Sink allows us to play with different methods for building
// the output to estimate the relative efficiency of various approaches
// (ex: a large buffer with no bounds checking vs. std::string).
template <typename Sink>
const unsigned char *
fix_utf8_engine(Sink &sink,
const unsigned char *i, const unsigned char *end)
{
while (i < end) {
// for sinks with limited capacity
if (!sink.check_capacity())
return i;
switch (i[0]) {
case 0x00 ... 0x7f:
// 1-byte UTF-8 sequence
sink.template write<1>(i);
i += 1;
continue;
...
我实现了 fix_utf8 的不同变体，包括写入预分配的 "infinite" 缓冲区（没有边界检查或增长，baseline )，一个产生动态增长的 malloc-ed 缓冲区 (malloc)，一个产生 std::string (string) 和那个产生 std::vector (vector).
结果如下（Ivy Bridge Core i7 笔记本电脑，clang-600.0.56 -O3）（基于 LLVM 3.5svn）：
ASCII Unicode Unicode Unicode Unicode Unicode 随机
小满恶混恶短恶长
基线 0.01307 0.01816 0.01912 0.01909 0.03104 0.03781 0.06127
malloc 0.01798 0.02068 0.02116 0.02095 0.03918 0.04684 0.06909
字符串 0.02791 0.03045 0.02575 0.02520 0.07871 0.11513 0.09580
矢量 0.06210 0.04925 0.04017 0.04027 0.10103 0.15159 0.12871
不同的列用于不同类型的随机生成的输入（Unicode small — 有限范围最多 2 个字节的结果 UTF-8，evil mix——各种破损的UTF-8数据穿插在正常数据中，邪恶short/long——所有UTF-8序列都被截断1字节）。
这些结果清楚地表明 string 和 vector 变体在至少两个非常重要的用例上要慢得多 — ASCII 和 Unicode（小）.
非常感谢任何有助于改善这些结果的帮助！
当您了解如何使用它们时，它们会很快。我的猜测是你不断地调用 vector.push_back(value)，它会在每次用完内存时重新分配一个新的缓冲区（通常它会在你达到限制时加倍分配）。你想先做一个 vector.reserve(reasonableCapacity)。
是的，你是对的。像那样使用向量或字符串确实很慢。基本上每次追加都是在容器的末尾追加，您可能会要求容器重新分配一个新缓冲区，将数据复制到新缓冲区，然后删除旧缓冲区。
您可以通过两种方式改进结果。首先，如果您知道大小，可以使用 reserve() 方法。其次，如果您使用的是矢量，则可以切换到 deque，当我对所需的大小感觉不太好时，我会使用它。在这个用例中，这会更好地工作。那是因为双端队列不重新分配内存——它按页面优雅地增长。在这种灵活性（一级间接）的访问上有一个权衡，但由于您现在只是插入它不应该适用。
有评论说你储备够了，其实不然。你可以写的比你读的更多。我仍然会使用与 check_capacity() 中的 malloc 策略类似的增长策略。这将为您提供最好的同类比较。
这是一个模板版本，应该正确实现 check_capacity() 并适用于所有 STL 容器（包括双端队列）。使用这个代替 std_vector_sink 和 std_string_sink.
// Write output to a container
template < typename CONTAINER >
struct std_sink
{
CONTAINER &v_;
std_sink(CONTAINER &v): v_(v) {}
bool check_capacity() {
if (v_.capacity() - v_.size() <= 8) {
v_.reserve(v_.size() + (v_.size() / 2));
}
return true;
}
template<size_t n> void write(const unsigned char *p) {
v_.insert(v_.end(), p, p+n);
}
void write_bad(const unsigned char *p) {
unsigned char esc[] = {
utf8b_1(*p),
utf8b_2(*p),
utf8b_3(*p)
};
v_.insert(v_.end(), esc, esc + 3);
}
};
另外，用双端队列试试：
std_sink< std::deque< unsigned char> > sink(result);
在我的特定环境中，以下内容有所帮助。
使用 std::string 的原始代码很慢，因为许多代码路径以对 insert() 的不同调用结束。 Insert 被部分内联，导致大量代码膨胀（尽管根本不内联会更糟）。
有效的解决方案是放弃 insert() 并使用指针呈现输出。一旦输出指针赶上输出缓冲区结束指针，我们确定字符串内的输出偏移量，将字符串大小增加固定数量并更新指针。
std::string output;
char *opos; // output pos
char *end_obuf;
while (...) {
if (opos + 6 > end_obuf) { // 6 bytes produced per iteration or less
output.resize(s.size() + 128);
// reinit opos, end_obuf pointers
...
}
// processing
...
}
重要的是永远不要写超过字符串末尾的内容，因为没有合法的方法使该数据成为字符串的一部分（一旦字符串增长，超过末尾的数据将被删除，至少使用默认分配器是这样）。
因此我们实际上是在调整字符串的大小（故意使用 resize() 而不是 reserve()）。
固定增长即可；实际上，标准要求缓冲区在内容线性增长时呈指数增长。特定数量 (128) 是一种权衡：增长太多是不好的，因为我们要对那么多字节进行零初始化。增长太少也不好，因为我们不想太频繁地执行调整大小代码。
总而言之，对 insert() 的许多调用已替换为对 resize() 的单个调用，从而使生成的代码更加精简。调整大小分支很少执行，因此可以在多个循环迭代中分摊成本。
一些结束语：
将 STL 分配器与 realloc 进行比较确实不公平。 Realloc 通常可以在不制作副本的情况下调整缓冲区的大小。由于 OOP 问题，STL 分配器总是制作完整的副本。
功能请求：如果STL默认为POD类型使用realloc就好了。
"Pessimizing" malloc 使结果几乎相同（大约 20% 的原始性能差异是由于这个唯一原因）。
看看字符串缓冲区的动态重新分配是否会带来那么多的性能开销，这很有趣。过度保留加上悲观的 malloc 不足以缩小差距。在这个特定问题中，数据处理速度更为重要（注意：此处的字符串大小为 8MiB，字符串越小，结果可能会发生变化。）
配置文件引导优化 (-fprofile-generate/-fprofile-use) 允许持续获得另外 5-10%，非常感谢这个选项。
我一直认为 C++ 代码在效率方面通常与 C 代码不相上下，甚至更好（例如：std::sort 由于比较器内联而优于 qsort）。人们还普遍认为，如果需要动态内存缓冲区，std::vector 将是合理的首选。
最近我实施了一个基准测试来获取硬数据并得到了令人惊讶的结果。基本上在紧密循环中附加到向量（或字符串）是相对较慢。
有没有办法让它更快，请赐教！
有关基准测试的详细信息，请参见下文。
当然，一种选择是使用自定义容器。出于显而易见的原因（代码的一致性加上在同一事物的不兼容表示之间进行转换的开销，比如 std::string 和 custom_string），我非常想尽可能避免这条路线。
关于benchmark。
有输入缓冲区和输出缓冲区。如果输入字节通过验证，它会按原样传输到输出，否则它会被编码并传输生成的 3 个字节（这里是某种转义）。正在实施的算法是 UTF-8 验证。
基本上是code:
// Templated Sink allows us to play with different methods for building
// the output to estimate the relative efficiency of various approaches
// (ex: a large buffer with no bounds checking vs. std::string).
template <typename Sink>
const unsigned char *
fix_utf8_engine(Sink &sink,
const unsigned char *i, const unsigned char *end)
{
while (i < end) {
// for sinks with limited capacity
if (!sink.check_capacity())
return i;
switch (i[0]) {
case 0x00 ... 0x7f:
// 1-byte UTF-8 sequence
sink.template write<1>(i);
i += 1;
continue;
...
我实现了 fix_utf8 的不同变体，包括写入预分配的 "infinite" 缓冲区（没有边界检查或增长，baseline )，一个产生动态增长的 malloc-ed 缓冲区 (malloc)，一个产生 std::string (string) 和那个产生 std::vector (vector).
结果如下（Ivy Bridge Core i7 笔记本电脑，clang-600.0.56 -O3）（基于 LLVM 3.5svn）：
ASCII Unicode Unicode Unicode Unicode Unicode 随机
小满恶混恶短恶长
基线 0.01307 0.01816 0.01912 0.01909 0.03104 0.03781 0.06127
malloc 0.01798 0.02068 0.02116 0.02095 0.03918 0.04684 0.06909
字符串 0.02791 0.03045 0.02575 0.02520 0.07871 0.11513 0.09580
矢量 0.06210 0.04925 0.04017 0.04027 0.10103 0.15159 0.12871
不同的列用于不同类型的随机生成的输入（Unicode small — 有限范围最多 2 个字节的结果 UTF-8，evil mix——各种破损的UTF-8数据穿插在正常数据中，邪恶short/long——所有UTF-8序列都被截断1字节）。
这些结果清楚地表明 string 和 vector 变体在至少两个非常重要的用例上要慢得多 — ASCII 和 Unicode（小）.
非常感谢任何有助于改善这些结果的帮助！
当您了解如何使用它们时，它们会很快。我的猜测是你不断地调用 vector.push_back(value)，它会在每次用完内存时重新分配一个新的缓冲区（通常它会在你达到限制时加倍分配）。你想先做一个 vector.reserve(reasonableCapacity)。
是的，你是对的。像那样使用向量或字符串确实很慢。基本上每次追加都是在容器的末尾追加，您可能会要求容器重新分配一个新缓冲区，将数据复制到新缓冲区，然后删除旧缓冲区。
您可以通过两种方式改进结果。首先，如果您知道大小，可以使用 reserve() 方法。其次，如果您使用的是矢量，则可以切换到 deque，当我对所需的大小感觉不太好时，我会使用它。在这个用例中，这会更好地工作。那是因为双端队列不重新分配内存——它按页面优雅地增长。在这种灵活性（一级间接）的访问上有一个权衡，但由于您现在只是插入它不应该适用。
有评论说你储备够了，其实不然。你可以写的比你读的更多。我仍然会使用与 check_capacity() 中的 malloc 策略类似的增长策略。这将为您提供最好的同类比较。
这是一个模板版本，应该正确实现 check_capacity() 并适用于所有 STL 容器（包括双端队列）。使用这个代替 std_vector_sink 和 std_string_sink.
// Write output to a container
template < typename CONTAINER >
struct std_sink
{
CONTAINER &v_;
std_sink(CONTAINER &v): v_(v) {}
bool check_capacity() {
if (v_.capacity() - v_.size() <= 8) {
v_.reserve(v_.size() + (v_.size() / 2));
}
return true;
}
template<size_t n> void write(const unsigned char *p) {
v_.insert(v_.end(), p, p+n);
}
void write_bad(const unsigned char *p) {
unsigned char esc[] = {
utf8b_1(*p),
utf8b_2(*p),
utf8b_3(*p)
};
v_.insert(v_.end(), esc, esc + 3);
}
};
另外，用双端队列试试：
std_sink< std::deque< unsigned char> > sink(result);
在我的特定环境中，以下内容有所帮助。
使用 std::string 的原始代码很慢，因为许多代码路径以对 insert() 的不同调用结束。 Insert 被部分内联，导致大量代码膨胀（尽管根本不内联会更糟）。
有效的解决方案是放弃 insert() 并使用指针呈现输出。一旦输出指针赶上输出缓冲区结束指针，我们确定字符串内的输出偏移量，将字符串大小增加固定数量并更新指针。
std::string output;
char *opos; // output pos
char *end_obuf;
while (...) {
if (opos + 6 > end_obuf) { // 6 bytes produced per iteration or less
output.resize(s.size() + 128);
// reinit opos, end_obuf pointers
...
}
// processing
...
}
重要的是永远不要写超过字符串末尾的内容，因为没有合法的方法使该数据成为字符串的一部分（一旦字符串增长，超过末尾的数据将被删除，至少使用默认分配器是这样）。
因此我们实际上是在调整字符串的大小（故意使用 resize() 而不是 reserve()）。
固定增长即可；实际上，标准要求缓冲区在内容线性增长时呈指数增长。特定数量 (128) 是一种权衡：增长太多是不好的，因为我们要对那么多字节进行零初始化。增长太少也不好，因为我们不想太频繁地执行调整大小代码。
总而言之，对 insert() 的许多调用已替换为对 resize() 的单个调用，从而使生成的代码更加精简。调整大小分支很少执行，因此可以在多个循环迭代中分摊成本。
一些结束语：
将 STL 分配器与 realloc 进行比较确实不公平。 Realloc 通常可以在不制作副本的情况下调整缓冲区的大小。由于 OOP 问题，STL 分配器总是制作完整的副本。
功能请求：如果STL默认为POD类型使用realloc就好了。
"Pessimizing" malloc 使结果几乎相同（大约 20% 的原始性能差异是由于这个唯一原因）。
看看字符串缓冲区的动态重新分配是否会带来那么多的性能开销，这很有趣。过度保留加上悲观的 malloc 不足以缩小差距。在这个特定问题中，数据处理速度更为重要（注意：此处的字符串大小为 8MiB，字符串越小，结果可能会发生变化。）
配置文件引导优化 (-fprofile-generate/-fprofile-use) 允许持续获得另外 5-10%，非常感谢这个选项。