Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: свой менеджер памяти и тормоза в list  (Прочитано 286 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Migmile
Помогающий

ru
Offline Offline

« : 02-11-2018 07:43 » 

Решил вспомнить с++ и сделать простейший memory manager.
Казалось, все просто, при запросе выделяется блок, его запоминаем в list.
Но когда посмотрел тайминг - ужаснулся, по сравнению со стандартным malloc медленнее в 10 раз!
Оказалось, что тормозит как раз список - его итераторы.
Можете подсказать, чем его заменить?

Код: (C++)
#include <iostream>
#include <list>
#include <vector>
#include <malloc.h>
#include <stdlib.h>
#include <chrono>


using std::cout;
using std::list;


class MemManager
{
        struct MemChain
        {
                unsigned shift;         // смещение от начала
                unsigned size;
                char free;      // занят - 0, свободен - 1
        };

        list <MemChain> List;
        char * Mem=NULL;
        unsigned totalSize=0;
public:
        MemManager(unsigned _size) {
                Mem = (char*) malloc(_size);
                if (Mem == NULL) throw "error allocating mem";
                totalSize = _size;
                MemChain ch;
                ch.shift = 0;
                ch.free = 1;
                ch.size = totalSize;
                List.push_front(ch);
        }

        ~MemManager() {
                if (Mem!=NULL) free(Mem);
        }

        void * alloc(unsigned size) {
//              if (есть память)
                {
                        auto ch=List.begin();
                        for (; ch != List.end();ch++) if (ch->free == 1 && ch->size>=size) break;
                        if (ch != List.end())
                        {                                               // выделим из данного блока нужный кусок и вставим в список ссылку на оставшуюся свободную часть
                                MemChain ch1;           // остаток
                                ch1.shift = ch->shift+size;
                                ch1.free = 1;
                                ch1.size = ch->size - size;
                                ch->size = size;
                                ch->free = 0;
                                auto ptr = ch;
                                ptr++;
                                List.insert(ptr,ch1);

                                return (Mem + ch->shift);
                        }
                }
                return NULL;
        }
        void  free(void*ptr) {
                if (ptr<Mem && ptr>Mem + totalSize) throw "wrong adr";
                auto ch = List.begin();
                for (; ch != List.end(); ch++) if (Mem + ch->shift == ptr) {
                        ch->free = 1;
                        break;
                }
        }
        unsigned maxSize() {};

        void GarbCol()
        {
                // сборщик мусора
                auto ch = List.begin(),pr=ch;
                for (int c = 0; ch != List.end(); ch++)
                {
                        if (ch->free == 1)
                        {
                                c++;
                                if (c == 2)     // предыдущий был тоже свободный
                                {
                                        pr->size += ch->size;
                                        List.erase(ch);
                                        c = 1;
                                        ch = pr;
                                        continue;
                                }
                        }
                        else c = 0;
                        pr = ch;
                }
        };

        void Print(const char * str) {
                cout << str << "\n";
                for (auto ch = List.begin(); ch != List.end(); ch++) cout << ch->shift << "    " << ch->size << "    " << ch->free << "\n";
        }

};

const unsigned Len = 1024 * 100;
const unsigned Count = 200;

int main()
{
        MemManager mm(Len*sizeof(int));
        std::vector<int *> pointers;
        pointers.reserve(Count);
        mm.Print("begin");
        std::chrono::time_point<std::chrono::high_resolution_clock> p1=std::chrono::high_resolution_clock::now(),p2,p3;

        for (int i = 0; i < Count; i++)
        {
                int * ptr = (int*)mm.alloc(Len / Count * sizeof(int));
                pointers.push_back(ptr);
        }
        p2 = std::chrono::high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >>(p2 - p1).count() << "\n";
       
        for (int i = 0; i < Count; i++)
        {
                mm.free(pointers[i]);
        }
        p3=std::chrono::high_resolution_clock::now();

        std::cout << std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >>(p3 - p2).count() << "\n";
        return 1;
« Последнее редактирование: 03-11-2018 23:46 от Джон » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #1 : 03-11-2018 01:07 » 

1. Для примера пример (сорри за тавтологию) очень громоздкий.
2. список стековых объектов? хм... я бы начал с list<MemChain*> List;
   
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 03-11-2018 13:23 » 

Вспомнил С++, вспомни и стандартную библиотеку! ))
Списки имеют линейную скорость доступа. Чем больше список, тем дольше искать. При предсказуемой длине списка выгоднее использовать vector. Можно еще deque, как симбиоз list и vector. Тип list выигрывает только при модели доступа "очередь", когда работа ведется только с концами списка. Ну или вставке/удалении из середины большого списка, но тут у него в конкурентах deque.
« Последнее редактирование: 03-11-2018 13:26 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Migmile
Помогающий

ru
Offline Offline

« Ответ #3 : 04-11-2018 07:36 » 

" список стековых объектов? хм... я бы начал с list<MemChain*> List;"
Попробовал - структура Memchain теперь размещается в начале каждого выделенного блока, в список запоминается ее адрес (т.е. убралось копирование при добавлении в список). улучшение производительности примерно на 5-10%. IMXO
из минусов - возможность затереть структуру в каком - либо блоке и , соответственно, потеря всех последующих выделенных блоко
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 04-11-2018 11:55 » 

Какая разница, затрешь ты описатель блока памяти или, переместив его в другое место, другие данные? И то и другое критично для программы. Но если бы менеджер писал я, то не стал бы размещать описатель в начале блока, его место среди структур менеджера, а среди данных программы. Это дает массы преимуществ и возможностей для оптимизации.

Какую цель ты преследуешь, кроме как вспомнить C++? Программа не может быть "просто так", даже к hello world есть требования. Без четкой постановки задачи выйдет только УГ, если ты конечно не Чак Норис от программирования.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Migmile
Помогающий

ru
Offline Offline

« Ответ #5 : 04-11-2018 19:29 » 

" И то и другое критично для программы. Но если бы менеджер писал я, то не стал бы размещать описатель в начале блока, его место среди структур менеджера, а среди данных программы. "
Полностью согласен Улыбаюсь
На самом деле мне действительно захотелось написать мм просто так, что бы решить хоть какую-нибудь задачку. А требование - максимальное быстродействие, поэтому и память резервируется заранее.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 04-11-2018 19:52 » 

Посмотри менеджеры типа slab. Это самое простое и быстрое. Такой менеджер хорошо работает на больших блоках. Поверх него можно добавить менеджер пула малых блоков.
« Последнее редактирование: 04-11-2018 19:56 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Migmile
Помогающий

ru
Offline Offline

« Ответ #7 : 07-11-2018 07:04 » new

Yesssss! Я сделал его быстрее стандартного malloc!
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines