两次堆分配是否比调用 std::string fill ctor 更昂贵？

Question

我想要一个容量为 131 个字符（或字节）的字符串。我知道实现这一目标的两种简单方法。那么这两个代码块哪个更快更高效呢？

std::string tempMsg( 131, '[=11=]' ); // constructs the string with a 131 byte buffer from the start
tempMsg.clear( ); // clears those '[=11=]' chars to free space for the actual data

tempMsg += "/* some string literals that are appended */";

或者这个：

std::string tempMsg; // default constructs the string with a 16 byte buffer
tempMsg.reserve( 131 ); // reallocates the string to increase the buffer size to 131 bytes??

tempMsg += "/* some string literals that are appended */";

我想第一种方法只使用 1 次分配，然后将所有这 131 个字节设置为 0 ('\0')，然后清除字符串（std::string::clear 通常是常量 根据：https://www.cplusplus.com/reference/string/string/clear/)。第二种方法使用 2 次分配，但另一方面，它不必将任何内容设置为“\0”。但我也听说编译器出于优化目的在堆栈上为字符串对象分配 16 个字节。所以第二种方法也可能只使用 1 个堆分配。

那么第一种方法比另一种方法快吗？或者还有其他更好的方法吗？

Answer 1

最准确的答案是视情况而定。最可能的答案是第二个更快或同样快。调用填充 ctor 不仅需要堆分配，还需要填充（根据我的经验，通常转换为 memset）。

clear 除了将第一个指针或大小整数设置为零之外，通常不会对 POD char 做任何事情，因为 char 是一种可轻易破坏的类型。 clear 通常不涉及循环，除非您使用非平凡的 UDT 创建 std::basic_string。 ~~否则它是常数时间的，而且在几乎每个标准库实现中都非常便宜。~~

编辑：重要提示： 我从未遇到过执行此操作的标准库实现，或者它已经忘记了我的记忆（很有可能，因为我认为我正在变老），但是 Viktor Sehl 向我指出了一些非常重要的事情，我在评论：

Please note that std::string::clear() on some implementations free the allocated memory (if there are any), unlike a std::vector. –

这实际上会使您的第一个版本涉及两个堆分配。但是第二个应该还是只有一个（和你想的相反）。

已恢复：

But I've also heard about compilers allocating 16 bytes on the stack for a string object for optimization purposes. So the 2nd method might use only 1 heap allocation as well.

小型缓冲区优化

第一个分配是针对使用它的实现的小缓冲区堆栈优化（技术上并不总是堆栈，但它会避免额外的堆分配）。它不是单独堆分配的，你不能用填充构造函数来避免它（填充构造函数仍然会分配小缓冲区）。你可以避免的是在你用你真正想要的东西填充它之前用 '[=16=]' 填充整个数组，这就是为什么第二个版本可能更快（略微或不取决于你从循环中调用它的次数).这是不必要的开销，除非优化器为您消除了它，而且根据我的经验，优化器不太可能在无法使用 SSA 之类的东西进行优化的循环情况下这样做。

我只是在这里投球，因为你的第二个版本的意图也比用一些东西填充字符串作为尝试优化更清晰（在这种情况下，如果你问我，这是一个很可能误入歧途的人）只是把它扔掉并替换它与你真正想要的。第二个至少在意图上更清晰，并且几乎可以肯定在大多数实现中同样快或更快。

分析

如果有疑问，我总是建议进行测量，尤其是在您开始尝试第一个示例中的有趣事情之前。如果您在性能关键领域工作，我怎么推荐分析器都不为过。探查器不仅会为您回答这个问题，还会教您不要像第一个示例那样编写这种违反直觉的代码，除非它会产生真正的积极影响（在这种情况下，我认为不同之处在于实际上是负面的或中性的）。在我看来，分析器和调试的使用应该是 CS 101 中最理想的教学内容。分析器有助于减轻人们优化错误事物的危险倾向，这会适得其反。它们往往非常易于使用；你只需运行它们并让你的代码执行你想要优化的昂贵操作，你就会得到像这样的好结果：

如果小缓冲区优化让你有点困惑，一个简单的例子是这样的：

struct SomeString
{
    // Pre-allocates (always) some memory in advance to avoid additional
    // heap allocs.
    char small_buffer[some_small_fixed_size] = {};

    // Will point to small buffer until string gets large.
    char* ptr = small_buffer;
};

小缓冲区的分配是不可避免的，但不需要单独调用malloc/new/new[]。而且它不是在堆上与字符串对象本身分开分配的（如果它是在堆上分配的）。因此，您展示的两个示例最多涉及单个堆分配（~~除非您的标准库实现是 FUBAR~~ -- edit: 或者 Viktor 正在使用的)。第一个例子在概念上是一个 fill/loop（可以在汇编中实现为一个非常有效的内在函数，但是 loopy/linear 时间的东西）除非优化器消除它。

字符串优化

So is the first method faster than the other one? Or are there any other better methods?

您可以编写自己的字符串类型，它使用一个 SBO，比如 256 字节的小缓冲区，这通常比任何 std::string 优化都大得多。然后，您可以完全避免为 131 长度的情况分配堆。

template <class Char, size_t SboSize=256>
class TempString
{
private:
    // Stores the small buffer.
    Char sbo[SboSize] = {};

    // Points to the small buffer until num > SboSize.
    Char* ptr = sbo;

   // Stores the length of the string.
   size_t num = 0;

   // Stores the capacity of the string.
   size_t cap = SboSize;

public:
    // Destroys the string.
    ~TempString()
    {
        if (ptr != sbo)
            delete[] ptr;
    }

    // Remaining implementation left to reader. Note that implementing
    // swap requires swapping the contents of the SBO if the strings
    // point to them rather than swapping pointers (swapping is a
    // little bit tricky with SBOs involved, so be wary of that).
};

这不适合持久存储，因为如果你将一堆字符串持久存储在容器。尽管您转入和转出函数调用，但它非常适合临时字符串。我主要是一名游戏开发人员，因此考虑到我们对具有高图形保真度的实时反馈的要求，在这里使用我们自己的标准 C++ 库替代品是很正常的。不过，我不会向胆小的人推荐它，而且绝对不能没有分析器。这在我的领域是一个非常实用和可行的选择，尽管在您的领域可能很荒谬。标准库非常好，但它是为满足整个世界的需求而量身定制的。如果您可以根据您的需要非常具体地定制您的代码并生成适用范围更广的代码，您通常可以击败它。

实际上，即使 std::string 与 SBO 无论如何也不适合持久存储，而不仅仅是上面的 TempString 因为如果你像 std::unordered_map<std::string, T> 和 std::string 那样存储使用一个 16 字节的 SBO 膨胀 sizeof(std::string) 到 32 字节或更多，那么你的键将需要 32 字节，即使它们只存储一个字符只适合两个或更少的字符串在散列遍历时在单个缓存行中 table.这是使用 SBO 的缺点。它们可能会破坏您对作为应用程序状态一部分的持久存储的内存使用。但是它们非常适合内存只是以 LIFO alloc/dealloc 模式压入和弹出 to/from 堆栈的临时对象，该模式只需要递增和递减堆栈指针。

如果您想从内存的角度优化许多字符串的存储，那么这在很大程度上取决于您的访问模式和需求。但是，如果您只想构建字典而不需要动态删除特定字符串，那么一个相当简单的解决方案就是这样：

// Just using a struct for simplicity of illustration:
struct MyStrings
{
    // Stores all the characters for all the null-terminated strings.
    std::vector<char> buffer;

    // Stores the starting index into the buffer for the nth string.
    std::vector<std::size_t> string_start;

    // Inserts a null-terminated string to the buffer.
    void insert(const std::string_view str)
    {
        string_start.push_back(buffer.size());
        buffer.insert(buffer.end(), str.begin(), str.end());
        buffer.push_back('[=12=]');
    }

    // Returns the nth null-terminated string.
    std::string_view operator[](int32_t n) const
    {
        return {buffer.data() + string_start[n]};
    }
};

如果您在关联容器中存储大量重复字符串或需要快速搜索可提前查找的字符串，另一种非常有用的常见解决方案是使用字符串驻留。上述解决方案也可以结合起来实现一种有效的方式来存储所有的驻留字符串。然后，您可以存储轻量级索引或指向驻留字符串的指针，并立即比较它们是否相等，例如，不涉及任何循环，并存储许多对仅花费整数或指针大小的字符串的重复引用。

两次堆分配是否比调用 std::string fill ctor 更昂贵？

Are two heap allocations more expensive than a call to std::string fill ctor?

c++

optimization

constructor

heap-memory

stdstring