Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
Казалось бы достаточно было бы сделать STL'ный buffer.reserve. Но при каждом увеличении массива происходит создание НОВОГО нативного массива, а потом ещё и создание поштучно конструктором копии/переноса в нем всех уже существующих элементов. То есть — если мы не хотим добавлять конструктор переноса в класс наших объектов — то работать будет очень медленно.
Можно было попробовать использовать std::deque. Ну и проблема скорее не в перемещении, а в том что все указатели на созданные объекты устаревают.
Мне почему то всегда казалось, что std::deque — это двухсвязаный список, тоесть есть издержки и на добавление и на поиск. Но перечитав документацию на него понял что ошибался.
Тем не менее — только что проверил — быстрее не оказалось:
Результаты (с декой — 5й):
1: 94
2: 64
3: 35
4: 140
5: 99
Тем не менее — только что проверил — быстрее не оказалось:
template <typename T, unsigned int chunk_size = 100>
class PoolDeque
{
public:
PoolDeque(){}
inline T* get(){
if(free_ptrs.empty()){
makeMore();
}
T* obj = free_ptrs.back();
free_ptrs.pop_back();
return obj;
}
inline void free(T* obj){
free_ptrs.push_back(obj);
}
void clearPool(){
buffers.clear();
free_ptrs.clear();
}
private:
std::deque<T> buffers;
std::vector<T*> free_ptrs;
void makeMore(){
buffers.resize(buffers.size() + chunk_size);
for (int i = 0; i < chunk_size; ++i) {
buffers.emplace_back();
free_ptrs.emplace_back(&buffers.back());
}
}
};
Результаты (с декой — 5й):
1: 94
2: 64
3: 35
4: 140
5: 99
В приведённом коде в makeMore() ошибка: вызывается и resize, и emplace_back. Из них я бы оставил resize.
Попробуйте убрать emplace_back и поймете в чем дело :)
resize() — всего лишь выделяет память. Но не создает новый объект.
Собственно объект создает (и добавляет элемент, и увеличивает size() ) — emplace_back/push_back
resize() — всего лишь выделяет память. Но не создает новый объект.
Собственно объект создает (и добавляет элемент, и увеличивает size() ) — emplace_back/push_back
… reserve? Собственно, у deque его даже и нет, потому что расширение считается простой операцией.
Вы имели ввиду наверное это (действительно перепутал с reserve):
Как ни странно — скорость выполнения все ещё ниже чем предложенным в статье способом.
void makeMore(){
int init_size = buffers.size();
int target_size = buffers.size() + chunk_size;
buffers.resize(target_size);
for (int i = init_size; i < target_size; ++i) {
//buffers.emplace_back();
free_ptrs.emplace_back(&buffers[i]);
}
}
Как ни странно — скорость выполнения все ещё ниже чем предложенным в статье способом.
путаете с reserve?
неправильно
www.cplusplus.com/reference/vector/vector/resize/
resize инициализирует новые объекты дефолтным конструктором, или копиями переданного объекта
www.cplusplus.com/reference/vector/vector/resize/
resize инициализирует новые объекты дефолтным конструктором, или копиями переданного объекта
В boost, это называется Boost.Pool. Есть ещё один быстрый аллокатор для мелких объектов из библиотеки Loki: SmallObjectAllocator . Интересно было бы посмотреть сравнение с ними.
Спасибо — буду знать.
Могу выложить qt проект — потестируете.
Мне же Буст встраивать в целевой проэкт не представляется возможным :) Хотел ptr_vector из библиотеки только вырвать — так там туча зависимостей. На этом моё знакомство с бустом закончилось :).
Про локи первый раз слышу :) (ну может второй)
Могу выложить qt проект — потестируете.
Мне же Буст встраивать в целевой проэкт не представляется возможным :) Хотел ptr_vector из библиотеки только вырвать — так там туча зависимостей. На этом моё знакомство с бустом закончилось :).
Про локи первый раз слышу :) (ну может второй)
С бустом поставляется утилита BCP, которая позволяет вырезать необходимое подмножество классов, чтобы не таскать всю библиотеку полностью. Вообще, при использовании небольших утилит из буста, зависимость появляется от сравнительного малого количества классов, обычно boost/config и что-то подобное.
Для удаления array внутри Buffer надо использовать delete[] а не простой delete.
И вы вызываете деструкторы даже для тех объектов, для который не был вызван конструктор.
И вы вызываете деструкторы даже для тех объектов, для который не был вызван конструктор.
можете еще new переопределить и использовать собственный аллокатор (e.g www.garret.ru/threadalloc/readme.html) ;)
Проблема ваших тестов, что они влияют друг на друга: используется «прогретый» вектор.
Если отключить все тесты, кроме одного, перекомпилировать, и запустить несколько раз, то у меня std::vector стабильно быстрее на ~30%:
код
Если отключить все тесты, кроме одного, перекомпилировать, и запустить несколько раз, то у меня std::vector стабильно быстрее на ~30%:
PoolFactory: 0.026922s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (57.9%)
PoolFactory: 0.026090s wall, 0.015600s user + 0.015600s system = 0.031200s CPU (119.6%)
PoolFactory: 0.026244s wall, 0.015600s user + 0.015600s system = 0.031200s CPU (118.9%)
PoolFactory: 0.026641s wall, 0.015600s user + 0.015600s system = 0.031200s CPU (117.1%)
PoolFactory: 0.027969s wall, 0.031200s user + 0.000000s system = 0.031200s CPU (111.6%)
PoolFactory: 0.027408s wall, 0.000000s user + 0.031200s system = 0.031200s CPU (113.8%)
std::vector: 0.018685s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (83.5%)
std::vector: 0.019019s wall, 0.015600s user + 0.015600s system = 0.031200s CPU (164.0%)
std::vector: 0.019300s wall, 0.000000s user + 0.015600s system = 0.015600s CPU (80.8%)
std::vector: 0.018718s wall, 0.000000s user + 0.015600s system = 0.015600s CPU (83.3%)
std::vector: 0.018500s wall, 0.015600s user + 0.015600s system = 0.031200s CPU (168.7%)
std::vector: 0.020583s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (75.8%)
код
#include <boost/timer/timer.hpp>
...
int main(int argc, char *argv[])
{
{
std::vector< BaseClass > ar;
ar.reserve(total);
boost::timer::auto_cpu_timer timer1;
for (int var = 0; var < total; ++var) {
ar.emplace_back(var);
}
timer1.stop();
std::cout <<"std::vector : ";
timer1.report();
}
{
std::vector< BaseClass* > ptr_ar;
PoolFactory<BaseClass> bPool;
ptr_ar.reserve(total);
boost::timer::auto_cpu_timer timer3;
for (int var = 0; var < total; ++var) {
ptr_ar.push_back(bPool.get(var));
}
timer3.stop();
std::cout <<"PoolFactory : ";
timer3.report();
}
}
При повторном заполнении vector всё равно чуть-чуть быстрее. Типичный запуск
PoolFactory: 0.027588s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (56.5%)
PoolFactory 2: 0.011758s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (132.7%)
…
std::vector: 0.018754s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (83.2%)
std::vector 2: 0.010039s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (155.4%)
…
std::vector< BaseClass > ar;
{
ar.reserve(total);
/// .... std::vector
ar.clear();
}
{
ar.reserve(total);
/// .... std::vector 2
ar.clear();
}
PoolFactory<BaseClass> bPool;
{
std::vector< BaseClass* > ptr_ar;
ptr_ar.reserve(total);
/// PoolFactory
bPool.freeAll();
}
{
std::vector< BaseClass* > ptr_ar;
ptr_ar.reserve(total);
/// PoolFactory 2
bPool.freeAll();
}
PoolFactory<BaseClass> bPool;
{
std::vector< BaseClass* > ptr_ar;
ptr_ar.reserve(total);
/// PoolFactory
bPool.freeAll();
}
{
std::vector< BaseClass* > ptr_ar;
ptr_ar.reserve(total);
/// PoolFactory 2
bPool.freeAll();
}
Здесь для чистоты эксперимента, раз уж мы «прогреваемся» следует и std::vector< BaseClass* > ptr_ar; вынести:
PoolFactory<BaseClass> bPool;
std::vector< BaseClass* > ptr_ar;
{
ptr_ar.reserve(total);
/// PoolFactory
bPool.freeAll();
}
{
ptr_ar.reserve(total);
/// PoolFactory 2
bPool.freeAll();
}
Пул от того выигрывать не станет, но по крайне мере проигрывает не так сильно :)
Насчет прогрева — в моём понимании reserve именно и должен был выполнить «прогрев». Попробовал ваш код. Получил несколько более медленное заполнение с пулом чем с emplace_back (порядка 5% разницы). Но вот при повторном проходе удивился — с пулом НЕ стало быстрее. Причина тому, то что при get() — пул инициализирует объект вызывая конструктор. Попробовал сравнивать emplace_back() и getRaw() — пул так же не выигрывает в скорости по сравнению с прямой emplace_back. Этого я уже объяснить не могу, учитывая тот факт что new в лоб явно не быстрее изъятия из пула.
Чем по вашему вызван подобный «прогрев», имею ввиду при повторном проходе? Ведь мы зарезервировали память изначально с reserve.
Чем по вашему вызван подобный «прогрев», имею ввиду при повторном проходе? Ведь мы зарезервировали память изначально с reserve.
Впрочем оно и так не было быстрее прямого создания в векторе :) Если ещё покажете как можно такой же фокус проделать с указателями, вообще перевернете мои представление о бытии :))
P.S. Просто брать указатель на только что добавленый через emplace_back объект нельзя, ибо если вектор содержащий объект, куда то скопировать/переместить — указатель будет валидным лишь для источника, что естественно.
P.S. Просто брать указатель на только что добавленый через emplace_back объект нельзя, ибо если вектор содержащий объект, куда то скопировать/переместить — указатель будет валидным лишь для источника, что естественно.
Чтобы с указателями можно было работать, память надо не в одном непрерывном векторе выделять, а выделять новые (области памяти) по мере необходимости. habrahabr.ru/post/148657/
А разве я не то же самое делаю в Buffer (в вашей реализации пула это, кажется, Block)? Для того буферы у меня и есть, чтобы с них указатели брать.
::operator new (sizeof(T[num])) — вот это именно и выделяет непрерывную область памяти (линейный массив объектов)
Собственно аналогично с вашим BlockAlloc.
::operator new (sizeof(T[num])) — вот это именно и выделяет непрерывную область памяти (линейный массив объектов)
Собственно аналогично с вашим BlockAlloc.
Прогрев, как оказалось связан с lazy memory OS model. Тобишь, реально память выделяется только при создании объекта.
stackoverflow.com/questions/20591821
Плюс, как показали мои тесты заполнение даже пустыми знаениями std::vector быстрее чем std::vector<T*>
stackoverflow.com/questions/20591821
Плюс, как показали мои тесты заполнение даже пустыми знаениями std::vector быстрее чем std::vector<T*>
[deleted]
А если объекты нужно создавать и удалять в нескольких потоках исполнения?
В Boost.Pool об этом даже задумываться не нужно.
Думаю, Вам стоит всё-таки обратить внимание на Boost.
Как я далею пул при помощи Boost.Pool:
При сборке пришлось скомпоновать с boost_system.
Как видите, после этого создавать и удалять объекты можно при помощи new и delete, а не специальными функциями. И ничего сложного с бустом нет. Буст и Qt отлично уживаются в одном проекте.
Это работает правильно, даже если объекты создаются и удаляются параллельно в разных потоках. Поэтому может работать медленнее, чем Ваш код. Кажется, бусту можно сказать специальным макросом, что всё в одном потоке, на этом можно выгадать в скорости.
Можно и под массив (new Data[size]) память брать из пула, но на практике оверхед себя не оправдывает.
В Boost.Pool об этом даже задумываться не нужно.
Думаю, Вам стоит всё-таки обратить внимание на Boost.
Как я далею пул при помощи Boost.Pool:
#include <boost/pool/singleton_pool.hpp>
class Data {
public:
void* operator new(size_t x);
void operator delete(void* ptr);
private:
int data[10];
};
class DataTag;
typedef boost::singleton_pool<DataTag, sizeof(Data)> DataPool;
void* Data::operator new(size_t x) {
return DataPool::malloc();
}
void Data::operator delete(void* ptr) {
DataPool::free(ptr);
}
int main() {
Data* data = new Data;
delete data;
}
При сборке пришлось скомпоновать с boost_system.
Как видите, после этого создавать и удалять объекты можно при помощи new и delete, а не специальными функциями. И ничего сложного с бустом нет. Буст и Qt отлично уживаются в одном проекте.
Это работает правильно, даже если объекты создаются и удаляются параллельно в разных потоках. Поэтому может работать медленнее, чем Ваш код. Кажется, бусту можно сказать специальным макросом, что всё в одном потоке, на этом можно выгадать в скорости.
Можно и под массив (new Data[size]) память брать из пула, но на практике оверхед себя не оправдывает.
Перегрузка new/delete выглядит интересно. Но… а как параметры передавать конструктору Data* data = new Data(10, 20)?
Да, именно так.
мне чего то казалось что перегружать можно только
void* Data::operator new(size_t x)
В смысле с фикс. кол. параметров, а-ля www.cplusplus.com/reference/new/operator%20new/
void* Data::operator new(size_t x)
В смысле с фикс. кол. параметров, а-ля www.cplusplus.com/reference/new/operator%20new/
Перегружается только операция выделения памяти. Конструктор вызывается потом и свыше.
Вам правильно ответили.
Кстати, должен признать, что я забыл про void* operator new (std::size_t size, const std::nothrow_t& nothrow_value) throw();
Так как pool::malloc возвращает 0, если у него кончается память, то его напрямую нужно как раз в этой версии использовать. А в версии void* operator new (std::size_t size) throw (std::bad_alloc); проверять указатель, который pool::malloc вернул, на 0 и кидать bad_alloc самому, если 0.
pastebin.com/uA58pqAr
Внёс исправления и добавил пару конструкторов.
ru.wikibooks.org/wiki/Boost.Pool#Singleton_pool — о boost::singleton_pool по-русски.
Кстати, должен признать, что я забыл про void* operator new (std::size_t size, const std::nothrow_t& nothrow_value) throw();
Так как pool::malloc возвращает 0, если у него кончается память, то его напрямую нужно как раз в этой версии использовать. А в версии void* operator new (std::size_t size) throw (std::bad_alloc); проверять указатель, который pool::malloc вернул, на 0 и кидать bad_alloc самому, если 0.
pastebin.com/uA58pqAr
Внёс исправления и добавил пару конструкторов.
ru.wikibooks.org/wiki/Boost.Pool#Singleton_pool — о boost::singleton_pool по-русски.
Честно говоря несколько непонятно. Что здесь [pastebin.com/uA58pqAr] Data* data = new Data(1); вызывается? void* Data::operator new(size_t x)? В таком случае как конструктор узнает что вы ему параметры передаете?
Я конечно не могу проверить с бустом, но я практически уверен, что при Data* data = new Data(1); не будет вызван конструктор Data(int first).
Разве что void* ptr = DataPool::malloc(); делает какую то немвслимую магию… Которую он делать не может.
Я конечно не могу проверить с бустом, но я практически уверен, что при Data* data = new Data(1); не будет вызван конструктор Data(int first).
Разве что void* ptr = DataPool::malloc(); делает какую то немвслимую магию… Которую он делать не может.
Впрочем я ошибаюсь. Магию делает сам new. ideone.com/DfJS4N
В new Data(1) вызывается operator new, потом конструктор Data(int first).
В delete data вызывается деструктор, потом operator delete. (В delete 0 ничто не происходит.)
Видимо, Вы спутали оператор new и метод operator new. Русское слово «оператор» не соответствует английскому «operator», которое на русский правильно переводится как «операция».
У Алёны хорошо написано про delete. С new аналогичная ситуация.
В delete data вызывается деструктор, потом operator delete. (В delete 0 ничто не происходит.)
Видимо, Вы спутали оператор new и метод operator new. Русское слово «оператор» не соответствует английскому «operator», которое на русский правильно переводится как «операция».
У Алёны хорошо написано про delete. С new аналогичная ситуация.
В общем спасибо вам за трюки с new. Разобрался.
А буст все равно не буду встраивать :). Пишу библиотеку. Стараюсь по возможности не добавлять лишних зависимостей (пусть и встроенных).
А буст все равно не буду встраивать :). Пишу библиотеку. Стараюсь по возможности не добавлять лишних зависимостей (пусть и встроенных).
Не думаю, что Вас удастся переубедить, но попробую :3
* В самописных библиотеках Вам придется самостоятельно исправлять все причуды конкретной платформы. В boost это уже сделано.
* В самописной библиотеке будут баги. Они во всём есть. В бусте баги исправляют сотни людей и делают это так хорошо, что я ни разу не сталкивался с багом, который бы ещё не исправили.
* Если Вы позовёте в проект нового разработчика, то весьма вероятно, что он знаком с бустом. Но не с Вашей библиотекой.
* Наконец, если Вы забросите свою библиотеку, то некому будет исправлять в ней баги. Boost никогда не будет заброшен, пока жив C++.
В стремлении избавиться от зависимостей можно дойти до абсурда, например написать свои реализации для vector, string и т.п. Это очень редко бывает действительно нужно, но по этому пути уже прошли до нас и можно воспользоваться их наработками.
Попробуйте Дебиан. Нужная часть буста ставится одной командой:
Это кажется сложным, пока сам не попробуешь.
* В самописных библиотеках Вам придется самостоятельно исправлять все причуды конкретной платформы. В boost это уже сделано.
* В самописной библиотеке будут баги. Они во всём есть. В бусте баги исправляют сотни людей и делают это так хорошо, что я ни разу не сталкивался с багом, который бы ещё не исправили.
* Если Вы позовёте в проект нового разработчика, то весьма вероятно, что он знаком с бустом. Но не с Вашей библиотекой.
* Наконец, если Вы забросите свою библиотеку, то некому будет исправлять в ней баги. Boost никогда не будет заброшен, пока жив C++.
В стремлении избавиться от зависимостей можно дойти до абсурда, например написать свои реализации для vector, string и т.п. Это очень редко бывает действительно нужно, но по этому пути уже прошли до нас и можно воспользоваться их наработками.
Попробуйте Дебиан. Нужная часть буста ставится одной командой:
sudo apt-get install libboost-system-dev
Это кажется сложным, пока сам не попробуешь.
Библиотека для рисования, буст получается мне был бы нужен лишь ради пула.
Никто не спорит что буст более надежен. Но не раз слышал и о его тормознутости, и даже некоторой непредсказуемости.
Но в проекте который будет использовать библиотеку, попробую буст :)
Так что не считайте свои старание напрасными :)
Никто не спорит что буст более надежен. Но не раз слышал и о его тормознутости, и даже некоторой непредсказуемости.
Но в проекте который будет использовать библиотеку, попробую буст :)
Так что не считайте свои старание напрасными :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Объектный пул и быстрое создание объектов в куче