UnknownNooby's blog

How does memory manager work?
By UnknownNooby, history, 8 years ago, In English

Recently, one guy posted this blog, and couldn't understand what was really wrong with his code. It turns out that his code was wrong anyway, but I've noticed one thing:

Take a look at these two submissions: TL and OK.

In both solutions I am using self-written vector class, but the difference between these two codes, obviously is that in the OK code I do not use the delete[] operator, thus it takes less time to destruct my class, but doesn't free the memory on destruction (which can be seen by memory taken by solution).

Solutions take about this much time on my machine:

No vects:                  248ms
Vects with no destruction: 370ms
Vects with destruction:    948ms

The question stands: Why is delete[] operation so slow and where can I read about memory manager in c++? Google only leads me to things like "writing your own memory manager in c++" which is actually interesting, but unfortunately hard to read and that's not exactly the case I'm looking for.

  • Vote: I like it
  • +48
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think, it depends on the memory manager implementation, the same issues here and here.

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Your link to another blog is broken...

Libstdc++ operator new and delete is a simple wrapper of C runtime library malloc and free. Since Codeforces runs on Windows, you should have a look at Microsoft Visual C++ Runtime Library documentation. I think you can find it on MSDN. (I'm not sure since I do most of my work on Linux.)

→ Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It seems that this time the slowdown isn't directly caused by delete[] itself but fact that destructor is not empty. Here are some observations done with Codeforces custom invocation, in all cases n=18, p[i][j] = (i == j ? 0 : 0.5)

  • original code without delete 561 ms
  • delete in incsize 561 ms
  • delete in destructor 2776 ms
  • no delete but counter in destructor 2776 ms

Some comments on 4 case, I added a counter in destructor and incsize to count how many times each is executed. Destructor was called ~ 5·105 but incsize 2·106 . Incsize was called 4 times as many, but inserting call to delete had very little impact on performance. Another interesting observation is that slowdown can be observed by inserting other code in destructor like increasing integer variable not only delete operator.

This makes me think that slowdown is caused by nonempty destructor. Destructor needs to be executed when either scope ends the normal way or exception is thrown. I guess that problem is caused by second case. Maybe the code for exception handling becomes more complicated because it needs to do some work in it or some optimizations can't be done because in case of error it might be necessary to do additional cleanup.

It would be interesting to see if compiling with -fno-exceptions make any difference. I couldn't repeat the problem locally (GCC 6.1.1 64bit linux), there was no major difference in time between delete and no delete versions.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you are right. I use i686-w64-mingw32-g++ (version 6.1.0) and wine to test the code. The result is almost same as the Codeforces custom invocation result. But with -fno-exceptions, both version of code (with/without delete[]) cost very short time.

    → Reply