нужен быстрый аллокатор, удовлетворяющий следующим условиям:
* распределять нужно блоки фиксированного, известного в compile-time, размера;
* количество этих блоков заранее неизвестно и не органичено (т.е. аллокаторы на пулах фиксированного размера не проходят);
* thread-safe;
* кроссплатформенный.
* свободный (в идеале BSD/MIT лицензия, в случае GPL придется делать свою реализацию под BSD лицензией).
Интересуют не только готовые реализации, но и алгоритмы подобных аллокаторов, чтобы в случае чего самому можно было реализовать.
Спасибо.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Коллеги,
E>нужен быстрый аллокатор, удовлетворяющий следующим условиям: E>* распределять нужно блоки фиксированного, известного в compile-time, размера; E>* количество этих блоков заранее неизвестно и не органичено (т.е. аллокаторы на пулах фиксированного размера не проходят); E>* thread-safe; E>* кроссплатформенный. E>* свободный (в идеале BSD/MIT лицензия, в случае GPL придется делать свою реализацию под BSD лицензией).
E>Интересуют не только готовые реализации, но и алгоритмы подобных аллокаторов, чтобы в случае чего самому можно было реализовать.
Посмотри реализацию SmallAllocator в Loki. Она там вроде немного кривая (я использую свою модификацию), но идея — то что тебе надо.
Здравствуйте, Lorenzo_LAMAS, Вы писали:
L_L>Doug Lea malloc не смотрел? Правда, надо сказать, он с большой долей вероятности уже используется под linux.
Вот прямо сейчас и смотрю.
Есть еще какой-то ptmalloc -- специальная адаптация dlmalloc для мультипоточных программ.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Lorenzo_LAMAS, Вы писали:
L_L>>Doug Lea malloc не смотрел? Правда, надо сказать, он с большой долей вероятности уже используется под linux.
E>Вот прямо сейчас и смотрю. E>Есть еще какой-то ptmalloc -- специальная адаптация dlmalloc для мультипоточных программ.
Как показали исходники ptmalloc -- он исключительно Unix-овый. Готовой поддержки Windows, в отличии от исходного dlmalloc в нем нет.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Коллеги,
E>нужен быстрый аллокатор, удовлетворяющий следующим условиям: E>* распределять нужно блоки фиксированного, известного в compile-time, размера; E>* количество этих блоков заранее неизвестно и не органичено (т.е. аллокаторы на пулах фиксированного размера не проходят); E>* thread-safe; E>* кроссплатформенный. E>* свободный (в идеале BSD/MIT лицензия, в случае GPL придется делать свою реализацию под BSD лицензией).
E>Интересуют не только готовые реализации, но и алгоритмы подобных аллокаторов, чтобы в случае чего самому можно было реализовать.
Я что-то туплю.. Если тебя устраивает thread-safe за счёт синхронизации, то такая штука пишется за час. И, если не учитывать блокировку потоков (если у нас один процессор, или если не собираемся активно выделять память из разных потоков), работает очень шустро.
Или я ошибаюсь?
Или тебе обязательно lock-free нужен?
Здравствуйте, SergH, Вы писали:
E>>нужен быстрый аллокатор, удовлетворяющий следующим условиям: E>>* распределять нужно блоки фиксированного, известного в compile-time, размера; E>>* количество этих блоков заранее неизвестно и не органичено (т.е. аллокаторы на пулах фиксированного размера не проходят); E>>* thread-safe; E>>* кроссплатформенный. E>>* свободный (в идеале BSD/MIT лицензия, в случае GPL придется делать свою реализацию под BSD лицензией).
E>>Интересуют не только готовые реализации, но и алгоритмы подобных аллокаторов, чтобы в случае чего самому можно было реализовать.
SH>Я что-то туплю.. Если тебя устраивает thread-safe за счёт синхронизации, то такая штука пишется за час. И, если не учитывать блокировку потоков (если у нас один процессор, или если не собираемся активно выделять память из разных потоков), работает очень шустро.
SH>Или я ошибаюсь? SH>Или тебе обязательно lock-free нужен?
Нет, про lock-free я даже не заикался.
Просто, имхо, если нет ограничения на количество выделяемых блоков, то, имхо, за час не напишешь достойный аллокатор.
Пока меня вполне устроил dlmalloc -- он работает ощутимо эффективнее штатного new в VC7.1.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
An EXTREMELY FAST portable thread caching malloc implementation written in C for multiple threads without lock contention based on dlmalloc. Optimised for x86 and x64. Compatible with C++.
вроде даже развивается
Сам не пробовал — может и сгодиться...
Здравствуйте, eao197, Вы писали:
E>Просто, имхо, если нет ограничения на количество выделяемых блоков, то, имхо, за час не напишешь достойный аллокатор. E>Пока меня вполне устроил dlmalloc -- он работает ощутимо эффективнее штатного new в VC7.1.
При постоянном размере выделяемого блока становятся не нужны все "интеллектуальные" части распределителя. При удалении не нужно дефрагментировать кучу (сливать оказавшиеся рядом свободные кусочки в один), при выделении не нужно искать свободный блок нужного размера и думать о фрагментации — подойдёт любой, причём подойдёт идеально. Нам даже не надо запоминать, сколько байт занимает выделенный блок!
За счёт всего этого выделение делается мгновенно. Свободные блоки объединяются в простой односвязный список, освободившийся идёт в голову. Поскольку мы ничего не объединяем (не надо) свободный блок размером в несколько элементов может быть только в самом конце списка — его надо по особому обрабатывать.
struct free_block
{
void* next;
int count;
};
Это всё хранится в самом свободном блоке + глобальная переменная head_of_free.
если next == 0 — смотрим count... Если он больше размера блока, то head_of_free = (char*)head_of_free + sizeof(block). Если count == sizeof(block) — у нас кончилась выделенная память, head_of_free = 0, в следующий раз надо будет выделять новый блок из системной кучи. Вариантов алгоритма расширения кучи — выделения новых блоков системной памяти, собственно, два — либо выделять блоки постоянного размера, либо увеличивать размер какой-нибудь прогрессией. Скорее всего, тупо умножать на 2.
Да, а вот если хочется, чтобы когда много места не нужно, куча опять сжималась, то это и правда за час не напишешь, это думать надо.
Здравствуйте, SergH, Вы писали:
E>>Просто, имхо, если нет ограничения на количество выделяемых блоков, то, имхо, за час не напишешь достойный аллокатор. E>>Пока меня вполне устроил dlmalloc -- он работает ощутимо эффективнее штатного new в VC7.1.
SH>При постоянном размере выделяемого блока становятся не нужны все "интеллектуальные" части распределителя. При удалении не нужно дефрагментировать кучу (сливать оказавшиеся рядом свободные кусочки в один), при выделении не нужно искать свободный блок нужного размера и думать о фрагментации — подойдёт любой, причём подойдёт идеально. Нам даже не надо запоминать, сколько байт занимает выделенный блок!
SH>За счёт всего этого выделение делается мгновенно. Свободные блоки объединяются в простой односвязный список, освободившийся идёт в голову. Поскольку мы ничего не объединяем (не надо) свободный блок размером в несколько элементов может быть только в самом конце списка — его надо по особому обрабатывать.
SH>
SH>Это всё хранится в самом свободном блоке + глобальная переменная head_of_free.
SH>если next == 0 — смотрим count... Если он больше размера блока, то head_of_free = (char*)head_of_free + sizeof(block). Если count == sizeof(block) — у нас кончилась выделенная память, head_of_free = 0, в следующий раз надо будет выделять новый блок из системной кучи. Вариантов алгоритма расширения кучи — выделения новых блоков системной памяти, собственно, два — либо выделять блоки постоянного размера, либо увеличивать размер какой-нибудь прогрессией. Скорее всего, тупо умножать на 2.
SH>Да, а вот если хочется, чтобы когда много места не нужно, куча опять сжималась, то это и правда за час не напишешь, это думать надо.
Если я правильно понимаю проблему распределителя памяти, то пулы свободных блоков и элементы списков свободных блоков нужно выделять заранее кусками некоторого размера. Чтобы затем при выделении/освобождения блока не дергать new/malloc (или даже средства OS). Если речь зайдет о сотнях тысяч, а то и миллионах блоков, то нужно будет озадачиться тем, чтобы:
* большие куски овобождались и возвращались операционной системе;
* поиск куска, в котором был выделен блок, при освобождении осуществлялся очень быстро.
Все это очень не хочется делать, тестировать и сопровождать самому. Разве что в крайнем случае.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>* поиск куска, в котором был выделен блок, при освобождении осуществлялся очень быстро.
Это делается очень просто — в хидере блока хранится указатель/индекс на суперблок.
Либо адрес блока округляется вниз до размера суперблока, и т.о. получается адрес суперблока (при условии, что суперблоки выделяются с соотв. выравниваем). Таким образом, кстати, можно сделать выделение маленьких объектов headerless. Допустим размер выделяемого блока 4 байта, а хидера — 8 байт — 66% памяти теряется. Если использовать headerless блоки для маленьких объектов, то будет использоваться вся память полностью.
E>* большие куски овобождались и возвращались операционной системе;
С этим немного посложнее, но основная идея следующая. Для суперблока хранится кол-во занятых в нём блоков, когда оно доходит до 0, суперблок освобождается, если нужно.
Поскольку перемещать объекты в С++ нельзя, то и что-то более замысловатое придумать сложно. Единственное над чем надо подумать — из какого суперблока выделять очередной блок.
E>Все это очень не хочется делать, тестировать и сопровождать самому. Разве что в крайнем случае.
Да разьве ж хочется вообще что-либо делать самому?
Здравствуйте, eao197, Вы писали:
E>нужен быстрый аллокатор, удовлетворяющий следующим условиям: E>* распределять нужно блоки фиксированного, известного в compile-time, размера; E>* количество этих блоков заранее неизвестно и не органичено (т.е. аллокаторы на пулах фиксированного размера не проходят); E>* thread-safe; E>* кроссплатформенный. E>* свободный (в идеале BSD/MIT лицензия, в случае GPL придется делать свою реализацию под BSD лицензией).
Как уже сказал SergH, если нужен аллокатор для блоков фиксированного размера, то в сторону аллокаторов общего назначения смотреть нет смысла. За исходный вариант можно взять Loki::SmallObjAllocator. Там только надо напильником надо доработать несколько мест.
Во-первых, он поддерживает выделение блоков не фиксированного размера (точнее не совсем фиксированного) — т.е. он поддерживает выделение блоков размера не больше некого заданного. Соответственно эту часть можно выкинуть целиком. Собственно аллокатор, который выделяет блоки фиксированного размера там уже выделен в отдельный класс — Loki::FixedAllocator.
Во-вторых, при освобождении блока неэффективно ищется суперблок, к которому относится блок. Фактически он там ищется перебором всех суперблоков, правда с хинтом — начиная с суперблока, в который последний раз освобождали блок и далее в две стороны по списку. Для некоторых паттернов нагрузки это может давать плохой результат. Суперблоки надо выделять по выровненным адресам памяти, тогда искомый суперблок можно будет найти простым округлением вниз адреса блока.
В-третьих, возможно там надо подправить алгоритм кэширования суперблоков. Сейчас там используется там используется предельно простой алгоритм — если суперблок становится пустым, и уже есть один пустой суперблок, то один из них освобождается.
В-четвёртых, надо при'align'ица к платформе. Т.е. надо получать размеры страниц памяти, размеры кэш-линий. И уже исходя из них выбирать размеры суперблоков и блоков.
С таким алгоритмом, при прогретом механизме кэширования аллокатора, выделение/освобождение памяти будет занимать порядка 20 машинных инструкций, т.е. порядка 20-30 тактов. Что очень неплохо.
Самое интересное начинается, когда мы пытаемся сделать этот аллокатор thread-safe. Решение в лоб подразумевает обрамление кода в mutex_lock/mutex_unlock. Стандартный мьютекс включает в себя по одной атомарной операции при входе и выходе. Одна атомарная операция на современных архитектурах занимает порядка 100 тактов процессора. Плюс передача кэш-линии с одного процессора на другой — это порядка 150-350 тактов. Плюс к этому передача кэш-линий относящихся к самому аллокатору. При самом хорошем раскладе это как минимум 2 кэш-линии. Т.е. ещё плюс 300-700 тактов.
Итого. На одноядерной машине (если вы всё ещё пользуетесь таким раритетом) вместо 20-30 тактов получаем 220-230 тактов. На многоядерной машине получаем 670-1280 тактов. Т.е. падение производительности до 64 раз. И это ещё не худший вариант — обычно падение производительности в пределах 10-100 раз.
И всё становится ещё хуже, когда возрастает конкуренция при доступе к мьютексу — начинаются ещё более частые передачи кэш-линий и переключения контекстов.
Что с этим делать сейчас напишу ниже.
Здравствуйте, remark, Вы писали:
R>Т.е. падение производительности до 64 раз. И это ещё не худший вариант — обычно падение производительности в пределах 10-100 раз. R>Что с этим делать сейчас напишу ниже.
Идея простая — надо партицировать кэш блоков по потокам. Т.е. на каждый поток свой кэш. Есть варианты делать кэш на ядро или просто несколько кэшей для всех потоков — но это всё плохие идеи. Надо делать на поток.
И вроде как всё хорошо — при выделении блока поток берёт блок из своего кэша, при освобождении — возвращает в свой кэш. Проблемы начинаются, когда потоку надо освободить блок, который выделил другой поток. Надо как-то вернуть блок потоку-владельцу.
Есть, правда, вариант и не возвращать блок владельцу, а освободить его в свой кэш. Но этот вариант работает только для аллокаторов на связных списках — для Loki::FixedAllocator не подойдёт. Во-вторых, не понятно как тогда освобождать пустые суперблоки, когда их становится слишком много. В-третьих, некоторые асимметричные паттерны нагрузки (producer-consumer) порождают постоянную необходимость в освобождении чужих блоков, т.е. у одного потока будет постоянный переизбыток блоков, а у другого — постоянная нехватка. Т.е. лучше всё-таки как-то возвращать блоки владельцу.
Есть алгоритмы lock-free аллокаторов. Например: Scalable Lock-Free Dynamic Memory Allocation by Maged M. Michael
или: Allocating Memory in a Lock-Free Manner by Philippas Tsigas
... это всё надо выкинуть на помойку!
Не знаю, о чём они думали, создавая эти алгоритмы, но явно не о получении высокой производительности. Видимо просто о модном слове lock-free
Самый эффективный из известных на сегодняшний день можно найти здесь
Идея следующая: если надо освободить блок чужого потока, то он кладётся на lock-free fifo stack того потока (это одна атомарная операция). Если у потока при аллокации закончились свои свободные блоки, то он разом забирает все блоки, которые накопились в его fifo stack от других потоков (эта одна атомарная операция на *N* блоков). Все остальные операции идут без атомарных операций и какого-либо взаимодействия между потоками.
Не смотря на кажущуюся тривиальность алгоритма, это есть первая публичная публикация алгоритма (3 окт 2005). здесь можно почитать подробную статью по поводу этого алгоритма (это июнь 2006, написали уже другие люди, уверяют, что сами придумали).
А здесь можно даже скачать код.
Самая соль этого алгоритма, что он неинтрузивно прикручивается поверх любого другого однопоточного аллокатора, превращая его в многопоточный. Т.е. если какая-либо реализация аллокатора предоставляет две версии — однопоточную и многопоточную, то можно взять однопоточную версию, прикрутить поверх этот lock-free алгоритм, и получить версию, которая работает быстрее, чем их же многопоточная версия. Проверялось на виндовом хипе (HeapCreate(HEAP_NO_SERIALIZE, 0, 0)).
Т.о. этот алгоритм можно прикрутить поверх Loki::FixedAllocator и получить очень достойную производительность.
R>
Здравствуйте, remark, Вы писали:
R>Т.о. этот алгоритм можно прикрутить поверх Loki::FixedAllocator и получить очень достойную производительность.
Дальше — больше.
Можно сделать thread-safe allocator без атомарных операций вообще!
Идея следующая. Берутся single-consumer/single-producer fifo очередь (т.е. только один поток может добавлять элементы и один забирать) (для краткости — spsc queue). Такая очередь может быть сделана без атомарных операций и без дорогих #StoreLoad барьеров памяти. Между всеми потоками устанавливается полносвязанная система с помощью этих spsc queue. И далее при освобождении блоки памяти, выделенные другим потоком, транспортируются к потоку-владельцу с помощью соотв. spsc queue. Вот собственно всё — остальное без изменений.
Т.о. *любой* однопоточный аллокатор памяти может быть трансформирован в многопоточный без атомарных операций. Реализация экстремально эффективная и multicore/SMP friendly.
Здравствуйте, remark, Вы писали:
R>В-четвёртых, надо при'align'ица к платформе. Т.е. надо получать размеры страниц памяти, размеры кэш-линий. И уже исходя из них выбирать размеры суперблоков и блоков.
А да, там ещё размер блока ран-тайм параметр, поэтому там при аллокации/деаллокации есть mul/div. Если вынести его как компайл-тайм параметр и он кратен степени 2, то ешё 20-100 тактов съэкономишь
R>
Здравствуйте, eao197, Вы писали:
E>* распределять нужно блоки фиксированного, известного в compile-time, размера; E>* thread-safe;
Существенно ограничивая область применимости аллокатора (возможность выделения блоков только фиксированного размера), ты получаешь существенную выгоду по производительности.
Аналогично, существенно ограничив требования по многопоточности, либо сузив паттерны рабочей нагрузки, ты можешь получить ещё большие выгоды.
Ты можешь попробовать конкретизировать требования в следующих областях:
— как чередуются выделения и освобождения блоков, сколько примерно живут выделенные блоки, есть ли чрезмерно долгоживущие блоки
— сколько потоков должны иметь возможность выделять блоки, сколько потоков должны иметь возможность освобождать память
— какой процент освобождения блоков, выделенных в других потоках
В качестве примера сильно кастомного решения можешь поглядеть одну из моих последних разработок — аллокатор нодов для фифо-очередей: http://groups.google.com/group/comp.programming.threads/browse_frm/thread/378a35b21ae2b42e
Аллокатор учитывает следующие особенности использования — блоки всегда освобождаются в чужом потоке, блоки освобождаются строго в фифо порядке. Как следствие аллокатор делает выделения и освобождения блоков без атомарных rmw операций либо дорогих барьеров памяти.
Вобщем к чему я это все — ты можешь попробовать ещё более заузить область применения аллокатора, чем просто "thread-safe". Точнее не заузить, а просто сформулировать, что именно тебе надо более детально. Тогда можно будет попробовать придумать что-то более простое и эффективное. Хотя, решение, которое я привёл здесь
Здравствуйте, remark, Вы писали:
R>Вобщем к чему я это все — ты можешь попробовать ещё более заузить область применения аллокатора, чем просто "thread-safe". Точнее не заузить, а просто сформулировать, что именно тебе надо более детально. Тогда можно будет попробовать придумать что-то более простое и эффективное.
Да все достаточно просто. Очередное профилирование SObjectizer показало, что изрядное время тратится на операциях создания таких маленьких объектов, как, например, event_data_t и event_data_single_t. Я создал для них собственные операторы new/delete на основе отдельных пулов (каждый пул сейчас использует dlmalloc). И получил прирост производительности еще на пару тысяч сообщений в секунду.
Но особенность этих event_data_t/event_data_single_t в том, что создаются они на одной нити (там, где вызывается send_msg), а удаляться будут на другой -- там где отработает обработчик сообщения. Отсюда и необходимость thread-safe.
В оправдание: Дима, извини, я тебе пока только оценки расставлял, но не отвечал ничего, т.к. времени нет. Пока занимаюсь экспериментами в совсем другой области. Надеюсь скоро закончить. Хотя и не уверен, что тогда появится время на эти аллокаторы. Есть другая очень важная задача -- переделка коммуникационной подсистемы
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Да все достаточно просто. Очередное профилирование SObjectizer показало, что изрядное время тратится на операциях создания таких маленьких объектов, как, например, event_data_t и event_data_single_t. Я создал для них собственные операторы new/delete на основе отдельных пулов (каждый пул сейчас использует dlmalloc). И получил прирост производительности еще на пару тысяч сообщений в секунду.
Ты можешь с помощью mxx_ru компилировать через nmake/devenv?
Я думаю выложить демо версию аллокатора, что бы ты мог отпрофилировать, но мне лень пока его портировать под g++. Для начала хочется поглядеть, есть ли смысл заниматься им дальше.
А для каких именно классов ты хочешь применить этот аллокатор? Может я сам поприпарирую SObjectizer ради интереса.
з.ы. А ты сейчас на каком компьютере тесты запускаешь? На Pentium M?
E>
Здравствуйте, remark, Вы писали:
E>>Да все достаточно просто. Очередное профилирование SObjectizer показало, что изрядное время тратится на операциях создания таких маленьких объектов, как, например, event_data_t и event_data_single_t. Я создал для них собственные операторы new/delete на основе отдельных пулов (каждый пул сейчас использует dlmalloc). И получил прирост производительности еще на пару тысяч сообщений в секунду.
R>Ты можешь с помощью mxx_ru компилировать через nmake/devenv?
В принципе, могу.
R>Я думаю выложить демо версию аллокатора, что бы ты мог отпрофилировать, но мне лень пока его портировать под g++. Для начала хочется поглядеть, есть ли смысл заниматься им дальше.
R>А для каких именно классов ты хочешь применить этот аллокатор? Может я сам поприпарирую SObjectizer ради интереса.
Но после перехода на dlmalloc выделение памяти под эти объекты уже перестало быть узким местом. Поэтому оптимизация в этом месте все равно не даст существенного эффекта, пока не будут устранены другие препятствия.
R>з.ы. А ты сейчас на каком компьютере тесты запускаешь? На Pentium M?
Да. Pentium M 1.5GHz, 512Mb RAM.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[4]: thread-safe allocator без атомарных операций
R>Идея следующая. Берутся single-consumer/single-producer fifo очередь (т.е. только один поток может добавлять элементы и один забирать) (для краткости — spsc queue). Такая очередь может быть сделана без атомарных операций и без дорогих #StoreLoad барьеров памяти. Между всеми потоками устанавливается полносвязанная система с помощью этих spsc queue. И далее при освобождении блоки памяти, выделенные другим потоком, транспортируются к потоку-владельцу с помощью соотв. spsc queue. Вот собственно всё — остальное без изменений.
Удивительно читать описания этих алгоритмов в 2007-м, если пользовался ими еще в 2000-м. Причём, знаю как минимум еще одного человека, который пришел к идее одного аллокатора на поток и использовании очереди возврата чужих блоков примерно в те же времена. Отличие "нашего" алгоритма было в том, что не использовались полносвязные fifo-очереди м/у всеми потоками (да и не во всех сценариях этот способ будет эффективным), у нас сам поток копил чужие блоки, и по достижении некоторого предела возвращал их родителям через блокирующие операции, т.е. одна блокировка на кучу освобождаемых блоков.
