std::map and 'fat' value objects

Question

Hello!

What's better from a performance point of view std::map<uint32_t, MyObject> or std::map<uint32_t. MyObject*> if MyObject is 'fat' (that is operator= rather expensive) and I have to insert/update/delete a lot ?

Answer 1

Inserting a object leads to a call of the assignment operator (=). So the performance depends on the implementation of MyObject's assignment operator. If the implementations has to copy large amounts of data, that may lead to a performance bottleneck. If the implementation used e.g. a kind of copy-on-write scheme it should not.

More often I suppose the object style is not as performance at the pointer style. However, if it leads to an bottleneck depends on the actual application.

The advantage of using the object instead of the pointer is that is makes the memory management much easier.

Answer 2

If copying MyObjects is an expensive operation then there will be a performance penalty. However you should probably benchmark this yourself and see if it's even an issue in the context of all the other things your app is doing.

If you have boost you should consider storing a smart pointer (possibly boost::shared_pointer) in your map instead of bare pointers as this is much safer

Answer 3

If you'd prefer to store the objects "by value", but don't want to perform expensive copying, then just don't do the copying at all. For example, you can always insert "empty" objects (which can be copied quickly) and then fill them with actual content after they are already inserted into the map. The latter can be done in more efficient way by employing, for example, move semantics instead of copy semantics. Associative containers are not supposed to perform any copying between the already inserted elements (although in theory it is probably possible), so once you have taken care of the new element insertion, you should not run into any additional issues with expensive copying.

For example, a typical "expensive" insertion scenario might look as follows

MyObject new_value(/* constructor arguments */);
// Maybe do some additional preparations on `new_value`
// ...

// And now: the actual insertion
map[key] = new_value;
// .. which makes a call to the heavy assignment operator

Note, that in this scenario it is you who's making the call to the assignment operator. Since you have the control over the actual copying, you can rewrite it in much less expensive fashion, as follows

MyObject& new_value = map[key];
// Now `new_value` is a reference to a default-constructed object

// Here you should "load" the `new_value` object with whatever information
// you want it to carry. That should cover both the original constructor's
// functionality from the previous piece of code, as well as any 
// post-constructor preparations
// ...

Note, that in the second scenario the effort required to build the new value is basically the same as in the first one, but there no extra copying for the actual insertion. Also note, that in this case your object has to be default-consructible, which is not normally a requirement imposed on standard container elements.

If you decide to store the objects "by pointer", a better idea would be to use appropriate smart pointers instead of raw pointers.

Answer 4

std::map<uint32_t, boost::shared_ptr<MyObject> > is the nice way to deal with this.

If copy is expensive, it will generally be undesirable to store the map values by value.

Answer 5

Check out the Boost Pointer Container Library for containers that hold pointers safely.

Answer 6

Inserting elements will actual invoke the copy constructor, not operator=, and you shouldn't automatically assume that the overhead of dynamically allocating and accessing the object through a pointer will be faster than paying the price of an extra construction. Especially with C++0x, rvalue references can make this cost evaporate, and storing containers of pointers as a performance optimization will disappear.

Point being, don't assume that storing a fat object in a container is bad, especially std::map (which should only make one copy). That extra level of indirection can really hurt on CPU bound operations. You should measure; but the "line" where it's better to store a pointer is often much higher than people think.

It also depends on what you mean by expensive. Modern processors are really good at moving memory around. But if by expensive you mean talking over a network or reading from disk, then yeah that extra copy might be painful (..again, until rvalue references come around).