свой менеджер памяти и тормоза в list

[Migmile]

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

[Джон]

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

[RXL]

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

[Migmile]

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

[RXL]

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

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

[Migmile]

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

[RXL]

Посмотри менеджеры типа slab. Это самое простое и быстрое. Такой менеджер хорошо работает на больших блоках. Поверх него можно добавить менеджер пула малых блоков.

[Migmile]

Yesssss! Я сделал его быстрее стандартного malloc!

[Migmile]

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

[RXL]

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

[Migmile]

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

[Migmile]

почистил

[RXL]

Учитывая обучающий характер задачи, опускаю 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 не стал писать, он как у тебя, только с предварительной сортировкой.

Такие аллокаторы быстры, но жутко неоптимальны в стратегии выбора блока и быстро фрагментируются.

[Migmile]

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

[RXL]

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

[Алексей++]

Ром,

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

Код: (C++)

(block + N) == (TYPEOFBLOCK*)(  (uint8_t*)block + N*sizeof(TYPEOFBLOCK)  )

[RXL]

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

[Migmile]

 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]

в продолжение:
нашел в "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]

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

Поправленный вариант, за одно еще пяток ошибок исправил.

Код: (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;
    }
};