Memory Allocator

длина сессии как-то ограничена?

>длина сессии как-то ограничена?

нет

зачем?

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

p/s

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

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

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

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

>зачем?

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

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

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

> в солярке например всё совсему убого.

http://developers.sun.com/solaris/articles/multiproc/multiproc.html

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

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

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

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

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

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

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

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

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

http://www.hoard.org/

http://rtportal.upv.es/rtmalloc/allocators/dlmalloc/index.shtml

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

> представь, хорошо представь 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) т.о. выделение куска из дерева позволит тебе только потерять но никак не выиграть в производительности, посему вариант для мелких кусков с одним листом или несколькими квик-листами гораздо быстрее

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

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

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

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

>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-раз до него - очень "быстро", с учетом того что у меня вверху будут в сплее часто юзаемые чанки, сам понимаешь ... , составление динамически квик листов ~= балансировке дерева - это надеюсь более менее понятно ? ;)

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

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

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

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


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

use quick lists:

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

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

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

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

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

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

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

Вот такая штука существует: http://www.nedprod.com/programs/portable/nedmalloc/index.html

а чего то то там только win32, мне win32 как собаке здрасти - мне портабельно чтобы под *nix было, до win32 мне лесом ;)

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

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

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

вот вот

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

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

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

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

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