Jump to content

    
__inline__

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

Recommended Posts

3 часа назад, __inline__ сказал:

pManager=&Manager; //пока так. в будущем возможно сделаю красивше.

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

template<size_t size_items>
manager::manager(int (& pool)[size_items])
    : start((mcb *)pool)
    , freemem((mcb *)pool)
    , Guard()
{
    init(start, sizeof(pool));

    extern manager * pManager;
    pManager = this;
}

 

3 часа назад, __inline__ сказал:

Компиляция - без указания флага -fno-threadsafe-statics выдавал ошибки :


undefined reference to `__cxa_guard_acquire'
undefined reference to `__cxa_guard_release'

Про это тоже было в ссылке от GenaSPBhttps://wiki.osdev.org/C++#Local_Static_Variables_.28GCC_Only.29

3 часа назад, __inline__ сказал:

Затем стартап требует освобождения по другому адресу!  Как это понимать? :shok:

А пройти его пошагово в отладчике или посмотреть исходник?

Share this post


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

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

 

Спасибо.  Просто ранее я не знал как это сделать, но с вашей помощью уже понял как :) И то, что присовение делается каждый раз в курсе.

 

26 minutes ago, Сергей Борщ said:

Про это тоже было в ссылке от GenaSPBhttps://wiki.osdev.org/C++#Local_Static_Variables_.28GCC_Only.29

 

Попробую раскурить.

 

26 minutes ago, Сергей Борщ said:

А пройти его пошагово в отладчике или посмотреть исходник?

 

Нечто подобное проделал и уже есть кое-какие результаты.

Как писал ранее, иногда при освобождении кучи значения указателей левые. Связано это с тем, что стартап кроме malloc вызывает ещё другие функции.  Одну из них обнаружил: realloc. Но это не всё. 

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

Экспериментально нашёл оптимальное значение числа пропусков, в моём случае оно оказалось =6.

Стартап 6 раз вызывает выделение кучи, двое из которых с левым адресом при высвобождении (потому что не malloc).

 

Код с отладкой:

void * do_alloc(size_t size)
{
    static pool<0x100000> HeapPool;
    static manager<heap_guard> Manager(HeapPool);

    pManager=&Manager;

    void *r=pManager->malloc(size);

    printf("Size=%d Return Address=%d\n",size,(int)r);

    return r;
}

void do_free(void * p)
{
 static char f=6;
 if(f)
 {
  f--;
  printf("Spurious(?) Free address=%d\n\n",(int)p);
  return;
 }

    printf("Free address=%d\n\n",(int)p);

    pManager->free(p);
}

void * operator new(size_t size, std::nothrow_t const &)
{
printf("1\n");
    return do_alloc(size);
}

void * operator new(size_t size)
{
printf("2\n");
    return do_alloc(size);
}

void operator delete(void * ptr)
{
printf("3\n");
    do_free(ptr);
}

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

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

void *calloc( size_t n, size_t bytes )
{
printf("6\n");
    return( NULL );
}

void *realloc( void *ptr, size_t newsize /*bytes*/ )
{
 printf("\nREALLOC ");

 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 *valloc( size_t bytes )
{
printf("8\n");
    return( NULL );
}

void *memalign( size_t alignment, size_t bytes )
{
printf("9\n");
    return( NULL );
}

int posix_memalign( void **ptr, size_t alignment, size_t bytes )
{
printf("10\n");
    return( -1 );
}

 

Итог такой:

 scr.png.67ce6dd70c1cb54643ecae84f47c27c2.png

 

Последняя аллокация в 1000 байт - моя.  И она успешно выделяется-освобождается.

+ 2 подозрительных освобождения по левым адресам.  Осталось найти функцию, которая выделяет кучу дважды таким образом .

 

test.cpp:

#include <stddef.h> //size_t
#include <stdio.h>  //printf

extern "C" void * malloc(size_t size);
extern "C" void free(void * ptr);

int main(void)
{
 void *p=malloc(1000);

 if(p) printf("All OK!\n");

 free(p);

 printf("End\n");

 while(1);

 return 0;
}

 

Edited by __inline__

Share this post


Link to post
Share on other sites

В общем, покопавшись ещё больше понял один факт.   Инит байды с классами и конструкторами тоже тянет за собой алоцирование памяти в стартапе.  А это значит, что классовая обёртка аллокатора вредит сама себе.  Вычистил код и превратил его просто в обычный Си.  В итоге левые вызовы аллокатора ушли.

 

Как раз тот случай, когда аллокатор должен быть сишным, нагромождения C++ тут только навредили.

 

Share this post


Link to post
Share on other sites
40 минут назад, __inline__ сказал:

Как раз тот случай, когда аллокатор должен быть сишным, нагромождения C++ тут только навредили.

Между си++ и дин.памятью нет никакой связи. Много лет пишу на си++ в embedded и нигде не использую дин.память.

Share this post


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

Инит байды с классами и конструкторами тоже тянет за собой алоцирование памяти в стартапе

Странно. Уже много лет использую этот менеджер памяти в плюсовых проектах для ARM7 и Cortex, никаких проблем с его плюсовостью не испытываю. Правда, я не выделяю динамически память при инциализации глобальных переменных. Может все же стоит найти исходники от cstartup из mingw и разобраться до конца?

Share this post


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

Странно. Уже много лет использую этот менеджер памяти в плюсовых проектах для ARM7 и Cortex, никаких проблем с его плюсовостью не испытываю.

 

На ПК этот аллокатор надо дорабатывать, потому что не работает в том виде что в репозитории.

 

11 minutes ago, Сергей Борщ said:

Может все же стоит найти исходники от cstartup из mingw и разобраться до конца?

 

Искал, не нашёл.   Возможно, mingw дёргает WinAPI-функцию HeapAlloc(...) в обход malloc.

Однако,  в обычном Си тоже при освобождении залетает левый указатель.

Сделал пока так (проверяю - если указатель за диапазоном пула, то идёт лесом):

void _free(void *pool )
{
 if(((int)pool<(int)HEAP_MEMORY)||((int)pool>(((int)HEAP_MEMORY)+(HEAP_VOLUME-1))))return; //защита от освобождения левых указателей
  ...
    

Так работает.

 

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

И исходный текст различается.

 

Алгоритмы как я вижу меняются.

 

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

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

  

Кстати, почему zltigo покинул форум?

 

Share this post


Link to post
Share on other sites

Ещё одно наблюдение.

 

Если убрать "extern C'  "  из функций, а инит кучи сделать в конструкторе через attribute (constructor), то - сишный рантайм-стартап дергает свой аллокатор, а в программе используется кастомный. И без всяких странностей.

 

При этом сборка должна быть С++.  Под Cи такой фокус не прокатит.

Share this post


Link to post
Share on other sites
On 9/17/2020 at 7:53 AM, __inline__ said:

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

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

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

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

"*овно" не либа, а ваша обёртка.

Во-первых, следует прочитать инструкцию, где написано, что 1. есть требования по выравниванию буфера (как в большинстве аллокаторов); 2. функция инциализации вернёт NULL, если буфер не выровнен (вы этого не проверили); 3. фраза "а фиг его знает" указывает на то, что вы не посмотрели даже README.

Я бы прошёл мимо, но крайне досадно видеть, как третьесортные бенчмарки, состряпанные на коленке абсолютно без понимания происходящего, вываливаются на публику под видом объективной оценки.

Библиотека моя.

Share this post


Link to post
Share on other sites
14 minutes ago, Spym said:

1. есть требования по выравниванию буфера (как в большинстве аллокаторов)

 

С этим как раз всё ОК.  Программе нужно выравнивание, намного бОльшее, чем требует аллокатор.

 

14 minutes ago, Spym said:

2. функция инциализации вернёт NULL, если буфер не выровнен (вы этого не проверили);

 

Если я об этом не пишу, то это не значит, что этого не сделано. В данном случае этот момент не представлен общественности, так как посчитал эту элементарщину неуместной публикации.

Любой сторонний аллокатор проверяется вначале подобными проверками.

 

14 minutes ago, Spym said:

3. фраза "а фиг его знает" указывает на то, что вы не посмотрели даже README.

 

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

 

14 minutes ago, Spym said:

Я бы прошёл мимо, но крайне досадно видеть, как третьесортные бенчмарки, состряпанные на коленке абсолютно без понимания происходящего, вываливаются на публику под видом объективной оценки.

 

Эти "третьесортные бенчмарки", как вы выразились, со штатным аллокатором ведут игру ОТ и ДО без эксепшенов. Аллокатор zltigo  также  работает успешно ОТ и ДО (не считая выкрутасов mingw вначале).

 

 А этот аллокатор завалил работу программы через  пару секунд,  при этом несколько аллокаций-освобождений всё-же успешно произошли.   Значит что-то пошло не так!

  

14 minutes ago, Spym said:

Библиотека моя.

 

Сомневаюсь!

Просто решили потроллить.

 

Проблема решена, читайте выше, даже штатный аллокатор вернули! :sun_bespectacled:

 

P.S.   https://electronix.ru/forum/index.php?app=core&module=members&controller=profile&id=35348

 

Дата последнего поста:  October 15, 2014

 

Прошло 7 лет с тех пор...

 

Странно это всё.  В последнее время часто вижу на форуме выходящих из долгой спячки  персонажей.   Тенденция? :acute:

 

 

Edited by __inline__

Share this post


Link to post
Share on other sites
16 minutes ago, __inline__ said:

А этот аллокатор завалил работу программы через  пару секунд,  при этом несколько аллокаций-освобождений всё-же успешно произошли.   Значит что-то пошло не так!

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

Share this post


Link to post
Share on other sites
20 minutes ago, Spym said:

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

   

Бенчмарки не использую (оставим их учёным и академикам для лабораторных исследований сферических коней в вакууме и для маркетологических статистик не имеющих ничего общего с реальностью),  а выкладывать целиком весь код целевой программы  нет ни желания, ни прав.

 

Проблема вылезала не сразу, а по прошествию какого-то времени.  Полагаю, алгоритм того аллокатора что-то не учёл. Иными словами, он не резистентен к случаям, которые предусмотрены в штатных аллокаторах (C6000+ и GNU ARM) и в аллокаторе, от zltigo.

  

Я сомневаюсь в вашем авторстве того кода.  Скорее всего вам стало скучно и прикалываетесь.

 

Share this post


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

Бенчмарки не использую [...],  а выкладывать целиком весь код целевой программы  нет ни желания, ни прав.

Хорошо. Тогда, пожалуйста, поделитесь сведениями о характере обнаруженного сбоя, и подтвердите, что ваша программа исполняется в одном потоке. Я надеюсь, вы понимаете, что вы сделали очень сильное заявление о неработоспособности библиотеки, которая успешно эксплуатируется в системах жёсткого реального времени и имеет полное покрытие тестами.

Share this post


Link to post
Share on other sites
5 hours ago, Spym said:

Тогда, пожалуйста, поделитесь сведениями о характере обнаруженного сбоя

 

Убедили!  Всё-же ещё раз выделил квант своего времени и ещё раз всё проверил, сделал контрольную проверку возвращаемого значения после malloc.

 

5 hours ago, Spym said:

подтвердите, что ваша программа исполняется в одном потоке.

 

На голом железе. Там один поток.  Есть прерывание для подкачки данных для звука, но там статическое распределение - буфер постоянной длины: обычный массив.

 

5 hours ago, Spym said:

Я надеюсь, вы понимаете, что вы сделали очень сильное заявление о неработоспособности библиотеки, которая успешно эксплуатируется в системах жёсткого реального времени и имеет полное покрытие тестами.

   

Проверка показала, что malloc вернул NULL спустя какое-то время, дисплей покрасился в красный цвет, и далее я сделал вечное зацикливание.   Недостаточно памяти.  Данный аллокатор либо неэффективно (по сравнению с другими)  использует кучу, либо куча сильно фрагментировалась.

 

Пул 24 Мегабайта.  Адрес пула 0xC2000000 - выравнивание - овердофига, чем надо.   Штатный и zltig'овский аллокаторы с этим пулом работают, ошибок выделения памяти нет.  Условия теже самые.

 

Ниже обёртка, на которой тестировались все сторонние аллокаторы:

 

/*
o1.cpp
cpp-wrapper for o1heap
*/

#include <string.h>
//#include <stdio.h>
#include <stddef.h>

#include "o1heap.h"

#include "API.h" //это API для работы с дисплеем, звуком, и т.п.

static O1HeapInstance *o1i;

#define HEAP_MEMORY_SIZE (24UL*0x100000UL) /* 24 МБ */

//static char HEAP_MEMORY[HEAP_MEMORY_SIZE] __attribute__ ((aligned (64))); //это для винды
  
static char *HEAP_MEMORY=(char*)0xC2000000; //с этого адреса лежит пул кучи (свободный участок, неиспользуемый более никем)

extern "C" void *malloc(size_t size)
{
 static char f=1;
 if(f)
 {
  o1i=o1heapInit((void*)HEAP_MEMORY,HEAP_MEMORY_SIZE,NULL,NULL); //одноразово инитим аллокатор
  f=0;
 }

 void *r;
 if(!size)
 {
//  printf("malloc size=0\n");
  return NULL;
 }
 r=o1heapAllocate(o1i,size);

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

 if(r==NULL) //если выделить не удалось
 {
  ClearVRAM(COLOR_RED); //заливаем буфер видео красным цветом
  OutLCD();             //выводим буфер на дисплей
  while(1);             //зацикливаем навечно
 }

 return r;
}

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

 if(ptr==NULL)return;

 o1heapFree(o1i,ptr);
}

extern "C" 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;
}

