Здравствуйте, enji, Вы писали:

E>Если раскоментить помеченную строку, то скорость работы что в debug, что в release увеличится в 10-15 раз (Windows XP, MSVC 2008)

E>Т.е. получается, что освобождение памяти в порядке получения сильно медленнее, чем удаление в случайном порядке. А почему?


Старые аллокаторы в основном строились на основе т.н. freelist'ов. Если в таком аллокатре освобождать в случайном порядке, то образуется множество маленьких свободых блоков, эти все блоки надо хранить в списках. Далее, когда освобождаются смежные блоки, их приходится склеивать вместе, соотв. общий размер свободного блока меняется, соотв. его надо переупорядочивать в списке (списки свободных блоков обычно упорядочены по размеру для быстрого поиска).
В итоге, множество лишней работы, каждое освобождение может выливаться в O(logN) или что-то типа того.

Когда же ты освобождаешь по порядку (с начала или с конца — не важно), то получается только 1 свободный блок, размер которого постоянно растёт. Соотв. практически никакой работы делать не надо.

В общем, попробуй подумать, как бы ты реализовал аллокатор общего назначения для блоков произвольного размера, и тогда всё станет понятно.


з.ы. современные аллокаторы в основном строятся на основе т.н. slab-блоков. У них множество преимуществ в т.ч. выделения и освобождения всегда O(1) не зависимо от порядка (так же они зачастую headerless и гораздо более дружественны к concurrency).