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

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

ru
Offline Offline

« : 02-11-2018 07:43 » new

Решил вспомнить с++ и сделать простейший 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 » 

Yesssss! Я сделал его быстрее стандартного malloc!
Записан
Migmile
Помогающий

ru
Offline Offline

« Ответ #8 : 27-11-2018 21:00 » 

наконец-то добрался доделать:)
https://github.com/migmile/MemoryManager
За критику отдельное спасибо.
Записан
RXL
Технический
Администратор

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

WWW
« Ответ #9 : 27-11-2018 23:32 » 

С какой стороны это смотреть? Как-то привычно когда есть библиотечный заголовок, чтобы использовать его в своем проекте, а тут много непонятных заголовков. А почему каменты в непонятной кодировке? Да, понимаю, винда, Борланд, но если хотите показать публике, и каменты надо писать ascii или utf8, и код надо форматировать, и переменные называть осмысленными именами. В общем, не понял, как оценить. Не увидел. Объясните?
Записан

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

ru
Offline Offline

« Ответ #10 : 28-11-2018 07:02 » 

согласен, согласен, просто не было времени, писал по несколько строк по ночам:) видимо, накопилось много мусора, надо почистить.
кстати, Борланд не виноват, в основном VS2017, bcc64 только иногда проверял.
попробую почистить
Записан
Migmile
Помогающий

ru
Offline Offline

« Ответ #11 : 28-11-2018 11:54 » 

почистил Улыбаюсь
Записан
RXL
Технический
Администратор

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

WWW
« Ответ #12 : 28-11-2018 23:30 » 

Учитывая обучающий характер задачи, опускаю 100 и 1 вопрос. Остается лишь один: а зачем заголовок блока ссылается на самого себя? Ненужная информация. Ну, почти один ) Зачем хранить адреса блоков в set? Эта структура — бинарное дерево и активно юзает new/delete. Почему бы не хранить в adr (почему, кстати, не addr?) адрес следующего блока. Тогда, внезапно, не нужен FreeList, достаточно указателя на первый блок. Стоп, он уже есть. Итого получаем односвязанный список. При удалении блока просто подставляем его в начало списка. Так, выкидываем половину кода и становится только лучше, да и сомнительную арифметику с указателями тоже можно подсократить. В gc нужно только отсортировать указатели перед поиском соседних.

Скажем так.
Код: (C++)
class heap_t {
    struct header_t {
        header_t* next;
        size_t size;
    };
    const size_t header_size = sizeof(header_t);

    header_t* free_list;
    void* heap;

public:
    heap_t(size_t size) {
        heap = malloc(size);
        header_t* h = (header_t*)heap;
        h->next = 0;
        h->size = size - header_size;
        free_list = h;
    }

    ~heap_t() {
        free(heap);
    }

    void* alloc(size_t size) {
        for (header_t* block = free_list; block; block = block->next) {
            if (block->size < size)
                continue;

            free_list = block->next;
            size_t free_size = block->size - size;

            if (free_size > block_size) {
                header_t* free_block = ((void*)block) + header_size + size;
                free_block->size = free_size - header_size;
                free_block->next = free_list;
                free_list = free_block;
            }

            return block + header_size;
        }

        return 0;
    }

    void free(void* ptr) {
        block_t free_block = (block_t*)(ptr - block_size);
        free_block->next = free_list;
        free_list = free_block;
    }
};
Gc не стал писать, он как у тебя, только с предварительной сортировкой.

Такие аллокаторы быстры, но жутко неоптимальны в стратегии выбора блока и быстро фрагментируются.
« Последнее редактирование: 29-11-2018 00:05 от RXL » Записан

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

ru
Offline Offline

« Ответ #13 : 29-11-2018 08:38 » 