extern "C" 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 *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);
}

 

Edited by __inline__

Share this post


Link to post
Share on other sites
8 minutes ago, __inline__ said:

Проверка показала, что malloc вернул NULL спустя какое-то время, дисплей покрасился в красный цвет, и далее я сделал вечное зацикливание.   Недостаточно памяти.  Данный аллокатор либо неэффективно (по сравнению с другими)  использует кучу, либо куча сильно фрагментировалась.

У вас здесь всего лишь закончилась память, об этом ниже. В своём первом посте об этой библиотеке (пятый пост в этой теме) вы говорили о замедлении, сбое, и зависании. Меня интересуют именно вот эти явления. Аллокатор постоянной вычислительной сложности в принципе не может приводить к замедлению и зависанию сам по себе; если вы посмотрите исходники, вы не увидите там ни одного цикла (кроме как при вычислении двоичного логарифма, если быть максимально педантичным). Можете ли вы подтвердить, что вы действительно наблюдали описанные эффекты? Я склоняюсь к версии, что тест был выполнен не вполне добросовестно, и ваш первый отзыв вводит людей в заблуждение. Пожалуйста, либо внесите ясность, либо отредактируйте пост.

В плане эффективности использования памяти мой аллокатор лучше, чем альтернатива от zltigo и, скорее всего, лучше чем ваш аллокатор из стандартной библиотеки (не могу быть в последнем уверен, потому что не знаю, что у вас за стандартная библиотека). В системах не-реального времени традиционно делается упор на оптимизацию среднего или амортизированного худшего случая, при этом худший случай (особенно если он достаточно редок) интерес для анализа представляет сравнительно небольшой. В системах реального времени приоритеты обратные, но вам, как разработчику встраиваемых систем, это известно и так. Что вам может быть неизвестно, так это применимость принципа оптимизации среднего случая в контексте не только времени, но и фрагментации кучи. В обычных аллокаторах часто применяется стратегия поиска наилучшего соответствия (best-fit), о которой писал и zltigo:

