c++ - 类中的 std::map :在执行速度和内存使用之间进行权衡

Question

我的问题涉及在设计一个将被实例化数千或数百万次并在不同上下文中以不同方式使用的类时，执行速度和内存使用之间的权衡。

所以我有一个包含一堆数字属性的类(存储在 int 和 double 中)。一个简单的例子是

class MyObject
{
  public:
    double property1;
    double property2;
    ...
    double property14
    int property15;
    int property16;
    ...
    int property25;
    MyObject();
    ~MyObject();
};

这个类被不同的实例化程序使用

std::vector<MyObject> SetOfMyObjects;

可能包含多达几百万个元素。问题是，根据上下文，一些或许多属性可能仍未使用(我们不需要在给定的上下文中计算它们)，这意味着为数百万无用的 int 和 double 分配了内存。正如我所说，属性的有用性和无用性取决于上下文，我想避免为每个特定上下文编写不同的类。

所以我正在考虑使用 std::maps 仅为我使用的属性分配内存。例如

class MyObject
{
  public:
    std::map<std::string, double> properties_double;
    std::map<std::string, int> properties_int;
    MyObject();
    ~MyObject();
};

如果必须计算“property1”，它将存储为

MyObject myobject;
myobject.properties_double["property1"] = the_value;

显然，我会定义正确的“set”和“get”方法。

我知道访问 std::map 中的元素是其大小的对数，但由于属性的数量非常少(大约 25 个)，我想这也不应该减慢代码的执行速度很多。

我是不是想太多了？你认为使用 std::map 是个好主意吗？经验丰富的程序员的任何建议将不胜感激。

Answer 1

我认为这不是您的最佳选择，对于 25 个元素，就查找性能而言，使用 map 不会给您带来太多好处。此外，这取决于您将拥有哪些类型的属性，如果它是您示例中的一组固定属性，那么字符串查找将浪费内存和 CPU 周期，您可以使用所有属性的枚举或者只是一个整数，并为每个元素具有的属性使用顺序容器。对于这么少的可能属性，由于缓存友好性和整数比较，查找时间将低于映射，并且内存使用率也会降低。对于这么小的一组属性，这个解决方案稍微好一点。

还有一个问题是int 通常是double 的两倍。而且它们是不同的类型。因此，不可能直接将两者存储在一个容器中，但是您可以在每个元素中为 double 提供足够的空间，并且可以使用 union 或仅读取/如果属性“index”大于 14，则从 double 的地址写入一个 int。

所以你可以有一些简单的东西:

struct Property {
   int type;
   union {
       int d_int;
       double d_double;
   };
};

class MyObject {
    std::vector<Property> properties;
};

对于 type 1 - 14，您读取 d_double 字段，对于 type 15 - 25，您读取 d_int字段。

基准!!!

出于好奇，我做了一些测试，创建了 250k 个对象，每个对象具有 5 个 int 和 5 个 double 属性，使用 vector 、映射和哈希作为属性，并测量了内存使用情况以及设置和获取属性所花费的时间，连续运行每个测试 3 次以查看对缓存的影响，计算 getter 的校验和以验证一致性，结果如下:

vector | iteration | memory usage MB | time msec | checksum 
setting 0 32 54
setting 1 32 13
setting 2 32 13
getting 0 32 77 3750000
getting 1 32 77 3750000
getting 2 32 77 3750000

map | iteration | memory usage MB | time msec | checksum 
setting 0 132 872
setting 1 132 800
setting 2 132 800
getting 0 132 800 3750000
getting 1 132 799 3750000
getting 2 132 799 3750000

hash | iteration | memory usage MB | time msec | checksum 
setting 0 155 797
setting 1 155 702
setting 2 155 702
getting 0 155 705 3750000
getting 1 155 705 3750000
getting 2 155 706 3750000

正如预期的那样， vector 解决方案是迄今为止最快和最有效的，尽管它受冷缓存的影响最大，即使是冷运行它也比映射或哈希实现快得多。

在冷运行时，vector 实现比 map 快 16.15 倍，比 hash 快 14.75 倍。在热运行时，它甚至更快 - 分别快 61 倍和 54 倍。

在内存使用方面， vector 解决方案的效率也高得多，比映射解决方案使用的内存少 4 倍多，比哈希解决方案少近 5 倍。

正如我所说，它稍微好一点。

为了澄清，“冷运行”不仅是第一次运行，而且是在属性中插入实际值的运行，因此它可以很好地说明插入操作的开销。没有一个容器使用预分配，因此它们使用了默认的扩展策略。至于内存使用情况，它可能无法 100% 准确地反射(reflect)实际内存使用情况，因为我将整个工作集用于可执行文件，并且通常在操作系统级别也会进行一些预分配，它会最随着工作集的增加，可能会更加保守。最后但并非最不重要的一点是，映射和哈希解决方案是使用字符串查找来实现的，正如 OP 最初的意图，这就是它们效率如此之低的原因。在 map 和 hash 中使用整数作为键会产生更具竞争力的结果:

vector | iteration | memory usage MB | time msec | checksum 
setting 0 32 55
setting 1 32 13
setting 2 32 13
getting 0 32 77 3750000
getting 1 32 77 3750000
getting 2 32 77 3750000

map | iteration | memory usage MB | time msec | checksum 
setting 0 47 95
setting 1 47 11
setting 2 47 11
getting 0 47 12 3750000
getting 1 47 12 3750000
getting 2 47 12 3750000

hash | iteration | memory usage MB | time msec | checksum 
setting 0 68 98
setting 1 68 19
setting 2 68 19
getting 0 68 21 3750000
getting 1 68 21 3750000
getting 2 68 21 3750000

hash 和 map 的内存使用率要低得多，虽然仍然高于 vector，但在性能方面却是翻了个身，而 vector 解决方案在插入方面胜出，在读取和写入方面，map 解决方案获得了奖杯。所以需要权衡取舍。

至于与将所有属性都作为对象成员相比节省了多少内存，粗略计算一下，在一个顺序容器中拥有 250k 个这样的对象大约需要 80 MB 的 RAM。因此， vector 解决方案节省了大约 50 MB，而散列解决方案几乎没有。不用说 - 直接成员访问会快得多。