类中的映射:在执行速度和内存使用之间进行权衡

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：：map来为我使用的属性分配内存。例如

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个元素，您将不会从使用地图的查找性能方面获益那么多。而且，这取决于您将拥有哪种属性，如果它是一组固定的属性，那么字符串查找将浪费内存和CPU周期，您可以选择所有属性的枚举，或者只是一个整数，并对每个元素所具有的属性使用顺序容器。对于如此少量的可能属性，由于缓存友好性和整数比较，查找时间将低于映射，而内存使用也将更低。对于这么小的一组属性，这个解决方案稍微好一些。

还有一个问题是，int通常是double的两倍。它们是不同的类型。因此，不可能将两者直接存储在单个容器中，但在每个元素中可以有足够的空间存储double，如果属性“索引”大于14，则可以使用union或从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字段.

BENCHMARKS!!!

出于好奇，我做了一些测试，创建了250k对象，每个对象具有5个int和5个双重属性，使用了一个向量、一个映射和一个属性哈希，并测量了设置和获取属性所需的内存使用量和时间，连续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

正如预期的那样，向量解决方案是迄今为止速度最快、效率最高的解决方案，尽管它受冷缓存的影响最大，即使冷运行它也比映射或散列实现要快得多。

在冷运行时，向量实现比map快16.15倍，比散列快14.75倍。在温暖的跑步中，速度甚至更快--分别快61倍和54倍。

在内存使用方面，向量解决方案的效率也要高得多，使用的内存比映射解决方案少4倍以上，比散列解决方案少5倍。

正如我所说，情况稍微好一些。

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

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

散列和映射的内存使用率要低得多，但仍然高于向量，但就性能而言，表被翻转，而向量解决方案在插入、读取和写入映射解决方案时获胜。所以这就是交易。

至于与将所有属性作为对象成员相比节省了多少内存，只需粗略计算，就需要大约80 MB的RAM才能将250 k这样的对象放在顺序容器中。因此，您节省了大约50 MB的矢量解决方案，几乎没有为哈希解决方案。不用说，直接访问会员的速度要快得多。

Answer 2

TL;DR:这不值得。

我们从木匠那里得到：度量两次，裁剪一次。应用它。

您的25 int和double将占用x86_64处理器：

• 14 double：112个字节(14 * 8)
• 11 int：44个字节(11 * 4)

总共156个字节。

在大多数实现中，std::pair<std::string, double>将消耗：

• 字符串的24个字节
• 双字节的8字节

std::map<std::string, double>中的一个节点将添加至少3个指针(1个父指针、2个子指针)和另一个24个字节的红黑标志。

每个属性至少有56字节。

即使使用0开销分配器，在此map中存储3个或更多元素时，也会使用超过156个字节.

压缩(类型，属性)对将占据：

• 属性的8个字节(double是最坏的情况)
• 类型的8个字节(您可以选择一个较小的类型，但对齐开始)

每对总共16个字节。比map好得多。

存储在vector中，这将意味着：

• vector的24字节开销
• 每个属性16字节

即使使用0开销分配器，在此vector中存储9个或更多元素时，也会使用超过156个字节。

你知道解决方案:分割那个对象。

Answer 3

你用名字查找对象，你知道它们会在那里。那就查一下他们的名字。

我理解访问std::map中的元素是其大小的对数，但是由于属性的数量很小(大约25)，我认为这样做不会太慢代码的执行。

你会放慢你的程序的速度超过一个数量级。一个映射的查找可能是O(logN)，但它是O(LogN) * C。与直接访问属性相比，C将是巨大的(慢数千倍)。

这意味着为数百万无用的int和double分配了内存。

在我所能想到的所有实现中，一个std::string至少是24个字节--假设您对属性的名称很感兴趣(谷歌的“短字符串优化”以获得详细信息)。

除非您的60%的属性是未填充的，否则使用字符串键的映射是不可能保存的。