Странное поведение free() в MinGW

1,00
р.
Столкнулся с очень странной проблемой, которая связана, по всей видимости, с работой free() из состава MinGW x32 и MinGW x64.
Все началось с языка C и функции, которая освобождает хэш-мультиотображение ото всех пар (узлов), вызывая для ключа и данных каждой пары простой free().
Проблема заключалась в том, что при не очень большом количестве узлов программа как буд-то бы уходила в вечный цикл. Перерыв весь свой код, я заподозрил, что проблема кроется не в нем, а где-то уровнем ниже.
Методом проб мне удалось выяснить, что большое количество вызовов маленьких free() имеет НЕЛИНЕЙНЫЙ рост по сложности.
Вот график:

Судя по графику, free() или то, что он там внутри себя вызывает, имеет сложность, близкую к O(n^2). И это странно. Я измерял время удаления не только всего связного списка, но и время free() для каждого узла.
И с каждым узлом это время растет.
Я пробовал использовать компиляторы MinGW x32 и MinGW x64, проблема осталась и там, и там. Debug/Release так же не влияют на происходящее. Используемая операционная система - Windows 10 x64.
Сперва я был уверен, что проблема свойственна исключительно языку C и его стандартной реализации free(), но все же решил написать небольшую проверку, используя то, что точно работает - std::forward_list.
При использовании C++ и MinGW результат оказался абсолютно идентичным.
Вот код:
#include #include #include #include
using namespace std
int main(int argc, char **argv) { clock_t t1, t2 { forward_list> list
t1 = clock() for (size_t i = 0 i < 10 * 1000 * 1000 ++i) { unique_ptr uf{ new float() } list.push_front(std::move(uf)) } t2 = clock()
cout << t2 - t1 << endl <br> t1 = clock() }
t2 = clock()
cout << t2 - t1 << endl <br> getchar()
return 0 }
Проблема та же - ОЧЕНЬ долгое удаление узлов и маленьких данных, которые в этих узлах хранятся. Выше приведенный код выполняется уже минут пять, а память освободилась только наполовину 600 Мб -> 320 МБ.
Приведенный код на моем ржавом железе выводит:
42 177 870 000
Мы пробовали повторить тесты в Visual Studio, оказалось, что список удаляется даже быстрее, чем создается.
То есть, проблема квадратичной сложности свойственна компиляторам MinGW. В понедельник я еще проверю поведение Clang.
Я не понимаю, что происходит.
Может быть, в MinGW реализация free(), а так же delete/delete[], содержит баг, из-за которого в Windows 10 происходит описанный атас? Это ведь ненормально, что связный список из 10 000 000 узлов удаляется 15(!!!) минут.
Очень хотелось бы понять, с чем это связано, кто виноват и что делать.

Ответ
После долгих размышлений в чате под вопросом выяснилось, что автор банально запускал свой, хоть и релизный, билд с помощью дебаггера.
Почему это так плохо влияет в данном случае на скорость - разберемся ниже.
Дисклеймер
Данный ответ относится только к ОС Windows, автор, судя по чату, тоже сидит на Windows. Есть ли Debug Heap на Unix/Linux и как там это все работает я не знаю. Если среди читающих это найдется знающий человек - с удовольствием прочту его ответ/дополнение к моему ответу по этому поводу.

