My Quora nano moment of glory


“Mr Chueng” was kind enough to ask a question on Quora, which due to some email meandering of destiny has dropped into my inbox, too.

I think there might be some educational quality in this text, so here it is for my followers, here.  So what was the question and what is the answer.

Is C++ stl map slower than a vector when it comes to element insertion since it allocates heap memory each time, or is it as fast as a vector due to some similar techniques, probably named “memory pool” or something else?

Dear Mr Chueng,

Let us be pragmatic (as ever)

Performance of a program depends on its runtime environment that is delivered by underlying operating system (OS). Some people assume version N of a program will be “measurably faster” vs version N-1. IF memory management is improved.

But. Runtime environment of a C++ program already has extremely optimized memory management which is turn uses extremely optimized memory management OS services.

It is very (very) difficult to achieve measurable speed improvements just by “clever coding” in a C++ program, running in a modern OS.

And for 99% of todays software every measurable speed improvement is rendered invisible (or ridiculous) by a network latency. This is why systems built on Node.JS are plenty fast even they are written in JavaScript. Also with no multiple threads inside.

Thinking of a speed of C++ std lib containers is therefore not a waste of time, in very limited number of very focused use cases.

In English: if you are writing a database, a super computer weather dynamic model, or C++ matrix multiplication or similar, then it **might** have some sense in dedicating your time and money to invest in finding a faster algorithms and mechanisms to improve the performance of your server side C++ wonder.

And I emphasized the word **might** because there are already open source concepts designs and C/C++ implementations solving the HPC (high perfomance computing) for these kind of use cases.

On the other hand if you are just a healthy curious C++ beginner that is perfectly ok.

The short answer is : in well written C++ std lib there is no faster general purpose container than std::vector.

Memory pooling is a concept where one pre-allocates a pool of finite size arrays of bytes (aka memory blocks) which are then delivered by something like “pool manager” when client code requests memory.

But the problem is here that all of this requires time and space in a program. The use case when one knows the type of the object for which the memory will be requested for, is much more feasible to apply to memory pool concept.

class some_type_of_mine {} ;
using specialized_mem_pool =
         myspace::memory_pool<some_type_of_mine> ;

And this is how modern C++ std lib container templates are written internally. So there is no point in reinventions here too.

using vector_of_my_types = std::vector<some_type_of_mine> ;

Conceptually std::vector is a sequence (aka “vector” or “array”) and underlying optimizations are based on that fact. While std::map is a “set” of “pairs”, which might be ordered or unordered. Underlying map implementations are using linked list to achieve the most feasible memory management for that concept.

There is no point of comparing std::vector and std::map performance. They exist for different reasons.

Sincerely yours …