Алгоритм управления памятью TLSF

Куда он внедрён или будет внедрён?

На каком языке программы в тексте статьи?

>На каком языке программы в тексте статьи?

ну чего ты как маленький, псевдокод это

Немного cмахивает на PL/SQL

как там дела с оверхедом? -)

данный алгоритм может за время O(1) фрагментировать память. )

>как там дела с оверхедом?

с ним все хорошо :)

Хорошая статья!

З.Ы. Тут недавно обсуждение планировщиков процессов в ядре было, интересно, есть подобное описание их алгоритмов?

Интересный алгоритм. Вместо битовых масок можно использовать связанный список диапазонов свободных блоков, упорядоченный по возрастанию размера. Так можно избежать фрагментации (поиск по fl). Диапазоны без свободных элементов содержат ссылку на первый больший диапазон со свободными. Так можно быстро вставить новый свободный элемент.

ада это

Вот подсказали место, где реализация на си лежит:

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

Мнда, я поторопился: битовых масок не избежать.

multimap из С++ хорошо подходит: он позволяет хранить несколько элементов с одним ключом

В качестве ключа используем размер свободного блока, итератор upper_bound() нам вернёт указатель на элемент с равным или большим ключом - как раз то, что нам надо.

>http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml

квест прошёл до

geek@geek-laptop:~/Projects/TLSF-2.2.1/src$ make
gcc -O2 -Wall -fomit-frame-pointer -I/usr/src/linux-headers-2.6.22-6-generic/include/ -c -o tlsf.o tlsf.c
/tmp/ccnjTgPM.s: Assembler messages:
/tmp/ccnjTgPM.s:103: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:149: Error: no such instruction: `clz %eax,%edx'
/tmp/ccnjTgPM.s:159: Error: no such instruction: `clz %edx,%esi'
/tmp/ccnjTgPM.s:181: Error: no such instruction: `clz %eax,%edx'
/tmp/ccnjTgPM.s:206: Error: no such instruction: `clz %eax,%eax'
/tmp/ccnjTgPM.s:216: Error: no such instruction: `clz %eax,%eax'
/tmp/ccnjTgPM.s:300: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:515: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:528: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:540: Error: no such instruction: `clz %eax,%ebx'
make: *** [tlsf.o] Ошибка 1


кто дальше

Исправь в tlsf.c

#define _ARMV5_ 1
//#define _IA32_ 1

на

//#define _ARMV5_ 1
#define _IA32_ 1

> multimap из С++ хорошо подходит

Он деревья использует, а скорость работы с ними O(log n)

Йо-хо-хо :)) квест пройден %))

src> make
gcc -O2 -Wall -fomit-frame-pointer   -c -o tlsf.o tlsf.c
src> cd ../example/
example> make
cc -O2 -I../src   -c -o test.o test.c
cc -O2 -I../src -o test test.o ../src/tlsf.o
example> ./test 
Total free memory= 1045392
Test OK

Это верно, но скорость поиска в упорядоченном массиве такая же:

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

Если я правильно понял, мы имеем массив размеров блоков, упорядоченный по возрастанию, но скорость поиска в нём тоже O(log n). Или есть способ как-то ускорить поиск в данном случае?

народ, а никому не показалось что нас тихонько обманывают про O(1)?

Если я правильно понял, то за счёт организации карты памяти таким хитрым образом получается, что как раз за постоянное количество операций находишь блок. Он, правда, не "оптимально подходящий", а "хорошо подходящий". И все остальные операции за постоянное количество команд делаются.

Т.е., как я понимаю, этот алгоритм не для нормальных систем, где надо наименьшее возможное время выделения желательно оптимального блока, а для real time систем, где важен гарантированный отклик за стандартизированное время. Пусть и большее, чем среднее по обычной методике и блок не идеальный.

>народ, а никому не показалось что нас тихонько обманывают про O(1)?

+1, читаем:

>Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

Натюрлих O(n)

Да нет, вроде всё честно. А что не так?

> народ, а никому не показалось что нас тихонько обманывают про O(1)?

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

кстати, а чем изначально забивается таблица? функции инициализации не вижу

>> Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

> Натюрлих O(n)

Какое тут O(n)? Смотрите алгоритм. Сначала поиск по битмапу в оптимальной строке (при фиксированном f1), если в строке нет ничего подходящего, то поиск по битмапу в столбце -> находим более высокую строку, а затем поиск по битмэпу в ней. Максимум 3 элементарных поисковых операции.

огнелис с ним уже тестили?

Но если блок не нашли мы можем получить тормоза в этом месте:

Цитата:
---------------
Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков. Опять же, использование инструкций для работы с битами позволяет реализовать такой поиск очень компактно
---------------

Кстати, я подозреваю, что при скорости O(log n) всё равно получаем фиксированное количество операций: ведь количество свободных блоков ограничено - оно никогда не превысит 2^A, где A - разрядность адреса.
Значит и количество операций всё равно не превысит некоторого максимального числа

