Недавно наткнулся на этот пост, где человек не мог понять, в чём у него ошибка. Конкретно его ошибку не нашёл, на моём компе это выглядело как вечный цикл, но я заметил вот что:
Взгляните на эти две посылки: TL и OK.
И в той и в другой посылке используется самописный вектор, но разница в том, что в OK посылке не используется оператор delete[] в деструкторе, потому деструктор работает значительно быстрее, но при этом не освобождает память (что можно заметить, посмотрев в графу память).
На моей машине рантайм примерно такой:
Без векторов | 248ms
Вектора без деструктора | 370ms
Вектора с деструктором | 948ms
Вопрос в том, почему оператор delete[] работает так медленно, и может ли кто-то дать линк, где можно прочитать об этом? Гугл ведёт на линки уровня "напишем свой менеджер памяти на c++", что, несомненно, интересно, но это не совсем то, что я пытаюсь найти.
Автокомментарий: текст был переведен пользователем UnknownNooby (оригинальная версия, переведенная версия, сравнить).
I think, it depends on the memory manager implementation, the same issues here and here.
Your link to another blog is broken...
Libstdc++ operator
newanddeleteis a simple wrapper of C runtime librarymallocandfree. 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.)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)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.
I think you are right. I use
i686-w64-mingw32-g++(version 6.1.0) andwineto test the code. The result is almost same as the Codeforces custom invocation result. But with-fno-exceptions, both version of code (with/withoutdelete[]) cost very short time.