LINUX.ORG.RU

Memory Allocator


0

0

Вообщем есть tcp server критичный очень, использует он libc-ный malloc. Суть в том что например в glibc аллокатор убогий. То есть нужен свой, по сему вопрос - я подумал и решил делать его на mmap, НО как будет с кроссплатформенностью ? Этот сервер возможно понадобится в будующем и на *bsd.

Делать на mmap ? или что посоветуете ?

PS у меня задумка следующая, выделить кусок на мелкие чанки, и кусок на большие (которые редко высвобождаются.маллочатся), для описания структуры использовать splay tree для мелких кусков, и обычный linked list для больших.

Что думает all по сабжу ?

Re: Memory Allocator

зачем?

есть hoard memory allocator, отлично работающий в *многопоточных* системах, т.е. для серверов идеальный вариант.

p/s

а вообще если самопалом заниматься, то нужно юзать self-balanced tree для больших кусков и двусвязный список с boundary tags для мелких, как это сделано в doug's lea malloc. (его кстати тоже можно попробовать поюзать, он меганастраиваемый, но если память будет активно выделяться/освобождаться в процессах/тредах, то луше хордовский юзать).

asgard ()

Re: Memory Allocator

Кое-кто из all думает, что аллокаторов изобретено уже до фига всяких, и не стоит изобретать велосипед.

tailgunner ★★★★★ ()

Re: Memory Allocator

