How costly is it to have multiple allocations c++?

Question

I wonder to learn how costly is the memory allocation process in a utility function. For example is there a big difference between the following implementations?

string method_A (string inp) {
   auto        num_fillers = inp.length() - 4;
   string filler(num_fillers, '-');
   string res = filler + inp.substr(num_fillers);
   return res;
}

string method_B (string inp) {
  const int expect_len =4;
  auto        num_fillers = inp.length() - expect_len;
  string res;
  res.reserve(num_fillers + expect_len);
  res.assign(num_fillers, '-');
  res+= inp.substr(num_fillers);
  return res;
}

Is there any benefit of using method_B instead of method_A? What are the Pros and cons of each?

Does memory allocation once and filling up the string with the "+=" operation have a better performance than what it has been done in method_A?

Answer 1

Allocations do incur overhead, and it's good to avoid unnecessary ones when practical. But not at the expense of maintainability/complexity unless necessary. So you should always weigh that up.

In the case of the standard library, there is no realloc equivalent. Appending to a dynamic container typically involves an allocation, a copy and a delete (ignoring small string optimizations and pre-reserved capacity). If you are doing this a lot in your program, you may need to consider the possibility of memory fragmentation.

In your case, you are doing quite a lot of allocations.

Method A:

1. string inp parameter is passed by value
2. filler constructor allocates another string
3. inp.substr(num_fillers) allocates another string
4. operator+ allocates another string

Method B (full of bugs right now):

1. string inp parameter is passed by value
2. res.reserve(num_fillers + expect_len) allocates another string
3. inp.substr(num_fillers) allocates another string

So, it's not a whole lot better. You avoided one allocation but still made three. An approach with fewer allocations (based on your attempt in method_B) would be:

std::string method_C(const std::string& inp)
{
  const std::size_t expect_len = 4;
  const std::size_t num_fillers = inp.size() - std::min(inp.size(), expect_len);
  std::string res;
  res.reserve(num_fillers + expect_len);
  res.assign(num_fillers, '-');
  res.append(inp.begin() + num_fillers, inp.end());
  return res;
}

The above performs only one allocation.

An alternative to the append, if you really like using substr is to use std::string_view instead:

  res += std::string_view(inp).substr(num_fillers);

Answer 2

Certainly fewer allocations is more efficient than more allocations; OTOH doing it the "most efficient" way (by precalculating the final buffer-size you'll need in advance, so you only have to allocate the space once) makes your code more complex and harder to maintain, and introduces the risk that you'll miscalculate the buffer-size (either now, or in the future after you've modified how the string is generated and didn't properly update the size-calculation afterwards), with results potentially ranging from reduced performance to a buffer-overrun.

So you'll need to weigh the importance of maximizing runtime efficiency against the importance of keeping the code simple and maintainable. A good rule of thumb is: if you can't easily measure the performance difference, then it doesn't matter, so you should just go with whatever method produces the clearest code. (and even if you can measure a performance difference, you should ask yourself if performance matters enough in this program to make the additional complexity worthwhile)

Answer 3

You have to understand that you are writing C++ code that gets compiled into machine code. This compilation step can make a lot of changes based on the as-if rule. In particular, a C++ compiler can optimize your code in ways you probably cannot predict unless you are particularly knowledgeable on that topic.

As a result, you cannot really compare method_A and method_B in terms of performance. A sufficiently good optimizer could produce the same machine code for both.

Here is yet another version of your code that could be compiled into the same machine code:

string method_C(string inp) {
    const int expect_len = 4;
    auto num_fillers = inp.length() - expect_len;
    inp.replace(0, num_fillers, num_fillers, '-');
    return inp;
}

As you can see, I got rid of the res local variable. Does that mean it performs less memory allocation? Not necessarily. It depends on what the optimizer does with it.

Now, what can you do about it? Benchmark, if it's really necessary (and if you do, learn to do it correctly). Otherwise, write readable code, because code is written just as much, if not more, for other humans as for compilers.

Answer 4

How many allocations are you intending to do? Two or three makes not the slightest difference. 10 million should be unnoticeable; if it isn't then your memory allocator is rubbish. One billion (probably with many deallocations as well), that's where you measure your code, see if it is a bottleneck, and try out different ways and pick what is fastest. Which might be surprising.