Статья :
QuickHeap

Автор(ы): Чистяков Владислав
Дата: 26.11.2002

Авторы :
Чистяков Владислав

Аннотация :
QuickHeap получил свое название из-за того, что при его разработке основным мотивом было получение максимально быстрого варианта хипа.

Идея, на которой базируется эта реализация, стара как мир. Для ускорения выделения памяти используется пул. Для тех, кто еще не знает, что это такое, поясню. Пул – это группа заранее проинициализированных равнозначных между собой ресурсов, из которой можно производить выделение ресурса запрашивающей стороне. Обычно пул подразумевает, что по окончанию использования ресурса он не уничтожается или освобождается, а помещается обратно в пул. Это позволяет значительно сократить время на запрос и возврат ресурса системе.

сабж

... эта фича, если я мелкими кусками выделю памяти под 2Gb и освобожу? Какой размер будет процесса ? Другие потоки смогут выделить хоть что после? Или COM'ики (MSXML) ?

Так я не понял: увеличивается ли скорость выделения ресурсов (памяти) с использованием QuickHeap по сравнению с обычноми методами или нет?
Не плохо было бы привести результаты тестирования (если они конечно есть :) )

Вообще перед написанием своего топика нужно читать предыдущие. (это я о тестах).

Ну а на счет увеличения... это вопрос. Дело в том что все зависит от оптимальности алгоритмов в программе. Если в программе основная масса объектов хранится в динамических массивах память под которые выделяется с опережением, то выигрыш или отсутствует или минимален. Но если в приложении преобладает создание объектов черз new, то выигрыш виден невооруженным взглядом. Самые высокие результаты достигаются если использовать квиг-хип для отдельных групп объектов которые интенсивно занимаются и освобождаются (оператором new).

Особо эффективен квик-хип в серверных приложениях так как отсутствуют проблемы с фрагментацией памяти. Но расход памяти увеличивается.

На реальных задачах все работает нормально. Но если постараться, то до маразма можно довести все что угодно. :)

Тесты в сатье Ткачева (http://www.rsdn.ru/mag/?0102/automemcontrol.xml)

Внимательный читатель может заметить, что размер занимаемого в хипе блока может быть сколь угодно большим, а размер массива ограничен. Прискорбно…,

а также что, играя на кратности размеров, возможно получить выигрыш.

первое что пришло на ум, при виде :



зачем два пула с размерами элементов 5 и 10 ?
можно ведь давать кусками, а непрерывность и эмулировать можно.
таким образом решается и вопрос о выделении размером 1025.

пределом развития этой мысли, является вывод о одном пуле, с размером элемента 1 байт.
по этому поводу, классик, уже говорил о единстве и боорьбе противоположностей.
следовательно, нужно прийти к наиболее оптимальному выбору.

---

Но при этом возникает другая проблема – как при освобождении памяти определить, что блок был занят в хипе, а не в пуле? К сожалению, для этого приходится тратить лишние 8 байт памяти, но так как размер выделяемого блока довольно велик, на это смело можно закрыть глаза.

мне видиться, что глаза прийдется закрывать не только для объектов в хипе, но также и для "маленьких" (в пулах).

--
"существует расстояние, на котором женщина кажется нам наиболее привлекательной. так как при x=0 и x=бесконечность, привлекательность нулевая. а в некоторой точке, внутри этого интервала, отлична от нуля." (с) "Физики шутят"

Сами пулы организованы очень просто. Память в них выделяется экстентами. [...] Таким образом, количество содержащихся в экстенте блоков удваивается с каждым следующим экстентом, и очень быстро пул набирает количество блоков, после которого добавление новых экстентов не нужно.

следует иметь в виду, что при таком подходе, очень быстро, половина занятой памяти, не будет использоваться.
точнее, скачкообразно прийдем к границе 50%, снизу. примерно 40-48%.

Здравствуйте, Чистяков Владислав, Вы писали:

ЧВ>Статья :


ЧВ>Авторы :
ЧВ>Чистяков Владислав

ЧВ>Аннотация :
ЧВ>QuickHeap получил свое название из-за того, что при его разработке основным мотивом было получение максимально быстрого варианта хипа.

У меня иногда возникает желание написать статью — "почему НЕ НАДО писать свой хип".
ИМХО в 99.9% софта сфой хип нафиг не нужен, а там где он нужен,.. там слишком специфичен, да и делается отнюдь не для того, что бы скорость увеличить, а для других целей. Если, конечно, стандартный не совсем больной, иногда и такое бывает.

На моей практике, для увеличения скорости, обычно хватает пула для совершенно конкретного типа обьектов.
Причем для какого, говорит профайлер.

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

S>

S>Сами пулы организованы очень просто. Память в них выделяется экстентами. [...] Таким образом, количество содержащихся в экстенте блоков удваивается с каждым следующим экстентом, и очень быстро пул набирает количество блоков, после которого добавление новых экстентов не нужно.

S>следует иметь в виду, что при таком подходе, очень быстро, половина занятой памяти, не будет использоваться.
S>точнее, скачкообразно прийдем к границе 50%, снизу. примерно 40-48%.

Следует, наверное, начать с классиков. Вопрос о динамическом распределении памяти не вчера возник. Над ним уже лет 30 наверное думают. Могу посоветовать почитать Кнута, там тема хорошо освещена и даны ссылки. В том числе, и правило 50% там обсуждается.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Чистяков Владислав, Вы писали:

ЧВ>Статья :


ЧВ>Авторы :
ЧВ>Чистяков Владислав

ЧВ>Аннотация :
ЧВ>QuickHeap получил свое название из-за того, что при его разработке основным мотивом было получение максимально быстрого варианта хипа.

ЧВ>Идея, на которой базируется эта реализация, стара как мир. Для ускорения выделения памяти используется пул. Для тех, кто еще не знает, что это такое, поясню. Пул – это группа заранее проинициализированных равнозначных между собой ресурсов, из которой можно производить выделение ресурса запрашивающей стороне. Обычно пул подразумевает, что по окончанию использования ресурса он не уничтожается или освобождается, а помещается обратно в пул. Это позволяет значительно сократить время на запрос и возврат ресурса системе.


попробовал потестить, ибо сам занимаюсь подобным вопросом,
есть вопрос
зачем в тестовых примерах оператор void delete пытается чтото вернуть (не компилируется)


разница действительно большая при маленьких блоков,
но наверное стоит прийти к компромису и переопределять операторы new и delete для определенных классов используя подобного рода механизм,
к томуже этой кучей можно будет управлять, а не оставлять выделенный блок пылиться, после того как
дорогостоящие операции выделения памяти завершены,

что думаете по этому поводу?

в догоку, test1 не работает,
ибо выражение (Rand()+10) % maxObjSize

может вернуть 0

Использование памяти можно неплохо сократить на sizeof(QHBlock*), если в реализации QHBlock поместить указатель m_pNext прямо в область пользовательских данных. Дело в том что или используется m_pNext (блок свободен), тогда пофиг на содержание пользовательского блока, или наоборот. По-моему выигрыш на 4-8 байт на каждый блок — это достаточно существенно.

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

Z>Использование памяти можно неплохо сократить на sizeof(QHBlock*), если в реализации QHBlock поместить указатель m_pNext прямо в область пользовательских данных. Дело в том что или используется m_pNext (блок свободен), тогда пофиг на содержание пользовательского блока, или наоборот. По-моему выигрыш на 4-8 байт на каждый блок — это достаточно существенно.

В коде он давно в union-е. Но на скорость это влияет мало.

Здравствуйте, VladD2, Вы писали:
VD>В коде он давно в union-е. Но на скорость это влияет мало.
На скорость да, а на размер — очень даже