только лишь на bsd или же на Solaris или ещё какие нить unix`ы. просто в солярке например всё совсему убого.

luch ()

Re: Memory Allocator

+ сплей лучше не использовать, у него баланс шаткий очень - при малейшем нарушение серьёзно пострадает производительность. имхо, лучше avl or rb

asgard ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

>зачем?

чтобы быть уверенным ;)

>то нужно юзать self-balanced tree для больших кусков и двусвязный список с boundary tags для мелких,

еще раз - мелкие, с ними работа идет чаще - тут splay tree сам доктор прописал, больших кусков мало - соотвественно там дерево не критично.

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от tailgunner

Re: Memory Allocator

>Кое-кто из all думает, что аллокаторов изобретено уже до фига всяких, и не стоит изобретать велосипед.

ссылки, ссылки сестра ;) ах да их много, только большинство убогие.

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

>+ сплей лучше не использовать, у него баланс шаткий очень - при малейшем нарушение серьёзно пострадает производительность. имхо, лучше avl or rb

есть вероятность - но при большом n

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> еще раз - мелкие, с ними работа идет чаще - тут splay tree сам доктор прописал

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

asgard ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

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

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

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> представь, хорошо представь splay tree и что вверху и почему именно оно будет так работать ;) подумай ... я тоже сначала сомневался - потом провел эксперимент - на деле все не так, splay tree подходит как нельзя лучше.

1) да, наверху будут наиболее часто используемые куски, НО это улучшит только процесс поиска - не более, причём выигрыша от этого ты большого не получишь. вся суть в процессе выделения и освобождения. *каждый* раз будут производится ребалансик дерева, а поскольку splay tree не полностью self-balanced, это повышает риск того, что баланс собьётся. ne worst case issue with the basic splay tree algorithm is that of sequentially accessing all the elements of the tree in the sort order. This leaves the tree completely unbalanced (this takes n accesses- each an O(log n) operation)

http://en.wikipedia.org/wiki/Splay_tree

2) т.о. выделение куска из дерева позволит тебе только потерять но никак не выиграть в производительности, посему вариант для мелких кусков с одним листом или несколькими квик-листами гораздо быстрее

asgard ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> ах да - забыл - не будет у меня тредов - у меня пул форков и сплошные select

не суть. форки-то есть. если память будет выделяться и освобождаться во многих "клонах" - то однозначно хорд.

asgard ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

>не суть. форки-то есть. если память будет выделяться и освобождаться во многих "клонах" - то однозначно хорд.

во многих клонах - ключевое слово - они сами по себе самостоятельны - так что тут не суть уже для "однопоточного" или для "многопоточного".

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

>1) да, наверху будут наиболее часто используемые куски, НО это улучшит только процесс поиска - не более, причём выигрыша от этого ты большого не получишь. вся суть в процессе выделения и освобождения. *каждый* раз будут производится ребалансик дерева, а поскольку splay tree не полностью self-balanced, это повышает риск того, что баланс собьётся. ne worst case issue with the basic splay tree algorithm is that of sequentially accessing all the elements of the tree in the sort order. This leaves the tree completely unbalanced (this takes n accesses- each an O(log n) operation)

Да знаю я что тебе не нравятся сплеи ;) вот именно что суть в выделении/освобождении - это ж поиск - не так ли ? Или ты про что тут пытаешься загнать ? ;)

>2) т.о. выделение куска из дерева позволит тебе только потерять но никак не выиграть в производительности, посему вариант для мелких кусков с одним листом или несколькими квик-листами гораздо быстрее

лист - высвобождаем такой то указатель - и вперед несемся n-раз до него - очень "быстро", с учетом того что у меня вверху будут в сплее часто юзаемые чанки, сам понимаешь ... , составление динамически квик листов ~= балансировке дерева - это надеюсь более менее понятно ? ;)

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> во многих клонах - ключевое слово - они сами по себе самостоятельны - так что тут не суть уже для "однопоточного" или для "многопоточного".

да, они самостоятельны, но "канал к памяти" у них один на всех. дав каждому клону свой пул памяти алокатор хорда позволяет очень неплохо ускорить производительность.

asgard ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> Да знаю я что тебе не нравятся сплеи ;) вот именно что суть в выделении/освобождении - это ж поиск - не так ли ? Или ты про что тут пытаешься загнать ? ;)

у тебя есть дерево - в нём хранятся *свободные* куски памяти, при выделении куска, ты должен будешь удалить его из дерева, поместив либо в хэш таблицу, либо в дерево/список заалокейченных кусков. если ты освобождаешь кусок, то в хэш-таблице/дереве/списке заалокейченных кусков должен быть произведён поиск & удаление куска с целью помещения оного обратно в дерево свободных кусков. это приведёт к большому кл-ву операций ребалансинга, которые могут обойтись тебе дороже, нежели поиск по списку.


> лист - высвобождаем такой то указатель - и вперед несемся n-раз до него - очень "быстро"

use quick lists:

array:
[size0] (node0)->(node1)->...->(nodeN)
...
[sizeN] (node0)->(node1)->...->(nodeM)

asgard ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

> у меня есть дерево в котором хранятся все куски - у меня есть поддерево с свободными и занятыми кусками

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

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

asgard ()
Ответ на: Re: Memory Allocator от asgard

Re: Memory Allocator

>если да, то это очень много гемора - разработка алгоритма, док-во его стабильности, тестинг, etc

уже писал, смотрел, и тестил

alphex_kaanoken ★★★ ()
Ответ на: Re: Memory Allocator от alphex_kaanoken

Re: Memory Allocator

он портаьильный, только я сомневаюсь, что он настолько хорош, на сколько его описывают.

да и лицензия у него boost.

asgard ()

Re: Memory Allocator

> Вообщем есть tcp server критичный очень, использует он libc-ный malloc. Суть в том что например в glibc аллокатор убогий.

Почему убогий? Чем не подходит?

>То есть нужен свой, по сему вопрос - я подумал и решил делать его на mmap, НО как будет с кроссплатформенностью ? Этот сервер возможно понадобится в будующем и на *bsd.

В OpenBSD сделано на m*map(), и разные кучки там используются для разного размера chunkов. Утверждалось, что на gnu/linux он тоже работает: http://mr.himki.net/index-alloc.html

anonymous ()

Re: Memory Allocator

Не знаю почему никто не написал, но помнится похожие проблемы были у squid и они описаны в документации и FAQ к нему. Кстати они вроде рекомендовали использовать или dmalloc (он вроде в исходниках идет) или GNU malloc (что странно, с учетом текста вашего сообщения) :-\ И еще вспоминается LUBheap (LUB - это Little Useful Bits library), там всего один файл в 7Кб posix/sysheap.c.

saper ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.