не все так просто:)
1. почему указатель на самого себя в блоке - мне не нравится, что управляющая структура находится в той-же памяти, что данные - легко случайно все потерять. поэтому как вариант я собирался вынести структуру в отдельный блок, но под нее нужно динамическое выделение памяти и все закольцовывается. пока оставил на будущее.
2. я, может сильно ошибаюсь, но мне казалось, что адресная арифметика с типом void * не разрешена?
header_t* free_block = ((void*)block) + header_size + size;Не понял?
3. односвязный список я уже пробовал в одном из вариантов:) Его недостаточно - при большом количестве выделений-освобождений если просматривать весь список с начала - жууутко медленно работает. Либо будут большие дырки.
насчет set - раньше не имел с ним дело, решил попробовать Улыбаюсь соблазнил меня  тем, что упорядоченный. Самому писать было лень:)
Пока как-то так...

Записан
RXL
Технический
Администратор

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

WWW
« Ответ #14 : 29-11-2018 23:16 » 

1. Не стоит писать ненужный код, думая, что он потребуется потом. Потом придется писать новый и разбираться со старым. Лишний код учетверяет работу.
2. Почему бы и нет. block + 1 == ((void*)block) + block_size
3. Итерация по set работает с той же скоростью, но ты тратишь время на каждое добавление и удаление? Хочешь сделать поиск подходящего блока быстрее, подумай как, выше обсуждали. И какие такие дырки?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #15 : 30-11-2018 05:02 » 

Ром,

2.  - по-моему, компилятор не даст так работать с void* . Тут нужен указатель на uint8_t

Код: (C++)
(block + N) == (TYPEOFBLOCK*)(  (uint8_t*)block + N*sizeof(TYPEOFBLOCK)  )
« Последнее редактирование: 30-11-2018 05:04 от Алексей++ » Записан

RXL
Технический
Администратор

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

WWW
« Ответ #16 : 30-11-2018 07:34 » 

Даст и работает. Адресуемой размерности менее байта языком не предусмотрено.
Записан

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

ru
Offline Offline

« Ответ #17 : 30-11-2018 08:39 » 

 void * p=0;
 void *p1= (void*)(  p + 5  );

bcc64:
error: arithmetic on pointer to void

vs2017
выражение должно представлять собой указатель на полный тип объекта   

gcc 9.0.0
warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
    8 |  void *p1= (void*)(  p + 5  );
Записан
Migmile
Помогающий

ru
Offline Offline

« Ответ #18 : 30-11-2018 19:50 » 

в продолжение:
нашел в "Working Draft, Standard for Programming Language C++" N4659 от 2017-03-21 (вроде черновик С++17)

стр. 1355

Note: Pointer arithmetic on void* or function pointers is ill-formed. — end note ]
Записан
RXL
Технический
Администратор

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

WWW
« Ответ #19 : 30-11-2018 22:09 » 

Сорри, тормознул. Был неправ.

Поправленный вариант, за одно еще пяток ошибок исправил.
Код: (C++)
#include <stdlib.h>

class heap_t {
    struct header_t {
        header_t* next;
        size_t size;
    };
    const size_t header_size = sizeof(header_t);

    header_t* free_list;
    void* heap;

public:
    heap_t(size_t size) {
        heap = malloc(size);
        header_t* h = (header_t*)heap;
        h->next = 0;
        h->size = size - header_size;
        free_list = h;
    }

    ~heap_t() {
        free(heap);
    }

    void* alloc(size_t size) {
        for (header_t* block = free_list; block; block = block->next) {
            if (block->size < size)
                continue;

            free_list = block->next;
            size_t free_size = block->size - size;
            block++;

            if (free_size > header_size) {
                header_t* free_block = (header_t*)(((char*)block) + size);
                free_block->size = free_size - header_size;
                free_block->next = free_list;
                free_list = free_block;
            }

            return (void*)block;
        }

        return 0;
    }

    void free(void* ptr) {
        header_t* free_block = (header_t*)(((char*)ptr) - header_size);
        free_block->next = free_list;
        free_list = free_block;
    }
};
« Последнее редактирование: 30-11-2018 22:33 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines