Jump to content

    
__inline__

Посоветуйте хороший аллокатор памяти

Recommended Posts

Здравствуйте.

 

Пишу на C6000+ C++ compiler версия 8.3.x.

 

Программа выполняет во время работы много malloc/free, new/delete.   Есть критический участок, где падает производительность во время циклического динамического выделения-освобождения памяти (система частиц с иерархией), если программу запускать сначала.   Если запустить критический алгоритм сразу, то производительность при динамическом выделении-высвобождении не падает.

 

Полагаю, что это связано с фрагментацией кучи и тормозами менеджера с поисками свободной дырки.

 

Какие есть пути решения данной проблемы?

 

Дефрагментация памяти(как?)?

Переход на другой аллокатор (какой?)?

 

Вариант переписать на статическую память - не предлагать!

 

 

Edited by __inline__

Share this post


Link to post
Share on other sites

Хороший алокатор делается на основе статистики приложения. т.е. получения априорной информации.  
Потом выгружают в  MATLAB эту  статистику  и на ее основе строят оптимальный мультипульный аллокатор. 

Но  для этого надо сначала сделать хороший телеметрический модуль. 
 

7 minutes ago, arhiv6 said:

Тут вы конктретно путаете алгоритмы с детерминированным временем и быстрые алгоритмы.
Это не одно и то же. 

Share this post


Link to post
Share on other sites
6 hours ago, __inline__ said:

(система частиц с иерархией)

Отдельный пул свободный блоков под каждый размер. Можно заранее их аллоцировать через malloc (когда блоки мелкие и важна локальность), а можно по мере работы пополнять пул, вместо того чтобы делать free. Когда надо alloc, то соответственно смотрим в пуле, если там пусто то уже делаем malloc.

Share this post


Link to post
Share on other sites
21 hours ago, arhiv6 said:

 

Проверку не прошёл.

Стартанул хорошо, затем через какое-то время пошли дикие тормоза по 1-2 секунды и затем был зарегистрирован сбой и всё повисло.

Cо штатным аллокатором памяти такого нет.

Вывод :  либа - *овно.

 

Обёртка ниже:

 

O1HeapInstance *O1HEAPINSTANCE;

u8 O1HEAPAREA[24UL*0x100000UL]; //24 МБ куча

void _malloc_init(void)
{
 O1HEAPINSTANCE=o1heapInit((void*)O1HEAPAREA,sizeof(O1HEAPAREA),NULL,NULL);
}

void *_malloc(u32 x)
{
 if(!x)return NULL;                         //а фиг его знает как поведёт себя этот аллокатор, если размер нулевой
 return o1heapAllocate(O1HEAPINSTANCE,x);
}

void _free(void *x)
{
 if(x==NULL)return;               //некоторые аллокаторы аварийно завершаются, если делать free(NULL)
 o1heapFree(O1HEAPINSTANCE,x);
}

 

Есть ещё на примете такие: smmalloc и Hoard - надо будет их проверить.

 

Подскажите, как глобально заменить malloc, free, calloc , чтобы в программе, в библиотеках использовались мои варианты функций, а не из stdlib.h ?

 

И чтобы они же вызывализь из new/delete и если в системных библиотеках  есть их вызовы, то тоже чтобы были мои функции, а не из stdlib ?

 

При этом, new кроме выделения, должен сохранить способность инициализировать память под методы конструкторов если потребуется.

 

 

15 hours ago, amaora said:

Отдельный пул свободный блоков под каждый размер. Можно заранее их аллоцировать через malloc (когда блоки мелкие и важна локальность), а можно по мере работы пополнять пул, вместо того чтобы делать free. Когда надо alloc, то соответственно смотрим в пуле, если там пусто то уже делаем malloc.

 

Не подходит!  Условие - не перекраивать весь текст программы.

Edited by __inline__

Share this post


Link to post
Share on other sites
11 hours ago, Сергей Борщ said:

Гляньте этот. Самому интересно - давно его использую, но в моих задачах нет активной работы с кучей.

 

При компиляции ругается в heap.cpp на эту строку:

extern std::nothrow_t const std::nothrow = {};

 

Если убрать равенство и фигурные скобки, то компиляция проходит.

 

Что не так?

 

Есть ли способ изменить синтаксис строки выше при сохранении той же функциональности?

Я не силён в этих nothrow и т.п.

 

Ошибка ниже:

error.thumb.png.4a3b8307b21fdca5baccaccf03dd46c3.png

Edited by __inline__

Share this post


Link to post
Share on other sites

Разобрался.  Ошибка была в излишней педантичности компилятора. Сделал явный типкаст и компилятор сожрал:

extern std::nothrow_t const std::nothrow = (std::nothrow_t const){};

 

Если эту строчку выбросить, то тоже компилируется. Зачем она нужна - пока мне не понятно.  Оставил вариант выше.

Edited by __inline__

Share this post


Link to post
Share on other sites

Собрал небольшую тестовую программу,  ничерта не работает.  Программа валится даже с пустым main().

Полагаю, что-то не так с конструкторами.

 

Вот  мой heapcfg.h  (заглушка, ибо потоков у меня нет и задача одна, не с кем делить, никому не перебить):

 

#ifndef _HEAPCFG_H_
#define _HEAPCFG_H_

struct heap_guard
{
 void lock(){}
 void unlock(){}
};

#endif

 

Тестовая программа heapinit.cpp -  ничего сложного: объявление пула на 4 кБ и какой-то менеджер:

 

#include <stdint.h>

#include "heap.h"

heap::pool<4096> HeapPool;
heap::manager<heap_guard> heap::Manager(HeapPool);

//int HeapPool[ 4096/sizeof(int) ];
//heap::manager<heap_guard> heap::Manager(HeapPool, sizeof(HeapPool));
//heap::manager<heap_guard> heap::manager(HeapPool);

//extern "C" void *malloc(size_t);
//extern "C" void free(void*);

int main(void)
{

// char *p=(char*)malloc(100);
// if(p==NULL)printf("%s\n","malloc error!");

// for(int i=0;i<100;i++)p[i]=i;
// for(int i=0;i<100;i++)printf("%c",p[i]);


 return 0;
}

 

Сборка такими командами:

 

g++ -c heap.cpp
g++ -c heapinit.cpp

g++ -o heap.exe heapinit.o heap.o

 

Запуск полученного исполняемого модуля heap.exe приводт к краху:

 

Clipboard01.png.0416a5853d0d1e16c1fe8dca47159c43.png

 

Что я сделал не так???

 

Share this post


Link to post
Share on other sites
22 hours ago, __inline__ said:

Что я сделал не так???

 

Очень странно что никто ничего не смог предположить.

 

Дальнейшие разбирательства привели меня к обнаружению причины аварийного вылета.  Проблема здесь:

extern "C" void * malloc(size_t size)
{
    return Manager.malloc(size);
}

extern "C" void free(void * ptr)
{
    Manager.free(ptr);
}

 

Если убрать эти объявления, то пустой main() отрабатывает корректно и программа не завершается аварийно.

 

Из увиденного, заключаю вывод, что в моём случае рантайм библиотеки используют malloc, new раньше, чем было объявление пула и инит менеджера кучи.

Вот это должно быть каким-то образом проинициализировано до того, как сработает C++-ный рантайм:

heap::pool<4096> HeapPool;
heap::manager<heap_guard> heap::Manager(HeapPool);

 

Дальнейшие мои копания были направлены на поиск первоисточника - C-версии аллокатора zltigo.  И я его нашёл:

 

 

Конкретно - версия от пользователя wave48:

 

Но пришлось переделать.

Во-1:  там задан максимальный размер кучи до 16 МБ. А мне надо 24 как минимум.  Исправил - теперь можно использовать кучу до 256 МБ:

#pragma pack( push, 1 )
typedef union type_size {
	unsigned long mark;
	struct {
	   unsigned size:28; //24; //2^28=256 MB max heap
	   unsigned type: 4; // 8;
	}bits;
}type_size;

 

Во-2: пришлось удалить всё что связано с многопоточностью, так как  задача у меня всего одна:

TaskResumeAll(), vTaskSuspendAll() - выкинуть

 

В-3:  пул памяти объявил по-своему исходя из свободного региона памяти:

#define HEAP_ALIGN 8 /* выравнивание */
  
#define HEAP_MEMORY_SIZE (32UL*0x100000UL) /* 32 МБ памяти */
static char *HEAP_MEMORY=(char*)0xC2000000;

void init_system_heap(void){
	system_heap.start = (void*)HEAP_MEMORY;
	system_heap.hsize = HEAP_MEMORY_SIZE;
	system_heap.freem = system_heap.start;
	heapinit( &system_heap );
}

 

В-4-х :  написал свои перегрузки malloc, free и им подрбным + операторы new/delete.  Очень важный момент: чтобы сишный рантайм не завешал всё, необходимо в первом вывозве malloc'а - проинициализировать аллокатор (то чего не хватает версии C++ с которой был вылет):

void _malloc_init(void)
{
 init_system_heap();
}

void *malloc(size_t size)
{
 static char f=1;
 if(f)
 {
  _malloc_init();  //вызов один единственный раз
  f=0;
 }

 void *r;
 if(!size)
 {
  printf("malloc size=0\n");
  return NULL;
 }
 r=malloc_z(&system_heap,size,MARK_SYSTEM);

 if(r)printf("malloc=%d",size);
 else printf("malloc error: not enougth memory");

 printf("   rest=%d\n",getHeapMaxSize(&system_heap));

 if(r==NULL)while(1);

 return r;
}

 

Перегрузка, почему-то не все функции были перегружены. Перегрузил всё что мне нужно и используется:

void free(void *ptr)
{
 printf("free\n");

 if(ptr==NULL)return;
 free_z(&system_heap,ptr);
}

void *calloc(size_t num,size_t size)
{
 printf(" CALLOC ");
 size_t ns=num*size;
 void *r=malloc(ns);
 if(r)memset(r,0,ns);
 return r;
}

void *realloc(void *ptr,size_t newsize)
{
 printf(" REALLOC ");

 if(ptr==NULL)return malloc(newsize); //только выделяем

 if(newsize==0) //только освобождаем
 {
  free(ptr);
  return NULL;
 }

 void *new_ptr=malloc(newsize);
 memcpy(new_ptr,ptr,newsize); //копируем старый фрагмент в новый
 free(ptr);

 return new_ptr;
}

void _defrag(void)
{
 defragHeap(&system_heap);
}

void *operator new(size_t sz)
{
 printf(" NEW 1 ");
 return malloc(sz);
}

void *operator new[](size_t sz)
{
 printf(" NEW 2 ");
 return malloc(sz);
}

void operator delete(void *ptr)
{
 printf(" DELETE 1 ");
 free(ptr);
}

void operator delete[](void *ptr)
{
 printf(" DELETE 2 ");
 free(ptr);
}

 

Как итог:

Сишный аллокатор прекрасно работает как на ПК, так и на DSP C6745 :dirol:  По сравнению со штатным (из C6000+ compile tools) получилось быстрее. Плюс радует возможность дефрагментации свободных кусков.

 

Остаётся открытым вопрос:  как приспособить C++ -версию аллокатора, чтоб инит пула был раньше сишного рантайма?

 

 

Share this post


Link to post
Share on other sites

Инициализация статических объектов в плюсах до main  делается. Нужно спец функцию ввзвать.

В realloc не выясня4тся размер старого объекта при коп рованиии. Он может бытт меньше нового.

Share this post


Link to post
Share on other sites
17 minutes ago, GenaSPB said:

Инициализация статических объектов в плюсах до main  делается. Нужно спец функцию ввзвать.

 

Проблема в том, что нужно кросс-платформенное решение: для ПК(mingw, win32, linux), для C6745 и для ARM.  А так можно хоть в ассемблерный стартап воткнуть.

Для этого в GCC есть атрибут конструктор:  __attribute__((constructor)), который даже в обычном Си работает.

Но в моём случае это не помогло, так как до main() вызывается рантайм, который дергает malloc() в первый раз и из-за отсутствия инита - аварийно завершается.

Поэтому ничего не осталось, как воткнуть инит кучи в первый вызов malloc().

 

А для C++ как сделать не знаю. Конкретно - как вызывать инит пула и манагера до того, как стартап начнёт использовать malloc:

Quote

heap::pool<4096> HeapPool;
heap::manager<heap_guard> heap::Manager(HeapPool);

 

 

Quote

В realloc не выясняется размер старого объекта при копированиии. Он может бытт меньше нового.

 

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

 

 

 

Edited by __inline__

Share this post


Link to post
Share on other sites

Корректность повеления в плане до main у современных gcc в порядке. если кто своевольничает, попробуйте найти версию поновее.
Вот есть сайт https://wiki.osdev.org/C++#The_Operators_.27new.27_and_.27delete.27 - там кое что про наши проблемы . Во всяком случае, gcc дрессированый в моем проекте нормально позволяет глобальные объекты с new/delete

Share this post


Link to post
Share on other sites
8 часов назад, __inline__ сказал:

А для C++ как сделать не знаю. Конкретно - как вызывать инит пула и манагера до того, как стартап начнёт использовать malloc:

Цитата


heap::pool<4096> HeapPool;
heap::manager<heap_guard> heap::Manager(HeapPool);

 

Если речь идет о gcc и принятом в нем startup-коде, то приходит в голову такая идея: зарезервировать память под HeapPool и Manager в виде массива байтов, в секции .init3 (или .init2) разместить код с вызовом placement new для Manager. Этот код вызовет конструктор Manager, а размещение в .init3 заставит выполниться до первых обращений к malloc(). Как это сделать для других компиляторов без переписывания startup я не знаю.

Добавлено:
такая идея:

heap::manager * pManager;
// в конструктор heap::manager добавить:
// extern heap::manager * pManager; pManager = this;
void * do_alloc(size_t size)
{
 	static heap::pool<4096> HeapPool;
	static heap::manager<heap_guard> heap::Manager(HeapPool);
  
    return pManager->malloc(size);
}

void do_free(void * p)
{
    pManager->free(p);
}

и во всех переопределениях new(), malloc(), delete() и free() использовать do_alloc() и do_free()

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.