0

我有一个将使用数百万个向量的应用程序。

似乎 std::vector 的大多数实现都使用 4 个指针（_First、_Last、_End 和 _Alloc），这在 64 位机器上消耗 32 个字节。对于向量的大多数“实际”用例，可能会使用单个指针和两个“无符号整数”字段来分别存储当前大小和分配的大小。忽略支持自定义分配的潜在挑战（而不是假设分配必须通过全局 new & delete 运算符），似乎可以构建一个仅使用 16 个字节（或最坏 24 个字节）的 STL 兼容向量类支持 _Alloc 指针）。

在我开始编写代码之前，1) 是否有任何我应该注意的陷阱以及 2) 是否存在开源实现？

4

3 回答 3

5

你可以完成这样的事情——但你不可能获得那么多。

首先是性能方面。您正在用时间来换取内存消耗。无论您节省多少内存，每次调用时都必须进行加法和乘法运算end（好吧，如果它是一个sizeof(vector<t>::value_type) == 1可以优化乘法的向量）。请注意，大多数基于向量的手写循环代码end都会在每次循环迭代时调用。在现代 CPU 上，这实际上将是一个重大胜利，因为它允许处理器将更多的东西保存在缓存中；除非内部循环中的那几条额外指令迫使处理器过于频繁地交换指令缓存中的内容）

此外，就向量中的整体内存使用而言，内存节省可能很小，原因如下：

  • 内存管理器开销。在大多数内存管理器实现中，来自内存管理器的每个分配（当然需要哪个向量）都会自行增加 16-24 字节的开销。（假设类似dlmalloc（UNIX/Linux/etc.）或RtlHeap（Windows））
  • 过度配置负载。为了在最后实现分摊的常量插入和移除，当向量调整大小时，它会调整到向量中数据大小的某个倍数。这意味着分配的典型内存容量向量足够 1.6 (MSVC++) 或 2 (STLPort, libstdc++) 乘以实际存储在向量中的元素数量。
  • 对齐限制。如果您将这些向量放入一个数组（或另一个向量）中，请记住该向量的第一个成员仍然是指向已分配内存块的指针。无论如何，这个指针通常需要 8 字节对齐——所以你保存的 4 个字节会丢失到数组中的结构填充中。

我现在会使用 vector 的简单实现。如果您通过内存分析器运行代码并发现摆脱这两个指针可以节省大量资金，那么您可能会实现自己的优化类来满足您的性能特征，而不是依赖于内置的矢量实现。（一个这样的优化类的例子是std::string在那些实现小字符串优化的平台上）

（注意：我知道的唯一优化Alloc指针的编译器是 VC11，它尚未发布。虽然 Nim 说当前的 libstdc++ 预发布版本也能做到这一点......）

于 2012-07-02T14:31:19.273 回答
1

除非这些向量的内容非常小，否则保存内容的 16 字节与 32 字节之间的差异将只是它们消耗的总内存的一小部分。重新发明这个轮子需要付出很多努力，因此请确保您为所有这些工作获得了足够的回报。

顺便说一句，教育也很有价值，通过这样做你会学到很多东西。如果您选择继续，您可能会考虑先编写一个测试套件，然后在当前实现上进行练习，然后在您发明的那个上进行练习。

于 2012-07-02T14:36:09.720 回答
0

要回答是否值得付出努力，请找到或编写适合您需求的兼容实现（也许 std::vector 中还有其他您不需要的东西），并将性能与std::vector<your_type>相关平台上的性能进行比较。您的建议至少可以提高移动构造函数以及移动赋值运算符的性能：

typedef int32_t v4si __attribute__ ((vector_size (16)));
union
    {
    v4si data;
    struct
        {
        T* pointer;
        uint32_t length;
        uint32_t capacity;
        } content;
    } m_data;

这仅涵盖“理智” T（除了移动语义）。https://godbolt.org/g/d5yU3o

于 2017-03-17T11:49:20.317 回答