Quote

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

Человеку не в теме это может показаться парадоксальным, но худший случай фрагментации кучи при использовании стратегии best-fit хуже, чем при использовании более простой стратегии поиска первого соответствия (first-fit). Я не буду утомлять вас матаном, но если вам это действительно интересно, обратите внимание на публикацию "Worst case fragmentation of first fit and best fit storage allocation strategies" [Robson 1977]. В моём аллокаторе используется first-fit, который, как вы уже поняли, показывает более высокую фрагментацию у вас на столе, но он при этом не сломается в полевых условиях у невезучего клиента, которому повезёт выбить из best-fit аллокатора редкую последовательность выделений памяти, что приводит к катастрофической фрагментации и отказу.

Большинство людей на этом форуме, в частности вы и уважаемый zltigo, ничего не понимают в аллокаторах, но я вас в этом не виню. Это довольно экзотическая область и нет ничего страшного в отсутствии столь узкоспециализированных познаний, нужно просто это аккуратно осознать. Меня задевает, что вы лезете в тему, в которой явно ничего не смыслите, и несправедливо критикуете работу других, не разобравшись в происходящем. Вам уже давали ссылку на мою статью на хабре, пожалуйста, прочитайте её и указанные в ней источники, если вы хотите разобраться в вопросе самостоятельно.

Share this post


Link to post
Share on other sites
14 minutes ago, Spym said:

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

 

А меня задевает, что у вас позиция: "Я - Д'Артаньян, а остальные пи****сы", иначе как понять ваше высказывание про:

 

15 minutes ago, Spym said:

Большинство людей на этом форуме, в частности вы и уважаемый zltigo, ничего не понимают в аллокаторах

 

Скажу так, что мне необязательно разбираться в кишках аллокатора, более того, я туда не лез. Так что вы лжёте по поводу:

 

16 minutes ago, Spym said:

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

   

Интересно, кто вы собственно такой, чтобы давать такие заключения другим людям? 

 

19 minutes ago, Spym said:

В своём первом посте об этой библиотеке (пятый пост в этой теме) вы говорили о замедлении, сбое, и зависании. Меня интересуют именно вот эти явления. Аллокатор постоянной вычислительной сложности в принципе не может приводить к замедлению и зависанию сам по себе; если вы посмотрите исходники, вы не увидите там ни одного цикла (кроме как при вычислении двоичного логарифма, если быть максимально педантичным). Можете ли вы подтвердить, что вы действительно наблюдали описанные эффекты?

 

Вам легче станет, если скажу, что "замедление-сбой-подвисание" -  это следствие того, что malloc вернул NULL, и программа пошла шагать дальше, а не застопорилась, как сделано в последнем случае?

 

20 minutes ago, Spym said:

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

 

Вы имеете право думать о чём угодно.  Я имею право писать о чём угодно.  В интернете, вам никто  ничем не обязан.

А раз выкладываете свой код  для пользования другими, будьте готовы увидеть любые отзывы, в том числе невыгодные вам !

Ваш диалог уже получается НЛП какое-то: насквозь прошпигован угрозами и призывом к ответственности.  Далеко пойдёте... :biggrin:

   

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

И скажите спасибо, что вашему аллокатору выделил своё время ДВАЖДЫ! :lazy:

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.