std::map in class : trade off between execution speed and memory usage

Question

My question concerns the trade off between execution speed and memory usage when designing a class that will be instantiated thousands or millions of times and used differently in different contexts.

So I have a class that contains a bunch of numerical properties (stored in int and double). A simple example would be

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

This class is used by different programs that instantiate

std::vector<MyObject> SetOfMyObjects;

that may contain as much as a few millions of elements. The thing is that depending on the context, some or many properties may remain unused (we do not need to compute them in this given context), implying that the memory for millions of useless int and double is allocated. As I said, the usefulness and uselessness of the properties depend on the context, and I would like to avoid writing a different class for each specific contexts.

So I was thinking about using std::maps to assign memory only for the properties I use. For example

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

such that if "property1" has to be computed, it would stored as

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

Obviously, I would define proper "set" and "get" methods.

I understand that accessing elements in a std::map goes as the logarithm of its size, but since the number of properties is quite small (about 25), I suppose that this should not slow down the execution of the code too much.

Am I overthinking this too much? Do you think using std::map is a good idea? Any suggestion from more seasoned programmers would be appreciated.

Answer 1

I don't think this is your best option, for 25 elements, you will not benefit that much from using a map in terms of lookup performance. Also, it depends on what kinds of properties are you going to have, if it is a fixed set of properties as in your example, then string lookup would be a waste of memory and CPU cycles, you could go for an enum of all properties or just an integer and use a sequential container for the properties each element has. For such a small number of possible properties, lookup time will be lower than a map because of cache friendliness and integer comparisons, and memory usage will be lower too. For such a small set of properties this solution is marginally better.

Then there is the problem that an int is usually twice as small as a double. And they are different types. So it is not directly possible to store both in a single container, but you could have enough space for a double in each element, and either use a union or just read/write an int from/to the address of the double if the property "index" is larger than 14.

So you can have something as simple as:

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

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

And for type 1 - 14 you read the d_double field, for type 15 - 25 the d_int field.

BENCHMARKS!!!

Out of curiosity I did some testing, creating 250k objects, each with 5 int and 5 double properties, using a vector, a map and a hash for the properties, and measured memory usage and time taken to set and get the properties, ran each test 3 times in a row to see impact on caching, calculate checksum for getters to verify consistency, and here are the results:

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

As expected, the vector solution is by far the fastest and most efficient, although it is most influenced by cold cache, even running cold it is way faster than a map or hash implementation.

On a cold run, the vector implementation is 16.15 times faster than map and 14.75 times faster than hash. On a warm run it is even faster - 61 times faster and 54 times faster respectively.

As for memory usage, the vector solution is far more efficient as well, using over 4 times less memory than the map solution and almost 5 times less than the hash solution.

As I said, it is marginally better.

To clarify, the "cold run" is not only the first run but also the one inserting the actual values in the properties, so it is fairly illustrative of the insert operations overhead. None of the containers used preallocation so they used their default policies of expanding. As for the memory usage, it is possible it doesn't accurately reflect actual memory usage 100% accurately, since I use the entire working set for the executable, and there is usually some preallocation taking place on OS level as well, it will most likely be more conservative as the working set increases. Last but not least, the map and hash solutions are implemented using a string lookup as the OP originally intended, which is why they are so inefficient. Using integers as keys in the map and hash produces far more competitive results:

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

Memory usage is much lower for hash and map, while still higher than vector, but in terms of performance the tables are turned, while the vector solution sill wins at inserts, at reading and writing the map solution takes the trophy. So there's the trade-off.

As for how much memory is saved compared to having all the properties as object members, by just a rough calculation, it would take about 80 MB of RAM to have 250k such objects in a sequential container. So you save like 50 MB for the vector solution and almost nothing for the hash solution. And it goes without saying - direct member access would be much faster.

Answer 2

TL;DR: it's not worth it.

From carpenters we get: measure twice, cut once. Apply it.

---

Your 25 int and double will occupy on a x86_64 processor:

• 14 double: 112 bytes (14 * 8)
• 11 int: 44 bytes (11 * 4)

for a total of 156 bytes.

---

A std::pair<std::string, double> will, on most implementation, consume:

• 24 bytes for the string
• 8 bytes for the double

and a node in the std::map<std::string, double> will add at least 3 pointers (1 parent, 2 children) and a red-black flag for another 24 bytes.

That's at least 56 bytes per property.

Even with a 0-overhead allocator, any time you store 3 elements or more in this map you use more than 156 bytes...

---

A compressed (type, property) pair will occupy:

• 8 bytes for the property (double is the worst case)
• 8 bytes for the type (you can choose a smaller type, but alignment kicks in)

for a total of 16 bytes per pair. Much better than map.

Stored in a vector, this will mean:

• 24 bytes of overhead for the vector
• 16 bytes per property

Even with a 0-overhead allocator, any time you store 9 elements or more in this vector you use more than 156 bytes.

---

You know the solution: split that object.