Параметры fl и sl находятся за постоянное количество операций (формула одна и та же). Чтобы найти первый свободный блок размером больше чем надо, операций надо не больше чем 32*2^{\alpha} (общее количество индексов в карте). Где зависимость от размера требуемой памяти? Пока не вижу.

Может чего не понимаю?

Кстати, верно заметил комрад: Sorcerer ** (*) (26.07.2007 18:32:54)

всё гораздо проще.

Работает быстрее HOARD?

http://www.hoard.org/

Хмм, оно на паскале и ограничено 32 битами...

Плюс, при выделении блока бОльшего размера, чем было запрошено, хорошие аллокаторы остаток отдают обратно в систему в пул меньших размеров. При освобождении пытаются склеить, тем самым уменьшая фрагментацию. Читая по диагонали понял, что это не поддерживается.

Про возвращение не видел (хотя, думаю, не проблема: по идее те же операции нахождения fl и sl), а вот про склейку есть (в самом конце):

Функция free всегда пытается объединять соседние блоки. Merge_left проверяет, свободен ли предыдущий физический блок и, если это так, удаляет его из списка свободных блоков и объединяет с освобождаемым блоком. Merge_right делает тоже самое, но со следующим физическим блоком. Соседние физические блоки могут быть быстро найдены при помощи размера текущего блока (для следующего блока) и указателя на предыдущий блок, хранимого в заголовке свободного блока. Все операции выполняются за время O(1).

Алгоритм не ограничен, что естественно. Просто реализация именно для 32-битного процессора приведена для примера.

Насчёт Паскаля - выше народ пости реализацию на Си и кто-то даже пробовал скомпилять.

Так что вроде нормально. Правда, насколько мне сказали, похожие алгоритмы есть и другие.

>народ, а никому не показалось что нас тихонько обманывают про O(1)?

Мне показалось, что по ссылке медленный боян. :D

Тут есть сравнение: http://rtportal.upv.es/rtmalloc/papers/tlsf_slides.pdf

Согласно этому сравнению, TLSF не хуже чем DLmalloc.

Processor instructions:
 Alloc memory:
   DLmalloc:  279
   TLSF:      147
  
 Free memory:
   DLmalloc:  70
   TLSF:      140

Fragmentation:
  DLmalloc:  10,11
  TLSF:      10,49

>>народ, а никому не показалось что нас тихонько обманывают про O(1)?

> +1, читаем:

>>Следующая функция ? search_suitable_block ? ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

> Натюрлих O(n)

Умнег, ты там хотя-бы один цикл видишь, в приведенных листингах (хоть прямой, хоть через рекурсию)? Все "проходы по спискам" делают аппаратные, отрабатывающие за 3 такта инструкции, завернутые в ffs и fls

> Хмм, оно на паскале и ограничено 32 битами...

Дану? А я думал на бейсике!

Малолетки, это не паскаль, это АДА! (и писать только так, все большие буквы, т.к. этот язык, в отличии от большинства других, достоин высочайших почестей).

>Умнег, ты там хотя-бы один цикл видишь, в приведенных листингах (хоть прямой, хоть через рекурсию)? Все "проходы по спискам" делают аппаратные, отрабатывающие за 3 такта инструкции, завернутые в ffs и fls

Обидели автора :)

И что же делает этот аллокатор, когда памяти больше нет, но есть дополнительный кэш? Например glibc malloc пожет замапить дополнительно несколько страниц, что сбросит в своп какие-то данные.

Этот же алокатор статически отображает всю память аллокатора (все 32 бита) на некую таблицу, при этом оверхед при выборе бОльшего блока становится чудовищным, если все малые блоки уже израсходованы. Ближайшая степень двойки в верхних разрядах.

> Этот же алокатор статически отображает всю память аллокатора (все 32 бита) на некую таблицу, при этом оверхед при выборе бОльшего блока становится чудовищным, если все малые блоки уже израсходованы. Ближайшая степень двойки в верхних разрядах.

Это не general purpose аллокатор, так что не надо к нему с требованиями общими лезть.

>Интересный алгоритм. Вместо битовых масок можно использовать связанный список диапазонов свободных блоков, упорядоченный по возрастанию размера. Так можно избежать фрагментации (поиск по fl). Диапазоны без свободных элементов содержат ссылку на первый больший диапазон со свободными. Так можно быстро вставить новый свободный элемент.

Прошло всего-то чуть больше 10-и лет и они осилили сделать что-то подобное борландовскому аллокатору? Я х.ею с таких инноваций, дорогая редакция ...

"Алгоритм расщипления" - списки размеров свободных блоков по убыванию, объеденение меньших в большие, добовление остатков в списки меньших и другие фичи. Все уже придумано в 70е годы прошлого века - _запатентовано_(!). А так же доказало свою несостоятельность на интенсивных нагрузках (читай многозадачных системах). Так что радоватся рано. И главное - в чем новизна творчества (плагиат)?