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

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

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

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

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


Хмм... действительно... я сходу прочитал так, что скорость освобождения в случайном порядке медленнее и это легко объяснить... а обратное

Слушай, а если освобождать по-порядку, но в обратном порядке — с конца, то какая скорость будет?