Запуск одинаковой программы в дебаггере и без него значительно снизит скорость ее работы, вернее сказать, скорость сильно зависит от кол-ва выделяемой памяти из кучи, будь то с помощью malloc или new. Почему? Ответ прост:
Debug Heap
В Windows существует специальная куча для отслеживания утечек памяти и прочих прелестей - речь сейчас не об этом. Суть в том, что дебаггер запускает приложение с помощью этой специальной кучи:
Processes that the debugger creates (also known as spawned processes) behave slightly differently than processes that the debugger does not create. Instead of using the standard heap API, processes that the debugger creates use a special debug heap.
В данном случае нас интересует, что там с выделением и освобождением памяти. Все просто:
The Debug versions of the heap functions call the standard or base versions used in Release builds. When you request a memory block, the debug heap manager allocates from the base heap a slightly larger block of memory than requested and returns a pointer to your portion of that block.For example, suppose your application contains the call: malloc( 10 ). In a Release build, malloc would call the base heap allocation routine requesting an allocation of 10 bytes. In a Debug build, however, malloc would call _malloc_dbg, which would then call the base heap allocation routine requesting an allocation of 10 bytes plus approximately 36 bytes of additional memory.
Вместо 10 байт мы получили в разы больше, это достаточно большой оверхед для 10ти байт, если выделять большие куски памяти самостоятельно их разделять - такой проблемы уже не будет. Да и выделять память пореже и большими кусками - в целом хорошая практика даже без дебаггера.
Вся эта дополнительная память уходит на, очевидно, информацию для дебага, конкретно, для этой структуры:
typedef struct _CrtMemBlockHeader { // Pointer to the block allocated just before this one: struct _CrtMemBlockHeader *pBlockHeaderNext // Pointer to the block allocated just after this one: struct _CrtMemBlockHeader *pBlockHeaderPrev char *szFileName // File name int nLine // Line number size_t nDataSize // Size of user block int nBlockUse // Type of block long lRequest // Allocation number // Buffer just before (lower than) the user's memory: unsigned char gap[nNoMansLandSize] } _CrtMemBlockHeader
Не вижу смысла углубляться, вопрос не об этом, да и лучше msdn я явно не объясню :)

Что же мы видим у вас в коде?
for (size_t i = 0 i < 10 * 1000 * 1000 ++i) { unique_ptr uf{ new float() } ... }
Миллионы запросов выделить 4 байта. Это и без дебагов, скажем так, не особо круто, ну а с дебаггером - тихий ужас. Вы, как выразились на msdn, приблизительно выделяете (4 + 36) * 10 * 1.000 * 1.000 ~ 382мб вместо 38мб, не совсем понятно, почему такие цифры вас не смутили изначально. И это я молчу про то, что сам аллокатор тоже выделяет память для контроля и прочей системной мишуры.
Из таких расчетов следует 2 факта:
Понятно, почему выделялись такие объемы памяти, вы в своем же вопросе писали о 600мб. Скорость работы malloc/free, new/delete напрямую зависит от того, как именно выделяется памяти.
В случае дебаггера - это много дебажной информации, которую тоже нужно выделить, причем отдельно от вашей памяти, а это как минимум 1 дополнительный вызов malloc/new и free/delete. Дебаггер при этом тоже использует ресурсы ЦП для управления всем этим. Более того, эти блоки для дебага памяти хранятся в виде двусвязного списка в порядке аллокации.
В данном примере память освобождается в обратном порядке, с чем двусвязный список справляется достаточно быстро, так что вам еще повезло. Был бы это какой-нибудь std::map - программа работала бы еще медленнее. Да и вы не указали конкретный код в вашем проекте, возможно, вы в разном порядке удаляете узлы - это тоже замедлит работу.
All the resulting memory blocks in the debug heap are connected in a single linked list, ordered according to when they were allocated.

В гугле полно примеров и одинаковых вопросов на эту тему, вот первый попавшийся пример быстродействия с дебажной кучей и без:

Чем чаще вызывается аллокация памяти - тем медленнее работает программа в дебаггере.

Как отключить Debug Heap?
Самый простой способ - не запускать приложение через дебаггер. Это можно сделать прямо в Visual Studio - Ctrl + F5.
Более "умные" способы:
Для отдельного проекта: присвоить переменной среды _NO_DEBUG_HEAP значение 1:
Для всех проектов: отключить Enable Windows debug heap allocator (Native only):

Подробнее можно прочесть по ссылке. Скриншоты взяты оттуда же.

Выводы
Программа под дебаггером всегда работает медленнее, ну уж точно не быстрее. Запуск release версии в дебаггере - это все равно дебаг на уровне выделения памяти. Следит за этим ОС через ntdll.dll, который и проверяет без спроса, как запускается ваше приложение. Кажется, что эту проблема можно вообще не решать - ведь конечное приложение будет запускаться без дебаггера. Да, это так. В чате уже писали про "выделяется страница, а конкретная реализация free/new управляет этим". Но тут возникает вопрос: а зачем вы вообще используете односвязный список для хранения float`ов? Только ради O(1) для вставки/удаления? Ну ради такой вставки использовать списки - плохая затея.