Здравствуйте, jazzer, Вы писали:
R>>Хмм... действительно... я сходу прочитал так, что скорость освобождения в случайном порядке медленнее и это легко объяснить... а обратное
J>
J>О Я. И. Френкеле рассказывают, что якобы в ФТИ в 30-е годы его изловил в коридоре некий экспериментатор и показал полученную на опыте кривую. Подумав минуту, Я. И. дал объяснение хода этой кривой. Однако выяснилось, что кривая случайно была перевёрнута вверх ногами. Кривую водворили на место и, немного поразмыслив, Я. И. объяснил и это поведение кривой.
J>(c) «Физики продолжают шутить»
Да, я тоже сразу вспомнил эту историю
... но всё-таки я надеюсь, что я не сильно уподобился Френкелю, т.к. на правильном тесте
Здравствуйте, remark, Вы писали:
R>Хмм... действительно... я сходу прочитал так, что скорость освобождения в случайном порядке медленнее и это легко объяснить... а обратное
О Я. И. Френкеле рассказывают, что якобы в ФТИ в 30-е годы его изловил в коридоре некий экспериментатор и показал полученную на опыте кривую. Подумав минуту, Я. И. дал объяснение хода этой кривой. Однако выяснилось, что кривая случайно была перевёрнута вверх ногами. Кривую водворили на место и, немного поразмыслив, Я. И. объяснил и это поведение кривой.
Здравствуйте, enji, Вы писали:
E>Если раскоментить помеченную строку, то скорость работы что в debug, что в release увеличится в 10-15 раз (Windows XP, MSVC 2008)
E>Т.е. получается, что освобождение памяти в порядке получения сильно медленнее, чем удаление в случайном порядке. А почему?
Старые аллокаторы в основном строились на основе т.н. freelist'ов. Если в таком аллокатре освобождать в случайном порядке, то образуется множество маленьких свободых блоков, эти все блоки надо хранить в списках. Далее, когда освобождаются смежные блоки, их приходится склеивать вместе, соотв. общий размер свободного блока меняется, соотв. его надо переупорядочивать в списке (списки свободных блоков обычно упорядочены по размеру для быстрого поиска).
В итоге, множество лишней работы, каждое освобождение может выливаться в O(logN) или что-то типа того.
Когда же ты освобождаешь по порядку (с начала или с конца — не важно), то получается только 1 свободный блок, размер которого постоянно растёт. Соотв. практически никакой работы делать не надо.
В общем, попробуй подумать, как бы ты реализовал аллокатор общего назначения для блоков произвольного размера, и тогда всё станет понятно.
з.ы. современные аллокаторы в основном строятся на основе т.н. slab-блоков. У них множество преимуществ в т.ч. выделения и освобождения всегда O(1) не зависимо от порядка (так же они зачастую headerless и гораздо более дружественны к concurrency).
Здравствуйте, remark, Вы писали:
R>Старые аллокаторы в основном строились на основе т.н. freelist'ов. Если в таком аллокатре освобождать в случайном порядке, то образуется множество маленьких свободых блоков, эти все блоки надо хранить в списках. Далее, когда освобождаются смежные блоки, их приходится склеивать вместе, соотв. общий размер свободного блока меняется, соотв. его надо переупорядочивать в списке (списки свободных блоков обычно упорядочены по размеру для быстрого поиска). R>В итоге, множество лишней работы, каждое освобождение может выливаться в O(logN) или что-то типа того.
R>Когда же ты освобождаешь по порядку (с начала или с конца — не важно), то получается только 1 свободный блок, размер которого постоянно растёт. Соотв. практически никакой работы делать не надо.
Если я правильно тебя понял, то получается, что освобождение по порядку должно быть быстрее, чем освобождение в случайном порядке (мне как-то так и казалось). Однако из моего эксперимента следует, что все ровно наоборот — если перемешать — быстро, если по порядку — медленно...
R>з.ы. современные аллокаторы в основном строятся на основе т.н. slab-блоков. У них множество преимуществ в т.ч. выделения и освобождения всегда O(1) не зависимо от порядка (так же они зачастую headerless и гораздо более дружественны к concurrency).
Здравствуйте, enji, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>Старые аллокаторы в основном строились на основе т.н. freelist'ов. Если в таком аллокатре освобождать в случайном порядке, то образуется множество маленьких свободых блоков, эти все блоки надо хранить в списках. Далее, когда освобождаются смежные блоки, их приходится склеивать вместе, соотв. общий размер свободного блока меняется, соотв. его надо переупорядочивать в списке (списки свободных блоков обычно упорядочены по размеру для быстрого поиска). R>>В итоге, множество лишней работы, каждое освобождение может выливаться в O(logN) или что-то типа того.
R>>Когда же ты освобождаешь по порядку (с начала или с конца — не важно), то получается только 1 свободный блок, размер которого постоянно растёт. Соотв. практически никакой работы делать не надо.
E>Если я правильно тебя понял, то получается, что освобождение по порядку должно быть быстрее, чем освобождение в случайном порядке (мне как-то так и казалось). Однако из моего эксперимента следует, что все ровно наоборот — если перемешать — быстро, если по порядку — медленно...
Хмм... действительно... я сходу прочитал так, что скорость освобождения в случайном порядке медленнее и это легко объяснить... а обратное
Слушай, а если освобождать по-порядку, но в обратном порядке — с конца, то какая скорость будет?
Здравствуйте, enji, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>Слушай, а если освобождать по-порядку, но в обратном порядке — с конца, то какая скорость будет?
E>В среднем получается примерно так: E>в порядке выделения — 9,6 E>в обратном порядке — 11,6 E>в случайном порядке — 1
E>Может быть при освобождении в случайном порядке не происходит объединения блоков?
Тогда уж логичнее предположить, что твой аллокатор при освобождении объединяет смежные свободные блоки:
— соотв при прямом/обратном порядке объединение выполняется каждый раз, кроме первого — к свободной памяти присоединяется один блок.
— при случайном же порядке — чем больше блоков уже освобождено, тем большая вероятность, что при новом освобождении к свободной памяти присоединиться уже сразу пачка непрерывно освобожденных блоков.
Здравствуйте, enji, Вы писали:
R>>Слушай, а если освобождать по-порядку, но в обратном порядке — с конца, то какая скорость будет?
E>В среднем получается примерно так: E>в порядке выделения — 9,6 E>в обратном порядке — 11,6 E>в случайном порядке — 1
E>Может быть при освобождении в случайном порядке не происходит объединения блоков?
Пока ничего в голову не приходит... даже не знаю, как они смогли такого добиться. Вроде уж кажется, такие стандартные паттерны освобождения как в прямом и обратном порядке хип должен поддерживать достаточно эффективно...
Кстати, slab аллокатор есть в винде (они его называют LFH, Low Fragmentation Heap) и его можно включить следующим образом:
ULONG opt = 2;
if (0 == HeapSetInformation((HANDLE)_get_heap_handle(), HeapCompatibilityInformation, &opt, sizeof(opt)))
exit(-printf("Failed to ennable LFH"));
Попробуй, мне кажется с ним цифры должны стать более консистентными. Хотя, конечно, поведение текущей кучи остаётся загадкой...
R>>Попробуй, мне кажется с ним цифры должны стать более консистентными. Хотя, конечно, поведение текущей кучи остаётся загадкой...
E>Не получается, Failed to ennable LFH
Надо без отладчика запускать, или определить переменную окружения _NO_DEBUG_HEAP=1
Здравствуйте, enji, Вы писали:
R>>Слушай, а если освобождать по-порядку, но в обратном порядке — с конца, то какая скорость будет?
E>В среднем получается примерно так: E>в порядке выделения — 9,6 E>в обратном порядке — 11,6 E>в случайном порядке — 1
E>Может быть при освобождении в случайном порядке не происходит объединения блоков?
Может он действительно откладывает объединение, если освобождается не первый и не последний блок. Откладывать он может, например, до того момента, пока не понадобится большой блок, под который нет достаточно памяти. В принципе это разумно, т.к. может большой блок и не понадобится.
Если это всё ещё интересно, то можешь попробовать запустить следующий код.
Тут во-первых чередуются выделения и освобождения, а во-вторых блоки разного размера, что бы сделать ситуацию по-интереснее.
enum {Count = 100000 };
enum {Repeat = 10 };
typedef std::vector<void*> TVector;
TVector alloc;
for (int x = 0; x != Repeat; ++x)
{
for (int i = 0; i < Count; ++i)
alloc.push_back(new char[rand()]);
//std::random_shuffle(alloc.begin(), alloc.end()); // !!!!!!!!!!!!for (TVector::iterator cur = alloc.begin(), end = alloc.end(); cur != end; ++cur)
delete[] *cur;
}
Здравствуйте, remark, Вы писали:
R>Если это всё ещё интересно, то можешь попробовать запустить следующий код. R>Тут во-первых чередуются выделения и освобождения, а во-вторых блоки разного размера, что бы сделать ситуацию по-интереснее.
Тут ситуация обратная — в случайном порядке освобождение идет дольше, чем в порядке выделения.
В случае случайных блоков — примерно в 5 раз, фиксированных — примерно в 2 раза
PS Собственно цель была сравнить boost::pool и new\delete на блоках фиксированного размера. Попутно вылез этот интересный эффект
Пока получается, что pool ускоряет примерно раза в 3 (и в 1,5 при включении LFH)
Здравствуйте, enji, Вы писали:
R>>Если это всё ещё интересно, то можешь попробовать запустить следующий код. R>>Тут во-первых чередуются выделения и освобождения, а во-вторых блоки разного размера, что бы сделать ситуацию по-интереснее.
E>Тут ситуация обратная — в случайном порядке освобождение идет дольше, чем в порядке выделения. E>В случае случайных блоков — примерно в 5 раз, фиксированных — примерно в 2 раза
и это легко объяснить... а обратное 
