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

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

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

Если я правильно тебя понял, то получается, что освобождение по порядку должно быть быстрее, чем освобождение в случайном порядке (мне как-то так и казалось). Однако из моего эксперимента следует, что все ровно наоборот — если перемешать — быстро, если по порядку — медленно...

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

Спасибо за наводку, почитаю